Re: Notions of Type
Date: 17 Aug 2006 09:53:22 -0700
Message-ID: <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:
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
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 Received on Thu Aug 17 2006 - 18:53:22 CEST