Re: completeness of the relational lattice

On Jun 22, 8:57 am, Marshall <marshall.spi..._at_gmail.com> wrote:
> (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?)

I was blissfully unaware of ^ v . I'm switching to them and reserve big ones for quantifiers (if such things would ever make an apearance)

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

OK

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

IMO the axioms would drive the notation. If there is no important axiom that involves 11 (I think there is), then we skip it. I suggest that the set

{00,01,10,11}

such that

01 < 00 < 10
01 < 11 < 10
00 ^ 11 = 10
00 v 11 = 01
00 != 11

is a smallest nontrivial relational lattice model.

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

Nice observation.

Overall, let's shoot down some axioms, then the rest of the notation would fall in place. Received on Fri Jun 22 2007 - 18:58:22 CEST