Efficient Transitive Closure Algorithms

Summary: Presents efficient directed-graph transitive-closure/reachability algorithms, extensible to path queries and broader one-sided recursions. Analytical and empirical comparisons show strong performance, especially for disk-based database systems. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8059
Venue: VLDB
Year: 1988
Pagerank: 0.00011140171
Overall Rank: 1,330 | 90.88%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Yannis E. Ioannidis (University of Wisconsin)
2. Raghu Ramakrishnan (University of Wisconsin)

BibTeX Citation

@article{ioannidis_vldb88,
        title = {{Efficient Transitive Closure Algorithms}},
        author = {Ioannidis, Yannis E. and Ramakrishnan, Raghu},
        journal = {PVLDB},
        series = {{VLDB} '88},
        pages = {382},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
282	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD	0.0002242162
1,382	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010965236
1,658	Finding Regular Simple Paths in Graph Databases	1989	VLDB	0.00010092304
1,855	The Input/Output Complexity Of Transitive Closure	1990	SIGMOD	9.606146e-05
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
3,491	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD	7.3658999e-05
5,341	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB	6.2602701e-05
5,975	Mixed-Approach Algorithms for Transitive Closure	1991	PODS	6.0220239e-05
6,031	Sia: Optimizing Queries using Learned Predicates	2021	SIGMOD	6.0007422e-05
6,840	Hybrid Transitive Closure Algorithms	1990	VLDB	5.7575344e-05
8,035	On Tree-Based Techniques for Query Evaluation	1992	PODS	5.5028526e-05
8,775	A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering	1990	VLDB	5.3766157e-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
217	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00024458594
1,086	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB	0.00012252192
1,114	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00012118382
1,259	On the Computation of the Transitive Closure of Relational Operators	1986	VLDB	0.00011437537
2,033	One-Sided Recursions	1987	PODS	9.2819369e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,259	On the Computation of the Transitive Closure of Relational Operators	1986	VLDB
2	8,035	On Tree-Based Techniques for Query Evaluation	1992	PODS
3	282	Efficient Management of Transitive Relationships in Large Data and Knowledge Bases	1989	SIGMOD
4	8,775	A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering	1990	VLDB
5	7,438	A Generalized Transitive Closure for Relational Queries	1988	PODS
6	5,975	Mixed-Approach Algorithms for Transitive Closure	1991	PODS
7	2,957	Graph-Theoretic Methods In Database Theory	1990	PODS
8	1,086	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB
9	3,491	A Performance Study Of Transitive Closure Algorithms	1994	SIGMOD
10	1,114	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB