Re: Notions of Type
Date: Fri, 18 Aug 2006 13:44:56 GMT
Message-ID: <svjFg.51093$pu3.597337_at_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 - 15:44:56 CEST