Re: Notions of Type

From: Bob Badour <bbadour_at_pei.sympatico.ca>
Date: Fri, 18 Aug 2006 13:44:56 GMT
Message-ID: <svjFg.51093$pu3.597337@ursa-nb00s0.nbnet.nb.ca>

Marshall wrote:

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

Not all that nasty when one considers that most relational proponents would demand a dbms have a system catalog that has all of those things. Most (all?) would also insist the dbms properly perform schema changes in reaction to assignments to the system catalog.

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

I agree. My suggestion for the operand to project was clearly inferior to the others.

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

Why introduce asymmetry? Why not S: Relation(A INTERSECT P) ?

Or perhaps better:

Given sets of attributes A and B

   A : {name: AttributeName, type: Type} and a relation R of type Relation(A)

   R : Relation(A)
   B : {name: AttributeName, type: Type} and a relation P of type Relation(B)

   P : Relation(B)
PROJECT takes two operands, R and P, and returns a relation S

   S : Relation(A INTERSECT B)

If the operation is really union, the language might differentiate PROJECT syntactically with a different operator from UNION and semantically with a constraint that {} = (B MINUS A).

  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.

There is that, but even still, the familiar project syntax could be just a short-hand for 'name x same type as...'.

  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.

One of these days I will have to take the time to understand it better. Received on Fri Aug 18 2006 - 08:44:56 CDT