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
1598
Venue
PODS
Year
2013
Pagerank
0.00014400452
Overall Rank
747 | 94.88%
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 34 of 34 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
547
Cypher: An Evolving Query Language for Property Graphs 2018
SIGMOD
0.00016731552
900
G-CORE: A Core for Future Graph Query Languages 2018
SIGMOD
0.00013337186
1,836
Graph Pattern Matching in GQL and SQL/PGQ 2022
SIGMOD
9.6489549e-05
2,209
Regular Path Query Evaluation on Streaming Graphs 2020
SIGMOD
8.9437338e-05
2,700
Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017
SIGMOD
8.2411888e-05
3,872
All-in-One: Graph Processing in RDBMSs Revisited 2017
SIGMOD
7.0580243e-05
5,322
ZipG: A Memory-efficient Graph Store for Interactive Queries 2017
SIGMOD
6.2659893e-05
5,418
Representing Paths in Graph Database Pattern Matching 2023
VLDB
6.2255373e-05
5,425
GPC: A Pattern Calculus for Property Graphs 2023
PODS
6.223218e-05
5,453
Querying in the Age of Graph Databases and Knowledge Graphs 2021
SIGMOD
6.2137771e-05
6,301
Evaluating Datalog over Semirings: A Grounding-based Approach 2024
PODS
5.9213518e-05
6,603
Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020
VLDB
5.824568e-05
6,876
A Hierarchical Contraction Scheme for Querying Big Graphs 2022
SIGMOD
5.7483615e-05
7,205
Containment of Graph Queries Modulo Schema 2024
PODS
5.6731473e-05
7,289
Conjunctive Regular Path Queries with String Variables 2020
PODS
5.654364e-05
7,487
When is the Evaluation of Extended CRPQ Tractable? 2022
PODS
5.6072799e-05
7,603
GQL and SQL/PGQ: Theoretical Models and Expressive Power 2025
VLDB
5.5853593e-05
7,658
The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs 2022
PODS
5.5738039e-05
8,017
Data Management for Social Networking 2016
PODS
5.5064531e-05
8,190
Conjunctive Regular Path Queries under Injective Semantics 2023
PODS
5.4700577e-05
9,012
Towards Theory for Real-World Data 2022
PODS
5.3323444e-05
9,181
Expressive Languages for Querying the Semantic Web 2014
PODS
5.3064263e-05
9,187
Transforming Property Graphs 2024
VLDB
5.3058708e-05
9,235
Output-Sensitive Evaluation of Regular Path Queries 2025
PODS
5.3016261e-05
9,617
NeuSO: Neural Optimizer for Subgraph Queries 2026
SIGMOD
5.2434488e-05
10,044
The (Almost) Complete Guide to Tree Pattern Containment 2015
PODS
5.1703259e-05
10,146
Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries 2026
PODS
5.093636e-05
10,167
A Logical View of GNN-Style Computation and the Role of Activation Functions 2026
PODS
5.093636e-05
10,215
cuRPQ: A High-Performance GPU-Based Framework for Processing Regular and Conjunctive Regular Path Queries 2026
SIGMOD
5.093636e-05
10,361
DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs 2026
SIGMOD
5.093636e-05
11,285
Complex-Path: Effective and Efficient Node Ranking with Paths in Billion-Scale Heterogeneous Graphs 2024
VLDB
5.093636e-05
11,525
Data Path Queries over Embedded Graph Databases 2022
PODS
5.093636e-05
12,098
Defining Relations on Graphs: How Hard is it in the Presence of Node Partitions? 2015
PODS
5.093636e-05
12,165
Does Query Evaluation Tractability Help Query Containment? 2014
PODS
5.093636e-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
300
GraphLog: a Visual Formalism for Real Life Recursion 1990
PODS
0.00022046803
312
A Graphical Query Language Supporting Recursion 1987
SIGMOD
0.00021733819
348
Regular Path Queries with Constraints 1997
PODS
0.00020518814
414
On the Complexity of Database Queries (Extended Abstract) 1997
PODS
0.00018893507
686
Query Containment for Conjunctive Queries With Regular Expressions 1998
PODS
0.00014948634
763
On the Complexity of Bounded-Variable Queries 1995
PODS
0.00014230134
1,233
Semistructured Data 1997
PODS
0.00011562468
1,359
GraphDB: Modeling and Querying Graphs in Databases 1994
VLDB
0.00011040427
1,575
Expressive Languages for Path Queries over Graph-Structured Data 2010
PODS
0.00010318258
2,446
Querying Semantic Web Data with SPARQL 2011
PODS
8.5728114e-05
3,452
The Complexity of Evaluating Path Expressions in SPARQL 2012
PODS
7.4007472e-05
4,445
View-Based Query Containment 2003
PODS
6.699172e-05
4,986
Querying Graph Patterns 2011
PODS
6.4120976e-05
5,146
Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003
PODS
6.3470184e-05
7,028
Semantic Acyclicity on Graph Databases 2013
PODS
5.7228058e-05
9,009
Efficient Approximations of Conjunctive Queries 2012
PODS
5.3335287e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
4,139
Foundations of Semantic Web Databases 2004
PODS
2
7,028
Semantic Acyclicity on Graph Databases 2013
PODS
3
7,214
Schema Mappings for Data Graphs 2017
PODS
4
4,495
Queries with Incomplete Answers over Semistructured Data 1999
PODS
5
3,067
Evaluating Queries with Generalized Path Expressions 1996
SIGMOD
6
1,658
Finding Regular Simple Paths in Graph Databases 1989
VLDB
7
9,682
Graph Data Models, Query Languages and Programming Paradigms 2018
VLDB
8
4,986
Querying Graph Patterns 2011
PODS
9
294
Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008
SIGMOD
10
1,575
Expressive Languages for Path Queries over Graph-Structured Data 2010
PODS