DBScholar

Back to papers

Graph-Theoretic Methods In Database Theory

Summary: Survey of graph-theoretic approaches to reachability/transitive-closure in databases, unifying classic algorithms, complexity bounds, and a semiring algebraic generalization. Also treats limited-memory, parallel, recursive-query and dynamic-update models, highlighting algorithmic tradeoffs and open problems. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
hb3863b41799151fa
Venue
PODS
Year
1990
Pagerank
7.7156987e-05
Overall Rank
3,030 | 79.70%
DOI
10.1145/298514.298576

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{yannakakis_pods90,
        address = {New York, NY, USA},
        series = {{PODS} '90},
        title = {{GRAPH-THEORETIC METHODS IN DATABASE THEORY}},
        url = {https://dl.acm.org/doi/10.1145/298514.298576},
        doi = {10.1145/298514.298576},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Yannakakis, Mihalis},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank Citing Paper Year Venue Pagerank
3,483 The Complexity of Evaluating Path Expressions in SPARQL 2012 PODS 7.2450764e-05
3,567 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 7.1826291e-05
3,685 Overbound and Right-Linear Queries 1991 PODS 7.081251e-05
6,443 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.7666211e-05
8,218 On Tree-Based Techniques for Query Evaluation 1992 PODS 5.3595692e-05
11,153 Circuits and Formulas for Datalog over Semirings 2025 PODS 4.9605343e-05
12,114 Context-Free Path Querying via Matrix Equations 2020 SIGMOD 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 23 of 23 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
18 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00058816744
67 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.0003786983
306 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00021533151
353 On the Power of Magic 1987 PODS 0.0002014941
637 Parallel Evaluation of Recursive Rule Queries 1986 PODS 0.00015323882
1,112 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00011945358
1,142 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00011812263
1,292 On the Computation of the Transitive Closure of Relational Operators 1986 VLDB 0.00011145435
1,368 Efficient Transitive Closure Algorithms 1988 VLDB 0.00010877284
1,423 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010696781
1,592 Finding Regular Simple Paths in Graph Databases 1989 VLDB 0.0001010713
1,688 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 9.8481921e-05
1,917 The Input/Output Complexity Of Transitive Closure 1990 SIGMOD 9.3649154e-05
1,986 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.2371562e-05
2,016 The Parallel Complexity of Simple Chain Queries (Extended Abstract) 1987 PODS 9.1708652e-05
2,078 One-Sided Recursions 1987 PODS 9.0607099e-05
2,126 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 8.9903441e-05
2,156 The Tree Property Is Fundamental For Query Processing (Extended Abstract) 1982 PODS 8.9291453e-05
4,447 Magic Counting Methods 1987 SIGMOD 6.5790432e-05
4,501 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS 6.5580877e-05
5,440 Worst-case Complexity Analysis of Methods for Logic Query Implementation 1987 PODS 6.1144635e-05
7,599 A Generalized Transitive Closure for Relational Queries 1988 PODS 5.4717527e-05
9,724 Counting Methods for Cyclic Relations 1988 PODS 5.121278e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 2,930 Extracting and Analyzing Hidden Graphs from Relational Databases 2017 SIGMOD
2 10,090 Tractable Database Design through Bounded Treewidth 2006 PODS
3 6,501 Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges 2022 VLDB
4 1,112 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB
5 288 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD
6 8,218 On Tree-Based Techniques for Query Evaluation 1992 PODS
7 3,567 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD
8 719 Querying Graph Databases 2013 PODS
9 1,142 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB
10 1,368 Efficient Transitive Closure Algorithms 1988 VLDB