Re: Proof of Completeness of Algebraic Properties of Relational Lattice

Marshall wrote:
>The algebra is quasi-distributive:
>A && (B || C) = (A && B) || (A && C) || empty(a,abc,b,bc,c)

This is an interesting attempt to formulate distributivity criteria. I interpret your identity as a formal algebraic equality in the lattice algebra

A /\ (B \/ C) = (A /\ B) \/ (A /\ C) \/ D

where the additional term D vanishes whenever Spight distributivity criteria is met. The analogy is with Lie algebras, which are not commutative ab != ba so that a special construction -- the commutator [a,b]=ab-bc -- is introduced. In this case the additional disjunct D can be called a "distributor term".

First of all, how can we be sure that there always exists a "distributor term"? The equation that defines distributor term D can have no solutions! Existence of distributor hinges on the following inequality:

A /\ (B \/ C) >= (A /\ B) \/ (A /\ C)

proof:

A /\ (B \/ C) /\ ((A /\ B) \/ (A /\ C)) =                 #

A /\ ((A /\ B /\ (B \/ C)) \/ (A /\ C /\ (B \/C ))) = # absorption

A /\ ((A /\ B) \/ (A /\ C)) =                             #

((A /\ B /\ A) \/ (A /\ C /\ A)) =                        # idempotence

(A /\ B) \/ (A /\ C)

So far so good. There are two problems, however.

Distributor term defined equationally as above is not unique, however. There has to be an extra condition.

Second, the distributor term can't be expressed as a closed form expression of the relations A, B, and C. You can witness this in a simple lattice generated by all the unions and joins of the following relations

Q = {x=1}
R = {x=1}\/{x=2}
S = {y=a}
T = {y=a}\/{y=b}

Take

A = R /\ T
B = Q
C = S

then

A /\ (B \/ C) = {(x=1,y=a),(x=1,y=b),(x=2,y=a),(x=2,y=b)}

(A /\ B) \/ (A /\ C) = {(x=1,y=a),(x=1,y=b),(x=2,y=a)}

It is natural to expect the distibutor term to be {(x=2,y=b)}, but this relation doesn't belong to the lattice generated by Q, R, S, T! Received on Sun May 21 2006 - 21:41:52 CEST