Re: MV Keys

Jon Heggland wrote:
> marshall.spight_at_gmail.com says...
> > >
> > > Maybe I'm being dense here, but doesn't that entail that a relation is a
> > > set of set of set of set of set of set of......?
> >
> > Not that I can see. A subset of a relation is a relation; the
> > non-proper subset is also a relation, etc.
>
> Yes, of course. But you say that an *element* of a relation is also a
> relation---which by definition also have elements that are relations
> that have elements that are relations...

What I would say is that "a subset of a relation is also a relation."

> To recap, with a concrete example: You said
>
> > Relation: a subset of a product of sets
> > Tuple: a subset of cardinality 1 of a product of sets.
>
> Given sets I { 1, 2 } and C { a, b }.
> The product is { (1,a), (1,b), (2,a), (2,b) }, right?
> A possible relation is then R { (1,b) }, right?
> This relation is also a tuple by your definition, right?

Yup.

> So I ask: What do you call an element of a relation?

What does it matter what we call it? My claim is that it's not a useful nor necessary abstraction, since it's just a kind of relation. Let's just stop talking about it as if it were something distinct. To me, it is like the distinction between list-of-char and string; entirely unnecessary; historical only.

> For example the
> sole element of R, which is (1,b)? You say:
>
> > "Tuple," "element" and "relation" all seem valid to me.
>
> Yet (1,b) is obviously not a relation, and equally obviously not a tuple
> by your definition! It is not the subset of anything, because it is not
> a set. Do you still not see the problem?

Yes, I still don't see the problem.

There is no way this issue can be resolved using arguments that use 'tuple' as a required abstraction, since that very thing is the issue in question. The way to resolve the issue is to either show that some important quality is lost if we don't make the distinction (and again, that important quality *cannot* be the distinction in question), or to show that everything we want to accomplish can be accomplished without it.

> > > How does a relation
> > > literal look like in your world? Or a tuple literal, for that matter?
> >
> > I don't think the syntax matters, particularly.
>
> Perhaps not, but I ask because I believe specifying this will help
> reveal either the flaw in my thinking, or the one in yours.

Okay, but I'm suspicious of any line of argumentation about semantics based on syntax.

Proposal:
A relation of multiple elements can be specified as follows

{
(attr1=val1_1, attr2=val1_2, ... attrn=val1_n), (attr1=val2_1, attr2=val2_2, ... attrn=val2_n),  ...
(attr1=valm_1, attr2=valm_2, ... attrn=valm_n) }

As a syntactic shorthand, perhaps a one-element relation could be specified as follows:

(attr1=val1, attr2=val2, ... attrn=valn)

but this is unnecessary and if it introduces any ambiguities it clearly cannot be allowed.

> > But since you asked,
> > I see nothing wrong with using a tuple-specific syntax for relations
> > that happen to have only one element. :-)
>
> Even though you make a point of treating relations and tuples the same
> for simplicity? Seems to me that you lose whatever gain you may have
> had.

I don't see how. Anyway, the value of this idea is hard to evaluate in the absence of a working system, or a formal semantics, or whatever.

> > As I mentioned in another post, the RA doesn't have any operations
> > on elements,
>
> I don't see what that has to do with it. Don't you agree that the
> ability to specify relation literals and tuple literals is needed?

I agree that the ability to specify relation literals is needed. I agree this includes cardinality-1 relation literals.

> > so this issue doesn't come up.
>
> It did come up for me trying to understand your system.

Is there any reason to think that this isn't just the result of the fact that you are used to working with a system in which this abstraction is important?

> > The operations on
> > tuples that are sometimes described are just special cases of
> > the relational operations; they may be discarded without loss
> > of generality. Operations on attributes are as they ever were;
> > specific to the attribute type and not part of the RA.
>
> But how can anyone ever get to the attributes? It's sets all the way
> down!

What do you mean by "get to?" I don't see that anything is necessary beyond the ability to invoke a function, and that can be considered a relational operation. Consider a function add(a:int, b:int) : (c: int). (This function has three attributes; two input and one output. After invocation, the c attribute has the value a+b.)

Here's a relational operation:

add natural_join { (a=1, b=2) }

The result is

{ (a=1, b=2, c=3) }

It is true that some facility beyond simply the relational operators is necessary. For example, you probably need something like pattern matching on union types. The type "int" is not a relation type, and you need arithmetic functions somehow.

> > > Anyway, what is *good* about this definition? :)
> >
> > It's simpler. You have fewer kinds of types. You also have
> > fewer things to implement.
>
> I think you are mixing interface/model and implementation here.

Certainly not! There were two sentences after "it's simpler." The first was about interface and the second about implementation. There are benefits at both levels. But that doesn't mean I'm mixing them.

> But
> consider this example: I have a procedure that takes/wants a tuple as an
> argument. It only works on tuples, or singleton relations in your world.
> With tuple types, this is fairly trivial. Without, it seems to me you
> must do a lot of extra work for this to function reliably:
>
> * Either, you must in your procedure check that the relation indeed
> contains exactly one element, and throw a run-time error if it doesn't.
>
> * Or, you must at compile time check that no invocation of the procedure
> ever uses a non-singleton relation as an argument. That may be hard, but
> more importantly: You then probably have to indicate to the compiler
> that your procedure expects/demands a singleton relation---by using some
> special syntax/annotation/metadata, I guess. And if you do, what is the
> meaningful difference between a proper tuple type and a singleton-
> relation-type-with-special-syntax?

Or, you could have it such that prodecurally defined functions were always, necessarily expressed in single-element terms (as is customary,)
and rely on the relation operators to handle the cardinality issues.

Function application as an abstract operation can be replaced with relational operators, specifically natural join and projection.

> > Note
> > that plenty of successful programming languages discard all type
> > information prior to the start of a program run. This can even be
> > done in safe languages.
>
> That's neither here nor there, IMO. When defining what a relation is, I
> don't want to have to think about programming language implementations.

I didn't ask you to! However you do need to be able to distinguish between static and dynamic qualities, since this is a semantic difference. Type is the quintessential static quality.

> > So, what are you going to do with this string now that you've got it?
>
> Compare it to another string? Put it into a variable of type String?
> Examine its third character?

All of these can be done with either relational operators on other relations, or relational operators on functions.

> > You might pass it to a function. And what do the arguments to a
> > function look like? Hmmm. A set of named attribute values. So
> > we reconstitute it into a tuple and then apply the function.
>
> So you envision a system where the arguments to a function are
> identified by name, not position?

Yes. Also, return values are identified by name, as opposed to having a single anonymous return value. This makes functions structurally identical to relation values.

Marshall Received on Wed Mar 08 2006 - 20:39:56 CET