Relational lattices

• Tadeusz Litak
• Department Informatik, Technische Fakultät, FAU Erlangen-Nürnberg, Germany

We study an interpretation of lattice connectives as natural join and
inner union between database relations with non-uniform headers. We
show that this interpretation proposed by database experts (Vadim
Tropashko from Oracle) yields a class of lattices which has not been
considered in the existing lattice-theoretical literature. We discuss
axiomatizability and decidability of their (quasi-)equational theory
and propose an equational axiomatization for a corresponding abstract
algebraic class. It turns out that addition of just the “header
constant” to the lattice signature already allows mimicking the Maddux
technique for cylindric algebras and encode the word problem for
semigroups in the quasiequational theory. Relational lattices,
however, are not as intangible as one may fear: for example, they do
form a pseudoelementary class. We also apply the tools of Formal
Concept Analysis and investigate standard contexts of relational
lattices, obtaining, e.g., results on their subdirect irreducibility.

This is a joint work with Szabolcs Mikulas and Jan Hidders