Document Open Access Logo

Fine-Grained Complexity of Regular Path Queries

Authors Katrin Casel , Markus L. Schmid

PDF
Thumbnail PDF

File

LIPIcs.ICDT.2021.19.pdf
  • Filesize: 0.92 MB
  • 20 pages

Document Identifiers

Author Details

Katrin Casel
  • Hasso Plattner Institute, Universität Potsdam, Germany
Markus L. Schmid
  • Humboldt-Universität zu Berlin, Germany

Funding

  • Casel, Katrin: Supported by the Federal Ministry of Education and Research of Germany (BMBF) in the KI-LAB-ITSE framework - project number 01IS19066.
  • Schmid, Markus L.: Supported by the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG) - project number 416776735 (gefördert durch die Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 416776735).

Acknowledgements

We wish to thank the anonymous reviewers for their valuable feedback. In particular, following the reviewer’s comments and suggestions, we have included more background information and comprehensive explanations of certain aspects, which substantially improved the overall exposition of this paper.

Cite AsGet BibTex

Katrin Casel and Markus L. Schmid. Fine-Grained Complexity of Regular Path Queries. In 24th International Conference on Database Theory (ICDT 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 186, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICDT.2021.19

Abstract

A regular path query (RPQ) is a regular expression q that returns all node pairs (u, v) from a graph database that are connected by an arbitrary path labelled with a word from L(q). The obvious algorithmic approach to RPQ evaluation (called PG-approach), i. e., constructing the product graph between an NFA for q and the graph database, is appealing due to its simplicity and also leads to efficient algorithms. However, it is unclear whether the PG-approach is optimal. We address this question by thoroughly investigating which upper complexity bounds can be achieved by the PG-approach, and we complement these with conditional lower bounds (in the sense of the fine-grained complexity framework). A special focus is put on enumeration and delay bounds, as well as the data complexity perspective. A main insight is that we can achieve optimal (or near optimal) algorithms with the PG-approach, but the delay for enumeration is rather high (linear in the database). We explore three successful approaches towards enumeration with sub-linear delay: super-linear preprocessing, approximations of the solution sets, and restricted classes of RPQs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Regular languages
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Database query languages (principles)
  • Theory of computation → Data structures and algorithms for data management
Keywords
  • Graph Databases
  • Regular Path Queries
  • Enumeration
  • Fine-Grained Complexity

Metrics

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

Related Versions

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is valiant’s parser. SIAM J. Comput., 47(6):2527-2555, 2018. URL: https://doi.org/10.1137/16M1061771.
  2. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434-443, 2014. URL: https://doi.org/10.1109/FOCS.2014.53.
  3. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. SIAM J. Comput., 47(3):1098-1122, 2018. URL: https://doi.org/10.1137/15M1050987.
  4. Rasmus Resen Amossen and Rasmus Pagh. Faster join-projects and sparse matrix multiplications. In Database Theory - ICDT 2009, 12th International Conference, St. Petersburg, Russia, March 23-25, 2009, Proceedings, pages 121-126, 2009. URL: https://doi.org/10.1145/1514894.1514909.
  5. Renzo Angles, Marcelo Arenas, Pablo Barceló, Aidan Hogan, Juan L. Reutter, and Domagoj Vrgoc. Foundations of modern query languages for graph databases. ACM Comput. Surv., 50(5):68:1-68:40, 2017. URL: https://doi.org/10.1145/3104031.
  6. Arturs Backurs and Piotr Indyk. Which regular expression patterns are hard to match? In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 457-466, 2016. URL: https://doi.org/10.1109/FOCS.2016.56.
  7. Guillaume Bagan, Angela Bonifati, and Benoît Groz. A trichotomy for regular simple path queries on graphs. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA - June 22 - 27, 2013, pages 261-272, 2013. Google Scholar
  8. Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On acyclic conjunctive queries and constant delay enumeration. In Computer Science Logic, 21st International Workshop, CSL 2007, 16th Annual Conference of the EACSL, Lausanne, Switzerland, September 11-15, 2007, Proceedings, pages 208-222, 2007. Google Scholar
  9. Jean-François Baget, Meghyn Bienvenu, Marie-Laure Mugnier, and Michaël Thomazo. Answering conjunctive regular path queries over guarded existential rules. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pages 793-799, 2017. URL: https://doi.org/10.24963/ijcai.2017/110.
  10. Pablo Barceló. Querying graph databases. In Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2013, New York, NY, USA - June 22 - 27, 2013, pages 175-188, 2013. Google Scholar
  11. Pablo Barceló, Diego Figueira, and Miguel Romero. Boundedness of conjunctive regular path queries. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 104:1-104:15, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.104.
  12. Pablo Barceló, Leonid Libkin, Anthony Widjaja Lin, and Peter T. Wood. Expressive languages for path queries over graph-structured data. ACM Transactions on Database Systems (TODS), 37(4):31:1-31:46, 2012. Google Scholar
  13. Christoph Berkholz, Fabian Gerhardt, and Nicole Schweikardt. Constant delay enumeration for conjunctive queries: a tutorial. ACM SIGLOG News, 7(1):4-33, 2020. URL: https://doi.org/10.1145/3385634.3385636.
  14. Christoph Berkholz, Jens Keppeler, and Nicole Schweikardt. Answering conjunctive queries under updates. In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 303-318, 2017. Google Scholar
  15. Meghyn Bienvenu, Magdalena Ortiz, and Mantas Simkus. Regular path queries in lightweight description logics: Complexity and algorithms. J. Artif. Intell. Res., 53:315-374, 2015. URL: https://doi.org/10.1613/jair.4577.
  16. Meghyn Bienvenu and Michaël Thomazo. On the complexity of evaluating regular path queries over linear existential rules. In Web Reasoning and Rule Systems - 10th International Conference, RR 2016, Aberdeen, UK, September 9-11, 2016, Proceedings, pages 1-17, 2016. URL: https://doi.org/10.1007/978-3-319-45276-0_1.
  17. Angela Bonifati, Wim Martens, and Thomas Timm. An analytical study of large SPARQL query logs. PVLDB, 11(2):149-161, 2017. Google Scholar
  18. Angela Bonifati, Wim Martens, and Thomas Timm. Navigating the maze of wikidata query logs. In The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, pages 127-138, 2019. URL: https://doi.org/10.1145/3308558.3313472.
  19. Angela Bonifati, Wim Martens, and Thomas Timm. An analytical study of large SPARQL query logs. VLDB J., 29(2-3):655-679, 2020. URL: https://doi.org/10.1007/s00778-019-00558-9.
  20. Johann Brault-Baron. De la pertinence de l'énumération : complexité en logiques propositionnelle et du premier ordre. (The relevance of the list: propositional logic and complexity of the first order). PhD thesis, University of Caen Normandy, France, 2013. URL: https://tel.archives-ouvertes.fr/tel-01081392.
  21. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 661-670, 2014. URL: https://doi.org/10.1109/FOCS.2014.76.
  22. Karl Bringmann. Fine-grained complexity theory (tutorial). In 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany, pages 4:1-4:7, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.4.
  23. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi. Reasoning on regular path queries. SIGMOD Record, 32(4):83-92, 2003. Google Scholar
  24. Katrin Casel, Tobias Friedrich, Stefan Neubert, and Markus L. Schmid. Shortest distances as enumeration problem. CoRR, abs/2005.06827, 2020. URL: http://arxiv.org/abs/2005.06827.
  25. Katrin Casel and Markus L. Schmid. Fine-grained complexity of regular path queries. CoRR, abs/2101.01945, 2021. URL: http://arxiv.org/abs/2101.01945.
  26. Isabel F. Cruz, Alberto O. Mendelzon, and Peter T. Wood. A graphical query language supporting recursion. In Proceedings of the Association for Computing Machinery Special Interest Group on Management of Data 1987 Annual Conference, San Francisco, California, May 27-29, 1987, pages 323-330, 1987. Google Scholar
  27. Diego Figueira. Containment of UC2RPQ: the hard and easy cases. In 23rd International Conference on Database Theory, ICDT 2020, March 30-April 2, 2020, Copenhagen, Denmark, pages 9:1-9:18, 2020. URL: https://doi.org/10.4230/LIPIcs.ICDT.2020.9.
  28. Diego Figueira, Adwait Godbole, Shankara Narayanan Krishna, Wim Martens, Matthias Niewerth, and Tina Trautner. Containment of simple regular path queries. CoRR, abs/2003.04411, 2020. URL: http://arxiv.org/abs/2003.04411.
  29. Dominik D. Freydenberger and Nicole Schweikardt. Expressiveness and static analysis of extended conjunctive regular path queries. J. Comput. Syst. Sci., 79(6):892-909, 2013. URL: https://doi.org/10.1016/j.jcss.2013.01.008.
  30. François Le Gall. Powers of tensors and fast matrix multiplication. In Katsusuke Nabeshima, Kosaku Nagasaka, Franz Winkler, and Ágnes Szántó, editors, International Symposium on Symbolic and Algebraic Computation, ISSAC '14, Kobe, Japan, July 23-25, 2014, pages 296-303. ACM, 2014. URL: https://doi.org/10.1145/2608628.2608664.
  31. Grzegorz Gluch, Jerzy Marcinkowski, and Piotr Ostropolski-Nalewaja. The first order truth behind undecidability of regular path queries determinacy. In 22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal, pages 15:1-15:18, 2019. Google Scholar
  32. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 21-30, 2015. URL: https://doi.org/10.1145/2746539.2746609.
  33. Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. Conditional hardness for sensitivity problems. In 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, pages 26:1-26:31, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.26.
  34. Leonid Libkin, Wim Martens, and Domagoj Vrgoc. Querying graphs with data. Journal of the ACM, 63(2):14:1-14:53, 2016. Google Scholar
  35. Katja Losemann and Wim Martens. The complexity of regular expressions and property paths in SPARQL. ACM Transactions on Database Systems (TODS), 38(4):24:1-24:39, 2013. Google Scholar
  36. Wim Martens. Personal communication by email, October 28, 2019. Google Scholar
  37. Wim Martens, Matthias Niewerth, and Tina Trautner. A trichotomy for regular trail queries. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, pages 7:1-7:16, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.7.
  38. Wim Martens and Tina Trautner. Evaluation and enumeration problems for regular path queries. In 21st International Conference on Database Theory, ICDT 2018, March 26-29, 2018, Vienna, Austria, pages 19:1-19:21, 2018. Google Scholar
  39. Wim Martens and Tina Trautner. Bridging theory and practice with query log analysis. SIGMOD Rec., 48(1):6-13, 2019. URL: https://doi.org/10.1145/3371316.3371319.
  40. Wim Martens and Tina Trautner. Dichotomies for evaluating simple regular path queries. ACM Trans. Database Syst., 44(4):16:1-16:46, 2019. URL: https://doi.org/10.1145/3331446.
  41. Alberto O. Mendelzon and Peter T. Wood. Finding regular simple paths in graph databases. SIAM Journal on Computing (SICOMP), 24(6):1235-1258, 1995. Google Scholar
  42. Bernard M. E. Moret and Henry D. Shapiro. Algorithms from P to NP (Vol. 1): Design and Efficiency. Benjamin-Cummings Publishing Co., Inc., USA, 1991. Google Scholar
  43. Juan L. Reutter, Miguel Romero, and Moshe Y. Vardi. Regular queries on graph databases. Theory of Computing Systems (ToCS), 61(1):31-83, 2017. Google Scholar
  44. Miguel Romero, Pablo Barceló, and Moshe Y. Vardi. The homomorphism problem for regular graph patterns. In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1-12, 2017. URL: https://doi.org/10.1109/LICS.2017.8005106.
  45. Luc Segoufin. Constant delay enumeration for conjunctive queries. SIGMOD Record, 44(1):10-17, 2015. Google Scholar
  46. Ryan Williams. A new algorithm for optimal constraint satisfaction and its implications. In Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings, pages 1227-1237, 2004. URL: https://doi.org/10.1007/978-3-540-27836-8_101.
  47. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.023.
  48. Virginia Vassilevska Williams. Algorithms column: An overview of the recent progress on matrix multiplication. SIGACT News, 43(4):57-59, 2012. URL: https://doi.org/10.1145/2421119.2421134.
  49. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 887-898. ACM, 2012. URL: https://doi.org/10.1145/2213977.2214056.
  50. Virginia Vassilevska Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, pages 17-29, 2015. URL: https://doi.org/10.4230/LIPIcs.IPEC.2015.17.
  51. Virginia Vassilevska Williams. Some open problems in fine-grained complexity. SIGACT News, 49(4):29-35, 2018. URL: https://doi.org/10.1145/3300150.3300158.
  52. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. J. ACM, 65(5):27:1-27:38, 2018. URL: https://doi.org/10.1145/3186893.
  53. Peter T. Wood. Query languages for graph databases. SIGMOD Rec., 41(1):50-60, 2012. URL: https://doi.org/10.1145/2206869.2206879.
  54. Raphael Yuster and Uri Zwick. Fast sparse matrix multiplication. ACM Trans. Algorithms, 1(1):2-13, 2005. URL: https://doi.org/10.1145/1077464.1077466.
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