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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01070903
Contributor : Luc Segoufin <>
Submitted on : Thursday, October 2, 2014 - 4:20:49 PM
Last modification on : Tuesday, February 5, 2019 - 1:46:02 PM

Identifiers

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, ⟨10.5441/002/icdt.2014.14⟩. ⟨hal-01070903⟩

Share

Metrics

Record views

166