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
7771
Venue
VLDB
Year
1986
Pagerank
0.00014422575
Overall Rank
1,055 | 92.67%
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
246 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00030949575
566 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00019970535
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,648 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 0.00011028408
2,474 Graph-Theoretic Methods In Database Theory 1990 PODS 8.7135761e-05
3,346 Efficiently Supporting Procedures In Relational Database Systems 1987 SIGMOD 7.1924206e-05
4,329 Commutativity And Its Role In The Processing Of Linear Recursion 1989 VLDB 6.2858126e-05
4,852 Distributed Transitive Closure Computations: The Disconnection Set Approach 1990 VLDB 5.8764777e-05
6,504 Hybrid Transitive Closure Algorithms 1990 VLDB 5.0357556e-05
7,181 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.8074621e-05
12,871 Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB 1993 VLDB 4.1945683e-05
12,984 Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy 1987 VLDB 4.1945683e-05
12,988 An Extended Disjunctive Normal Form Approach For Optimizing Recursive Logic Queries In Loosely Coupled Environments 1987 VLDB 4.1945683e-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.0014279444
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.0010066783
175 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.00038338694
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
8,572 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB 4.4937074e-05
246 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00030949575
688 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00018134733
1,648 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 0.00011028408
4,852 Distributed Transitive Closure Computations: The Disconnection Set Approach 1990 VLDB 5.8764777e-05
786 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016660109
7,293 On Tree-Based Techniques for Query Evaluation 1992 PODS 4.7740089e-05
880 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015667998
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00016369666
7,181 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.8074621e-05