Datalog Rewritings of Regular Path Queries using Views

DOI10.2168/LMCS-11(4:14)2015MaRDI QIDQ3460416zbMATH OpenOpenAlexFDO

Authors Nadime Francis, Luc Segoufin, Cristina Sirangelo

Publication date 7 January 2016

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.00938

zbMATH Keywords

Datalogregular path queriesrewritingviews

Mathematics Subject Classification ID

Database theory (68P15)

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.

Recommendations

• A Top-Down Approach to Rewriting Conjunctive Queries Using Views
• Logical queries over views, decidability and expressiveness
• Determinacy and query rewriting for conjunctive queries and views
• scientific article; zbMATH DE number 2086266
• Bounded regular path queries in view-based data integration
• Bounded query rewriting using views

Cited in

(8)

• Asymptotic determinacy of path queries using union-of-paths views
• scientific article; zbMATH DE number 1735826 (Why is no real title available?)
• Certified Graph View Maintenance with Regular Datalog
• Database Theory - ICDT 2005
• scientific article; zbMATH DE number 2241908 (Why is no real title available?)
• Asymptotic determinacy of path queries using union-of-paths views
• On Monotonic Determinacy and Rewritability for Recursive Queries and Views
• Determinacy and rewriting of functional top-down and MSO tree transformations

Describes a project that uses

Uses Software

• Datalog

This page was built for publication: Datalog Rewritings of Regular Path Queries using Views

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460416)