Back to papers
Querying Graph Databases
Summary: Characterizes expressiveness and data complexity of navigational query languages (RPQs, with conjunctions/inverses) under two semantics: simple-paths (typically data-intractable) vs arbitrary-paths (admit tractable evaluation for an expressive class). Also formalizes two modern extensions—paths as first-class values and topology+data queries—and analyzes their complexity trade-offs.
(summarized by gpt-5-mini on Feb 09 2026)
Paper ID
he4aeea97c6840000
Venue
PODS
Year
2013
Pagerank
0.00014493767
Overall Rank
719 | 95.19%
DOI
10.1145/2463664.2465216
Incoming Non-self Citations Over Time
BibTeX Citation
@inproceedings{barcelo_pods13,
address = {New York, NY, USA},
series = {{PODS} '13},
title = {{Querying Graph Databases}},
url = {https://dl.acm.org/doi/10.1145/2463664.2465216},
doi = {10.1145/2463664.2465216},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Barceló, Pablo},
year = {2013}
}
Incoming Citations (Sorted by Pagerank)
Showing 35 of 35 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
420
Cypher: An Evolving Query Language for Property Graphs 2018
SIGMOD
0.00018489392
854
G-CORE: A Core for Future Graph Query Languages 2018
SIGMOD
0.00013432811
1,428
Graph Pattern Matching in GQL and SQL/PGQ 2022
SIGMOD
0.000106884
2,272
Regular Path Query Evaluation on Streaming Graphs 2020
SIGMOD
8.7108429e-05
2,744
Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017
SIGMOD
8.0484475e-05
3,805
All-in-One: Graph Processing in RDBMSs Revisited 2017
SIGMOD
6.99039e-05
4,572
GQL and SQL/PGQ: Theoretical Models and Expressive Power 2025
VLDB
6.514625e-05
4,989
GPC: A Pattern Calculus for Property Graphs 2023
PODS
6.3121508e-05
5,196
Querying in the Age of Graph Databases and Knowledge Graphs 2021
SIGMOD
6.2198467e-05
5,468
ZipG: A Memory-efficient Graph Store for Interactive Queries 2017
SIGMOD
6.1027486e-05
5,574
Representing Paths in Graph Database Pattern Matching 2023
VLDB
6.0628579e-05
6,192
Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020
VLDB
5.8377174e-05
6,443
Evaluating Datalog over Semirings: A Grounding-based Approach 2024
PODS
5.7666211e-05
7,034
A Hierarchical Contraction Scheme for Querying Big Graphs 2022
SIGMOD
5.5998447e-05
7,372
Containment of Graph Queries Modulo Schema 2024
PODS
5.5249024e-05
7,461
Conjunctive Regular Path Queries with String Variables 2020
PODS
5.5066099e-05
7,647
When is the Evaluation of Extended CRPQ Tractable? 2022
PODS
5.4607562e-05
7,835
The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs 2022
PODS
5.4281549e-05
8,200
Data Management for Social Networking 2016
PODS
5.3626246e-05
8,380
Conjunctive Regular Path Queries under Injective Semantics 2023
PODS
5.3271197e-05
9,210
Towards Theory for Real-World Data 2022
PODS
5.1930561e-05
9,392
Expressive Languages for Querying the Semantic Web 2014
PODS
5.1677817e-05
9,401
Transforming Property Graphs 2024
VLDB
5.1672232e-05
9,445
Output-Sensitive Evaluation of Regular Path Queries 2025
PODS
5.1630894e-05
9,837
NeuSO: Neural Optimizer for Subgraph Queries 2026
SIGMOD
5.1064323e-05
10,275
The (Almost) Complete Guide to Tree Pattern Containment 2015
PODS
5.0352713e-05
10,441
Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries 2026
PODS
4.9605343e-05
10,462
A Logical View of GNN-Style Computation and the Role of Activation Functions 2026
PODS
4.9605343e-05
10,509
cuRPQ: A High-Performance GPU-Based Framework for Processing Regular and Conjunctive Regular Path Queries 2026
SIGMOD
4.9605343e-05
10,635
DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs 2026
SIGMOD
4.9605343e-05
10,853
Testing Graph Databases via Transformations Between Fixed-Length and Variable-Length Queries 2026
VLDB
4.9605343e-05
11,662
Complex-Path: Effective and Efficient Node Ranking with Paths in Billion-Scale Heterogeneous Graphs 2024
VLDB
4.9605343e-05
11,884
Data Path Queries over Embedded Graph Databases 2022
PODS
4.9605343e-05
12,440
Defining Relations on Graphs: How Hard is it in the Presence of Node Partitions? 2015
PODS
4.9605343e-05
12,505
Does Query Evaluation Tractability Help Query Containment? 2014
PODS
4.9605343e-05
Outgoing Citations (Sorted by Pagerank)
Showing 16 of 16 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Rank
Cited Paper
Year
Venue
Pagerank
299
GraphLog: a Visual Formalism for Real Life Recursion 1990
PODS
0.00021766741
306
A Graphical Query Language Supporting Recursion 1987
SIGMOD
0.00021533151
358
Regular Path Queries with Constraints 1997
PODS
0.00020030407
424
On the Complexity of Database Queries (Extended Abstract) 1997
PODS
0.00018448553
703
Query Containment for Conjunctive Queries With Regular Expressions 1998
PODS
0.00014638214
796
On the Complexity of Bounded-Variable Queries 1995
PODS
0.00013890233
1,258
Semistructured Data 1997
PODS
0.00011301839
1,352
GraphDB: Modeling and Querying Graphs in Databases 1994
VLDB
0.00010913807
1,474
Expressive Languages for Path Queries over Graph-Structured Data 2010
PODS
0.00010526746
2,494
Querying Semantic Web Data with SPARQL 2011
PODS
8.3699384e-05
3,483
The Complexity of Evaluating Path Expressions in SPARQL 2012
PODS
7.2450764e-05
4,533
View-Based Query Containment 2003
PODS
6.540906e-05
5,122
Querying Graph Patterns 2011
PODS
6.2506877e-05
5,249
Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003
PODS
6.1979445e-05
7,163
Semantic Acyclicity on Graph Databases 2013
PODS
5.5797798e-05
9,205
Efficient Approximations of Conjunctive Queries 2012
PODS
5.1945931e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
4,242
Foundations of Semantic Web Databases 2004
PODS
2
7,163
Semantic Acyclicity on Graph Databases 2013
PODS
3
7,384
Schema Mappings for Data Graphs 2017
PODS
4
4,609
Queries with Incomplete Answers over Semistructured Data 1999
PODS
5
3,135
Evaluating Queries with Generalized Path Expressions 1996
SIGMOD
6
1,592
Finding Regular Simple Paths in Graph Databases 1989
VLDB
7
8,858
Graph Data Models, Query Languages and Programming Paradigms 2018
VLDB
8
5,122
Querying Graph Patterns 2011
PODS
9
288
Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008
SIGMOD
10
1,474
Expressive Languages for Path Queries over Graph-Structured Data 2010
PODS