dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

SVP: A Model Capturing Sets, Lists, Streams, and Parallelism.

Douglas Stott Parker Jr., Eric Simon, Patrick Valduriez: SVP: A Model Capturing Sets, Lists, Streams, and Parallelism. VLDB 1992: 115-126
@inproceedings{DBLP:conf/vldb/ParkerSV92,
  author    = {Douglas Stott Parker Jr. and
               Eric Simon and
               Patrick Valduriez},
  editor    = {Li-Yan Yuan},
  title     = {SVP: A Model Capturing Sets, Lists, Streams, and Parallelism},
  booktitle = {18th International Conference on Very Large Data Bases, August
               23-27, 1992, Vancouver, Canada, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1992},
  isbn      = {1-55860-151-1},
  pages     = {115-126},
  ee        = {db/conf/vldb/ParkerSV92.html},
  crossref  = {DBLP:conf/vldb/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We describe the SVP data model. The goal of SVP is to model both set and stream data, and to model parallelism in bulk data processing. SVP also shows promise for other parallel processing applications.

SVP models collections, which include sets and streams as special cases. Collections are represented as ordered tree structures, and divide-and-conquer mappings are easily defined on these structures. We show that many useful database mappings (queries) have a divide-and-conquer format when specified using collections, and that this specification exposes parallelism.

We formalize a class of divide-and-conquer mappings on collections called SVP-transducers. SVP-transducers generalize aggregates, set mappings, stream transductions, and scan computations. At the same time, they have a rigorous semantics based on continuity with respect to collection orderings, and permit implicit specification of both independent and pipeline parallelism.

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

Li-Yan Yuan (Ed.): 18th International Conference on Very Large Data Bases, August 23-27, 1992, Vancouver, Canada, Proceedings. Morgan Kaufmann 1992, ISBN 1-55860-151-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Dina Bitton, Haran Boral, David J. DeWitt, W. Kevin Wilkinson: Parallel Algorithms for the Execution of Relational Database Operations. ACM Trans. Database Syst. 8(3): 324-353(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Pascale Borla-Salamet, Carla Chachaty, Benoît Dageville: Compiling Control into Database Queries for Parallel Execution Management. PDIS 1991: 271-279 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
...
[4]
Nicholas Carriero, David Gelernter: Linda in Context. Commun. ACM 32(4): 444-458(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
...
[6]
Stan Danforth, Patrick Valduriez: A FAD for Data Intensive Applications. IEEE Trans. Knowl. Data Eng. 4(1): 34-51(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Anoop Gupta, Charles Forgy, Allen Newell: High-Speed Implementations of Rule-Based Systems. ACM Trans. Comput. Syst. 7(2): 119-146(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Brian E. Hart, Scott Danforth, Patrick Valduriez: Parallelizing a Database Programming Language. DPDS 1988: 72-79 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
W. Daniel Hillis, Guy L. Steele Jr.: Data Parallel Algorithms. Commun. ACM 29(12): 1170-1183(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
...
[11]
Gilles Kahn: The Semantics of Simple Language for Parallel Programming. IFIP Congress 1974: 471-475 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Richard E. Ladner, Michael J. Fischer: Parallel Prefix Computation. J. ACM 27(4): 831-838(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
...
[14]
...
[15]
...
[16]
David B. Skillicorn: Architecture-Independent Parallel Computation. IEEE Computer 23(12): 38-50(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
...
[18]
...
[19]
...
[20]
...
[21]
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

Referenced by

  1. Anthony J. Bonner, Giansalvatore Mecca: Querying String Databases with Transducers. DBPL 1997: 118-135
  2. Dan Suciu: Implementation and Analysis of a Parallel Collection Query Language. VLDB 1996: 366-377
  3. Giansalvatore Mecca, Anthony J. Bonner: Sequences, Datalog and Transducers. PODS 1995: 23-35
  4. Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: SEQ: A Model for Sequence Databases. ICDE 1995: 232-239
  5. Giansalvatore Mecca, Anthony J. Bonner: Finite Query Languages for Sequence Databases. DBPL 1995: 12
  6. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  7. Val Tannen: Tutorial: Languages for Collection Types. PODS 1994: 150-154
  8. Dan Suciu, Val Tannen: A Query Language for NC. PODS 1994: 167-178
  9. Latha S. Colby, Edward L. Robertson, Lawrence V. Saxton, Dirk Van Gucht: A Query Language for List-Based Complex Objects. PODS 1994: 179-189
  10. David Maier, Bennet Vance: A Call to Order. PODS 1993: 1-16
  11. Bennet Vance: An Abstract Object-Oriented Query Execution Language. DBPL 1993: 176-199

Last update Fri Sep 14 17:38:14 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page