The relational model and skew lattices, Part II

In our previous post we established a connection between skew lattices and the relational model in data science. It is thus time to answer the following question: What exactly are skew lattices?

A skew lattice is a set S equipped with a pair of binary operations ∧ (meet) and ∨ (join) such that given any x, y, z in S the following identities hold:

x ∧ x = x    idempotency of meet

x ∨ x = x    idempotency of join

(x ∧ y) ∧ z = x ∧ (y ∧ z)    associativity of meet

(x ∨ y) ∨ z = x ∨ (y ∨ z)    associativity of join

x ∧ (x ∨ y) = x = x ∨ (x ∧ y)    absorption

(x ∧ y) ∨ y = y = (x ∨ y) ∧ y    absorption

Noncommutative (in the inclusive sense as in "not necessarily commutative") lattices were first introduced by a German physicist Pascual Jordan in 1949, however the modern theory of skew lattices is due to the extensive study developed mainly by Jonathan Leech and initiated in the paper:

J. Leech, Skew lattices in rings, Algebra Universalis 26 (1989), 48--72. 

The reader might be interested in Jordan's  at the time classified report on noncommutative lattices prepared for the Armed Services Technical Information Agency, which is now unclassified and can be found here. 

A reader familiar with the lattice theory will notice that if we add to the above list of axioms the following pair of commutativity axioms, we obtain exactly the definition of a lattice:

x ∧ y = y ∧ x    commutativity of meet

x ∨ y = y ∨ z   commutativity of join

Lattices are thus special cases of skew lattices. 

Skew lattices abound throughout mathematics. For example, we encounter them in rings (for instance, in rings of matrices) or even as sheaves over certain topological spaces. Probably the most intuitive is the following example obtained by Leech in:

J. Leech, Normal skew lattices, Semigroup Forum 44 (1992), 1--8. 

Given nonempty sets A and B let P(A, B) denote the set of all partial functions from A to B, i.e. all  functions f: X → B, with the domain X being a subset of A. Then P(A, B) is a skew lattice for the operations defined by:

f ∨ g = f ∪ g | _{G - F}                                     (1)

f ∧ g =  g | _{F ∩ G}                                         (2)

where F = dom(f) and G = dom(g). The join operation defined by (1) above is ofter referred to as override, and the meet operation defined by (2) is referred to as restriction.

A subalgebra of P(A, B) (i.e. a subset that is closed under the operations ∧ and ∨) is called a ring of partial functions. 

Green's relation D is defined on a skew lattice S by:

a D b iff a ∧ b ∧ a = a and b ∧ a ∧ b = b (or, equivalently, a ∨ b ∨ a = a and b ∨ a ∨ b = b)

Relation D is an equivalence relation. Moreover, it is a congruence, which means that the factor set S/D is a skew lattice for the induced operations. By Leech's First Decomposition Theorem, S/D is a (commutative) lattice, the maximal lattice image of S. In the case of a ring of partial functions, relation D simplifies to 

a D b iff dom(f) = dom(g).

I have worked with skew lattices throughout my academic career. It is thus understandable that when I first encountered the relational model (RM) some eight months ago, its structure (the tables of records that can be understood as partial functions) as well as the fact that the concept of join(s) occurs in RM immediately captured my attention. 

Stijn Vansummeren was the first person that I began explaining the connection to. He listened to me stating the definition and basic concepts of the skew lattice theory, but he was not convinced. He shook his head. "I'm not sure that this is related," he said. "You see, the joins in the relational model are always commutative." 

I thought for a moment and then I realized where the confusion was arising from. "Yes," I replied. "But that's because you only study the joins of full tables, not of individual records. Joins of full tables are commutative in our case, too. However, we also consider joins of elements (records) because they are naturally there."

Let's see what is going on here. The following pairs of concepts are analogous:

 

Skew lattices	Relational model
element	record
D-class	table

Given partial functions f and g, their join is defined by equation (1) above and is not commutative in general, i.e. f ∨ g = g ∨ f  need not hold. However, the join of the D-classes that f and g belong to is the set of all partial functions with the domain being the union of the two domains. Since set union is a commutative operation, so is the join of D-classes.

Actually, more is true. The following result was proven by Leech in his 1989 paper mentioned above.

Theorem (Leech, 1989). Let S be a skew lattice and let A and B be D-classes in S with join class J and meet class M. Then:

J = {a ∨ b | a ∈ A, b ∈  B and a ∨ b = b ∨ a}

and

M = {a ∧ b | a ∈ A, b ∈  B and a ∧ b = b ∧ a}.

Interesting, right? It means that although skew lattices are in general inherently noncommutative, all (noncommutative) joins and meets within a skew lattice could just as easily be achieved as commutative joins and meets of possibly other elements.

For example, given partial functions

f : a ↦ 0, b ↦ 0

g : a ↦ 1, c ↦ 1

their joins are 

f ∨ g : a ↦ 0, b ↦ 0, c ↦ 1

g ∨ f : a ↦ 1, b ↦ 0, c ↦ 1

However, taking

f : a ↦ 0, b ↦ 0

g' : a ↦ 0, c ↦ 1

we would obtain 

f ∨ g' : a ↦ 0, b ↦ 0, c ↦ 1

g' ∨ f : a ↦ 0, b ↦ 0, c ↦ 1

which means that the function f ∨g can be obtained as a join of commuting functions f and g'.

There is of course much more structure to both skew lattices and the relational model than explored above. More can therefore be said about the connection between both concepts.