Database Paper Browser

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
1599
Venue
PODS
Year
2013
Pagerank
0.00014483577
Overall Rank
1,040 | 92.78%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 31 of 31 citing papers.

Rank Citing Paper Year Venue Pagerank
787 Cypher: An Evolving Query Language for Property Graphs 2018 SIGMOD 0.00016624372
964 G-CORE: A Core for Future Graph Query Languages 2018 SIGMOD 0.00014967208
2,504 Graph Pattern Matching in GQL and SQL/PGQ 2022 SIGMOD 8.629969e-05
2,832 Regular Path Query Evaluation on Streaming Graphs 2020 SIGMOD 8.048358e-05
3,221 Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017 SIGMOD 7.3541078e-05
3,984 All-in-One: Graph Processing in RDBMSs Revisited 2017 SIGMOD 6.5587512e-05
4,987 ZipG: A Memory-efficient Graph Store for Interactive Queries 2017 SIGMOD 5.7769841e-05
5,527 Representing Paths in Graph Database Pattern Matching 2023 VLDB 5.4573655e-05
5,663 GPC: A Pattern Calculus for Property Graphs 2023 PODS 5.3853781e-05
5,802 Querying in the Age of Graph Databases and Knowledge Graphs 2021 SIGMOD 5.3209544e-05
5,996 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.2365238e-05
6,796 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 4.9195203e-05
6,818 Conjunctive Regular Path Queries with String Variables 2020 PODS 4.911014e-05
6,899 Containment of Graph Queries Modulo Schema 2024 PODS 4.8878659e-05
7,179 A Hierarchical Contraction Scheme for Querying Big Graphs 2022 SIGMOD 4.803776e-05
7,712 GQL and SQL/PGQ: Theoretical Models and Expressive Power 2025 VLDB 4.6667433e-05
7,926 Data Management for Social Networking 2016 PODS 4.6107647e-05
8,803 Conjunctive Regular Path Queries under Injective Semantics 2023 PODS 4.4426077e-05
8,827 The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs 2022 PODS 4.4369334e-05
8,947 Towards Theory for Real-World Data 2022 PODS 4.4216375e-05
9,038 Transforming Property Graphs 2024 VLDB 4.3997447e-05
9,494 When is the Evaluation of Extended CRPQ Tractable? 2022 PODS 4.3300131e-05
9,738 Expressive Languages for Querying the Semantic Web 2014 PODS 4.2895392e-05
9,743 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 4.2856385e-05
9,889 The (Almost) Complete Guide to Tree Pattern Containment 2015 PODS 4.2576366e-05
10,070 DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs 2026 SIGMOD 4.1905499e-05
10,096 NeuSO: Neural Optimizer for Subgraph Queries 2026 SIGMOD 4.1905499e-05
11,082 Complex-Path: Effective and Efficient Node Ranking with Paths in Billion-Scale Heterogeneous Graphs 2024 VLDB 4.1905499e-05
11,328 Data Path Queries over Embedded Graph Databases 2022 PODS 4.1905499e-05
11,907 Defining Relations on Graphs: How Hard is it in the Presence of Node Partitions? 2015 PODS 4.1905499e-05
11,975 Does Query Evaluation Tractability Help Query Containment? 2014 PODS 4.1905499e-05
Previous Page 1 / 1 Next

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
256 GraphLog: a Visual Formalism for Real Life Recursion 1990 PODS 0.00030241337
276 Regular Path Queries with Constraints 1997 PODS 0.00029365217
364 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00025657601
432 On the Complexity of Database Queries (Extended Abstract) 1997 PODS 0.00023349408
603 On the Complexity of Bounded-Variable Queries 1995 PODS 0.00019334592
808 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.000164132
1,314 Semistructured Data 1997 PODS 0.00012618313
1,327 GraphDB: Modeling and Querying Graphs in Databases 1994 VLDB 0.00012571112
1,812 Expressive Languages for Path Queries over Graph-Structured Data 2010 PODS 0.00010458164
2,302 Querying Semantic Web Data with SPARQL 2011 PODS 9.0662698e-05
3,659 The Complexity of Evaluating Path Expressions in SPARQL 2012 PODS 6.8684407e-05
4,552 View-Based Query Containment 2003 PODS 6.0856349e-05
4,949 Querying Graph Patterns 2011 PODS 5.8090034e-05
5,415 Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003 PODS 5.5188622e-05
6,945 Semantic Acyclicity on Graph Databases 2013 PODS 4.8874695e-05
8,850 Efficient Approximations of Conjunctive Queries 2012 PODS 4.4324268e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,285 Foundations of Semantic Web Databases 2004 PODS 7.2738104e-05
6,945 Semantic Acyclicity on Graph Databases 2013 PODS 4.8874695e-05
7,435 Schema Mappings for Data Graphs 2017 PODS 4.7265981e-05
3,683 Queries with Incomplete Answers over Semistructured Data 1999 PODS 6.84255e-05
2,506 Evaluating Queries with Generalized Path Expressions 1996 SIGMOD 8.6273062e-05
1,445 Finding Regular Simple Paths in Graph Databases 1989 VLDB 0.00011937596
9,536 Graph Data Models, Query Languages and Programming Paradigms 2018 VLDB 4.3225428e-05
4,949 Querying Graph Patterns 2011 PODS 5.8090034e-05
460 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022679846
1,812 Expressive Languages for Path Queries over Graph-Structured Data 2010 PODS 0.00010458164