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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: