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

@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

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• 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

• 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

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

[2]

Pascale Borla-Salamet, Carla Chachaty, Benoît Dageville: Compiling Control into Database Queries for Parallel Execution Management. PDIS 1991: 271-279 BibTeX

[3]

...

[4]

Nicholas Carriero, David Gelernter: Linda in Context. Commun. ACM 32(4): 444-458(1989) BibTeX

[5]

...

[6]

Stan Danforth, Patrick Valduriez: A FAD for Data Intensive Applications. IEEE Trans. Knowl. Data Eng. 4(1): 34-51(1992) BibTeX

[7]

Anoop Gupta, Charles Forgy, Allen Newell: High-Speed Implementations of Rule-Based Systems. ACM Trans. Comput. Syst. 7(2): 119-146(1989) BibTeX

[8]

Brian E. Hart, Scott Danforth, Patrick Valduriez: Parallelizing a Database Programming Language. DPDS 1988: 72-79 BibTeX

[9]

W. Daniel Hillis, Guy L. Steele Jr.: Data Parallel Algorithms. Commun. ACM 29(12): 1170-1183(1986) BibTeX

[10]

...

[11]

Gilles Kahn: The Semantics of Simple Language for Parallel Programming. IFIP Congress 1974: 471-475 BibTeX

[12]

Richard E. Ladner, Michael J. Fischer: Parallel Prefix Computation. J. ACM 27(4): 831-838(1980) BibTeX

[13]

...

[14]

...

[15]

...

[16]

David B. Skillicorn: Architecture-Independent Parallel Computation. IEEE Computer 23(12): 38-50(1990) BibTeX

[17]

...

[18]

...

[19]

...

[20]

...

[21]

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