Re: completeness of the relational lattice

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