The Power of Methods With Parallel Semantics.

Karl Denninghoff, Victor Vianu: The Power of Methods With Parallel Semantics. VLDB 1991: 221-232
  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,}


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

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


Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 BibTeX
Serge Abiteboul, Paris C. Kanellakis, Emmanuel Waller: Method Schemas. PODS 1990: 16-27 BibTeX
Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250 BibTeX
Serge Abiteboul, Victor Vianu: Datalog Extensions for Database Queries and Updates. J. Comput. Syst. Sci. 43(1): 62-124(1991) BibTeX
Serge Abiteboul, Victor Vianu: Generic Computation and Its Complexity. STOC 1991: 209-219 BibTeX
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
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 BibTeX
François Bancilhon: Object-Oriented Database Systems. PODS 1988: 152-162 BibTeX
Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62 BibTeX
Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9 BibTeX
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
Richard Hull, Jianwen Su: On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions (Extended Abstract). SIGMOD Conference 1989: 147-158 BibTeX
Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX
Peter Lyngbæk, Victor Vianu: Mapping a Semantic Database Model to the Relational Model. SIGMOD Conference 1987: 132-142 BibTeX
Nicholas Pippenger: On Simultaneous Resource Bounds (Preliminary Version). FOCS 1979: 307-311 BibTeX
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

Referenced by

  1. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
  2. Dan Suciu, Val Tannen: A Query Language for NC. PODS 1994: 167-178
  3. Karl Denninghoff, Victor Vianu: Database Method Schemas and Object Creation. PODS 1993: 265-275
  4. Christian Laasch, Marc H. Scholl: Deterministic Semantics of Set-Oriented Update Sequences. ICDE 1993: 4-13
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:48 2009