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 mainly consider views and queries specified by Regular Path Queries (RPQ). 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. We say that 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 rewriting query can be evaluated in time polynomial in the size of V(D). Moreover this implies that it is decidable whether an RPQ query can be rewritten in Datalog using RPQ views.
Type de document :
Article dans une revue
Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2015, 11 (4)
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01248391
Contributeur : Luc Segoufin <>
Soumis le : vendredi 25 décembre 2015 - 22:13:43
Dernière modification le : mercredi 30 mai 2018 - 13:54:01

Fichier

views-rpq-datalog.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01248391, version 1

Citation

Nadime Francis, Luc Segoufin, Cristina Sirangelo. Datalog Rewritings of Regular Path Queries using Views. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2015, 11 (4). 〈hal-01248391〉

Partager

Métriques

Consultations de la notice

174

Téléchargements de fichiers

60