License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2023.13
URN: urn:nbn:de:0030-drops-177552
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17755/
Go to the corresponding LIPIcs Volume Portal

Cucumides, Tamara ; Reutter, Juan ; Vrgoč, Domagoj

Size Bounds and Algorithms for Conjunctive Regular Path Queries

pdf-format:
LIPIcs-ICDT-2023-13.pdf (0.7 MB)

Abstract

Conjunctive regular path queries (CRPQs) are one of the core classes of queries over graph databases. They are join intensive, inheriting their structure from the relational setting, but they also allow arbitrary length paths to connect points that are to be joined. However, despite their popularity, little is known about what are the best algorithms for processing CRPQs. We focus on worst-case optimal algorithms, which are algorithms that run in time bounded by the worst-case output size of queries, and have been recently deployed for simpler graph queries with very promising results. We show that the famous bound on the number of query results by Atserias, Grohe and Marx can be extended to CRPQs, but to obtain tight bounds one needs to work with slightly stronger cardinality profiles. We also discuss what algorithms follow from our analysis. If one pays the cost for fully materializing graph queries, then the techniques developed for conjunctive queries can be reused. If, on the other hand, one imposes constraint on the working memory of algorithms, then worst-case optimal algorithms must be adapted with care: the order of variables in which queries are processed can have striking implications on the running time of queries.

BibTeX - Entry

@InProceedings{cucumides_et_al:LIPIcs.ICDT.2023.13,
  author =	{Cucumides, Tamara and Reutter, Juan and Vrgo\v{c}, Domagoj},
  title =	{{Size Bounds and Algorithms for Conjunctive Regular Path Queries}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17755},
  URN =		{urn:nbn:de:0030-drops-177552},
  doi =		{10.4230/LIPIcs.ICDT.2023.13},
  annote =	{Keywords: graph databases, regular path queries, worst-case optimal algorithms}
}

Keywords: graph databases, regular path queries, worst-case optimal algorithms
Collection: 26th International Conference on Database Theory (ICDT 2023)
Issue Date: 2023
Date of publication: 17.03.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI