Re: Notions of Type

From: J M Davitt <jdavitt_at_aeneas.net>
Date: Thu, 17 Aug 2006 23:21:50 GMT
Message-ID: <iS6Fg.55213$vl5.37756@tornado.ohiordc.rr.com>

David Cressey wrote:

> "Marshall" <marshall.spight_at_gmail.com> wrote in message
> news:1155833602.403082.5690_at_h48g2000cwc.googlegroups.com...
> 

>>paul c wrote:
>>
>>>Marshall wrote:
>>>
>>>>erk wrote:
>>>>
>>>>>Sorry if this is obvious to everyone else, but does an algebra

> 
> include
> 


>>>>>only operations defined on values of the type in question?

>>>>

>>>>Yes.

>>>>

>>>>

>>>>>I ask
>>>>>because in relational algebra, at least the rename operator involves

> 
> a
> 


>>>>>different type ("attribute name") than the "core type" (relation).

>>>>

>>>>Very true. Of the various relational operators that have been

>>>>identified over the years, only a few, like union, are really

>>>>algebraic. RESTRICT, PROJECT, etc. aren't. ...

>>>

>>>Just a quick question - is your reason for making that statement that

>>>restrict, project, etc. result in a relation that doesn't necessarily
>>>have all the attributes of the operand relations?
>>
>>No; that's actually not a problem.
>>
>>The problem is the operands. Strictly speaking, an algebraic operator
>>would be one which had the type
>>
>> op: 'a, 'a -> 'a
>>
>>("The thing named "op" has the type: function taking operands of
>>type some-a and some-a and returning a value of type some-a.")
>>
>>So the algebra of the integers has operators like:
>>
>> +: int, int -> int
>>
>>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.
>>
>>Note that the type Relation is a what Date et al call a "type
>>generator"
>>and others call a parameterized type. However this doesn't affect
>>our definition of algebra. For example, one can define a list algebra
>>operator "concatenate"
>>
>> concat: ['a], ['a] -> ['a]
>>
>>Now, I'm not blaming anyone :-) for calling the classical relational
>>operators algebraic; in fact, I think we've all intuited, loosely
>>speaking, that there's a real algebra in there trying to get out.
>>
>>
>>Marshall
>>

> 
> 
> I'm surprised the PROJECT is such a problem.  Maybe I should stay out of the
> discussion,  because this is a little over my head.  But here goes, anyway:
> 
> Why can't you define a "set of attributes"  as a relation?  I'm thinking
> that an empty relation  (one with no tuples) has exactly the same
> information content as a "set of attributes".  If you do that,  why can't
> you say,
> 
> PROJECT <relation>, <empty relation>  ->  <relation>
> 
> 
> Or have I violated some other aspect of the formalism?

Wait a minute...

   PROJECT <relation> <set of attributes> -> <relation>

right? And the question is, "Does this definition of PROJECT demonstrate lack of algebraic closure?" I think

   PROJECT <relation> <relation> -> <relation>

is a step in the wrong direction and don't think such a thing is necessary for closure. I think that the fact that one of the operands and the result are relations is what provides closure. Received on Thu Aug 17 2006 - 18:21:50 CDT