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)
Incoming Non-self Citations Over Time
Authors
- 1. Hongjun Lu (Honeywell; National University of Singapore)
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 |
|---|---|---|---|---|
| 294 | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases | 1989 | SIGMOD | 0.00021927874 |
| 330 | Fast and Practical Indexing and Querying of Very Large Graphs | 2007 | SIGMOD | 0.00020838159 |
| 1,229 | Random Sampling from Hash Files | 1990 | SIGMOD | 0.00011420642 |
| 1,363 | Efficient Transitive Closure Algorithms | 1988 | VLDB | 0.00010914322 |
| 1,416 | Estimating the Size of Generalized Transitive Closures | 1989 | VLDB | 0.00010734049 |
| 3,020 | Graph-Theoretic Methods In Database Theory | 1990 | PODS | 7.7448163e-05 |
| 5,451 | Distributed Transitive Closure Computations: The Disconnection Set Approach | 1990 | VLDB | 6.1243992e-05 |
| 6,981 | Hybrid Transitive Closure Algorithms | 1990 | VLDB | 5.6287975e-05 |
| 7,576 | A Generalized Transitive Closure for Relational Queries | 1988 | PODS | 5.4924986e-05 |
| 7,835 | Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs | 1990 | VLDB | 5.4436011e-05 |
| 13,329 | Database Graph Views: A Practical Model to Manage Persistent Graphs | 1994 | VLDB | 4.9793485e-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.00081992507 |
| 67 | An Amateur's Introduction to Recursive Query Processing Strategies | 1986 | SIGMOD | 0.00038009523 |
| 225 | Traversal Recursion: A Practical Approach to Supporting Recursive Applications | 1986 | SIGMOD | 0.00023995155 |
| 1,287 | On the Computation of the Transitive Closure of Relational Operators | 1986 | VLDB | 0.00011184757 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,451 | Distributed Transitive Closure Computations: The Disconnection Set Approach | 1990 | VLDB |
| 2 | 13,355 | Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB | 1993 | VLDB |
| 3 | 1,287 | On the Computation of the Transitive Closure of Relational Operators | 1986 | VLDB |
| 4 | 3,555 | A Performance Study Of Transitive Closure Algorithms | 1994 | SIGMOD |
| 5 | 7,576 | A Generalized Transitive Closure for Relational Queries | 1988 | PODS |
| 6 | 294 | Efficient Management of Transitive Relationships in Large Data and Knowledge Bases | 1989 | SIGMOD |
| 7 | 1,416 | Estimating the Size of Generalized Transitive Closures | 1989 | VLDB |
| 8 | 1,363 | Efficient Transitive Closure Algorithms | 1988 | VLDB |
| 9 | 1,140 | Direct Algorithms for Computing the Transitive Closure of Database Relations | 1987 | VLDB |
| 10 | 8,937 | A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering | 1990 | VLDB |