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.00014502493
Overall Rank
1,037 | 92.79%
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
789 Cypher: An Evolving Query Language for Property Graphs 2018 SIGMOD 0.00016634256
964 G-CORE: A Core for Future Graph Query Languages 2018 SIGMOD 0.0001497475
2,505 Graph Pattern Matching in GQL and SQL/PGQ 2022 SIGMOD 8.634551e-05
2,826 Regular Path Query Evaluation on Streaming Graphs 2020 SIGMOD 8.056119e-05
3,213 Landmark Indexing for Evaluation of Label-Constrained Reachability Queries 2017 SIGMOD 7.3669794e-05
3,988 All-in-One: Graph Processing in RDBMSs Revisited 2017 SIGMOD 6.5589605e-05
4,990 ZipG: A Memory-efficient Graph Store for Interactive Queries 2017 SIGMOD 5.7825419e-05
5,517 Representing Paths in Graph Database Pattern Matching 2023 VLDB 5.4626107e-05
5,651 GPC: A Pattern Calculus for Property Graphs 2023 PODS 5.3905536e-05
5,792 Querying in the Age of Graph Databases and Knowledge Graphs 2021 SIGMOD 5.325937e-05
5,992 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.2415551e-05
6,730 A Hierarchical Contraction Scheme for Querying Big Graphs 2022 SIGMOD 4.9479867e-05
6,795 Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond 2020 VLDB 4.9242446e-05
6,820 Conjunctive Regular Path Queries with String Variables 2020 PODS 4.9157306e-05
6,896 Containment of Graph Queries Modulo Schema 2024 PODS 4.8925595e-05
7,713 GQL and SQL/PGQ: Theoretical Models and Expressive Power 2025 VLDB 4.6712228e-05
7,998 Data Management for Social Networking 2016 PODS 4.6101889e-05
8,804 Conjunctive Regular Path Queries under Injective Semantics 2023 PODS 4.4468701e-05
8,827 The Complexity of Regular Trail and Simple Path Queries on Undirected Graphs 2022 PODS 4.4411907e-05
8,943 Towards Theory for Real-World Data 2022 PODS 4.4258797e-05
9,037 Transforming Property Graphs 2024 VLDB 4.4039656e-05
9,493 When is the Evaluation of Extended CRPQ Tractable? 2022 PODS 4.3341665e-05
9,739 Expressive Languages for Querying the Semantic Web 2014 PODS 4.2936538e-05
9,744 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 4.2897489e-05
9,890 The (Almost) Complete Guide to Tree Pattern Containment 2015 PODS 4.2617199e-05
10,070 DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs 2026 SIGMOD 4.1945683e-05
10,096 NeuSO: Neural Optimizer for Subgraph Queries 2026 SIGMOD 4.1945683e-05
11,079 Complex-Path: Effective and Efficient Node Ranking with Paths in Billion-Scale Heterogeneous Graphs 2024 VLDB 4.1945683e-05
11,326 Data Path Queries over Embedded Graph Databases 2022 PODS 4.1945683e-05
11,899 Defining Relations on Graphs: How Hard is it in the Presence of Node Partitions? 2015 PODS 4.1945683e-05
11,967 Does Query Evaluation Tractability Help Query Containment? 2014 PODS 4.1945683e-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.00030259041
274 Regular Path Queries with Constraints 1997 PODS 0.00029390022
363 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00025715157
431 On the Complexity of Database Queries (Extended Abstract) 1997 PODS 0.00023370207
602 On the Complexity of Bounded-Variable Queries 1995 PODS 0.00019352415
810 Query Containment for Conjunctive Queries With Regular Expressions 1998 PODS 0.00016428374
1,314 Semistructured Data 1997 PODS 0.0001263326
1,327 GraphDB: Modeling and Querying Graphs in Databases 1994 VLDB 0.00012569127
1,812 Expressive Languages for Path Queries over Graph-Structured Data 2010 PODS 0.00010467069
2,304 Querying Semantic Web Data with SPARQL 2011 PODS 9.0648775e-05
3,652 The Complexity of Evaluating Path Expressions in SPARQL 2012 PODS 6.875313e-05
4,553 View-Based Query Containment 2003 PODS 6.091702e-05
4,946 Querying Graph Patterns 2011 PODS 5.8149362e-05
5,406 Query Containment and Rewriting Using Views for Regular Path Queries Under Constraints 2003 PODS 5.5243825e-05
6,948 Semantic Acyclicity on Graph Databases 2013 PODS 4.8898337e-05
8,851 Efficient Approximations of Conjunctive Queries 2012 PODS 4.4363908e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,282 Foundations of Semantic Web Databases 2004 PODS 7.2808673e-05
6,948 Semantic Acyclicity on Graph Databases 2013 PODS 4.8898337e-05
7,436 Schema Mappings for Data Graphs 2017 PODS 4.7311358e-05
3,681 Queries with Incomplete Answers over Semistructured Data 1999 PODS 6.8492288e-05
2,503 Evaluating Queries with Generalized Path Expressions 1996 SIGMOD 8.6379665e-05
1,444 Finding Regular Simple Paths in Graph Databases 1989 VLDB 0.00011946075
9,535 Graph Data Models, Query Languages and Programming Paradigms 2018 VLDB 4.3265843e-05
4,946 Querying Graph Patterns 2011 PODS 5.8149362e-05
461 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022499343
1,812 Expressive Languages for Path Queries over Graph-Structured Data 2010 PODS 0.00010467069