A Unified Query Planning Framework for Conjunctive Regular Path Queries

Conjunctive regular path queries (CRPQs) form a critical backbone of modern graph query languages, integrating subgraph matching with regular path queries (RPQs). Despite their ubiquity in applications like social networks, finance, and scientific data analysis, CRPQ optimization lacks a unified framework, relying instead on heuristic combinations of disjoint techniques for subgraph matching and RPQs. This paper bridges this gap by introducing a novel algebraic optimization framework for CRPQs. We propose a hypergraph query model that enables composability, addressing a longstanding challenge in graph query languages including GQL and SQL/PGQ, and define six core operators (TI, KC, SJ, UNION, INV, and SCAN) to abstract CRPQ semantics. Leveraging algebraic transformation rules, we enumerate a rich space of equivalent query plans and devise a cost-based optimizer to select near-optimal plans for execution. Implemented based on MillenniumDB and Neo4j, our framework achieves significant speedups on CRPQs extracted from the WDBench and LDBC SNB benchmarks.