ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Efficient Transitive Closure Algorithms.

Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394
@inproceedings{DBLP:conf/vldb/IoannidisR88,
  author    = {Yannis E. Ioannidis and
               Raghu Ramakrishnan},
  editor    = {Fran\c{c}ois Bancilhon and
               David J. DeWitt},
  title     = {Efficient Transitive Closure Algorithms},
  booktitle = {Fourteenth International Conference on Very Large Data Bases,
               August 29 - September 1, 1988, Los Angeles, California, USA,
               Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1988},
  isbn      = {0-934613-75-3},
  pages     = {382-394},
  ee        = {db/conf/vldb/IoannidisR88.html},
  crossref  = {DBLP:conf/vldb/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We have developed some efficient algorithms for computing the transitive closure of a directed graph. This paper presents the algorithms for the problem of reachability. The algorithms, however, can be adapted to deal with path computations and a significantly broader class of queries based on one-sided recursions. We analyze these algorithms and compare them to algorithms in the literature. The results indicate that these algorithms, in addition to their ability to deal with queries that are generalizations of transitive closure, also perform very efficiently, in particular, in the context of a disk-based database environment.

Copyright © 1988 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

François Bancilhon, David J. DeWitt (Eds.): Fourteenth International Conference on Very Large Data Bases, August 29 - September 1, 1988, Los Angeles, California, USA, Proceedings. Morgan Kaufmann 1988, ISBN 0-934613-75-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Journal Version

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

References

[Agrawal and Jagadish 87]
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
[Agrawal et al. 87]
...
[Agrawal and Jagadish 88]
...
[Aho et al. 74]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bancilhon 85]
...
[Carre 79]
...
[Dijkstra 59]
...
[Eve and Kurik-Suonio 77]
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
[Ioannidis 86]
Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ioannidis and Ramakrishnan 88]
...
[Lu 87]
Hongjun Lu: New Strategies for Computing the Transitive Closure of a Database Relation. VLDB 1987: 267-274 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Lu, Mikkilineni and Richardson 87]
Hongjun Lu, Krishna P. Mikkilineni, James P. Richardson: Design and Evaluation of Algorithms to Compute the Transitive Closure of a Database Relation. ICDE 1987: 112-119 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Naughton 87]
Jeffrey F. Naughton: One-Sided Recursions. PODS 1987: 340-348 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rosenthal et al. 86]
Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Schmitz 83]
...
[Schnorr 78]
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
[Tarjan 72]
Robert Endre Tarjan: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2): 146-160(1972) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Valduriez and Boral 86]
Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Warren 75]
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
[Warshall 62]
Stephen Warshall: A Theorem on Boolean Matrices. J. ACM 9(1): 11-12(1962) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:00 2010 by Michael Ley (ley@uni-trier.de)