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: 7809
Venue: VLDB
Year: 1987
Pagerank: 0.00016660109
Overall Rank: 786 | 94.54%
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
246	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030949575
334	Fast and Practical Indexing and Querying of Very Large Graphs	2007	SIGMOD	0.00027081079
688	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00018134733
783	Random Sampling from Hash Files	1990	SIGMOD	0.00016704834
880	Efficient Transitive Closure Algorithms	1988	VLDB	0.00015667998
2,474	Graph-Theoretic Methods In Database Theory	1990	PODS	8.7135761e-05
4,852	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB	5.8764777e-05
6,504	Hybrid Transitive Closure Algorithms	1990	VLDB	5.0357556e-05
7,090	Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs	1990	VLDB	4.8371966e-05
7,181	A Generalized Transitive Closure for Relational Queries	1988	PODS	4.8074621e-05
12,846	Database Graph Views : A Practical Model to Manage Persistent Graphs	1994	VLDB	4.1945683e-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.0014279444
77	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00057043861
175	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00038338694
1,055	On The Computation Of The Transitive Closure Of Relational Operators	1986	VLDB	0.00014422575

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,852	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB	5.8764777e-05
12,871	Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB	1993	VLDB	4.1945683e-05
1,055	On The Computation Of The Transitive Closure Of Relational Operators	1986	VLDB	0.00014422575
2,675	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	8.3315228e-05
7,181	A Generalized Transitive Closure for Relational Queries	1988	PODS	4.8074621e-05
246	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.00030949575
688	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00018134733
880	Efficient Transitive Closure Algorithms	1988	VLDB	0.00015667998
815	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00016369666
8,572	A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering	1990	VLDB	4.4937074e-05