Re: Notions of Type
Date: Thu, 17 Aug 2006 20:44:37 GMT
Message-ID: <Vy4Fg.3834$v_1.924_at_trndny01>
"erk" <eric.kaun_at_gmail.com> wrote in message
news:1155839007.739204.204210_at_h48g2000cwc.googlegroups.com...
> 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
> > >
> >
> > 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?
>
> 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
>
Sure it can.... if you don't mind getting dragged into yet another discussion about nulls !!!! Received on Thu Aug 17 2006 - 22:44:37 CEST