# Re: completeness of the relational lattice

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

On Jun 25, 5:34 am, Jan Hidders <hidd..._at_gmail.com> wrote:
>
> 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 * [].

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

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

Original text of this message