# Re: completeness of the relational lattice

Date: Mon, 25 Jun 2007 12:34:25 -0000

Message-ID: <1182774865.386727.278570_at_q69g2000hsb.googlegroups.com>

E ::= R | E * E | E + E | {()} | [H] | <H>

If we adapt the equations we get:

(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:

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

Equalities

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

(28) R * <x> = R

if x in header H (NOTE x is a single attribute) (30) <> = {()}

(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'

Btw., important related literature: http://citeseer.ist.psu.edu/379191.html Vadim will like it, lots of lattices and cylindrical algebras. ;-)

Cheers,

- Jan Hidders