Abstract
We study a relational perspective of graph database querying. Such a perspective underlies various graph database systems but very few theoretical investigations have been conducted on it. This perspective offers a powerful and unified framework to study graph database querying, by which algorithms and complexity follow from classical results. We provide two concrete applications. The first is querying property graphs. The property graph data model supersedes previously proposed graph models and underlies the new standard GQL for graph query languages. We show that this standard can be, by and large, expressed by extensions of relational calculus with transitive closure operators (FO[TC]) and existential second-order quantifiers (ESO). With this, we obtain optimal data complexity bounds, along with extensions including schema validation. The second application is incorporating data from concrete domains (e.g., numbers) in graph database querying. We use embedded finite model theory and, by exploiting a generic Restricted Quantifier Collapse (RQC) result for FO[TC] and ESO, we obtain optimal data complexity bounds for GQL with arithmetics and comparisons. Moreover, we show that Regular Data Path Querying with operations on data (i.e. using register automata formalisms) can be captured in FO[TC] over embedded finite graphs while preserving nondeterministic logspace data complexity.
Introduction
In the realm of relational databases, SQL has long served as the definitive standard. However, the rise of interconnected data has popularized "Property Graphs"—structures where nodes and edges are enriched with labels and key-value properties. While systems like Neo4j and AWS Neptune have seen wide adoption, the theoretical underpinnings of the new ISO standard, GQL (Graph Query Language), remained largely unmapped. Specifically, its data complexity—the computational cost of evaluating a fixed query as the database size grows—was an open question. This paper addresses this gap by establishing a relational perspective on graph querying, providing a unified framework to derive complexity bounds from classical logic results.
The Property Graph Data Model
The property graph model is a superset of traditional graph models, allowing for complex metadata to be associated with both vertices and edges. This expressiveness is central to GQL. For example, a graph might represent a transportation network where nodes (towns) have coordinates and edges (roads or bike lanes) have lengths and tolls.
Methodology: Relational Embedding
The core technique used in this study is relational embedding. Rather than analyzing GQL in isolation, the authors translate its constructs into established fragments of mathematical logic:
- Restrictor-Free GQL is mapped to First-Order logic extended with a Transitive Closure operator (FO[TC]).
- General GQL (incorporating path constraints) is mapped to First-Order logic with Existential Second-Order quantifiers (ESO).
By creating these logical bridges, the authors leverage decades of research in Finite Model Theory to establish tight complexity bounds.
Complexity Analysis and Key Results
The research identifies path restrictors—keywords such as simple (no repeated nodes) or trail (no repeated edges)—as the primary drivers of computational complexity. Without these restrictors, GQL evaluation is highly efficient. With them, the complexity increases significantly.
| GQL Fragment | Complexity Class | Intuition |
|---|---|---|
| Restrictor-Free | NL-complete | Similar to basic graph reachability. |
| General (with Restrictors) | $P^{NP[\log]}$-complete | Equivalent to running multiple NP-hard checks in parallel. |
Furthermore, the study demonstrates that the inclusion of infinite data domains, such as real-number arithmetic, does not increase the complexity class. This is due to the Restricted Quantifier Collapse (RQC) property, which allows queries involving arithmetic to be evaluated based solely on the finite set of values present in the database.
Conclusion
This work provides the first precise characterization of GQL's data complexity, placing it firmly within the landscape of computational logic. While the worst-case bounds are now established, future work is needed to explore the complexity of path-based aggregation and to develop practical heuristics for query optimization in real-world scenarios.
Summary updated