dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

A Performance Study of Transitive Closure Algorithms.

Shaul Dar, Raghu Ramakrishnan: A Performance Study of Transitive Closure Algorithms. SIGMOD Conference 1994: 454-465
@inproceedings{DBLP:conf/sigmod/DarR94,
  author    = {Shaul Dar and
               Raghu Ramakrishnan},
  editor    = {Richard T. Snodgrass and
               Marianne Winslett},
  title     = {A Performance Study of Transitive Closure Algorithms},
  booktitle = {Proceedings of the 1994 ACM SIGMOD International Conference on
               Management of Data, Minneapolis, Minnesota, May 24-27, 1994},
  publisher = {ACM Press},
  year      = {1994},
  pages     = {454-465},
  ee        = {http://doi.acm.org/10.1145/191839.191928},
  crossref  = {DBLP:conf/sigmod/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present a comprehensive performance evaluation of transitive closure (reachability) algorithms for databases. The study is based upon careful implementations of the algorithms, measures page I/O, and covers algorithms for full transitive closure as well as partial transitive closure (finding all successors of each node in a set of given source nodes). We examine a wide range of acyclic graphs with varying density and "locality" of arcs in the graph. We also consider query parameters such as the selectivity of the query, and system parameters such as the buffer size and the page and successor list replacement policies. We show that significant cost tradeoffs exist between the algorithms in this spectrum and identify the factors that influence the performance of the algorithms.

An important aspect of our work is that we measure a number of different cost metrics, giving us a good understanding of the predictive power of these metrics with respect to I/O cost. This is especially significant since metrics such as number of tuples generated or number of successor list operations have been widely used to compare transitive closure algorithms in the literature. Our results strongly suggest that these other metrics cannot be reliably used to predict I/O cost of transitive closure evaluation.

Copyright © 1994 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Richard T. Snodgrass, Marianne Winslett (Eds.): Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, May 24-27, 1994. ACM Press 1994 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 23(2), June 1994
Contents

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1278 KB]

References

[1]
Rakesh Agrawal, H. V. Jagadish: Direct Algorithms for Computing the Transitive Closure of Database Relations. VLDB 1987: 255-266 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Rakesh Agrawal, H. V. Jagadish: Hybrid Transitive Closure Algorithms. VLDB 1990: 326-334 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Rakesh Agrawal, Shaul Dar, H. V. Jagadish: Direct Transitive Closure Algorithms: Design and Performance Evaluation. ACM Trans. Database Syst. 15(3): 427-458(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Shaul Dar, H. V. Jagadish: A Spanning Tree Transitive Closure Algorithm. ICDE 1992: 2-11 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Shaul Dar: Augmenting Databases with Generalized Transitive Closure. Ph.D. thesis, Univ. of Wisconsin-Madison 1993
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Jürgen Ebert: A Sensitive Transitive Closure Algorithm. Inf. Process. Lett. 12(5): 255-258(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
J. Eve, Reino Kurki-Suonio: On Computing the Transitive Closure of a Relation. Acta Inf. 8: 303-314(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
A. Goralciková, Václav Koubek: A Reduct-and-Closure Algorithm for Graphs. MFCS 1979: 301-307 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Kien A. Hua, Jeffrey X. W. Su, Chau M. Hua: Efficient Evaluation of Traversal Recursive Queries Using Connectivity Index. ICDE 1993: 549-558 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Yannis E. Ioannidis, Raghu Ramakrishnan, Linda Winger: Transitive Closure Algorithms Based on Graph Traversal. ACM Trans. Database Syst. 18(3): 512-576(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Håkan Jakobsson: Mixed-Approach Algorithms for Transitive Closure. PODS 1991: 199-205 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Håkan Jakobsson: On Tree-Based Techniques for Query Evaluation. PODS 1992: 380-392 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
...
[17]
...
[18]
Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Robert Kabler, Yannis E. Ioannidis, Michael J. Carey: Performance evaluation of algorithms for transitive closure. Inf. Syst. 17(5): 415-441(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
Inderpal Singh Mumick, Hamid Pirahesh: Overbound and Right-Linear Queries. PODS 1991: 127-141 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Jeffrey F. Naughton, Raghu Ramakrishnan, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Evaluation of Right-, Left-, and Mult-Lineare Rules. SIGMOD Conference 1989: 235-242 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
...
[23]
Lothar Schmitz: An Exercise in Program Synthesis: Algorithms for Computing the Transitive Closure of a Relation. Sci. Comput. Program. 1(3): 235-254(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
Claus-Peter Schnorr: An Algorithm for Transitive Closure with Linear Expected Time. SIAM J. Comput. 7(2): 127-133(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
Jeffrey D. Ullman, Mihalis Yannakakis: The Input/Output Complexity of Transitive Closure. SIGMOD Conference 1990: 44-53 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
Henry S. Warren Jr.: A Modification of Warshall's Algorithm for the Transitive Closure of Binary Relations. Commun. ACM 18(4): 218-220(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
Stephen Warshall: A Theorem on Boolean Matrices. J. ACM 9(1): 11-12(1962) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[28]
Mihalis Yannakakis: Graph-Theoretic Methods in Database Theory. PODS 1990: 230-242 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Tue Sep 18 00:25:11 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page