THE QUASIEQUATIONAL THEORY OF RELATIONAL LATTICES, IN THE PURE LATTICE SIGNATURE

Luigi Santocanale (1)

1 LIF - Laboratoire d'informatique Fondamentale de Marseille

The natural join and the inner union operations combine relations in a database. Tropashko and Spight realized that these two operations are the meet and join operations in a class of lattices, known by now as the relational lattices. They proposed then lattice theory as an algebraic approach, alternative to the relational algebra, to the theory of databases. Litak et al. proposed an axiomatization in the signature extending the pure lattice signature with the header constant. They argued then that the quasiequational theory of relational lattices is undecidable in this extended signature. We refine this result by showing that the quasiequational theory of relational lattices in the pure lattice signature is undecidable as well. We obtain this result as a consequence of the following statement: it is undecidable whether a finite subdirectly-irreducible lattice can be embedded into a relational lattice. Our proof of this statement is a reduction from a similar problem for relation algebras and from the coverability problem of a frame by a universal product frame. As corollaries, we also obtain the following results: the quasiequational theory of relational lattices has no finite base; there is a quasiequation which holds in all the finite lattices but fails in an infinite relational lattice.

Mots clés: inner union; natural join; relational lattice; undecidability; generalized ultrametric space; universal product frame

Domaines: Logique en informatique [cs.LO]; Logique [math.LO]; Base de données [cs.DB]; Catégories et ensembles [math.CT]

Luigi Santocanale. THE QUASIEQUATIONAL THEORY OF RELATIONAL LATTICES, IN THE PURE LATTICE SIGNATURE. 2016. ⟨hal-01344299v1⟩