Relational Lattices via Duality

Abstract : 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 A to D, with the P(A)-valued distance being the Hamming one but lifted to subsets of A. 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.
Type de document :
Communication dans un congrès
Ichiro Hasuo. 13th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2016, Eindhoven, Netherlands. Lecture Notes in Computer Science, LNCS-9608, pp.195-215, 2016, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-319-40370-0_12〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01446027
Contributeur : Hal Ifip <>
Soumis le : mercredi 25 janvier 2017 - 15:24:14
Dernière modification le : lundi 13 février 2017 - 17:52:35
Document(s) archivé(s) le : mercredi 26 avril 2017 - 16:02:11

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Luigi Santocanale. Relational Lattices via Duality. Ichiro Hasuo. 13th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2016, Eindhoven, Netherlands. Lecture Notes in Computer Science, LNCS-9608, pp.195-215, 2016, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-319-40370-0_12〉. 〈hal-01446027〉

Partager

Métriques

Consultations de la notice

97