Answering Constraint Path Queries over Graphs

Heyang Li, Anthony Widjaja Lin, Domagoj VrgocarXiv 2025 · DOI · arXiv

Introduction

Graph databases excel at identifying structural patterns, such as finding a connection between two individuals in a social network. Standard Regular Path Queries (RPQs) facilitate flexible searching based on edge labels. However, these tools often struggle when queries require reasoning about the data attributes attached to nodes and edges along a path. For instance, finding a chain of "follows" where every connection occurred after a specific year and the age difference between participants is constrained is computationally expensive or impossible in current standards like GQL or SQL/PGQ.

Example property graph with attributes

Existing theoretical solutions for such "Constraint Path Queries" often suffer from exponential complexity, limiting their use to tiny datasets. This paper introduces a new query language and engine designed to bridge the gap between expressive data constraints and industrial-scale performance.

Methodology

The proposed framework consists of three primary components:

  1. Parametric Regular Expressions: An extension of standard regex that incorporates variables and constraints, supporting equality for strings and Linear Real Arithmetic (LRA) for numerical data.
  2. Parametric Automata: A formal execution model that translates these expressions into state machines capable of capturing data during graph traversal.
  3. Macro-State Optimization: To avoid the exponential explosion of checking constraints for every possible path, the authors group paths into "macro-states." An SMT solver (Z3) acts as an oracle to prune the search space by determining the feasibility of accumulated constraints early in the traversal.

The system is implemented within MillenniumDB, an open-source graph database engine.

Experimental Evaluation

The researchers evaluated the system across six diverse datasets, ranging from sparse real-world data to massive synthetic benchmarks.

Evaluation datasets summary

Key results include:

  • Scalability: The system successfully processed graphs with up to 178 million edges (LDBC10), a significant advancement over previous prototypes.
  • Performance: On medium-density graphs, most queries finished in under 100ms. Even on the extremely dense Telecom dataset (50M edges), complex queries typically resolved within 1 second.
  • Optimization Impact: The "macro-state" algorithm significantly outperformed naive BFS approaches, particularly on complex queries where the naive version frequently timed out.

Insights and Limitations

The study reveals that while the problem is NP-hard in general, the "data complexity" remains linear relative to graph size because query sizes are typically small. The primary performance bottleneck is the time spent querying the SMT solver, with a 0.964 correlation between oracle calls and total runtime. Interestingly, more complex constraints can sometimes improve performance by allowing the SMT solver to identify contradictions and prune paths faster.

Current limitations include a restriction to linear constraints and the absence of complex integer arithmetic. Future work aims to explore localized data dependencies and leverage advancements in SMT technology to further enhance query speeds.

Summary updated

BibTeX
@misc{li2025answering,
  author = {Heyang Li and Anthony Widjaja Lin and Domagoj Vrgoc},
  title = {{Answering Constraint Path Queries over Graphs}},
  year = {2025},
  eprint = {2512.01733},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.01733},
}
Figure