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.00014522278
Overall Rank
720 | 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.00018537915
860
G-CORE: A Core for Future Graph Query Languages 2018
SIGMOD
0.00013401414
1,494
Graph Pattern Matching in GQL and SQL/PGQ 2022
SIGMOD
0.00010497226
2,258
Regular Path Query Evaluation on Streaming Graphs 2020
SIGMOD
8.7393197e-05
2,734
Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017
SIGMOD
8.0751431e-05
3,801
All-in-One: Graph Processing in RDBMSs Revisited 2017
SIGMOD
7.0128676e-05
4,554
GQL and SQL/PGQ: Theoretical Models and Expressive Power 2025
VLDB
6.5362379e-05
4,967
GPC: A Pattern Calculus for Property Graphs 2023
PODS
6.3330919e-05
5,175
Querying in the Age of Graph Databases and Knowledge Graphs 2021
SIGMOD
6.2402956e-05
5,453
ZipG: A Memory-efficient Graph Store for Interactive Queries 2017
SIGMOD
6.1229951e-05
5,559
Representing Paths in Graph Database Pattern Matching 2023
VLDB
6.082972e-05
6,180
Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020
VLDB
5.8570846e-05
6,432
Evaluating Datalog over Semirings: A Grounding-based Approach 2024
PODS
5.7857524e-05
7,016
A Hierarchical Contraction Scheme for Querying Big Graphs 2022
SIGMOD
5.6184227e-05
7,350
Containment of Graph Queries Modulo Schema 2024
PODS
5.5432318e-05
7,440
Conjunctive Regular Path Queries with String Variables 2020
PODS
5.5248786e-05
7,633
When is the Evaluation of Extended CRPQ Tractable? 2022
PODS
5.4788728e-05
7,818
The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs 2022
PODS
5.4461633e-05
8,184
Data Management for Social Networking 2016
PODS
5.3804156e-05
8,366
Conjunctive Regular Path Queries under Injective Semantics 2023
PODS
5.3447929e-05
9,185
Towards Theory for Real-World Data 2022
PODS
5.2102846e-05
9,366
Expressive Languages for Querying the Semantic Web 2014
PODS
5.1849263e-05
9,375
Transforming Property Graphs 2024
VLDB
5.1843659e-05
9,420
Output-Sensitive Evaluation of Regular Path Queries 2025
PODS
5.1802184e-05
9,804
NeuSO: Neural Optimizer for Subgraph Queries 2026
SIGMOD
5.1233734e-05
10,243
The (Almost) Complete Guide to Tree Pattern Containment 2015
PODS
5.0519762e-05
10,375
Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries 2026
PODS
4.9769913e-05
10,396
A Logical View of GNN-Style Computation and the Role of Activation Functions 2026
PODS
4.9769913e-05
10,443
cuRPQ: A High-Performance GPU-Based Framework for Processing Regular and Conjunctive Regular Path Queries 2026
SIGMOD
4.9769913e-05
10,572
DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs 2026
SIGMOD
4.9769913e-05
10,792
Testing Graph Databases via Transformations Between Fixed-Length and Variable-Length Queries 2026
VLDB
4.9769913e-05
11,615
Complex-Path: Effective and Efficient Node Ranking with Paths in Billion-Scale Heterogeneous Graphs 2024
VLDB
4.9769913e-05
11,840
Data Path Queries over Embedded Graph Databases 2022
PODS
4.9769913e-05
12,397
Defining Relations on Graphs: How Hard is it in the Presence of Node Partitions? 2015
PODS
4.9769913e-05
12,462
Does Query Evaluation Tractability Help Query Containment? 2014
PODS
4.9769913e-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
298
GraphLog: a Visual Formalism for Real Life Recursion 1990
PODS
0.00021830158
305
A Graphical Query Language Supporting Recursion 1987
SIGMOD
0.00021580917
356
Regular Path Queries with Constraints 1997
PODS
0.0002009439
421
On the Complexity of Database Queries (Extended Abstract) 1997
PODS
0.00018507815
699
Query Containment for Conjunctive Queries With Regular Expressions 1998
PODS
0.00014680086
794
On the Complexity of Bounded-Variable Queries 1995
PODS
0.0001393526
1,254
Semistructured Data 1997
PODS
0.00011331788
1,350
GraphDB: Modeling and Querying Graphs in Databases 1994
VLDB
0.00010939854
1,468
Expressive Languages for Path Queries over Graph-Structured Data 2010
PODS
0.00010561507
2,484
Querying Semantic Web Data with SPARQL 2011
PODS
8.3957732e-05
3,474
The Complexity of Evaluating Path Expressions in SPARQL 2012
PODS
7.2684123e-05
4,516
View-Based Query Containment 2003
PODS
6.5619066e-05
5,099
Querying Graph Patterns 2011
PODS
6.2713809e-05
5,230
Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003
PODS
6.2178069e-05
7,142
Semantic Acyclicity on Graph Databases 2013
PODS
5.5979329e-05
9,177
Efficient Approximations of Conjunctive Queries 2012
PODS
5.2117841e-05
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
4,223
Foundations of Semantic Web Databases 2004
PODS
2
7,142
Semantic Acyclicity on Graph Databases 2013
PODS
3
7,364
Schema Mappings for Data Graphs 2017
PODS
4
4,594
Queries with Incomplete Answers over Semistructured Data 1999
PODS
5
3,126
Evaluating Queries with Generalized Path Expressions 1996
SIGMOD
6
1,597
Finding Regular Simple Paths in Graph Databases 1989
VLDB
7
8,840
Graph Data Models, Query Languages and Programming Paradigms 2018
VLDB
8
5,099
Querying Graph Patterns 2011
PODS
9
289
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