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
7809
Venue
VLDB
Year
1987
Pagerank
0.0001629507
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
255 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00030342925
334 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00027077424
885 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015565543
897 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00015484372
1,389 The Input/Output Complexity Of Transitive Closure 1990 SIGMOD 0.00012247602
1,551 A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011 SIGMOD 0.00011395294
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
2,679 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 8.3223476e-05
7,182 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.802834e-05
7,225 Efficient Search in Very Large Databases 1988 VLDB 4.7910249e-05
7,289 On Tree-Based Techniques for Query Evaluation 1992 PODS 4.7692311e-05
8,569 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB 4.4893996e-05
10,415 Dynamic Pruning for Recursive Joins 2025 SIGMOD 4.1905499e-05
12,855 Database Graph Views : A Practical Model to Manage Persistent Graphs 1994 VLDB 4.1905499e-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.0012093675
77 Multiprocessor Hash-Based Join Algorithms 1985 VLDB 0.00056488357
157 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.0004048407
1,078 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014223265
1,905 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 0.00010142772
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
7,289 On Tree-Based Techniques for Query Evaluation 1992 PODS 4.7692311e-05
255 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00030342925
8,569 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB 4.4893996e-05
7,182 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.802834e-05
897 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00015484372
2,473 Graph-Theoretic Methods In Database Theory 1990 PODS 8.7048914e-05
2,679 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 8.3223476e-05
1,078 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014223265
792 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016580866
885 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015565543