Introduction
As graph databases grow to sizes that exceed modern memory limits, the efficiency of query languages becomes critical. Traditionally, "feasible" languages are those with NL (non-deterministic logarithmic space) data complexity—the same complexity class as simple reachability. However, existing languages often force a trade-off: they are either efficient but limited to structural properties (e.g., "is node A reachable from node B?"), or they are expressive (allowing data comparisons and arithmetic) but computationally expensive (NP-hard or worse).
This paper introduces LARE (Language for Arithmetical Regular Expressions), a powerful new query language for "data graphs"—graphs where edges have labels and nodes store numerical values. LARE allows users to write complex queries involving arithmetic and aggregation while maintaining NL data complexity, making it computationally feasible even for massive graph databases.
The LARE Framework
LARE is built on several key technical pillars designed to bridge the gap between structural topology and numerical data reasoning.
1. Arithmetical Regular Expressions (ARE)
LARE extends standard regular expressions by incorporating registers to store node values. These expressions can perform arithmetic operations—such as sum, max, min, and count—and execute comparisons on the data encountered along a path. By using registers to "remember" nodes and values, LARE can express properties that standard regular path queries cannot, such as checking if a path visits the node with the maximum value in the entire graph.
2. Unary Representation and Log-Space Aggregation
To keep arithmetic within logarithmic space, the authors define the "size" of the graph using unary notation for node labels. This ensures that basic arithmetic operations do not cause a complexity blow-up relative to the input size. The authors demonstrate that aggregative functions, such as summing weights on a path, can be handled in NL if constants are treated carefully, effectively allowing weighted graph reasoning within a standard graph query framework.
3. Automata Giving Turing Machines (AGTM)
The paper's core theoretical contribution is the introduction of Effective Relational Conditions via a formalism called AGTM. Instead of building one massive automaton for a query, an AGTM succinctly represents a family of automata—one for each possible graph. This framework decouples the complexity of the query from the complexity of the data, proving that even with arithmetic, query answering can stay within the same complexity class as simple connectivity.
4. Nesting and Negation
LARE supports nested queries and negation. This allows for complex logic, such as identifying paths where no sub-path visits an undesirable state or satisfies a specific numerical condition.
Key Results and Expressiveness
The authors prove several critical complexity bounds for LARE:
- Data Complexity: The data complexity of answering LARE queries is NL-complete. This is the "gold standard" for graph querying, as it matches the complexity of simple reachability.
- Combined Complexity: When considering both the query and the data as input, the complexity is PSPACE-complete.
In terms of expressiveness, LARE is strictly more powerful than several existing formalisms, including Extended Conjunctive Regular Path Queries (ECRPQs) and certain fragments of Register Logic. It is capable of handling "greedy" paths, detecting directed acyclic graphs (DAGs), and performing complex path-weight calculations.
Limitations and Future Work
While LARE represents a significant step forward, the authors identify specific boundaries for its current application:
- Nesting Depth: The NL complexity result specifically applies to queries with bounded nesting depth. If nesting is allowed to grow arbitrarily with the data, the complexity bounds may shift.
- Cross-Path Comparisons: While LARE excels at aggregating values along a single path, comparing sums of values across different paths remains a challenge. Future research aims to incorporate more global aggregative properties while maintaining low complexity.
- Data Domains: The current work assumes natural numbers as data values. While the approach can be adjusted for other domains, formalisms for strings or other complex data types are still under development.
Conclusion
LARE provides a robust theoretical foundation for querying data graphs without sacrificing computational efficiency. By proving that arithmetic and aggregation can coexist with NL data complexity, the authors offer a path forward for more expressive and scalable graph database engines.
Summary updated