Asymptotic Determinacy of Path Queries using Union-of-Paths Views

Nadime Francis 1
1 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : We consider the view determinacy problem over graph databases for queries defined as (possibly infinite) unions of path queries. These queries select pairs of nodes in a graph that are connected through a path whose length falls in a given set. A view specification is a set of such queries. We say that a view specification V determines a query Q if, for all databases D, the answers to V on D contain enough information to answer Q. Our main result states that, given a view V, there exists an explicit bound that depends on V such that we can decide the determinacy problem for all queries that ask for a path longer than this bound, and provide first-order rewritings for the queries that are determined. We call this notion asymptotic determinacy. As a corollary, we can also compute the set of almost all path queries that are determined by V.
Type de document :
Communication dans un congrès
18th International Conference on Database Theory (ICDT 2015), Mar 2015, Brussels, Belgium. 2015, 〈http://edbticdt2015.be/〉. 〈10.4230/LIPIcs.ICDT.2015.44〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01150780
Contributeur : Nadime Francis <>
Soumis le : lundi 11 mai 2015 - 19:19:36
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : mercredi 19 avril 2017 - 21:55:39

Fichier

3.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

Citation

Nadime Francis. Asymptotic Determinacy of Path Queries using Union-of-Paths Views. 18th International Conference on Database Theory (ICDT 2015), Mar 2015, Brussels, Belgium. 2015, 〈http://edbticdt2015.be/〉. 〈10.4230/LIPIcs.ICDT.2015.44〉. 〈hal-01150780〉

Partager

Métriques

Consultations de la notice

117

Téléchargements de fichiers

68