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

A Parallel Strategy for Transitive Closure usind Double Hash-Based Clustering.

Jean-Pierre Cheiney, Christophe de Maindreville: A Parallel Strategy for Transitive Closure usind Double Hash-Based Clustering. VLDB 1990: 347-358
@inproceedings{DBLP:conf/vldb/CheineyM90,
  author    = {Jean-Pierre Cheiney and
               Christophe de Maindreville},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {A Parallel Strategy for Transitive Closure usind Double Hash-Based
               Clustering},
  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     = {347-358},
  ee        = {db/conf/vldb/CheineyM90.html},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present a parallel algorithm to compute the transitive closure of a relation. The transitive closure operation has been recognized as an important extensionof the relational algebra. The importance of the performance problem brought by its evaluation brings oneto consider parallel execution strategies. Such strategies constitute one of the keys to efficiency in a very large data base environment. The innovative aspects of the presented algorithm concern: 1) the possibility of working with a reasonable amount of memory space without creating extra Inputs/Outputs; 2) the use of on-disk clustering accomplished by double hashing; and 3) the parallelization of the transitive closure operation. The processing time is reduced by a factor of p, where p is the number of processors allocated for the operation. Communication times remain limited; a cyclic organization eliminates the need for serialization of transfers. The evaluation in a shared nothing architecture, shows the benefits of the proposed parallel transitive algorithm.

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

[AGRA87]
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
[AGRA89]
Rakesh Agrawal, Alexander Borgida, H. V. Jagadish: Efficient Management of Transitive Relationships in Large Data and Knowledge Bases. SIGMOD Conference 1989: 253-262 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BANC86]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CHEI86]
Jean-Pierre Cheiney, Pascal Faudemay, Rodolphe Michel, Jean-Marc Thévenin: A Reliable Backend Using Multiattribute Clustering and Select-Join Operator. VLDB 1986: 220-227 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CHEI89]
Jean-Pierre Cheiney, Christophe de Maindreville: Relational Storage and Efficient Retrieval of Rules in a Deductive DBMS. ICDE 1989: 644-651 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DEWI84]
David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DEWI86]
David J. DeWitt, Robert H. Gerber, Goetz Graefe, Michael L. Heytens, Krishna B. Kumar, M. Muralikrishna: GAMMA - A High Performance Dataflow Database Machine. VLDB 1986: 228-237 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GARD84]
Georges Gardarin, Patrick Valduriez, Yann Viémont: Predicate Trees: An Approach to Optimize Relational Query Operations. ICDE 1984: 439-444 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GARD86]
...
[GARD88]
...
[HAN88]
Jiawei Han, Ghassan Z. Qadah, Chinying Chaou: The Processing and Evaluation of Transitive Closure Queries. EDBT 1988: 49-75 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HSIA85]
Steven A. Demurjian, David K. Hsiao: Benchmarking Database Systems in Multiple Systems in Multiple Backend Configurations. IEEE Database Eng. Bull. 8(1): 29-39(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[IOAN88]
Yannis E. Ioannidis, Raghu Ramakrishnan: Efficient Transitive Closure Algorithms. VLDB 1988: 382-394 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KITS83]
Masaru Kitsuregawa, Hidehiko Tanaka, Tohru Moto-Oka: Application of Hash to Data Base Machine and Its Architecture. New Generation Comput. 1(1): 63-74(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KUBL88]
...
[SCHN89]
Donovan A. Schneider, David J. DeWitt: A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment. SIGMOD Conference 1989: 110-121 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[VALD86]
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
[VALD88a]
Patrick Valduriez, Setrag Khoshafian: Transitive Closure of Transitively Closed Relations. Expert Database Conf. 1988: 377-400 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[VALD88b]
...

Referenced by

  1. Weining Zhang, Ke Wang, Siu-Cheung Chau: Data Partition and Parallel Evaluation of Datalog Programs. IEEE Trans. Knowl. Data Eng. 7(1): 163-176(1995)
  2. Qi Yang, Clement T. Yu, Chengwen Liu, Son Dao, Gaoming Wang, Tracy Pham: A Hybrid Transitive Closure Algorithm for Sequential and Parallel Processing. ICDE 1994: 498-505
  3. Wolfgang Nejdl, Stefano Ceri, Gio Wiederhold: Evaluating Recursive Queries in Distributed Databases. IEEE Trans. Knowl. Data Eng. 5(1): 104-121(1993)
  4. Maurice A. W. Houtsma, Annita N. Wilschut, Jan Flokstra: Implementation and Performance Evaluation of a Parallel Transitive Closure Algorithm on PRISMA/DB. VLDB 1993: 206-217
  5. Jean-Pierre Cheiney, Gerald Kiernan, Christophe de Maindreville: A Database Rule Language Compiler Supporting Parallelism. DASFAA 1993: 279-286
  6. Yan-Nong Huang, Jean-Pierre Cheiney: Parallel Computation of Direct Transitive Closures. ICDE 1991: 192-199

Last update Fri Sep 14 17:38:12 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