# Re: completeness of the relational lattice

Date: Fri, 22 Jun 2007 09:58:22 -0700

Message-ID: <1182531502.104482.168450_at_i38g2000prf.googlegroups.com>

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