Re: Notions of Type

erk wrote:
> Marshall wrote:
> > 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.
>
> To be pedantic, do operators of type R x R x ... -> R x R x ..., for
> any number of R on either side, fit the algebra of R? Or is there some
> cardinality "constraint"?

Lacking a decent definition of "algebra" I can't really say. :-( You'd think some of the algebra books I have would bother to define the word "algebra" in them somewhere, but I don't recall that they do. Wait, I just bought a new one; let me go check it.... Nope. No definition of algebra anywhere in that algebra book.

(By the way, I don't want anyone to get the idea that I think I'm some kind of math whiz. I actually suck at math. I don't know that much of it and what I do know has been quite painful to acquire. I do the the RA is cool, though.)

> > Exercise for the
> > reader: what *is* the type of the other argument? This should
> > make your head hurt a least a little bit.
>
> Maybe I'm off-base, but isn't the type of the second argument a subset
> of the heading of the relation?

Sure, why not? But now can I define a relvar V1 that has the type: subset of the heading of V2? Can I have an attribute with that type? What happens to V1 if I drop a column in V2? Nasty nasty questions.

I think it's quite reasonable to investigate the idea of types as values. But I think it would be bad if our motivation for doing so was because we needed to go through various convolutions just to write the type rules for our basic algebra. Much better to start with a clean algebra and investigate from there.

> So if RELATION is a type generator, the
> second argument is a type parameterized by the actual type of the
> relation parameter.

Yes. So let's try to write that, shall we?

Well, I don't have a notation for that exactly. I need to write constraints in the type domain to do it. Hmmm. Making it up on the spot ...

Given a set of attributes A
  A : {name: string, type: Type}
and a relation R of type Relation(A)
  R : Relation(A)
and a relation P of type ? that's a subset of A   P : ? | subset(P, A)
PROJECT takes two operands, R and P, and returns a relation S

  S : Relation(A MINUS P)

Ugh. I still need to define MINUS which isn't so bad. But again, what's the type of P? I don't think it's the same as the type of A; that overspecifies things, because we don't need a type attribute in P. We really only need the name column. So now to write the definition of PROJECT, we need some operator ... hmmm ... we need an operator that can take a relation of a given set of attributes and return us another relation like that, but with fewer ... uh oh; now we're in trouble.

> There are various sense of type parameterization
> here, and I'm not smart enough right now to find their proper names.
> Does some type jockey care to rescue us?

I weigh too much to make a decent jockey, but hey.

Most of these things are just simple (ha!) parametric polymorphism. The tricky part comes in at P; it's type is not merely parametrically polymorphic but dependently typed as well.

> > Note that the type Relation is a what Date et al call a "type
> > generator"
> > and others call a parameterized type.
>
> Are these one and the same?

As best I understand the terms, yes.

> > [...] I think we've all intuited, loosely
> > speaking, that there's a real algebra in there trying to get out.
>
> I think for purposes of the relational model we all know and love
> (especially its useful operators), a real algebra won't suffice. Or am
> I just being short-sighted?

I think the Tropashko algebra proves it will suffice. Furthermore, it paves the way for a unified relation type that encompases both the data-valued relations we are used to, and predicate valued relations. Which is jaw-droppingly amazing, if you ask me.

Marshall Received on Fri Aug 18 2006 - 07:48:59 CEST