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: ha3983fce568c1041
Venue: VLDB
Year: 1987
Pagerank: 0.00011853213
Overall Rank: 1,140 | 92.34%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Rakesh Agrawal (AT&T)
2. H. V. Jagadish (AT&T)

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
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,329	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011000029
1,363	Efficient Transitive Closure Algorithms	1988	VLDB	0.00010914322
1,416	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010734049
1,904	The Input/Output Complexity Of Transitive Closure	1990	SIGMOD	9.3991536e-05
2,109	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD	9.0238479e-05
3,020	Graph-Theoretic Methods In Database Theory	1990	PODS	7.7448163e-05
3,555	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	7.2086693e-05
7,355	Efficient Search in Very Large Databases	1988	VLDB	5.5436083e-05
7,576	A Generalized Transitive Closure for Relational Queries	1988	PODS	5.4924986e-05
8,195	On Tree-Based Techniques for Query Evaluation	1992	PODS	5.3798301e-05
8,937	A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering	1990	VLDB	5.2559789e-05
10,431	cuRPQ: A High-Performance GPU-Based Framework for Processing Regular and Conjunctive Regular Path Queries	2026	SIGMOD	4.9793485e-05
11,126	Dynamic Pruning for Recursive Joins	2025	SIGMOD	4.9793485e-05
13,329	Database Graph Views: A Practical Model to Manage Persistent Graphs	1994	VLDB	4.9793485e-05

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
46	Benchmarking Database Systems: A Systematic Approach	1983	VLDB	0.00044784799
156	Multiprocessor Hash-Based Join Algorithms	1985	VLDB	0.00028522117
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
2,109	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD	9.0238479e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,195	On Tree-Based Techniques for Query Evaluation	1992	PODS
2	294	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD
3	8,937	A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering	1990	VLDB
4	7,576	A Generalized Transitive Closure for Relational Queries	1988	PODS
5	1,416	Estimating the Size of Generalized Transitive Closures	1989	VLDB
6	3,020	Graph-Theoretic Methods In Database Theory	1990	PODS
7	3,555	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD
8	1,287	On the Computation of the Transitive Closure of Relational Operators	1986	VLDB
9	1,110	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB
10	1,363	Efficient Transitive Closure Algorithms	1988	VLDB