Implementation and Analysis of a Parallel Collection Query Language.

Dan Suciu: Implementation and Analysis of a Parallel Collection Query Language. VLDB 1996: 366-377

@inproceedings{DBLP:conf/vldb/Suciu96a,
  author    = {Dan Suciu},
  editor    = {T. M. Vijayaraman and
               Alejandro P. Buchmann and
               C. Mohan and
               Nandlal L. Sarda},
  title     = {Implementation and Analysis of a Parallel Collection Query Language},
  booktitle = {VLDB'96, Proceedings of 22th International Conference on Very
               Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India},
  publisher = {Morgan Kaufmann},
  year      = {1996},
  isbn      = {1-55860-382-4},
  pages     = {366-377},
  ee        = {db/conf/vldb/Suciu96a.html},
  crossref  = {DBLP:conf/vldb/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We study implementation techniques for a parallel query language for nested collections. The language handles collections of three kinds (sets, bags, and sequences), and its expressive power is essentially that of OQL (ODMG93). From the perspective of parallel evaluation, the novelty of such a query language is that it can express nested parallelism, which is naturally associated to nested collections. The first implementation step is a translation into a specially designed algebra for flat sequences, having only flat parallelism: the translation ``flattens'' the nested parallelism, and we prove that it preserves the asymptotic parallel complexity. The second step consists in an implementation of the sequence algebra on a shared nothing architecture. Here we show that all data communications needed by the sequence algebra operators (with one exception) have a particular communication pattern, called monotone communication. We give a provably optimal algorithm for monotone communications on a shared nothing architecture. Here ``optimal'' means that for any particular initial and final data layout, its communication cost is absolute minimum (not within a constant factor). To account for the communication costs we chose as shared nothing model the recently proposed LogP model. Finally we report some preliminary experiments of our implementation techniques, on a LogP simulator.

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

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

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

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

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

T. M. Vijayaraman, Alejandro P. Buchmann, C. Mohan, Nandlal L. Sarda (Eds.): VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases, September 3-6, 1996, Mumbai (Bombay), India. Morgan Kaufmann 1996, ISBN 1-55860-382-4
Contents

Electronic Edition

References

[AB88]: Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995)
[ABD+92]: Malcolm P. Atkinson, François Bancilhon, David J. DeWitt, Klaus R. Dittrich, David Maier, Stanley B. Zdonik: The Object-Oriented Database System Manifesto. DOOD 1989: 223-240
[AISS95]: Albert Alexandrov, Mihai F. Ionescu, Klaus E. Schauser, Chris J. Scheiman: LogGP: Incorporating Long Messages into the LogP Model - One Step Closer Towards a Realistic Model for Parallel Computation. SPAA 1995: 95-105
[BBKV87]: François Bancilhon, Ted Briggs, Setrag Khoshafian, Patrick Valduriez: FAD, a Powerful and Simple Database Language. VLDB 1987: 97-105
[BBW92]: Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154
[Ble90]: Guy E. Blelloch: Vector Models for Data-Parallel Computing. MIT Press 1990, ISBN 0-262-02313-X
[Ble94]: ...
[BS90]: ...
[Cat94]: R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.1). Morgan Kaufmann 1994
[CDF+94]: Michael J. Carey, David J. DeWitt, Michael J. Franklin, Nancy E. Hall, Mark L. McAuliffe, Jeffrey F. Naughton, Daniel T. Schuh, Marvin H. Solomon, C. K. Tan, Odysseas G. Tsatalos, Seth J. White, Michael J. Zwilling: Shoring Up Persistent Applications. SIGMOD Conference 1994: 383-394
[CDN93]: Michael J. Carey, David J. DeWitt, Jeffrey F. Naughton: The oo7 Benchmark. SIGMOD Conference 1993: 12-21
[CKP+93]: David E. Culler, Richard M. Karp, David A. Patterson, Abhijit Sahay, Klaus E. Schauser, Eunice E. Santos, Ramesh Subramonian, Thorsten von Eicken: LogP: Towards a Realistic Model of Parallel Computation. PPOPP 1993: 1-12
[Deu90]: O. Deux: The Story of O2. IEEE Trans. Knowl. Data Eng. 2(1): 91-108(1990)
[DG92]: David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992)
[FM95]: Leonidas Fegaras, David Maier: Towards an Effective Calculus for Object Query Languages. SIGMOD Conference 1995: 47-58
[GCKL93]: Shahram Ghandeharizadeh, Vera Choi, Clifford Ker, Kai-Ming Lin: Design and Implementation of the Omega Object-Based System. Australian Database Conference 1993: 198-209
[GWLZ93]: Shahram Ghandeharizadeh, David Wilhite, Kai-Ming Lin, Xiaoming Zhao: Object Placement in Parallel Object-Oriented Database Systems. ICDE 1994: 253-262
[Jaj92]: Joseph JáJá: An Introduction to Parallel Algorithms. Addison-Wesley 1992, ISBN 0-201-54856-9
[KSSS93]: ...
[PSV92]: Douglas Stott Parker Jr., Eric Simon, Patrick Valduriez: SVP: A Model Capturing Sets, Lists, Streams, and Parallelism. VLDB 1992: 115-126
[SD89]: 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
[ST94]: ...
[Suc95]: ...
[TM94]: Lewis W. Tucker, Alan M. Mainwaring: CMMD: Active Messages on the CM-5. Parallel Computing 20(4): 481-496(1994)
[Val75]: Leslie G. Valiant: Parallelism in Comparison Problems. SIAM J. Comput. 4(3): 348-355(1975)
[VD91]: Scott L. Vandenberg, David J. DeWitt: Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance. SIGMOD Conference 1991: 158-167