Francis, Nadime and Segoufin, Luc and Sirangelo, Cristina - Datalog Rewritings of Regular Path Queries using Views

lmcs:1615 - Logical Methods in Computer Science, December 22, 2015, Volume 11, Issue 4
Datalog Rewritings of Regular Path Queries using Views

Authors: Francis, Nadime and Segoufin, Luc and Sirangelo, Cristina

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.


Source : oai:arXiv.org:1511.00938
DOI : 10.2168/LMCS-11(4:14)2015
Volume: Volume 11, Issue 4
Published on: December 22, 2015
Submitted on: December 23, 2014
Keywords: Computer Science - Databases


Share

Consultation statistics

This page has been seen 147 times.
This article's PDF has been downloaded 86 times.