Re: Notions of Type
From: paul c <toledobythesea_at_oohay.ac>
Date: Thu, 17 Aug 2006 18:18:45 GMT
Message-ID: <9q2Fg.412096$iF6.405033_at_pd7tw2no>
>>>>> because in relational algebra, at least the rename operator involves
>>> 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
>>
Date: Thu, 17 Aug 2006 18:18:45 GMT
Message-ID: <9q2Fg.412096$iF6.405033_at_pd7tw2no>
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>>>>> I ask
>>>>> only operations defined on values of the type in question?
>>>> Yes.
>>>>
>>>>> because in relational algebra, at least the rename operator involves
> a>>> restrict, project, etc. result in a relation that doesn't necessarily
>>>>> 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
>>> 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? >
I'll interrupt too - I don't think empty relations come into it (unless both operands are empty). I thought by definition that an N-ary relation implies 2**N relations (that many relations having that many subset headings). Maybe I'm talking axioms, not algebra, I'm not sure.
p Received on Thu Aug 17 2006 - 20:18:45 CEST