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.741152e-05
Overall Rank
3,021 | 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,474 The Complexity of Evaluating Path Expressions in SPARQL 2012 PODS 7.2684123e-05
3,557 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 7.2052788e-05
3,677 Overbound and Right-Linear Queries 1991 PODS 7.1041732e-05
6,432 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.7857524e-05
8,203 On Tree-Based Techniques for Query Evaluation 1992 PODS 5.3772846e-05
11,092 Circuits and Formulas for Datalog over Semirings 2025 PODS 4.9769913e-05
12,070 Context-Free Path Querying via Matrix Equations 2020 SIGMOD 4.9769913e-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.00058997063
67 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00037991902
305 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00021580917
353 On the Power of Magic 1987 PODS 0.00020213935
633 Parallel Evaluation of Recursive Rule Queries 1986 PODS 0.00015373336
1,110 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00011979358
1,140 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00011847659
1,287 On the Computation of the Transitive Closure of Relational Operators 1986 VLDB 0.00011179513
1,364 Efficient Transitive Closure Algorithms 1988 VLDB 0.00010909199
1,416 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010729775
1,597 Finding Regular Simple Paths in Graph Databases 1989 VLDB 0.00010119507
1,682 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 9.8804595e-05
1,905 The Input/Output Complexity Of Transitive Closure 1990 SIGMOD 9.3947277e-05
1,981 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.267247e-05
2,007 The Parallel Complexity of Simple Chain Queries (Extended Abstract) 1987 PODS 9.2011602e-05
2,067 One-Sided Recursions 1987 PODS 9.0898007e-05
2,110 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 9.0195865e-05
2,144 The Tree Property Is Fundamental For Query Processing (Extended Abstract) 1982 PODS 8.9582569e-05
4,427 Magic Counting Methods 1987 SIGMOD 6.6008592e-05
4,483 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS 6.5780787e-05
5,423 Worst-case Complexity Analysis of Methods for Logic Query Implementation 1987 PODS 6.1347456e-05
7,583 A Generalized Transitive Closure for Relational Queries 1988 PODS 5.4898987e-05
9,695 Counting Methods for Cyclic Relations 1988 PODS 5.1382653e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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