DBScholar

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
7999
Venue
VLDB
Year
1987
Pagerank
0.00012118382
Overall Rank
1,114 | 92.36%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{agrawal_vldb87,
        title = {{Direct Algorithms for Computing the Transitive Closure of Database Relations}},
        author = {Agrawal, Rakesh and Jagadish, H. V.},
        journal = {PVLDB},
        series = {{VLDB} '87},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank Citing Paper Year Venue Pagerank
282 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.0002242162
322 Fast and Practical Indexing and Querying of Very Large Graphs 2007 SIGMOD 0.00021275303
1,301 A Memory Efficient Reachability Data Structure Through Bit Vector Compression 2011 SIGMOD 0.00011255351
1,330 Efficient Transitive Closure Algorithms 1988 VLDB 0.00011140171
1,382 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010965236
1,855 The Input/Output Complexity Of Transitive Closure 1990 SIGMOD 9.606146e-05
2,076 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 9.212586e-05
2,957 Graph-Theoretic Methods In Database Theory 1990 PODS 7.9200375e-05
3,491 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD 7.3658999e-05
7,342 Efficient Search in Very Large Databases 1988 VLDB 5.6386997e-05
7,438 A Generalized Transitive Closure for Relational Queries 1988 PODS 5.6184826e-05
8,035 On Tree-Based Techniques for Query Evaluation 1992 PODS 5.5028526e-05
8,775 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB 5.3766157e-05
10,215 cuRPQ: A High-Performance GPU-Based Framework for Processing Regular and Conjunctive Regular Path Queries 2026 SIGMOD 5.093636e-05
10,690 Dynamic Pruning for Recursive Joins 2025 SIGMOD 5.093636e-05
13,039 Database Graph Views: A Practical Model to Manage Persistent Graphs 1994 VLDB 5.093636e-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
45 Benchmarking Database Systems: A Systematic Approach 1983 VLDB 0.00045531113
152 Multiprocessor Hash-Based Join Algorithms 1985 VLDB 0.00029038365
217 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.00024458594
1,259 On the Computation of the Transitive Closure of Relational Operators 1986 VLDB 0.00011437537
2,076 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 9.212586e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 8,035 On Tree-Based Techniques for Query Evaluation 1992 PODS
2 282 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD
3 8,775 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB
4 7,438 A Generalized Transitive Closure for Relational Queries 1988 PODS
5 1,382 Estimating the Size of Generalized Transitive Closures 1989 VLDB
6 2,957 Graph-Theoretic Methods In Database Theory 1990 PODS
7 3,491 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD
8 1,259 On the Computation of the Transitive Closure of Relational Operators 1986 VLDB
9 1,086 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB
10 1,330 Efficient Transitive Closure Algorithms 1988 VLDB