Database Paper Browser

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
905
Venue
PODS
Year
1990
Pagerank
8.7135761e-05
Overall Rank
2,474 | 82.80%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank Citing Paper Year Venue Pagerank
2,675 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 8.3315228e-05
3,414 Overbound and Right-Linear Queries 1991 PODS 7.1232056e-05
3,652 The Complexity of Evaluating Path Expressions in SPARQL 2012 PODS 6.875313e-05
5,992 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.2415551e-05
7,293 On Tree-Based Techniques for Query Evaluation 1992 PODS 4.7740089e-05
10,344 Circuits and Formulas for Datalog over Semirings 2025 PODS 4.1945683e-05
11,564 Context-Free Path Querying via Matrix Equations 2020 SIGMOD 4.1945683e-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.0010066783
77 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00057043861
363 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00025715157
365 On the Power of Magic 1987 PODS 0.00025585898
537 Parallel Evaluation of Recursive Rule Queries 1986 PODS 0.0002068591
673 One-Sided Recursions 1987 PODS 0.00018348841
688 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00018134733
786 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016660109
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00016369666
880 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015667998
1,055 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014422575
1,358 The Tree Property Is Fundamental For Query Processing (Extended Abstract) 1982 PODS 0.00012387987
1,389 The Input/Output Complexity Of Transitive Closure 1990 SIGMOD 0.00012260807
1,444 Finding Regular Simple Paths in Graph Databases 1989 VLDB 0.00011946075
1,545 The Parallel Complexity of Simple Chain Queries (Extended Abstract) 1987 PODS 0.0001144821
1,648 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 0.00011028408
1,712 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00010804573
2,042 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.699257e-05
3,999 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS 6.5469939e-05
4,555 Magic Counting Methods 1987 SIGMOD 6.0891017e-05
5,515 Worst-case Complexity Analysis of Methods for Logic Query Implementation 1987 PODS 5.4636431e-05
7,156 Counting Methods for Cyclic Relations 1988 PODS 4.8145046e-05
7,181 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.8074621e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,143 Extracting and Analyzing Hidden Graphs from Relational Databases 2017 SIGMOD 7.4804326e-05
9,740 Tractable Database Design through Bounded Treewidth 2006 PODS 4.2936538e-05
6,639 Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges 2022 VLDB 4.9801324e-05
786 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016660109
461 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022499343
7,293 On Tree-Based Techniques for Query Evaluation 1992 PODS 4.7740089e-05
2,675 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 8.3315228e-05
1,037 Querying Graph Databases 2013 PODS 0.00014502493
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00016369666
880 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015667998