ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Implementation and Performance Evaluation of a Parallel Transitive Closure Algorithm on PRISMA/DB.

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
@inproceedings{DBLP:conf/vldb/HoutsmaWF93,
  author    = {Maurice A. W. Houtsma and
               Annita N. Wilschut and
               Jan Flokstra},
  editor    = {Rakesh Agrawal and
               Se{\'a}n Baker and
               David A. Bell},
  title     = {Implementation and Performance Evaluation of a Parallel Transitive
               Closure Algorithm on PRISMA/DB},
  booktitle = {19th International Conference on Very Large Data Bases, August
               24-27, 1993, Dublin, Ireland, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1993},
  isbn      = {1-55860-152-X},
  pages     = {206-217},
  ee        = {db/conf/vldb/HoutsmaWF93.html},
  crossref  = {DBLP:conf/vldb/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper is one of the first to discuss actual implementation of and experimentation with parallel transitive closure operations on a full-fledged relational database system. It brings two research efforts together; the development of an efficient execution strategy for parallel computation of path problems, called Disconnection Set Approach, and the development and implementation of a parallel, main-memory DBMS, called PRISMA/DB. First, we report on the implementation of the disconnection set approach on PRISMA/DB, showing how the latter's design allowed us to easily extend the functionality of the system. Second, we investigate the disconnection set approach's parallel behavior and performance by means of extensive experimentation.

It is shown that the parallel implementation of the disconnection set approach yields very good performance characteristics, and that (super)linear speedup w.r. t. a special implementation of semi-naive is achieved for regular, so-calledlinear fragmentations. We also present a number of experiments that show to what extent data fragmentation issues influence the performance. Finally, we discuss the speedup and benefits to be achieved for arbitrary fragmentations.

Copyright © 1993 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

Rakesh Agrawal, Seán Baker, David A. Bell (Eds.): 19th International Conference on Very Large Data Bases, August 24-27, 1993, Dublin, Ireland, Proceedings. Morgan Kaufmann 1993, ISBN 1-55860-152-X
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Rakesh Agrawal, H. V. Jagadish: Multiprocessor Transitive Closure Algorithms. DPDS 1988: 56-66 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Peter M. G. Apers, Carel A. van den Berg, Jan Flokstra, Paul W. P. J. Grefen, Martin L. Kersten, Annita N. Wilschut: PRISMA/DB: A Parallel Main Memory Relational DBMS. IEEE Trans. Knowl. Data Eng. 4(6): 541-554(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
...
[4]
François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
...
[6]
Filippo Cacace, Stefano Ceri, Maurice A. W. Houtsma: A Survey of Parallel Execution Strategies for Transitive Closure and Logic Programs. Distributed and Parallel Databases 1(4): 337-382(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Stefano Ceri, Georg Gottlob, Luigi Lavazza: Translation and Optimization of Logic Queries: The Algebraic Approach. VLDB 1986: 395-402 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Stefano Ceri, Georg Gottlob, Letizia Tanca: Logic Programming and Databases. Springer 1990, ISBN 3-540-51728-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
Jean-Pierre Cheiney, Christophe de Maindreville: A Parallel Strategy for Transitive Closure usind Double Hash-Based Clustering. VLDB 1990: 347-358 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Sumit Ganguly, Abraham Silberschatz, Shalom Tsur: A Framework for the Parallel Processing of Datalog Queries. SIGMOD Conference 1990: 143-152 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Paul W. P. J. Grefen, Peter M. G. Apers: Parallel Handling of Integrity Constraints on Fragmented Relations. DPDS 1990: 138-145 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Maurice A. W. Houtsma, Peter M. G. Apers: Algebraic optimization of recursive queries. Data Knowl. Eng. 7: 299-325(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Distributed Transitive Closure Computations: The Disconnection Set Approach. VLDB 1990: 335-346 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Complex Transitive Closure Queries on a Fragmented Graph. ICDT 1990: 470-484 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Maurice A. W. Houtsma, Peter M. G. Apers, Gideon L. V. Schipper: Data fragmentation for parallel transitive closure strategies. ICDE 1993: 447-456 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Maurice A. W. Houtsma, Filippo Cacace, Stefano Ceri: Parallel Hierarchical Evaluation of Tranitive Closure Queries. PDIS 1991: 130-137 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Kien A. Hua, Sridhar Hannenhalli: Parallel Transitive Closure Computations Using Topological Sort. PDIS 1991: 122-129 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
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
[19]
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
[20]
Martin L. Kersten, Peter M. G. Apers, Maurice A. W. Houtsma, Erik J. A. van Kuyk, Rob L. W. van de Weg: A Distributed, Main-Memory Database Machine. IWDM 1987: 353-369 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Per-Åke Larson, Vinay Deshpande: A File Structure Supporting Traversal Recursion. SIGMOD Conference 1989: 243-252 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
Ismail H. Toroslu, Ghassan Z. Qadah: The Efficient Computation of Strong Partial Transitive-Closures. ICDE 1993: 530-537 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
J. Shao, David A. Bell, M. Elizabeth C. Hull: An Experimental Performance Study of a Pipelined Recursive Query Processing Strategy. DPDS 1990: 30-43 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
...
[25]
Annita N. Wilschut, Peter M. G. Apers: Dataflow Query Execution in a Parallel Main-Memory Environment. PDIS 1991: 68-77 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
Annita N. Wilschut, Jan Flokstra, Peter M. G. Apers: Parallelism in a Main-Memory DBMS: The Performance of PRISMA/DB. VLDB 1992: 521-532 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
Ouri Wolfson, Aya Ozeri: A New Paradigm for Parallel and Distributed Rule-Processing. SIGMOD Conference 1990: 133-142 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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