Database Paper Browser

Back to papers

Efficient Transitive Closure Algorithms

Summary: DFS-based transitive-closure algorithms with a node-marking scheme for efficient reachability on disk-based databases. Extendable to path queries and one-sided recursion; achieve no I/O costs for duplicate elimination, boosting performance for large relations. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
7868
Venue
VLDB
Year
1988
Pagerank
0.00015667998
Overall Rank
880 | 93.88%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank Citing Paper Year Venue Pagerank
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,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
2,474 Graph-Theoretic Methods In Database Theory 1990 PODS 8.7135761e-05
2,675 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 8.3315228e-05
4,852 Distributed Transitive Closure Computations: The Disconnection Set Approach 1990 VLDB 5.8764777e-05
5,492 Mixed-Approach Algorithms for Transitive Closure 1991 PODS 5.4771871e-05
6,504 Hybrid Transitive Closure Algorithms 1990 VLDB 5.0357556e-05
7,283 Sia: Optimizing Queries using Learned Predicates 2021 SIGMOD 4.7764688e-05
7,293 On Tree-Based Techniques for Query Evaluation 1992 PODS 4.7740089e-05
8,572 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB 4.4937074e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank Cited Paper Year Venue Pagerank
175 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.00038338694
673 One-Sided Recursions 1987 PODS 0.00018348841
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
1,055 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014422575
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,055 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014422575
7,293 On Tree-Based Techniques for Query Evaluation 1992 PODS 4.7740089e-05
246 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00030949575
8,572 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB 4.4937074e-05
7,181 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.8074621e-05
5,492 Mixed-Approach Algorithms for Transitive Closure 1991 PODS 5.4771871e-05
2,474 Graph-Theoretic Methods In Database Theory 1990 PODS 8.7135761e-05
786 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016660109
2,675 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 8.3315228e-05
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00016369666