Re: completeness of the relational lattice

On Jun 22, 2:06 am, Jan Hidders <hidd..._at_gmail.com> wrote:
> Hello Vadim, Marshall and others,
>
> The discussion seems to warrant it's own thread, so here goes.
>
> There seems to be some disagreement on what algebra we are studying.
> So let's discuss this first. It is important this get's fixed, because
> otherwise any time I spent on proving things might be lost. I think
> it's also important that we settle on notation, because I noticed I
> was getting confused. Since it's bascially Vadim's idea I'll try to
> stick to his notation as much as possible.

Okay.

(Over in sci.math, they mostly use ^ v for conjunction/disjunction instead of /\ \/. Once I got over my horror of seeing a letter used as an operator in mostly worked for me. Do we care?)

Anyway, as mentioned elsewhere, Vadim's notation is a good mathematic notation, but it makes a poor one for a programming language, which is my larger interest. I can use his notation for the newsgroup, but the software that I write will use my own, since my notation was carefully designed and optimized for language use.

Oh, we haven't mentioned precedence. I propose \/ and /\ have the same precedence, so that when we write the dual of an expression, we will never have to add any parentheses.

> So the syntax of the algebra is as follows: (E is the non-terminal for
> algebra expressions)
> - R : a relation name
> - E /\ E : the natural join
> - E \/ E : the inner union
> - 00 : the empty relation with empty header
> - 01 : the relation with the empty tuple and empty header
> - 10 : the empty relation with the set of all attributes as header
> - 11 : the relation with all tuples over all attributes
> - [x] : the empty relation over header {x} with x a single attribute
> - 'x=y' : the binary equality relation with header {x,y} and the
> restriction that x<>y

I believe we might be able to get along without the last three. (11, [x], and `x=y`.) And if we do need to talk about attributes, I think we need to be talking about sets of attributes. (So x above would be a set.)

I didn't see (relational) = mentioned in there. Is that just assumed? We need either relational equality or the relational comparator.

Also I don't see division in there yet. We were talking about including that, weren't we?

> I don't like having 10 and 11 because it clearly steps outside the
> relational model and first order logic, but I see no direct reasons to
> remove them.

10 seems required, because without it, the lattice is neither bounded nor complete, whereas with it it is both. Complete lattices are much nicer to work with. Also, 10 can be thought of a just an atom, rather than having any infinite properties. And looking at these equations it appears quite benign:

  10 /\ R = 10
  10 \/ R = R

11 is more problematic, not only because of its infinity of infinities,
but also because its infinities are "contagious."

11 /\ R

  has an infinite number of attributes and an infinite number of rows, but some (few) projections of it have a finite number of rows.

11 \/ R
  is more tractable, in that it has the same (finite) attributes as R but infinite rows.

> There was some doubt on the presence of [x] but I don't
> see how we can otherwise define projection.

Any expression of the form

E \/ [x]

can be rewritten as

E \/ (X /\ 00)

where X is any relation with the same header as [x]. I don't know that we need to be able to say what that header *is*, but we need to be able to say "free relation variable with fixed header." I think the latter is necessary and sufficient.

> Also I don't see how we can avoid mentioning attributes
> since we already have 'x=y' where the are already mentioned.

Will go looking for where we use that and respond there.

> So can we agree on this algebra and notation?

Sure, modulo the questions above.

Marshall Received on Fri Jun 22 2007 - 17:57:34 CEST