# Re: completeness of the relational lattice

Date: Mon, 25 Jun 2007 11:04:31 -0700

Message-ID: <1182794671.126631.246330_at_e9g2000prf.googlegroups.com>

On Jun 25, 5:34 am, Jan Hidders <hidd..._at_gmail.com> wrote:

> Hello Marshall and Vadim,

*>
**> The axioms for equality axioms looked a bit ugly, so I wondered if
**> that could be improved. I think we can if we introduce in analogy to
**> [H] the operation <H> which denotes the relation with header H that
**> contains all tuples of the form (x,x,..,x).
**>
**> The syntax:
**>
**> E ::= R | E * E | E + E | {()} | [H] | <H>
**>
**> If we adapt the equations we get:
**>
**> Standard equalities:
**>
**> (1) r * r = r
**> (2) r * s = s * r
**> (3) r * (s * t) = (r * s) * t
**>
**> (4) r + r = r
**> (5) r + s = s + r
**> (6) r + (s + t) = (r + s) + t
**>
**> (7) r * {()} = r
**> (13) {()} = {()} + []
**>
**> Special distribution equalities:
**>
**> (8) r * (s + t) = (r * s) + (r * t)
**> if A(r) * A(s) <= A(t) or A(r) * A(t) <= A(s)
**> (9) r + (s * t) = (r + s) * (r + t)
**> if A(s) * A(t) <= A(r)
**>
**> Absorption:
**>
**> (20) r + (r * s) = r
**> (21) r * (r + s) = r
**>
**> Empty relations:
**>
**> (10) R = R + [H]
**> if H is the header of R
**> (11) [H] * [S] = [H + S]
**> (12) [H] + [S] = [H * S]
*

> (22) R * [] = [H]

*> if H is the header of R
*

You have informal "H is the header of R" in many places. Why don't we use this axiom as a definition of [H]? Then, we just substitute [H] with R * [].

Also given that we agreed not to introduce operator precedence, the RL expressions contain a lot of parenthesis. Therefore, introducing constants which include brackets is not the best choice.

The [] brakets are very convenient when we want to specify relation arguments explicitly, e.g [x,y]. In the algebraic context relation header is just R * 00.

*> Equalities
**>
**> (27) <H> * <S> = <H + S>
*

> (28) R * <x> = R

*> if x in header H (NOTE x is a single attribute)
*

I don't see why it is an equality axiom. The <x> is unary relation which is domain x.

00 <= X <= R /\ 00 implies X = 00 or X = R /\ 00

> (30) <> = {()}

*>
**> Miscellaneous
**>
**> (26) <H> + [S] = <H * S>
**> (29) [H] * <S> = [H + S]
**> (31) ((r * <S>) + [H]) * <S> = ((r * <S>) + [H'])
**> if S * H nonempty and H + S = H'
*

You have to specify that headers of <S> and r overlap on no more than a single attribute -- and I don't see this condition here. Received on Mon Jun 25 2007 - 20:04:31 CEST