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
904
Venue
PODS
Year
1990
Pagerank
7.9200375e-05
Overall Rank
2,957 | 79.72%
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,452 The Complexity of Evaluating Path Expressions in SPARQL 2012 PODS 7.4007472e-05
3,491 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 7.3658999e-05
3,603 Overbound and Right-Linear Queries 1991 PODS 7.2683975e-05
6,301 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.9213518e-05
8,035 On Tree-Based Techniques for Query Evaluation 1992 PODS 5.5028526e-05
10,640 Circuits and Formulas for Datalog over Semirings 2025 PODS 5.093636e-05
11,761 Context-Free Path Querying via Matrix Equations 2020 SIGMOD 5.093636e-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
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00060089598
63 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00038782376
312 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00021733819
344 On the Power of Magic 1987 PODS 0.00020659405
616 Parallel Evaluation of Recursive Rule Queries 1986 PODS 0.00015712636
1,086 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00012252192
1,114 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00012118382
1,259 On the Computation of the Transitive Closure of Relational Operators 1986 VLDB 0.00011437537
1,330 Efficient Transitive Closure Algorithms 1988 VLDB 0.00011140171
1,382 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010965236
1,653 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.000101081
1,658 Finding Regular Simple Paths in Graph Databases 1989 VLDB 0.00010092304
1,855 The Input/Output Complexity Of Transitive Closure 1990 SIGMOD 9.606146e-05
1,921 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.4809066e-05
1,957 The Parallel Complexity of Simple Chain Queries (Extended Abstract) 1987 PODS 9.4146943e-05
2,033 One-Sided Recursions 1987 PODS 9.2819369e-05
2,076 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 9.212586e-05
2,102 The Tree Property Is Fundamental For Query Processing (Extended Abstract) 1982 PODS 9.1638984e-05
4,337 Magic Counting Methods 1987 SIGMOD 6.7554367e-05
4,425 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS 6.7101609e-05
5,295 Worst-case Complexity Analysis of Methods for Logic Query Implementation 1987 PODS 6.2784683e-05
7,438 A Generalized Transitive Closure for Relational Queries 1988 PODS 5.6184826e-05
9,503 Counting Methods for Cyclic Relations 1988 PODS 5.2586367e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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