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

@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

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb8997 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[1]

Rakesh Agrawal, H. V. Jagadish: Multiprocessor Transitive Closure Algorithms. DPDS 1988: 56-66

[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)

[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

[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)

[7]

Stefano Ceri, Georg Gottlob, Luigi Lavazza: Translation and Optimization of Logic Queries: The Algebraic Approach. VLDB 1986: 395-402

[8]

Stefano Ceri, Georg Gottlob, Letizia Tanca: Logic Programming and Databases. Springer 1990, ISBN 3-540-51728-6

[9]

Jean-Pierre Cheiney, Christophe de Maindreville: A Parallel Strategy for Transitive Closure usind Double Hash-Based Clustering. VLDB 1990: 347-358

[10]

Sumit Ganguly, Abraham Silberschatz, Shalom Tsur: A Framework for the Parallel Processing of Datalog Queries. SIGMOD Conference 1990: 143-152

[11]

Paul W. P. J. Grefen, Peter M. G. Apers: Parallel Handling of Integrity Constraints on Fragmented Relations. DPDS 1990: 138-145

[12]

Maurice A. W. Houtsma, Peter M. G. Apers: Algebraic optimization of recursive queries. Data Knowl. Eng. 7: 299-325(1991)

[13]

Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Distributed Transitive Closure Computations: The Disconnection Set Approach. VLDB 1990: 335-346

[14]

Maurice A. W. Houtsma, Peter M. G. Apers, Stefano Ceri: Complex Transitive Closure Queries on a Fragmented Graph. ICDT 1990: 470-484

[15]

Maurice A. W. Houtsma, Peter M. G. Apers, Gideon L. V. Schipper: Data fragmentation for parallel transitive closure strategies. ICDE 1993: 447-456

[16]

Maurice A. W. Houtsma, Filippo Cacace, Stefano Ceri: Parallel Hierarchical Evaluation of Tranitive Closure Queries. PDIS 1991: 130-137

[17]

Kien A. Hua, Sridhar Hannenhalli: Parallel Transitive Closure Computations Using Topological Sort. PDIS 1991: 122-129

[18]

Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411

[19]

Bin Jiang: A Suitable Algorithm for Computing Partial Transitive Closures in Databases. ICDE 1990: 264-271

[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

[21]

Per-Åke Larson, Vinay Deshpande: A File Structure Supporting Traversal Recursion. SIGMOD Conference 1989: 243-252

[22]

Ismail H. Toroslu, Ghassan Z. Qadah: The Efficient Computation of Strong Partial Transitive-Closures. ICDE 1993: 530-537

[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

[24]

...

[25]

Annita N. Wilschut, Peter M. G. Apers: Dataflow Query Execution in a Parallel Main-Memory Environment. PDIS 1991: 68-77

[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

[27]

Ouri Wolfson, Aya Ozeri: A New Paradigm for Parallel and Distributed Rule-Processing. SIGMOD Conference 1990: 133-142