# Re: completeness of the relational lattice

Date: Mon, 25 Jun 2007 10:19:08 -0700

Message-ID: <1182791948.391802.208830_at_m37g2000prh.googlegroups.com>

On Jun 24, 4:32 pm, Jan Hidders <hidd..._at_gmail.com> wrote:

> > Let R(u,w), S(u), Q(w), T(V), P(u,v), then we can't apply

*> > distributivity to simplify
**>
**> > ( (R /\ (S \/ Q)) \/ T ) /\ P
**>
**> This is solved by the extra rules for [H]. These allow me to make the
**> attributes of an expression explicit by rewriting it to r \/ [H] where
**> H contains all attributes of r. That means that in the above you can
**> rewrite S \/ Q to (S \/ [H1]) \/ (Q \/ [H2]) which in turn can be
**> rewritten to (S \/ [H1*H2]) \/ (Q \/ [H1*H2]). By then distribtivity
**> will apply.
*

OK, the nesting remains, although we have simpler conjunctive clauses.
For example, assuming

R(u,w), S(u,t), Q(w,t), T(v,t), P(u,v) the expression

( (R /\ (S \/ Q) ) \/ T ) /\ P

"simplifies" to a union normal form:

( ( (R /\ (S \/ [t])) \/ [t] ) /\ P ) \/ ( ( (R /\ (Q \/ [t])) \/ [t] ) /\ P ) \/ ( (T \/ [t]) /\ P )

This is indeed something new.

> What it should have said is that

*> every expression r that returns always an empty result can be
**> rewritten to [A(r)] where A is the function that give the attribute
**> set of the result.
*

I assume you have to know if each relation in the expression is empty or not. Then exvaluating the emptiness of the result is just a matter of evaluating boolean expression. In the example above suppose

R - empty, S - empty, Q - non empty, T - empty, P - non empty

( (0 /\ (0 \/ 1) ) \/ 0 ) /\ 1 = 0

The issue becomes much less obvious when we introduce negation/ difference/division.

> We consider the following algebra:

*>
**> E ::= R | E * E | E + E | {()} | [H] | 'x=y'
**>
**> Where:
**> - R : a relation with name R (and known header)
**> - E * E : natural join
**> - E + E : generalized union
**> - {()} : the relation with empty header and a single empty tuple
**> - [H] : the empty relation with header H (possibly empty)
**> - 'x=y' : the relation { (x=a, y=b) | a in D, b in D, a=b }
**>
**> The * and + will also be used as intersection and union on sets of
**> attributes.
**>
**> We define a function A that computes the header of the result:
**> - A(R) = H where H is the header of R
**> - A(r * s) = A(r) + A(s)
**> - A(r + s) = A(r) * A(s)
**> - A({()}) = {}
**> - A([H]) = H
**> - A('x=y') = {x,y}
**>
**> 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)
*

"and", not "or". I like the distributivity critera in this form!

> (9) r + (s * t) = (r + s) * (r + t) if A(s) * A(t) <= A(r)

Even more so...

*> Absorption:
**>
**> (20) r + (r * s) = r
*

> (21) r * (r + s) = r

*>
**> Empty relations:
**>
**> (14) 'x=y' = 'x=y' + [x,y]
**> (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
**>
**> Equalities
**>
**> (15) 'x=y' = 'x=y' * 'x=x'
**> (16) 'x=y' = 'x=y' * 'y=x'
**> (17) 'x=y' * 'y=z' = 'x=y' * 'y=z' * 'x=z'
**> (18a) R * 'x=x' = R if x in header R
**>
**> Miscellaneous
**>
**> (18b) [] * 'x=y' = [x,y]
**> (18c) 'x=y' + [H] = 'x=x' if x in H and y not in H
**> (19) 'x=y' + [] = {()}
**> (24) ((r * 'x=y') + [H]) * 'x=y' = ((r * 'x=y') + [H + {y}]) if x
**> in H
*

Received on Mon Jun 25 2007 - 19:19:08 CEST