Re: Notions of Type

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

>

>

>

>
>

No, you can certainly do that. I was trying to be conservative in the type definition - a relation we'll be using only for its attribute definitions (its header, not its body) isn't really being "used" as a relation. For that reason, it seemed parsimonious to require only a set of attributes. One still needs to constrain the header of the second relation - it can't have attributes the first one doesn't.

• erk