Re: Notions of Type

"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? Received on Thu Aug 17 2006 - 20:08:43 CEST