Proof of Completeness of Algebraic Properties of Relational Lattice

It has been shown that the RL operations possess the following properties:

commutative: A && B = B && A

              A || B = B || A

associative: A && (B && C) = (A && B) && C

              A || (B || C) = (A || B) || C

idempotent: A && A = A

              A || A = A

absorbtive: (A && B) || B = B

              (A || B) && B = B

Furthermore, the algebra is quasi-distributive:

              A && (B || C) = (A && B) || (A && C) || empty(a,abc,b,bc,c)

(The empty term contains all attributes that are not common to both A
and B,
nor common to both A and C.)

Given commutativity, associativity, and the above quasi-distributivity, we can
rewrite any RL expression into a disjunctive normal form, which consists of a
collection of minterms connected by ||. Some of the minterms might be "empty"
terms, created by the application of quasi-distributivity. If there are more than
one "empty" minterm, they can be coalesced into a single one, containing only
those attributes that are common to all of the empty minterms. If the result
contains any attributes that are not part of the result of the expression,
those attributes can be dropped from the empty minterm as well.

If no applications of distributivity are required, there will be no empty term,
but we can manufacture one, again by inspecting the attributes of the result
and creating an empty minterm that corresponds. Thus all DNF expressions have
exactly one empty term, and if two expressions have the same type, they will
have the same empty term.

The minterms other than the empty term can be viewed as a set of sets of relation
variables. For example, (v1 || (v2 && v3)) || ((v2 && v4) && v5) || empty(...)
can be thought of as { {v1}, {v2, v3}, {v2, v4, v5} } || empty(...). Let us call
this the set representation.

Applications of the idemponent and absorbtive property can convert any set
representation into a set representation that is subset-free. That is, for
{ C1, C2, ... Cn }, there does not exist Ci, Cj such that Ci is a subset of Cj.
Let us call this subset-free disjunctive normal form, or SF-DNF.

Consider two expressions e1 and e2, each written in terms of a set of relation
variables v1 .. vn. If, for all possible values of v1 .. vn, e1 = e2, we say
e1 and e2 are semantically equivalent.

Now to address the main question. We wish to prove that if two expressions
e1 and e2 can be rewritten to SF-DNF form s1 and s2, and e1 and e2 are semantically equivalent, then s1 = s2.

Proof is by contradiction.

Given two semantically equivalent expressions e1 and e2 with SF-DNF form s1 and s2 respectively. ASSUME s1 != s2.

Let s1 = {B1, ..., Bn} || empty and s2 = {C1, ..., C2} || empty

Because e1 and e2 are semantically equivalent, they have the same set of attributes, so the two empty terms will be identical.

s1 and s2 are different, finite, and subset-free. Therefore, either there exists some Bi that is not a superset of any of C1, ..., Cn,
or there exists some Cj that is not a superset of any of B1, ... , Bn.
(If there were no such term, it would mean s1 and s2 were identical.)

We can assume without loss of generality that Bi is the not-superset term. (The proof is the same if we assume it is Cj.)

For each attribute of each variable in Bi, choose an arbitrary value from the type of that attribute. (The specific value is irrelevant. Note that this introduces the requirement into the proof that all types of all attributes contain at least one value.) For each variable in Bi, assign a value to the variable that consists of a single element, where each attribute has the chosen value from that type. For each variable not
in Bi, assign a value that is empty (that is, has no element.) Because each variable in the Bi minterm contains one element, and the attributes
in common with each variable are equal (because we chose the same value for each attribute), the result of the && operations on all the variables
in the Bi minterm will have a single element. Because all the other variables in all the minterms in s1 are empty, the minterms will be empty as well. The result of the || of each minterm will have exactly one row, from the Bi minterm. So s1 will have exactly one element.

In s2, every minterm will evaluate to an empty result, because we assigned to each variable an empty value, except for those in Bi, and no C1 .. Cn is a subset of Bi. Therefore, s2 will have exactly zero element.

This contradicts our assumption that s1 != s2. Therefore by RAA, if e1 and e2 are semantically equivalent, the SF-DNF form of e1 and e2 are equal. Since we can apply the equalities to rewrite e1 to s1, (and vice versa) and e2 to s2, and since s1 = s2, we can rewrite any two semantically equivalent e1 and e2 into each other.

QED. Marshall Received on Sun May 21 2006 - 01:56:54 CEST