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}
}
BibTeX

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 ... BibTeX

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 BibTeX

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