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: 7810
Venue: VLDB
Year: 1987
Pagerank: 0.00016580866
Overall Rank: 792 | 94.50%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Hongjun Lu

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 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
764	Random Sampling from Hash Files	1990	SIGMOD	0.00016958917
885	Efficient Transitive Closure Algorithms	1988	VLDB	0.00015565543
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
4,855	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB	5.8698466e-05
6,499	Hybrid Transitive Closure Algorithms	1990	VLDB	5.0307246e-05
7,086	Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs	1990	VLDB	4.8325254e-05
7,182	A Generalized Transitive Closure for Relational Queries	1988	PODS	4.802834e-05
12,855	Database Graph Views : A Practical Model to Manage Persistent Graphs	1994	VLDB	4.1905499e-05

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
9	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.001426258
79	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00056010993
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

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,855	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB	5.8698466e-05
12,881	Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB	1993	VLDB	4.1905499e-05
1,078	On The Computation Of The Transitive Closure Of Relational Operators	1986	VLDB	0.00014223265
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
255	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030342925
897	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00015484372
885	Efficient Transitive Closure Algorithms	1988	VLDB	0.00015565543
815	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.0001629507
8,569	A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering	1990	VLDB	4.4893996e-05