Asymptotic Determinacy of Path Queries using Union-of-Paths Views

Author Nadime Francis



PDF
Thumbnail PDF

File

LIPIcs.ICDT.2015.44.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Nadime Francis

Cite AsGet BibTex

Nadime Francis. Asymptotic Determinacy of Path Queries using Union-of-Paths Views. In 18th International Conference on Database Theory (ICDT 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 31, pp. 44-59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.ICDT.2015.44

Abstract

We consider the view determinacy problem over graph databases for queries defined as (possibly infinite) unions of path queries. These queries select pairs of nodes in a graph that are connected through a path whose length falls in a given set. A view specification is a set of such queries. We say that a view specification V determines a query Q if, for all databases D, the answers to V on D contain enough information to answer Q. Our main result states that, given a view V, there exists an explicit bound that depends on V such that we can decide the determinacy problem for all queries that ask for a path longer than this bound, and provide first-order rewritings for the queries that are determined. We call this notion asymptotic determinacy. As a corollary, we can also compute the set of almost all path queries that are determined by V.
Keywords
  • Graph databases
  • Views
  • Determinacy
  • Rewriting
  • Path queries

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Serge Abiteboul and Oliver M. Duschka. Complexity of answering queries using materialized views. In ACM Symp. on Principles of Database Systems (PODS), pages 254-263, 1998. Google Scholar
  2. Foto N. Afrati. Determinacy and query rewriting for conjunctive queries and views. Theoretical Computer Science, 412(11):1005-1021, 2011. Google Scholar
  3. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. Lossless regular views. In ACM Symp. on Principles of Database Systems (PODS), pages 247-258. ACM, 2002. Google Scholar
  4. Nadime Francis, Luc Segoufin, and Cristina Sirangelo. Datalog rewritings of regular path queries using views. In Proceedings of the 17th International Conference on Database Theory (ICDT'14), pages 107-118, 2014. Google Scholar
  5. Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, and Divesh Srivastava. Answering queries using views. In ACM Symp. on Principles of Database Systems (PODS), pages 95-104, 1995. Google Scholar
  6. Alan Nash, Luc Segoufin, and Victor Vianu. Views and queries: Determinacy and rewriting. ACM Transactions on Database Systems, 35(3), 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail