There is one nearly ubiquitous discrete mathematics structure familiar to every software professional — Boolean Algebra. It is named after George Boole who invented it around 1840. Half century later Dedekind studied more general lattice structures; however, his work was ahead of the time. In 1930s Birkhoff rediscovered lattices and, from that time on, the subject has been active and growing.

General lattices are weaker structures than Boolean algebras. Relational lattices are positioned somewhere in-between. In the next section we’ll rehash the key Boolean Algebra ideas and cast them into a shape convenient for moving on to Relational Lattices.

Boolean Algebra

Algebra is an abstract field which ordinary person finds hard to comprehend. Traditional introduction develops one’s intuition based on examples. In elementary school we study numbers and arithmetic; much later venturing to variables and equations.

When adding numbers we examine their structure (as sequence of digits) and apply arithmetic addition (or multiplication) rules to digits in individual positions:

6 5 3
2 7 4
-----
9 2 7

Boolean arithmetic operates binary vectors pretty much in the same spirit. The above column-wise example of addition is mirrored by disjunction

0 1 1 0
1 0 1 0
-------
1 1 1 0

The algorithm is virtually the same, except for the absence of carry-over rule and different “addition table”.

Binary vectors could be viewed as sets of numbers. For example, the vector 1 1 0 0 has 1s at positions 2 and 3 (0-based, counted from the right). Then Boolean disjunction is essentially set union, conjunction is set intersection, and negation is set complement.

Classic algebra [of numbers] honors several laws:

1. Symmetry
x + y = y + x
x * y = y * x

2. Associativity
x + (y + z) = (x + y) + z
x * (y * z) = (x * y) * z

3. Distributivity
x * (y + z) = (x * y) + (x * z)

Boolean algebra respects these laws as well (with any of the two possible replacements of the addition “+” and multiplication “*” with conjunction “&” and disjunction “|“). One more law that carries over to Boolean algebra with substitution of arithmetic negation by logical negation:

4. Double Negation
- (-x) = x

The laws unique to Boolean algebra are:

5. Idempotence
x & x = x
x | x = x

6. Absorption
x & (x | y) = x
x | (x & y) = x

7. DeMorgan
-x & -y = -(x | y)

Relational lattices are weakened Boolean algebras that retain some of these axioms.

Relational Lattice

In previous section we went through concepts of binary vectors and sets as prototypical Boolean algebra models. Relations generalize sets. Relation can be viewed as table, for example

People = [name    sex]
          max     male
          peter   male
          marina     female
          sravanti   female
;

Relation inherits column and row table structure and, therefore, is more sophisticated than a set. In the example of People relation attributes alone form the set {name,sex}. The other noteworthy set is relation content organized into tuples

{
(max, male),
(peter, male),
(marina, female),
(sravanti, female),
}

A significant part of relational lattice theory plays around duality between relation attributes and tuples (or, loosely speaking, table columns and rows).

Now that we have relations as our relational algebra elements what are the operations among them? Since the elements now have more elaborate structure we can’t expect classic Boolean algebra conjunction, disjunction and negation to apply without breaking some axioms. The algebra of relations is distinct from Boolean algebra, indeed. The big picture is that each operation splits into two: relational lattice has two variants of conjunction, two variants of disjunction, and two negations. In addition to binary and unary operations Boolean algebra has two distinguished constants (which are formally 0-ary operations). They also bifurcate twofold and give rise to four distinguished relational lattice constants!

Let’s dive into details and look closely into each relational lattice operation. Again, each relation is “composed” of the two sets, therefore, and set operations over each component are independent of each other. Here are the possibilities:

1. Natural join^” is an operation that unions relation attributes and intersects tuples. For example, given the two relations

Pets=[nickname  specie]
      folly    dog
      scruffy  cat
;

and

Fed=[name  nickname  time]
     claire  folly   200
     max   folly    200
     max   folly    300
     max   scruffy  200
;

their natural join is

Pets ^ Fed=[name   nickname  specie  time]
          claire folly     dog     200
          max    folly     dog     200
          max    folly     dog     300
          max    scruffy   cat     200
;

2. Inner unionv” is an operation that intersects relation attributes and unions tuples. For example,

Pets v Fed=[nickname]
          folly
          scruffy
;

These two operations honor lattice laws ([1]). It is instructive to compare Hasse diagrams for Boolean algebra and Relational lattice side-by-side:

BAvsRL

You can see that some of Boolean algebra perfect symmetry is lost, yet Relational lattice has Boolean sub algebras in some facets ([2]).

Uniting attributes while intersection tuples in natural join, and intersecting attributes while uniting tuples are two possible interpretation for Boolean conjunction and disjunction. There is alternative possibility where we union both attributes and tuples, or intersect both. In [4] we explored the connections between these four operations.

The same idea carries over to the negation operation. It is impossible to introduce genuine negation for relational lattice that satisfies all the Boolean algebra laws, but it is feasible to reincarnate it into two weaker forms. Relational complement keeps relation attribute set intact, while applying set complement to tuples. Contrast it with inversion that complements relation attributes. It is not possible to keep the relation content when changing attributes so, algebraically, relational inversion is deficient compared to relational complement — the former doesn’t honor the law of double negation.

To conclude, relational lattice is more sophisticated structure than Boolean algebra. It inherits some Boolean algebra properties, while breaking the symmetry in peculiar way. Yet, compared to classic Relational Algebra it is genuine algebraic properties that make it promising both for research and programming.

References

1. Relational Algebra as non-distributive lattice. The originating paper with motivation (rather thin on formalism).

2. First steps in relational lattice. Initial investigation of non-distributivity phenomenon with algebraic emphasis onto query transformations.

3. Relational Lattices: an introduction. The title of this paper by Litak,Hidders,Mikulas is somewhat misleading: it is introduction for mathematicians. It suggests a set of three powerful axioms (in addition to standard lattice framework). Arguably, the notation is confusing: the \oplus and \otimes are commonly used for semirings, and while relational join ^ is indeed a good candidate for \otimes, the addition \oplus is better captured by <OR> so that both operations satisfy pre-semiring laws. It is an open question if one can find genuine semiring pair of operations in Relational Lattice.

4. Relational Lattice Foundation for Algebraic Logic discovers a parallel (broken) lattice that leads to yet another axiom system. It is genuine pre-bilattice if inner join is substituted by De Morgan’s dual of inner union.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: