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.7048914e-05
Overall Rank
2,473 | 82.82%
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,679 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 8.3223476e-05
3,417 Overbound and Right-Linear Queries 1991 PODS 7.116211e-05
3,659 The Complexity of Evaluating Path Expressions in SPARQL 2012 PODS 6.8684407e-05
5,996 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.2365238e-05
7,289 On Tree-Based Techniques for Query Evaluation 1992 PODS 4.7692311e-05
10,356 Circuits and Formulas for Datalog over Semirings 2025 PODS 4.1905499e-05
11,568 Context-Free Path Querying via Matrix Equations 2020 SIGMOD 4.1905499e-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.00099936325
79 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00056010993
359 On the Power of Magic 1987 PODS 0.00025830228
364 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00025657601
541 Parallel Evaluation of Recursive Rule Queries 1986 PODS 0.00020586706
792 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016580866
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.0001629507
885 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015565543
897 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00015484372
1,078 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014223265
1,366 The Tree Property Is Fundamental For Query Processing (Extended Abstract) 1982 PODS 0.00012375931
1,389 The Input/Output Complexity Of Transitive Closure 1990 SIGMOD 0.00012247602
1,445 Finding Regular Simple Paths in Graph Databases 1989 VLDB 0.00011937596
1,532 The Parallel Complexity of Simple Chain Queries (Extended Abstract) 1987 PODS 0.00011466849
1,611 One-Sided Recursions 1987 PODS 0.00011146101
1,636 Bounds on the Propagation of Selection into Logic Programs 1987 PODS 0.00011058643
1,905 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 0.00010142772
2,048 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.689916e-05
3,990 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS 6.5536618e-05
4,440 Magic Counting Methods 1987 SIGMOD 6.180671e-05
5,347 Worst-case Complexity Analysis of Methods for Logic Query Implementation 1987 PODS 5.555803e-05
7,182 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.802834e-05
9,128 Counting Methods for Cyclic Relations 1988 PODS 4.3866751e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,147 Extracting and Analyzing Hidden Graphs from Relational Databases 2017 SIGMOD 7.4825501e-05
9,739 Tractable Database Design through Bounded Treewidth 2006 PODS 4.2895392e-05
6,640 Modern Techniques for Querying Graph-Structured Relations: Foundations, System Implementations, and Open Challenges 2022 VLDB 4.9753538e-05
792 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016580866
460 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022679846
7,289 On Tree-Based Techniques for Query Evaluation 1992 PODS 4.7692311e-05
2,679 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 8.3223476e-05
1,040 Querying Graph Databases 2013 PODS 0.00014483577
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.0001629507
885 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015565543