Database Paper Browser

Back to papers

Direct Algorithms for Computing the Transitive Closure of Database Relations

Summary: Direct algorithms compute transitive closure for large relations with termination independent of path length, outperforming semi-naive methods. Simulations show uniform gains and propose new methodology for evaluating recursive query performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
7808
Venue
VLDB
Year
1987
Pagerank
0.00016369666
Overall Rank
815 | 94.34%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank Citing Paper Year Venue Pagerank
246 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00030949575
334 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00027081079
688 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00018134733
880 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015667998
1,389 The Input/Output Complexity Of Transitive Closure 1990 SIGMOD 0.00012260807
1,553 A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011 SIGMOD 0.00011402871
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
2,675 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 8.3315228e-05
7,181 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.8074621e-05
7,226 Efficient Search in Very Large Databases 1988 VLDB 4.7953551e-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
10,404 Dynamic Pruning for Recursive Joins 2025 SIGMOD 4.1945683e-05
12,846 Database Graph Views : A Practical Model to Manage Persistent Graphs 1994 VLDB 4.1945683e-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
10 Benchmarking Database Systems: A Systematic Approach 1983 VLDB 0.0012103754
78 Multiprocessor Hash-Based Join Algorithms 1985 VLDB 0.00056413752
175 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.00038338694
1,055 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014422575
1,648 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 0.00011028408
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
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
688 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00018134733
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
1,055 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014422575
786 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016660109
880 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015667998