A Performance Study Of Transitive Closure Algorithms

Summary: Comprehensive evaluation of transitive-closure algorithms in a uniform framework, focusing on page I/O, buffering, and full/partial reachability across DAGs. Finds standard metrics do not predict I/O cost and proposes a DAG-height/width workload model from a single traversal. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2810
Venue: SIGMOD
Year: 1994
Pagerank: 7.3658999e-05
Overall Rank: 3,491 | 76.05%
DOI: 10.1145/191839.191928

Incoming Non-self Citations Over Time

Authors

1. Shaul Dar (AT&T; University of Wisconsin)
2. Raghu Ramakrishnan (University of Wisconsin)

BibTeX Citation

@inproceedings{dar_sigmod94,
        title = {{A PERFORMANCE STUDY OF TRANSITIVE CLOSURE ALGORITHMS}},
        author = {Dar, Shaul and Ramakrishnan, Raghu},
        series = {{SIGMOD} '94},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/191839.191928},
        url = {https://dl.acm.org/doi/10.1145/191839.191928},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
301	Proximity Search in Databases	1998	VLDB	0.00022032878
542	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00016838296
3,619	OLAP over Imprecise Data with Domain Constraints	2007	VLDB	7.2508853e-05
5,565	Efficient Allocation Algorithms for OLAP over Imprecise Data	2006	VLDB	6.171506e-05
8,462	Inferray: fast in-memory RDF inference	2016	VLDB	5.4211759e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
344	On the Power of Magic	1987	PODS	0.00020659405
1,114	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00012118382
1,330	Efficient Transitive Closure Algorithms	1988	VLDB	0.00011140171
1,855	The Input/Output Complexity Of Transitive Closure	1990	SIGMOD	9.606146e-05
1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.4809066e-05
2,957	Graph-Theoretic Methods In Database Theory	1990	PODS	7.9200375e-05
3,603	Overbound and Right-Linear Queries	1991	PODS	7.2683975e-05
5,975	Mixed-Approach Algorithms for Transitive Closure	1991	PODS	6.0220239e-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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,259	On the Computation of the Transitive Closure of Relational Operators	1986	VLDB
2	1,382	Estimating the Size of Generalized Transitive Closures	1989	VLDB
3	7,438	A Generalized Transitive Closure for Relational Queries	1988	PODS
4	13,065	Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB	1993	VLDB
5	8,035	On Tree-Based Techniques for Query Evaluation	1992	PODS
6	2,957	Graph-Theoretic Methods In Database Theory	1990	PODS
7	8,775	A Parallel Strategy for Transitive Closure using Double Hash-Based Clustering	1990	VLDB
8	1,086	New Strategies for Computing the Transitive Closure of a Database Relation	1987	VLDB
9	1,114	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB
10	1,330	Efficient Transitive Closure Algorithms	1988	VLDB