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@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 ...

As I mentioned before, the only problem I had with the TA is that it seemed that certain logical behaviour was missing, eg. de Morgan's laws.   I imagined this might create some difficulty for the CWA.

p Received on Fri Aug 18 2006 - 00:52:14 CDT