Output bounds for conjunctions of path queries

Abstract

Conjunctive regular queries (CRQs) extend conjunctive regular path queries (CRPQs) by allowing path patterns defined through regular queries, a language that strictly generalizes regular path queries and underpins the recently published GQL standard. Despite their importance, little is known about how to derive tight output bounds for CRQs, which are crucial in the design of worst-case optimal algorithms. In this paper we extend the classical Atserias-Grohe-Marx (AGM) bound and the recent techniques for CRPQs to CRQs. We show that while the AGM approach provides general bounds, obtaining tight results requires refined information on the sets of nodes that can participate in the answers of regular queries. We introduce the use of derivation trees and marked nodes to capture this information, and show how they can be integrated into linear programs that yield tight bounds. We also provide lower bounds showing the optimality of our techniques. Our results strictly extend previous bounds for CRPQs, and offer new insights into the evaluation of richer query languages over graph databases.