Abstract
Relational lattices are obtained by interpreting lattice connectives as natural join and inner union between database relations. Our study of their equational theory reveals that the variety generated by relational lattices has not been discussed in the existing literature. Furthermore, we show that addition of just the header constant to the lattice signature leads to undecidability of the quasiequational theory. Nevertheless, we also demonstrate that relational lattices 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 the structure of relational lattices via their standard contexts.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley (1995)
Codd, E.F.: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13, 377–387 (1970)
Craig, W.: Logic in Algebraic Form. Three Languages and Theories. Studies in Logic and the Foundations of Mathematics, p. 72. North Holland (1974)
Düntsch, I., Mikulás, S.: Cylindric structures and dependencies in relational databases. Theor. Comput. Sci. 269, 451–468 (2001)
Ganter, B., Wille, R.: Applied Lattice Theory: Formal Concept Analysis. In: Grätzer, G. (ed.) General Lattice Theory, 2nd edn., Birkhäuser (1996)
Gurevich, Y.: The word problem for certain classes of semigroups. Algebra and Logic 5, 25–35 (1966)
Gurevich, Y., Lewis, H.R.: The Word Problem for Cancellation Semigroups with Zero. The Journal of Symbolic Logic 49, 184–191 (1984)
Harrop, R.: On the existence of finite models and decision procedures for propositional calculi. Mathematical Proceedings of the Cambridge Philosophical Society 54, 1–13 (1958)
Hirsch, R., Hodkinson, I.: Relation Algebras by Games. Studies in Logic and the Foundations of Mathematics, vol. 147. Elsevier (2002)
Imieliński, T., Lipski, W.: The Relational Model of Data and Cylindric Algebras. J. Comput. Syst. Sci. 28, 80–102 (1984)
Jacobs, B.: Categorical Logic and Type Theory. Studies in Logic and the Foundations of Mathematics, vol. 141. North Holland, Amsterdam (1999)
Jipsen, P., Rose, H.: Varieties of Lattices. Lecture Notes in Mathematics, vol. 1533. Springer (1992)
Jipsen, P., Rose, H.: Varieties of Lattices. In: Grätzer, G. (ed.) General Lattice Theory, pp. 555–574. Birkhäuser (1998); Appendix F to the second edition
Maddux, R.: The Equational Theory of CA 3 is Undecidable. The Journal of Symbolic Logic 45, 311–316 (1980)
Maeda, S.: Locally Modular Lattices and Locally Distributive Lattices. Proceedings of the American Mathematical Society 44, 237–243 (1974)
McKenzie, R.: Equational bases and non-modular lattice varieties. Trans. Amer. Math. Soc. 174, 1–43 (1972)
Padmanabhan, R., McCune, W., Veroff, R.: Lattice Laws Forcing Distributivity Under Unique Complementation. Houston Journal of Mathematics 33, 391–401 (2007)
Post, E.L.: Recursive Unsolvability of a Problem of Thue. The Journal of Symbolic Logic 12, 1–11 (1947)
Spight, M., Tropashko, V.: First Steps in Relational Lattice (2006), http://arxiv.org/abs/cs/0603044
Stanley, R.P.: Supersolvable lattices. Algebra Universalis 2, 197–217 (1972)
Stern, M.: Semimodular Lattices. Encyclopedia of Mathematics and its Applications, vol. 73. Cambridge University Press (1999)
Tropashko, V.: The website of QBQL: Prototype of relational lattice system, https://code.google.com/p/qbql/
Tropashko, V.: Relational Algebra as non-Distributive Lattice (2005), http://arxiv.org/abs/cs/0501053
Van den Bussche, J., Van Gucht, D., Vansummeren, S.: A crash course on database queries. In: PODS 2007: Proceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 143–154. ACM, New York (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Litak, T., Mikulás, S., Hidders, J. (2014). Relational Lattices. In: Höfner, P., Jipsen, P., Kahl, W., Müller, M.E. (eds) Relational and Algebraic Methods in Computer Science. RAMICS 2014. Lecture Notes in Computer Science, vol 8428. Springer, Cham. https://doi.org/10.1007/978-3-319-06251-8_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-06251-8_20
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06250-1
Online ISBN: 978-3-319-06251-8
eBook Packages: Computer ScienceComputer Science (R0)