## 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 `true` and `false`.

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 `R00` and `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.