Size Bounds and Algorithms for Conjunctive Regular Path Queries

Cucumides, Tamara; REUTTER-DE LA MAZA, JUAN LORENZO; Vrgoc, Domagoj


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.

Más información

Título según SCOPUS: ID SCOPUS_ID:85150746459 Not found in local SCOPUS DB
Título de la Revista: Leibniz International Proceedings in Informatics, LIPIcs
Volumen: 255
Fecha de publicación: 2023