Datalog Rewritings of Regular Path Queries using Views

Nadime Francis, Luc Segoufin, Cristina Sirangelo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationProceedings of the 17th International Conference on Database Theory (ICDT'14)
EditorsNicole Schweikardt, Vassilis Christophides, Vincent Leroy
Place of PublicationAthens, Greece
Pages107-118
Number of pages12
DOIs
Publication statusPublished - 1 Mar 2014

Fingerprint

Dive into the research topics of 'Datalog Rewritings of Regular Path Queries using Views'. Together they form a unique fingerprint.

Cite this