DBScholar

Back to papers

New Strategies for Computing the Transitive Closure of a Database Relation

Summary: Two dynamic data-size reduction strategies introduced for computing the transitive closure, integrated into a hash-based algorithm. Empirical results show faster convergence to the least fixed point and outperformance of other approaches in most cases. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
8000
Venue
VLDB
Year
1987
Pagerank
0.00012252192
Overall Rank
1,086 | 92.56%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{lu_vldb87,
        title = {{New Strategies for Computing the Transitive Closure of a Database Relation}},
        author = {Lu, Hongjun},
        journal = {PVLDB},
        series = {{VLDB} '87},
        pages = {267--274},
        year = {1987}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 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,206 Random Sampling from Hash Files 1990 SIGMOD 0.00011663837
1,330 Efficient Transitive Closure Algorithms 1988 VLDB 0.00011140171
1,382 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010965236
2,957 Graph-Theoretic Methods In Database Theory 1990 PODS 7.9200375e-05
5,341 Distributed Transitive Closure Computations: The Disconnection Set Approach 1990 VLDB 6.2602701e-05
6,840 Hybrid Transitive Closure Algorithms 1990 VLDB 5.7575344e-05
7,438 A Generalized Transitive Closure for Relational Queries 1988 PODS 5.6184826e-05
7,680 Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs 1990 VLDB 5.5684407e-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 4 of 4 cited papers.

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

Rank Cited Paper Year Venue Pagerank
7 Implementation Techniques For Main Memory Database Systems 1984 SIGMOD 0.00083340894
63 An Amateur's Introduction to Recursive Query Processing Strategies 1986 SIGMOD 0.00038782376
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
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 5,341 Distributed Transitive Closure Computations: The Disconnection Set Approach 1990 VLDB
2 13,065 Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB 1993 VLDB
3 1,259 On the Computation of the Transitive Closure of Relational Operators 1986 VLDB
4 3,491 A Performance Study Of Transitive Closure Algorithms 1994 SIGMOD
5 7,438 A Generalized Transitive Closure for Relational Queries 1988 PODS
6 282 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD
7 1,382 Estimating the Size of Generalized Transitive Closures 1989 VLDB
8 1,330 Efficient Transitive Closure Algorithms 1988 VLDB
9 1,114 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB
10 8,775 A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering 1990 VLDB