Yet Another Relational Algebra Operation
July 14, 2010
Relational Lattice theory originated as Relational Algebra cast into genuine mathematical shape. It gives a satisfactory foundation for ad-hock query transformation laws, such as push-selection-via-projection, which reduce to elementary algebraic laws of associativity, distributivity, absorption and so on. Relational Algebra cast into Relational Lattice looks like Boolean Algebra with every operation split twofold: there are two versions of disjunction, two version of conjunction, two negations, and finally, two versions of each constant
Here is a recent development which, on one hand, answers a long standing puzzle and, on the other hand, skews this little symmetry. Consider the following operation:
x # y = (x' v y')'.
It is idempotent, symmetric, associative. In addition, it honors both absorption laws over outer union:
x + (x # y) = x.
x # (x + y) = x.
Therefore, this new operation together with outer union forms a lattice! The constants
R11 become the supremum and infimum in the new lattice:
x # R00 = R00.
x # R11 = x.
Please note, that this operation is different from inner join by the mere fact that it is associative. The relationship between the two is:
x # y < x * y.
Unlike inner join, which is just a projection of natural join into common set of attributes, it appears to be much less intuitive.
To summarize, the bi-lattice structure that has been hinted two years ago is well and alive. However, the question “How many versions of logical AND operation is there” now appears to give a surprising answer of 3.