Re: Notions of Type

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 Received on Thu Aug 17 2006 - 11:53:22 CDT