ACM SIGMOD Anthology VLDB dblp.uni-trier.de

The Power of Methods With Parallel Semantics.

Karl Denninghoff, Victor Vianu: The Power of Methods With Parallel Semantics. VLDB 1991: 221-232
@inproceedings{DBLP:conf/vldb/DenninghoffV91,
  author    = {Karl Denninghoff and
               Victor Vianu},
  editor    = {Guy M. Lohman and
               Am\'{\i}lcar Sernadas and
               Rafael Camps},
  title     = {The Power of Methods With Parallel Semantics},
  booktitle = {17th International Conference on Very Large Data Bases, September
               3-6, 1991, Barcelona, Catalonia, Spain, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1991},
  isbn      = {1-55860-150-3},
  pages     = {221-232},
  ee        = {db/conf/vldb/DenninghoffV91.html},
  crossref  = {DBLP:conf/vldb/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A model capturing the data manipulation capabilities of a large class of methods in object-oriented databases is proposed and investigated. The model uses a deterministic, parallel synchronous semantics with concurrent -read and concurrent-write. The results focus on the expressive power of methods and help understand various constructs and semantics associated with methods. Restrictions of methods providing various tractability guarantees are also discussed. The restrictions correspond closely to well-known relational query languages such as relational calculus, Datalog, the fixpoint queries, and the while queries. They provide complexity bounds such as constant parallel time, PTIME, and PSPACE. Exact characterizations for some complexity classes are also obtained under certain assumptions. Our methods provide a model of database parallel computation which makes explicit the potential parallelism in databases. We compare our model to traditional parallel computation models such as PRAMs and Hardware Modification Machines and show mutual simulation results with reasonable cost. We also compare methods to a newer model of generic computation involving parallelism. We show that certain complexity classes defined using the two models are the same, which suggests that methods capture database parallel computation in a natural and robust fashion.

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

Guy M. Lohman, Amílcar Sernadas, Rafael Camps (Eds.): 17th International Conference on Very Large Data Bases, September 3-6, 1991, Barcelona, Catalonia, Spain, Proceedings. Morgan Kaufmann 1991, ISBN 1-55860-150-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[AK89]
Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AKW90]
Serge Abiteboul, Paris C. Kanellakis, Emmanuel Waller: Method Schemas. PODS 1990: 16-27 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AV88a]
Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AV88b]
Serge Abiteboul, Victor Vianu: Datalog Extensions for Database Queries and Updates. J. Comput. Syst. Sci. 43(1): 62-124(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AV91]
Serge Abiteboul, Victor Vianu: Generic Computation and Its Complexity. STOC 1991: 209-219 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AHU76]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AU79]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[A+90]
Malcolm P. Atkinson, François Bancilhon, David J. DeWitt, Klaus R. Dittrich, David Maier, Stanley B. Zdonik: The Object-Oriented Database System Manifesto. SIGMOD Conference 1990: 395 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[B88]
François Bancilhon: Object-Oriented Database Systems. PODS 1988: 152-162 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ch81]
Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ch88]
Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CH80]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Co81]
...
[DV91]
...
[G90]
...
[D80]
...
[HS89]
Richard Hull, Jianwen Su: On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions (Extended Abstract). SIGMOD Conference 1989: 147-158 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[I86]
Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[I87]
...
[LV87]
Peter Lyngbæk, Victor Vianu: Mapping a Semantic Database Model to the Relational Model. SIGMOD Conference 1987: 132-142 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Pa87]
...
[Pi79]
Nicholas Pippenger: On Simultaneous Resource Bounds (Preliminary Version). FOCS 1979: 307-311 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[V82]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:01 2010 by Michael Ley (ley@uni-trier.de)