Re: View vs. Statement Query Plan

On Wed, Jun 05, 2002 at 06:35:10PM +0900, Curt Sampson wrote:
> On Wed, 5 Jun 2002, Martijn van Oosterhout wrote:
>
> > One thing I don't know and that is how closely SQL follows relational
> > algebra. Is it close enough that you can prove results in relational algebra
> > and have them work in SQL. Or there enough special cases to make that
> > tricky.
>
> Ha! Nowhere near close enough. SQL actually breaks the relational model
> in many ways; C. J. Date's books (particularly _The Third Manifesto_ and
> his _Introduction to Database Systems_) go into this in detail.

Interesting. I don't know these books, I may see if I can find them.

> I've not really had time to sit down and think about the characteristics
> of the problem of whether or not a WHERE clause on a pair of SELECT
> statements joined by UNION is distributitive or not. The easiest
> thing would be if someone could find a case that proves by example
> that the WHERE clause is not distributitive.

Well, I think UNION ALL may be doable, but straight UNION could be tricky.
You need something stricter than iscachable do be able to use functions.
I've got a nifty example below.

> Providing a formal proof that it is distributive seems to me rather
> difficult, because I can't even really see how to translate SQL
> into relational algebra....

Most places I've looked at on the web that relate SQL and relational algebra
seem good, but tend to ignore outer joins and group by, which kinda blows a
hole in most things.

Nifty example:

select lower(f) from (select f from a union select f from b);
(select lower(f) from a) union (select lower(f) from b);

If table a has "HELLO" and table b has "hello", the first will produce two
rows of output, whereas the second produce only one. To work, you require
the function to be *invertable* (1-to-1 mapping) which is pretty strict. Off
the top of my head I'd say the vast majority would fail that test.

UNION ALL would be fine I think, as long as the functions ware cachable and
there were no aggregates. Basically, as long all you're pushing down is a
cacheable projection.

--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> There are 10 kinds of people in the world, those that can do binary
> arithmetic and those that can't.