%0 Conference Proceedings
%T Relational Lattices via Duality
%+ Aix Marseille Université (AMU)
%A Santocanale, Luigi
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 13th International Workshop on Coalgebraic Methods in Computer Science (CMCS)
%C Eindhoven, Netherlands
%Y Ichiro Hasuo
%3 Coalgebraic Methods in Computer Science
%V LNCS-9608
%P 195-215
%8 2016-04-02
%D 2016
%R 10.1007/978-3-319-40370-0_12
%Z Computer Science [cs]Conference papers
%X The natural join and the inner union combine in different ways tables of a relational database. Tropashko [18] observed that these two operations are the meet and join in a class of lattices—called the relational lattices—and proposed lattice theory as an alternative algebraic approach to databases. Aiming at query optimization, Litak et al. [12] initiated the study of the equational theory of these lattices. We carry on with this project, making use of the duality theory developed in [16]. The contributions of this paper are as follows. Let A be a set of column’s names and D be a set of cell values; we characterize the dual space of the relational lattice $\mathsf {R}(D,A)$ by means of a generalized ultrametric space, whose elements are the functions from <i>A</i> to <i>D</i>, with the <i>P</i>(<i>A</i>)-valued distance being the Hamming one but lifted to subsets of <i>A</i>. We use the dual space to present an equational axiomatization of these lattices that reflects the combinatorial properties of these generalized ultrametric spaces: symmetry and pairwise completeness. Finally, we argue that these equations correspond to combinatorial properties of the dual spaces of lattices, in a technical sense analogous of correspondence theory in modal logic. In particular, this leads to an exact characterization of the finite lattices satisfying these equations.
%G English
%Z TC 1
%Z WG 1.3
%2 https://inria.hal.science/hal-01446027/document
%2 https://inria.hal.science/hal-01446027/file/418352_1_En_12_Chapter.pdf
%L hal-01446027
%U https://inria.hal.science/hal-01446027
%~ UNIV-AMU
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-LNCS-9608
%~ IFIP-WG1-3
%~ IFIP-CMCS