PathDB: A system for evaluating regular path queries
For graph database users and developers, PathDB provides a more efficient and flexible system for evaluating RPQs with controlled path semantics.
PathDB introduces an algebraic query engine for regular path queries (RPQs) that supports multiple path semantics and outperforms traversal-based baselines by over an order of magnitude on a benchmark of 142 queries.
Regular Path Queries (RPQs) are a core mechanism for expressing recursion and reachability in graph databases. However, most systems evaluate RPQs with traversal-based algorithms that repeatedly explore overlapping subpaths and offer limited control over path semantics. We present PathDB, an algebraic query engine for RPQs based on a closed path algebra over multisets of paths with five operators: selection, join, union, recursive join, and projection. PathDB provides (i) a GQL-inspired declarative language that supports RPQs with multiple semantics (walk, trail, simple, and acyclic), (ii) an operator-at-a-time execution procedure analogous to relational query processing, and (iii) result formats that include full paths, not only endpoint pairs. The experimental evaluation, based on four LDBC Social Network Benchmark property graphs and a workload of 142 queries derived from 26 path patterns, showed that PathDB outperforms two automaton-guided traversal baselines (DFS and BFS), often by more than an order of magnitude.