Database Paper Browser

Back to papers

On The Computation Of The Transitive Closure Of Relational Operators

Summary: Divide-and-conquer for computing the transitive closure of relational operators reduces iterations to O(log N) for complete materializations of recursively defined relations. Analytical and experimental results show this approach often beats N-iteration algorithms. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
7772
Venue
VLDB
Year
1986
Pagerank
0.00014223265
Overall Rank
1,078 | 92.51%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank Citing Paper Year Venue Pagerank
255 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00030342925
569 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00019912758
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,905 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 0.00010142772
2,473 Graph-Theoretic Methods In Database Theory 1990 PODS 8.7048914e-05
3,350 Efficiently Supporting Procedures In Relational Database Systems 1987 SIGMOD 7.1867845e-05
4,324 Commutativity And Its Role In The Processing Of Linear Recursion 1989 VLDB 6.279813e-05
4,855 Distributed Transitive Closure Computations: The Disconnection Set Approach 1990 VLDB 5.8698466e-05
6,499 Hybrid Transitive Closure Algorithms 1990 VLDB 5.0307246e-05
7,182 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.802834e-05
12,881 Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB 1993 VLDB 4.1905499e-05
12,995 Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy 1987 VLDB 4.1905499e-05
12,999 An Extended Disjunctive Normal Form Approach For Optimizing Recursive Logic Queries In Loosely Coupled Environments 1987 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank Cited Paper Year Venue Pagerank
9 Implementation Techniques For Main Memory Database Systems 1984 SIGMOD 0.001426258
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00099936325
157 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.0004048407
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,569 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB 4.4893996e-05
255 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00030342925
897 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00015484372
1,905 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 0.00010142772
792 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016580866
4,855 Distributed Transitive Closure Computations: The Disconnection Set Approach 1990 VLDB 5.8698466e-05
7,289 On Tree-Based Techniques for Query Evaluation 1992 PODS 4.7692311e-05
885 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015565543
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.0001629507
7,182 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.802834e-05