Embeddability into relational lattices is undecidable - Laboratoire d'Informatique et Systèmes Accéder directement au contenu
Article Dans Une Revue Journal of Logical and Algebraic Methods in Programming Année : 2018

Embeddability into relational lattices is undecidable

Résumé

The natural join and the inner union operations combine relations of 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 to the theory of databases alternative to the relational algebra. Litak et al. proposed an axiomatization of relational lattices over the signature that extends the pure lattice signature with a constant and argued that the quasiequational theory of relational lattices over this extended signature is undecidable. We prove in this paper that embeddability is undecidable for relational lattices. More precisely, it is undecidable whether a finite subdirectly-irreducible lattice can be embedded into a relational lattice. Our proof is a reduction from the coverability problem of a multimodal frame by a universal product frame and, indirectly, from the representability problem for relation algebras. As corollaries we obtain the following results: the quasiequational theory of relational lattices over the pure lattice signature is undecidable and has no finite base; there is a quasiequation over the pure lattice signature which holds in all the finite relational lattices but fails in an infinite relational lattice.
Fichier principal
Vignette du fichier
0.pdf (326.86 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01344299 , version 1 (11-07-2016)
hal-01344299 , version 2 (21-07-2016)
hal-01344299 , version 3 (08-03-2017)

Licence

Copyright (Tous droits réservés)

Identifiants

Citer

Luigi Santocanale. Embeddability into relational lattices is undecidable. Journal of Logical and Algebraic Methods in Programming, 2018, 97, pp.131-148. ⟨10.1016/j.jlamp.2018.03.001⟩. ⟨hal-01344299v3⟩
343 Consultations
223 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More