A Practical Query Language for Graph DBs

Renzo Angles, Pablo Barceló, Gonzalo RiosAMW 2013 · OpenReview

Introduction

Graph databases have become indispensable for managing complex, interconnected data in domains ranging from social networks to bioinformatics. However, the current landscape of graph query languages is often described as a "Wild West," characterized by a lack of formal semantics and unpredictable performance. Researchers from the Universidad de Talca, VU University Amsterdam, and the Universidad de Chile propose a solution: using Propositional Dynamic Logic (PDL) as a formal foundation to balance expressive power with computational efficiency.

A Formal Foundation: PDL with Converse

The core proposal involves adopting PDL with converse ($PDL^-$). Originally designed for program verification, PDL treats graph edges as "programs" and nodes as "states." By incorporating the "converse" operator, the language can navigate edges in both forward and backward directions.

The primary advantage of this logic-based approach is its theoretical efficiency. The authors demonstrate that $PDL^-$ formulas can be evaluated in linear time ($O(|G| \cdot |\phi|)$), where $|G|$ is the graph size and $|\phi|$ is the formula length. This provides a "Goldilocks" level of expressivity: powerful enough for most real-world reachability and property queries, yet restricted enough to avoid the NP-hard complexity traps common in more permissive languages.

Experimental Methodology

To evaluate the practicality of PDL, the researchers developed a prototype engine featuring a custom disk-based storage system. They compared its performance against two industry-standard engines: Dex (now Sparksee) and Neo4j. The evaluation utilized synthetic social network datasets of varying scales, designed to mimic real-world power-law distributions.

Table 1: Graph characteristics and loading performance across three scales (G1, G2, G3).

As shown in the table above, the datasets ranged from 10,000 nodes (G1) to 1,000,000 nodes (G3). While the PDL prototype demonstrated the viability of the logic, it also revealed significant overhead in loading times and storage requirements compared to mature commercial systems. For instance, loading the G3 graph took over 2,300 seconds for PDL, compared to just 77 seconds for Dex.

Performance and Scalability

The true test of the PDL approach lies in query execution. The researchers tested ten different queries (Q1-Q10) representing common social network tasks, such as finding common neighbors or multi-step reachability.

Table 2: Query execution times (in ms) for ten queries across different graph sizes and engines.

The results indicate that the PDL prototype is competitive on smaller scales (G1), sometimes outperforming Neo4j. However, as the graph size increases to G3, the performance gap between the unoptimized prototype and the highly-tuned Dex engine becomes more apparent. Despite this, the prototype successfully executed all queries across all graph sizes, confirming that the navigational fragment covered by PDL is indeed computationally tractable for large-scale data.

Conclusion

The research highlights a critical trade-off in graph database design. By deliberately excluding cycle-detection—a feature that often leads to exponential complexity—PDL ensures predictable, linear-time performance. While the current prototype lags behind industrial engines in storage efficiency, the authors suggest that the most promising path forward is not a standalone PDL engine, but rather the integration of PDL-based query logic into existing, optimized graph backends. This approach would combine formal mathematical guarantees with the industrial-grade performance required for modern big data applications.

Summary updated

BibTeX
@inproceedings{angles2013practical,
  author = {Renzo Angles and Pablo Barceló and Gonzalo Rios},
  title = {{A Practical Query Language for Graph DBs}},
  booktitle = {AMW},
  year = {2013},
  url = {https://openreview.net/forum?id=C0b7IuYLf5},
}
Figure