D.S. Parker, E. Simon, P. Valduriez
appeared in: Proc. 18th Conf. on Very Large Data Bases, pp. 115-126, Vancouver, British Columbia, August 1992.
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.
D.S. Parker, E. Simon, P. Valduriez
(full version) Technical Report CSD-920020, April 1992.
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 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. We achieve these semantics by extending Kahn's networks of parallel processes to operate on collections instead of sequences, and in so doing extract both independent and pipeline parallelism.
Claudia Amador
Report, UCLA Computer Science Department, September 1993.
We describe an implementation of the SVP data model. SVP is a database model intended for modeling both set and stream data, and to model parallelism in bulk data processing.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 describe a multithreaded implementation written in C. This implementation is parametric in control schemes for forking threads; that is, one can easily modify the control scheme used for generating new threads of execution while processing queries. It has been run successfully on an Encore Multimax at INRIA Rocquencourt. While performance has not been a key focus of this implementation, we feel the implementation shows what is possible.