Re: Notions of Type
From: paul c <toledobythesea_at_oohay.ac>
Date: Fri, 18 Aug 2006 05:52:14 GMT
Message-ID: <iAcFg.429674$IK3.5888_at_pd7tw1no>
>
> 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!
>
Date: Fri, 18 Aug 2006 05:52:14 GMT
Message-ID: <iAcFg.429674$IK3.5888_at_pd7tw1no>
Marshall wrote:
> 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!
>
Thanks, and
Okay, maybe you are right but what if project is not binary but unary? Isn't the idea of treating it as a binary operator arbitrary? Is it enough to say that a projection joined with the relation it was produced from results in that same relation? Just wondering ...
p Received on Fri Aug 18 2006 - 07:52:14 CEST