Datalog Rewritings of Regular Path Queries using Views

Nadime Francis 1 Luc Segoufin 1 Cristina Sirangelo 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 query answering using views on graph databases, i.e. databases structured as edge-labeled graphs. We consider views and queries specified by Regular Path Queries. These are queries selecting pairs of nodes in a graph database that are connected via a path whose sequence of edge labels belongs to some regular language. A view V determines a query Q if for all graph databases D, the view image V(D) always contains enough information to answer Q on D. In other words, there is a well defined function from V(D) to Q(D). Our main result shows that when this function is monotone, there exists a rewriting of Q as a Datalog query over the view instance V(D). In particular the query can be evaluated in time polynomial in the size of V(D). As a side result we also prove that it is decidable whether an RPQ query can be rewritten in Datalog using RPQ views.
Type de document :
Communication dans un congrès
Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014., Mar 2014, Athens, Greece. pp.107--118, 2014, 〈10.5441/002/icdt.2014.14〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01070903
Contributeur : Luc Segoufin <>
Soumis le : jeudi 2 octobre 2014 - 16:20:49
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14

Identifiants

Collections

Citation

Nadime Francis, Luc Segoufin, Cristina Sirangelo. Datalog Rewritings of Regular Path Queries using Views. Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014., Mar 2014, Athens, Greece. pp.107--118, 2014, 〈10.5441/002/icdt.2014.14〉. 〈hal-01070903〉

Partager

Métriques

Consultations de la notice

98