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: h7d1d35b3b46bd7c6
Venue: SIGMOD
Year: 1994
Pagerank: 7.2086693e-05
Overall Rank: 3,555 | 76.10%
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
303	Proximity Search in Databases	1998	VLDB	0.0002164278
557	Hexastore: Sextuple Indexing for Semantic Web Data Management	2008	VLDB	0.00016497067
3,694	OLAP over Imprecise Data with Domain Constraints	2007	VLDB	7.0927742e-05
5,695	Efficient Allocation Algorithms for OLAP over Imprecise Data	2006	VLDB	6.0334848e-05
8,628	Inferray: fast in-memory RDF inference	2016	VLDB	5.2995392e-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
352	On the Power of Magic	1987	PODS	0.00020223279
1,140	Direct Algorithms for Computing the Transitive Closure of Database Relations	1987	VLDB	0.00011853213
1,363	Efficient Transitive Closure Algorithms	1988	VLDB	0.00010914322
1,904	The Input/Output Complexity Of Transitive Closure	1990	SIGMOD	9.3991536e-05
1,979	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.2716242e-05
3,020	Graph-Theoretic Methods In Database Theory	1990	PODS	7.7448163e-05
3,675	Overbound and Right-Linear Queries	1991	PODS	7.1075276e-05
6,098	Mixed-Approach Algorithms for Transitive Closure	1991	PODS	5.8875106e-05
6,981	Hybrid Transitive Closure Algorithms	1990	VLDB	5.6287975e-05
8,195	On Tree-Based Techniques for Query Evaluation	1992	PODS	5.3798301e-05

Semantically Similar Papers

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