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


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

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 BibTeX


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) BibTeX
Pascale Borla-Salamet, Carla Chachaty, Benoît Dageville: Compiling Control into Database Queries for Parallel Execution Management. PDIS 1991: 271-279 BibTeX
Nicholas Carriero, David Gelernter: Linda in Context. Commun. ACM 32(4): 444-458(1989) BibTeX
Stan Danforth, Patrick Valduriez: A FAD for Data Intensive Applications. IEEE Trans. Knowl. Data Eng. 4(1): 34-51(1992) BibTeX
Anoop Gupta, Charles Forgy, Allen Newell: High-Speed Implementations of Rule-Based Systems. ACM Trans. Comput. Syst. 7(2): 119-146(1989) BibTeX
Brian E. Hart, Scott Danforth, Patrick Valduriez: Parallelizing a Database Programming Language. DPDS 1988: 72-79 BibTeX
W. Daniel Hillis, Guy L. Steele Jr.: Data Parallel Algorithms. Commun. ACM 29(12): 1170-1183(1986) BibTeX
Gilles Kahn: The Semantics of Simple Language for Parallel Programming. IFIP Congress 1974: 471-475 BibTeX
Richard E. Ladner, Michael J. Fischer: Parallel Prefix Computation. J. ACM 27(4): 831-838(1980) BibTeX
David B. Skillicorn: Architecture-Independent Parallel Computation. IEEE Computer 23(12): 38-50(1990) BibTeX
Ouri Wolfson, Aya Ozeri: A New Paradigm for Parallel and Distributed Rule-Processing. SIGMOD Conference 1990: 133-142 BibTeX

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
  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
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:51 2009