Document Open Access Logo

Boundedness of Conjunctive Regular Path Queries (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors Pablo Barceló , Diego Figueira, Miguel Romero

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.104.pdf
  • Filesize: 0.57 MB
  • 15 pages

Document Identifiers

Author Details

Pablo Barceló
  • Department of Computer Science, University of Chile, Santiago, Chile
  • IMFD, Santiago, Chile
Diego Figueira
  • CNRS & LaBRI, Talence, France
Miguel Romero
  • Department of Computer Science, University of Oxford, Oxford, UK

Funding

Barceló is funded by the Millennium Inst. for Foundational Research on Data and Fondecyt 1170109, and Figueira by ANR project DELTA (grant ANR-16-CE40-0007) and ANR project QUID (grant ANR-18-CE40-0031). This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors' views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein.

Acknowledgements

We are grateful to Thomas Colcombet for helpful discussions and valuable ideas in relation to the results of Section \ref{sec:distance}.

Cite AsGet BibTex

Pablo Barceló, Diego Figueira, and Miguel Romero. Boundedness of Conjunctive Regular Path Queries (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 104:1-104:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.104

Abstract

We study the boundedness problem for unions of conjunctive regular path queries with inverses (UC2RPQs). This is the problem of, given a UC2RPQ, checking whether it is equivalent to a union of conjunctive queries (UCQ). We show the problem to be ExpSpace-complete, thus coinciding with the complexity of containment for UC2RPQs. As a corollary, when a UC2RPQ is bounded, it is equivalent to a UCQ of at most triple-exponential size, and in fact we show that this bound is optimal. We also study better behaved classes of UC2RPQs, namely acyclic UC2RPQs of bounded thickness, and strongly connected UCRPQs, whose boundedness problem is, respectively, PSpace-complete and Pi_2^P-complete. Most upper bounds exploit results on limitedness for distance automata, in particular extending the model with alternation and two-wayness, which may be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Database query languages (principles)
  • Theory of computation → Quantitative automata
Keywords
  • regular path queries
  • boundedness
  • limitedness
  • distance automata

Metrics

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

Related Versions

References

  1. Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan L. Reutter, and Domagoj Vrgoč. Foundations of Modern Query Languages for Graph Databases. ACM Computing Surveys, 50(5):68:1-68:40, 2017. Google Scholar
  2. Pablo Barceló. Querying graph databases. In ACM Symposium on Principles of Database Systems (PODS), pages 175-188, 2013. Google Scholar
  3. Pablo Barceló, Gerald Berger, Carsten Lutz, and Andreas Pieris. First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries. In International Joint Conference on Artificial Intelligence (IJCAI), pages 1707-1713, 2018. Google Scholar
  4. Pablo Barceló, Miguel Romero, and Moshe Y. Vardi. Does Query Evaluation Tractability Help Query Containment? In ACM Symposium on Principles of Database Systems (PODS), pages 188-199, 2014. Google Scholar
  5. Pablo Barceló, Miguel Romero, and Moshe Y. Vardi. Semantic Acyclicity on Graph Databases. SIAM Journal on computing, 45(4):1339-1376, 2016. Google Scholar
  6. Michael Benedikt, Pierre Bourhis, and Michael Vanden Boom. A Step Up in Expressiveness of Decidable Fixpoint Logics. In Annual IEEE Symposium on Logic in Computer Science (LICS), pages 817-826, 2016. Google Scholar
  7. Michael Benedikt, Balder ten Cate, Thomas Colcombet, and Michael Vanden Boom. The Complexity of Boundedness for Guarded Logics. In Annual IEEE Symposium on Logic in Computer Science (LICS), pages 293-304. IEEE Computer Society Press, 2015. URL: http://dx.doi.org/10.1109/LICS.2015.36.
  8. Meghyn Bienvenu, Peter Hansen, Carsten Lutz, and Frank Wolter. First Order-Rewritability and Containment of Conjunctive Queries in Horn Description Logics. In International Joint Conference on Artificial Intelligence (IJCAI), pages 965-971, 2016. Google Scholar
  9. Jean-Camille Birget. State-complexity of finite-state devices, state compressibility and incompressibility. Mathematical systems theory, 26(3):237-269, 1993. Google Scholar
  10. Achim Blumensath, Thomas Colcombet, Denis Kuperberg, Pawel Parys, and Michael Vanden Boom. Two-way cost automata and cost logics over infinite trees. In Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS '14, pages 16:1-16:9. ACM Press, 2014. URL: http://dx.doi.org/10.1145/2603088.2603104.
  11. Achim Blumensath, Martin Otto, and Mark Weyer. Decidability Results for the Boundedness Problem. Logical Methods in Computer Science (LMCS), 10(3), 2014. Google Scholar
  12. Mikołaj Bojańczyk and Szymon Toruńczyk. Deterministic Automata and Extensions of Weak MSO. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), volume 4 of Leibniz International Proceedings in Informatics (LIPIcs), pages 73-84. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2308.
  13. Angela Bonifati, Wim Martens, and Thomas Timm. An Analytical Study of Large SPARQL Query Logs. PVLDB, 11(2):149-161, 2017. Google Scholar
  14. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. Containment of Conjunctive Regular Path Queries with Inverse. In Principles of Knowledge Representation and Reasoning (KR), pages 176-185, 2000. Google Scholar
  15. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. Rewriting of Regular Expressions and Regular Path Queries. Journal of Computer and System Sciences (JCSS), 64(3):443-465, 2002. Google Scholar
  16. Ashok K. Chandra and Philip M. Merlin. Optimal Implementation of Conjunctive Queries in Relational Data Bases. In Symposium on Theory of Computing (STOC), pages 77-90, 1977. Google Scholar
  17. Thomas Colcombet. The Theory of Stabilisation Monoids and Regular Cost Functions. In International Colloquium on Automata, Languages and Programming (ICALP), volume 5556 of Lecture Notes in Computer Science, pages 139-150. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-02930-1_12.
  18. Thomas Colcombet and Christof Löding. The Nesting-Depth of Disjunctive μ-Calculus for Tree Languages and the Limitedness Problem. In EACSL Annual Conference on Computer Science Logic (CSL), pages 416-430, 2008. Google Scholar
  19. Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, and Moshe Y. Vardi. Decidable Optimization Problems for Database Logic Programs (Preliminary Report). In Symposium on Theory of Computing (STOC), pages 477-490, 1988. Google Scholar
  20. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  21. Manfred Droste, Werner Kuich, and Heiko Vogler. Handbook of weighted automata. Springer Science &Business Media, 2009. Google Scholar
  22. Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, and Moshe Y. Vardi. Undecidable Optimization Problems for Database Logic Programs. J. ACM, 40(3):683-713, 1993. Google Scholar
  23. Peter Hansen, Carsten Lutz, Inanç Seylan, and Frank Wolter. Efficient Query Rewriting in the Description Logic EL and Beyond. In International Joint Conference on Artificial Intelligence (IJCAI), pages 3034-3040, 2015. Google Scholar
  24. Kosaburo Hashiguchi. Limitedness theorem on finite automata with distance functions. Journal of Computer and System Sciences (JCSS), 24(2):233-244, 1982. Google Scholar
  25. Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, and Moshe Y. Vardi. Tools for Datalog Boundedness. In ACM Symposium on Principles of Database Systems (PODS), pages 1-12, 1991. Google Scholar
  26. Daniel Kirsten. Distance desert automata and the star height problem. Informatique Théorique et Applications (ITA), 39(3):455-509, 2005. Google Scholar
  27. Dexter Kozen. Lower Bounds for Natural Proof Systems. In Annual Symposium on Foundations of Computer Science (FOCS), pages 254-266, 1977. Google Scholar
  28. Hing Leung. Limitedness Theorem on Finite Automata with Distance Functions: An Algebraic Proof. Theoretical Computer Science (TCS), 81(1):137-145, 1991. URL: http://dx.doi.org/10.1016/0304-3975(91)90321-R.
  29. Hing Leung and Viktor Podolskiy. The limitedness problem on distance automata: Hashiguchi’s method revisited. Theoretical Computer Science (TCS), 310(1-3):147-158, 2004. URL: http://dx.doi.org/10.1016/S0304-3975(03)00377-3.
  30. Wim Martens and Tina Trautner. Evaluation and Enumeration Problems for Regular Path Queries. In International Conference on Database Theory (ICDT), pages 19:1-19:21, 2018. Google Scholar
  31. Jeffrey F. Naughton. Data Independent Recursion in Deductive Databases. Journal of Computer and System Sciences (JCSS), 38(2):259-289, 1989. Google Scholar
  32. Nir Piterman and Moshe Y. Vardi. From bidirectionality to alternation. Theoretical Computer Science (TCS), 295:295-321, 2003. URL: http://dx.doi.org/10.1016/S0304-3975(02)00410-3.
  33. Juan L. Reutter, Miguel Romero, and Moshe Y. Vardi. Regular Queries on Graph Databases. Theoretical Computer Science (TCS), 61(1):31-83, 2017. Google Scholar
  34. John C. Shepherdson. The reduction of two-way automata to one-way automata. IBM Journal of Research and Development, 3(2):198-200, 1959. Google Scholar
  35. Michael Vanden Boom. Weak Cost Monadic Logic over Infinite Trees. In International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 580-591, 2011. Google Scholar
  36. Michael Vanden Boom. Weak cost automata over infinite trees. PhD thesis, University of Oxford, UK, 2012. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact