ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Hybrid Transitive Closure Algorithms.

Rakesh Agrawal, H. V. Jagadish: Hybrid Transitive Closure Algorithms. VLDB 1990: 326-334
@inproceedings{DBLP:conf/vldb/AgrawalJ90,
  author    = {Rakesh Agrawal and
               H. V. Jagadish},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {Hybrid Transitive Closure Algorithms},
  booktitle = {16th International Conference on Very Large Data Bases, August
               13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1990},
  isbn      = {1-55860-149-X},
  pages     = {326-334},
  ee        = {db/conf/vldb/AgrawalJ90.html},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present a new family of hybrid transitive closure algorithms, and present experimental results showing that these algorithms perform better than existing transitive closure algorithms, including matrix-based algorithms that divide a matrix into stripes or into square blocks, and graph-based algorithms. This family of algorithms can be generalized to solve path problems and to solve problems in which some selection criteria have been specified for source ordestination nodes.

Copyright © 1990 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 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Dennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek (Eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings. Morgan Kaufmann 1990, ISBN 1-55860-149-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
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
[2]
Rakesh Agrawal: Alpha: An Extension of Relational Algebra to Express a Class of Recursive Queries. IEEE Trans. Software Eng. 14(7): 879-885(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
...
[4]
...
[5]
...
[6]
Isabel F. Cruz, Theodore S. Norvell: Aggregative Closure: An Extension of Transitive Closure. ICDE 1989: 384-391 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
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
[8]
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
[9]
Ulrich Güntzer, Werner Kießling, Rudolf Bayer: On the Evaluation of Recursion in (Deductive) Database Systems by Efficient Differential Fixpoint Iteration. ICDE 1987: 120-129 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
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
[11]
Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
H. V. Jagadish, Rakesh Agrawal, Linda Ness: A Study of Transitive Closure As a Recursion Mechanism. SIGMOD Conference 1987: 331-344 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Bin Jiang: Making the Partial Transitive Closure an Elementary Database Operation. BTW 1989: 231-245 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
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
[15]
Ru-Mei Kung, Eric N. Hanson, Yannis E. Ioannidis, Timos K. Sellis, Leonard D. Shapiro, Michael Stonebraker: Heuristic Search in Data Base Systems. Expert Database Workshop 1984: 537-548 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
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
[17]
...
[18]
...
[19]
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
[20]
...
[21]
Seppo Sippu, Eljas Soisalon-Soininen: A Generalized Transitive Closure for Relational Queries. PODS 1988: 325-332 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
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
[23]
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
[24]
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
[25]
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
[26]
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 © Fri Mar 12 17:22:50 2010 by Michael Ley (ley@uni-trier.de)