Re: MV Keys

From: Marshall Spight <>
Date: 10 Mar 2006 07:59:41 -0800
Message-ID: <>

Jon Heggland wrote:
> says...
> As for the RA not having tuple operations, true, but I find it very
> convenient to be able to talk about tuples when explaining how the RA
> operators work to my students.

I have no desire to constrain how anyone talks. :-)

> Anyway, I think there are two relatively independent issues here. One is
> whether your system will be complete and usable without tuple types.
> That is to a certain degree a matter of taste; I'll admit it may be
> possible.


> The other issue is your redefinition of "tuple" and the inconsistencies
> I claim arise because of that.

So I'll just stop doing that then.

> I have the impression you dodge all my
> questions about infinite nesting of relations (a tuple being a set of
> one tuple which is a set of one tuple and so on ad infinitum), so to my
> mind, you don't take your own definition seriously.

You are correct. Once I dropped type type "tuple" from the design, I pretty much stopped thinking about tuples per se. I have enough trouble getting relations and scalars right.

> I'd guess you have
> discovered that you don't need tuple types/variables, and so you reuse
> the "tuple" term for convenience---without really thinking about the
> theoretical consequences.

In fact, I try *not* to use the term "tuple."

> I guess that since you are convinced your
> system can work, you see no fault with your tuple definition---but I say
> that your system might work because you don't really take the
> consequences of your definition.

Fair. You have uncovered a terminological inconsistency of mine, which I will now correct.

> > > The problem is that you contradict yourself. You say (1,b) is a tuple,
> > > and you say that a tuple is a set. (1,b) is not a set.
> >
> > Syntactically, that is true. Semanticly, it may not be true.
> No, the other way around. Through creative use of syntax, you can
> *define* (1,b) to represent a set (though you sun into trouble if you
> want it to represent the same set as { (1,b) }---what does (1,b)
> represent in the second case?).

One does not run in to any trouble. In my last post I made the analogy with {} in Java; they don't mean the same thing everywhere they appear. Likewise with parentheses here.

And just for fun, here's an alternative semantics for the syntax above, in which the parentheses *do* mean the same thing.


Above, "(" means "introduce a new set, cardinality 1, with the following attributes."

{ (1,b), (2,a) }

Here, "{" means "introduce a new set of arbitrary cardinality". "(1,b)" means the same as it did before, and the comma after it means "union".


> > > Do you also agree that the cardinality-1 relation literals must (or at
> > > least should) be specified in such a way that the compiler knows that
> > > the cardinality is 1?
> >
> > Sure. How could it not know?
> When a method in Java takes an array as a parameter, it does not know
> the size of it at compile time.

Ah, I see what you mean now.

> The compiler of course knows the size of the literal, but the
> size of an array is not part of its type.

This is actually an extremely interesting question, and one that I'm not far enough along to discuss well. But there are, in a very few experimental systems, quite interesting things one can do with considering list size as a static quality.

> So you cannot in your system
> define a procedure that requires a tuple as an argument---but you don't
> need to or want to anyway?

Right. Functions are relations; "tables" are relations; join.

(But I do allow nested relations, so it's possible to have an attribute of relation type that has just one row. But there's no point to an attribute with a relation type that's statically one row; it's identical to flattening the attribute up a level.)

> > How well it works in practice will have a lot to do with
> > how well the idea is executed. A convenient syntax could
> > help a lot.
> Sure. I guess what one does in practise, is to use conventional syntax,
> and just define the result using such relational terms. I.e. more an
> intellectual game than an actual language design / operator
> implementation strategy.

That's a bit dismissive, don't you think? Since you put it in those terms, I'll just say that design *is* an intellectual game. A hard one, with potentially significant benefits. The relational algebra is also an intellectual game.

> > ... I don't envision a separate language;
> > users will certainly be able to write their own functions; it
> > would not be a general purpose language otherwise.
> But they won't be able to use anything but relation types? I have a hard
> time envisioning how this will work, but maybe I'm just unimaginative.
> :)

Again: functions as relations; tables as relations; join. Add union and it's relationally complete. Allow recursive functions and now it's turing complete. Add sum types so users can define their own scalars, along with a few scalars that are predefined for efficiency and convenience. Add lists for more convenience. Stir.

> My main issue is your definition of relation, and your use of the term
> "tuple". You say that a relation is a subset of a cross product of sets.
> An element of such a product is called a tuple; this is really not up
> for debate, I think. It is *not* a set.

Sure, that's fine.

> When you say that it is, you are
> gainsaying elementary set theory. You don't need to do this in order to
> simplify your system by removing tuple types!

Fair enough. I'll stop doing that.

> > > And how would you do the variable assignment (if that is applicable---do
> > > you plan to have string variables?)?
> >
> > I had assignment for a while, but I dropped it; it was redundant
> > with UPDATE.
> There are some who say UPDATE *is* assignment. :) But are you saying
> that you don't have scalar variables, only relvars? Or that you use
> UPDATE to change a scalar variable?

Update and assignment are both imperative operators, but they are not the same thing. Also, I am saying no scalar variables.

Marshall Received on Fri Mar 10 2006 - 16:59:41 CET

Original text of this message