Re: Notions of Type
Date: 17 Aug 2006 21:48:39 -0700
Message-ID: <1155876519.670739.303540_at_74g2000cwt.googlegroups.com>
paul c wrote:
> Marshall wrote:
> > paul c wrote:
> >> Marshall wrote:
> >>> erk wrote:
> >>>> ...
> > Consider PROJECT:
> >
> > PROJECT: Relation, Set-of-attributes -> Relation
> >
> > So for PROJECT of an x,y point over x, we pass it two
> > things:
> >
> > 1) A relation defined over attributes x and y
> > 2) ???
> > and it returns
> > 3) A relation defined over attribute x (aka "profit")
> >
> > Whoops! Doesn't fit the template. The second argument isn't
> > a relation. So, strictly speaking, this is not an algebraic operator,
> > because it isn't closed over the type Relation. Exercise for the
> > reader: what *is* the type of the other argument? This should
> > make your head hurt a least a little bit.
> > ...
>
> Thanks for that. Is it not equally reasonable to have:
>
> PROJECT: Relation, Relation -> Relation
>
> and pass it
>
> 1) A relation defined over attributes x and y
> > 2) A relation defined over attribute y
> > and it returns
> > 3) A relation defined over attribute x (aka "profit")
>
> I don't know the formalism for this, but I had thought that if I have a
> value (or even type) R{x,y}, a value R{x} is implied by definition
> (implied in the sense that if one has a value, the other has a value,
> similarly for types) and that all Project does is expose the
> implication, just as TABLE_DEE and DUM do if I project 'nothing'.
>
> Is this too shallow?
I don't see anything to object to in the above.
However, earlier we were discussing just how "algebraic"
the operators of the relational algebra are. And the standard
definition of PROJECT is not very algebraic. It doesn't have
a lot of useful algebraic properties.
Is it commutative? No, because the two operands don't even
have the same type. Is it associative? No, because if we
have
(R{x,y,z} PROJECT {x,y}) PROJECT {x}
and try to rewrite that, we get
R{x,y,z} PROJECT ({x,y} PROJECT {x})
and we fail because {x,y} PROJECT {x} is not well-typed.
These considerations are not merely decorative. If we
have a well-understood set of algebraic properties that
our operators obey, we are going to have a much
easier time proving, say, a theorem about the
validity of a query transformation we might want to
apply in our optimizer. Is it always valid? You have
only to write a proof to determine so. Now try writing
that proof when you have five operators and many
of them are neither commutative nor associative, and
take operands of different types.
The Tropashko algebra's operators ARE commutative,
and associative, and absorbitive and idempotent
to boot! And semi-distributive as it turns out. And
there's only two of them. Now THAT is an algebra
for you!
Marshall Received on Fri Aug 18 2006 - 06:48:39 CEST