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.00014529156
Overall Rank
719 | 95.17%
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
419
Cypher: An Evolving Query Language for Property Graphs 2018
SIGMOD
0.0001854669
860
G-CORE: A Core for Future Graph Query Languages 2018
SIGMOD
0.00013406849
1,494
Graph Pattern Matching in GQL and SQL/PGQ 2022
SIGMOD
0.00010502195
2,257
Regular Path Query Evaluation on Streaming Graphs 2020
SIGMOD
8.7434588e-05
2,734
Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017
SIGMOD
8.0789676e-05
3,798
All-in-One: Graph Processing in RDBMSs Revisited 2017
SIGMOD
7.0161889e-05
4,553
GQL and SQL/PGQ: Theoretical Models and Expressive Power 2025
VLDB
6.5393335e-05
4,965
GPC: A Pattern Calculus for Property Graphs 2023
PODS
6.3360914e-05
5,174
Querying in the Age of Graph Databases and Knowledge Graphs 2021
SIGMOD
6.243251e-05
5,448
ZipG: A Memory-efficient Graph Store for Interactive Queries 2017
SIGMOD
6.125895e-05
5,557
Representing Paths in Graph Database Pattern Matching 2023
VLDB
6.085853e-05
6,177
Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020
VLDB
5.8598586e-05
6,429
Evaluating Datalog over Semirings: A Grounding-based Approach 2024
PODS
5.7884926e-05
7,015
A Hierarchical Contraction Scheme for Querying Big Graphs 2022
SIGMOD
5.6210836e-05
7,347
Containment of Graph Queries Modulo Schema 2024
PODS
5.5458571e-05
7,437
Conjunctive Regular Path Queries with String Variables 2020
PODS
5.5274952e-05
7,627
When is the Evaluation of Extended CRPQ Tractable? 2022
PODS
5.4814676e-05
7,811
The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs 2022
PODS
5.4487427e-05
8,177
Data Management for Social Networking 2016
PODS
5.3829638e-05
8,362
Conjunctive Regular Path Queries under Injective Semantics 2023
PODS
5.3473243e-05
9,176
Towards Theory for Real-World Data 2022
PODS
5.2127522e-05
9,357
Expressive Languages for Querying the Semantic Web 2014
PODS
5.1873819e-05
9,366
Transforming Property Graphs 2024
VLDB
5.1868213e-05
9,410
Output-Sensitive Evaluation of Regular Path Queries 2025
PODS
5.1826718e-05
9,797
NeuSO: Neural Optimizer for Subgraph Queries 2026
SIGMOD
5.1257999e-05
10,237
The (Almost) Complete Guide to Tree Pattern Containment 2015
PODS
5.0543689e-05
10,363
Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries 2026
PODS
4.9793485e-05
10,384
A Logical View of GNN-Style Computation and the Role of Activation Functions 2026
PODS
4.9793485e-05
10,431
cuRPQ: A High-Performance GPU-Based Framework for Processing Regular and Conjunctive Regular Path Queries 2026
SIGMOD
4.9793485e-05
10,561
DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs 2026
SIGMOD
4.9793485e-05
10,782
Testing Graph Databases via Transformations Between Fixed-Length and Variable-Length Queries 2026
VLDB
4.9793485e-05
11,609
Complex-Path: Effective and Efficient Node Ranking with Paths in Billion-Scale Heterogeneous Graphs 2024
VLDB
4.9793485e-05
11,834
Data Path Queries over Embedded Graph Databases 2022
PODS
4.9793485e-05
12,391
Defining Relations on Graphs: How Hard is it in the Presence of Node Partitions? 2015
PODS
4.9793485e-05
12,456
Does Query Evaluation Tractability Help Query Containment? 2014
PODS
4.9793485e-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
297
GraphLog: a Visual Formalism for Real Life Recursion 1990
PODS
0.00021840374
305
A Graphical Query Language Supporting Recursion 1987
SIGMOD
0.0002159111
356
Regular Path Queries with Constraints 1997
PODS
0.00020103855
421
On the Complexity of Database Queries (Extended Abstract) 1997
PODS
0.00018516535
699
Query Containment for Conjunctive Queries With Regular Expressions 1998
PODS
0.00014686953
794
On the Complexity of Bounded-Variable Queries 1995
PODS
0.00013941847
1,251
Semistructured Data 1997
PODS
0.00011337126
1,350
GraphDB: Modeling and Querying Graphs in Databases 1994
VLDB
0.0001094492
1,468
Expressive Languages for Path Queries over Graph-Structured Data 2010
PODS
0.00010566509
2,483
Querying Semantic Web Data with SPARQL 2011
PODS
8.3997473e-05
3,474
The Complexity of Evaluating Path Expressions in SPARQL 2012
PODS
7.2718547e-05
4,514
View-Based Query Containment 2003
PODS
6.5650143e-05
5,096
Querying Graph Patterns 2011
PODS
6.2743507e-05
5,226
Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003
PODS
6.2207517e-05
7,140
Semantic Acyclicity on Graph Databases 2013
PODS
5.6005794e-05
9,169
Efficient Approximations of Conjunctive Queries 2012
PODS
5.2141412e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
4,222
Foundations of Semantic Web Databases 2004
PODS
2
7,140
Semantic Acyclicity on Graph Databases 2013
PODS
3
7,359
Schema Mappings for Data Graphs 2017
PODS
4
4,592
Queries with Incomplete Answers over Semistructured Data 1999
PODS
5
3,124
Evaluating Queries with Generalized Path Expressions 1996
SIGMOD
6
1,597
Finding Regular Simple Paths in Graph Databases 1989
VLDB
7
8,831
Graph Data Models, Query Languages and Programming Paradigms 2018
VLDB
8
5,096
Querying Graph Patterns 2011
PODS
9
288
Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008
SIGMOD
10
1,468
Expressive Languages for Path Queries over Graph-Structured Data 2010
PODS