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 `1`

s 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 union* “`v`

” 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:

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 and are commonly used for semirings, and while relational join ^ is indeed a good candidate for , the addition 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.

December 23, 2014 at 12:48 pm

[…] for algebraic rules for query optimization, relational algebra is known to be axiomatized into Relational Lattice which simplifies query transformations as demonstrated here and […]