ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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

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

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BBKV87]
François Bancilhon, Ted Briggs, Setrag Khoshafian, Patrick Valduriez: FAD, a Powerful and Simple Database Language. VLDB 1987: 97-105 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BBW92]
Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ble90]
Guy E. Blelloch: Vector Models for Data-Parallel Computing. MIT Press 1990, ISBN 0-262-02313-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ble94]
...
[BS90]
...
[Cat94]
R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.1). Morgan Kaufmann 1994
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CDN93]
Michael J. Carey, David J. DeWitt, Jeffrey F. Naughton: The oo7 Benchmark. SIGMOD Conference 1993: 12-21 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Deu90]
O. Deux: The Story of O2. IEEE Trans. Knowl. Data Eng. 2(1): 91-108(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DG92]
David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FM95]
Leonidas Fegaras, David Maier: Towards an Effective Calculus for Object Query Languages. SIGMOD Conference 1995: 47-58 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GWLZ93]
Shahram Ghandeharizadeh, David Wilhite, Kai-Ming Lin, Xiaoming Zhao: Object Placement in Parallel Object-Oriented Database Systems. ICDE 1994: 253-262 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Jaj92]
Joseph JáJá: An Introduction to Parallel Algorithms. Addison-Wesley 1992, ISBN 0-201-54856-9
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KSSS93]
...
[PSV92]
Douglas Stott Parker Jr., Eric Simon, Patrick Valduriez: SVP: A Model Capturing Sets, Lists, Streams, and Parallelism. VLDB 1992: 115-126 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ST94]
...
[Suc95]
...
[TM94]
Lewis W. Tucker, Alan M. Mainwaring: CMMD: Active Messages on the CM-5. Parallel Computing 20(4): 481-496(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Val75]
Leslie G. Valiant: Parallelism in Comparison Problems. SIAM J. Comput. 4(3): 348-355(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[VD91]
Scott L. Vandenberg, David J. DeWitt: Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance. SIGMOD Conference 1991: 158-167 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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