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

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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

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

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

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

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

References

[AK89]: Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173
[AKW90]: Serge Abiteboul, Paris C. Kanellakis, Emmanuel Waller: Method Schemas. PODS 1990: 16-27
[AV88a]: Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250
[AV88b]: Serge Abiteboul, Victor Vianu: Datalog Extensions for Database Queries and Updates. J. Comput. Syst. Sci. 43(1): 62-124(1991)
[AV91]: Serge Abiteboul, Victor Vianu: Generic Computation and Its Complexity. STOC 1991: 209-219
[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
[AU79]: Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120
[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
[B88]: François Bancilhon: Object-Oriented Database Systems. PODS 1988: 152-162
[Ch81]: Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62
[Ch88]: Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9
[CH80]: Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980)
[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
[I86]: Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986)
[I87]: ...
[LV87]: Peter Lyngbæk, Victor Vianu: Mapping a Semantic Database Model to the Relational Model. SIGMOD Conference 1987: 132-142
[Pa87]: ...
[Pi79]: Nicholas Pippenger: On Simultaneous Resource Bounds (Preliminary Version). FOCS 1979: 307-311
[V82]: Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146