On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions (Extended Abstract).

Richard Hull, Jianwen Su: On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions (Extended Abstract). SIGMOD Conference 1989: 147-158

@inproceedings{DBLP:conf/sigmod/HullS89,
  author    = {Richard Hull and
               Jianwen Su},
  editor    = {James Clifford and
               Bruce G. Lindsay and
               David Maier},
  title     = {On Accessing Object-Oriented Databases: Expressive Power, Complexity,
               and Restrictions (Extended Abstract)},
  booktitle = {Proceedings of the 1989 ACM SIGMOD International Conference on
               Management of Data, Portland, Oregon, May 31 - June 2, 1989},
  publisher = {ACM Press},
  year      = {1989},
  pages     = {147-158},
  ee        = {http://doi.acm.org/10.1145/67544.66940, db/conf/sigmod/HullS89.html},
  crossref  = {DBLP:conf/sigmod/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A formal framework for studying the expressive power and complexity of OODB queries is developed. Three approaches to modeling sets are articulated and compared. The class of regular OODB schemas supports the explicit representation of set-valued types. Using an object-based semantics for sets, the regular schemas correspond to most implemented OODB systems in the literature; a value- based semantics for sets is also introduced. Without restrictions, both of these approaches support the specification of all computable queries. Assuming that the new operator is prohibited, the query language of the regular OODB schemes under the object-based semantics is complete in PSPACE; and under the value-based semantics it has hyper-exponential complexity. The third approach to modeling sets is given by the algebraic OODB model, in which multi-valued attributes rather than set-valued types are supported. Method implementations can use operators stemming from the relational algebra, and do not have side-effects. The query language of algebraic OODBs is more powerful than the relational algebra but has complexity bounded by PTIME. The expressive power and complexity of data access for other variations of OODBs are also considered. Finally, a new relational query language, called algebra + pointwise recursion, is introduced. This is equivalent to the algebraic OODB language, and can compute generalized transitive closure.

Copyright © 1989 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" 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/smod7592 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

James Clifford, Bruce G. Lindsay, David Maier (Eds.): Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989. ACM Press 1989

, SIGMOD Record 18(2), June 1989
Contents

Online Edition: ACM Digital Library

References

[Ah87a]: Serge Abiteboul, Richard Hull: IFO: A Formal Semantic Database Model. ACM Trans. Database Syst. 12(4): 525-565(1987)
[AH87b]: Tim Andrews, Craig Harris: Combining Language and Database Advances in an Object-Oriented Development Environment. OOPSLA 1987: 430-440
[AV88]: Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250
[BCD89]: François Bancilhon, Sophie Cluet, Claude Delobel: A Query Language for the O₂ Object-Oriented Database System. DBPL 1989: 122-138
[BCG+87]: Jay Banerjee, Hong-Tai Chou, Jorge F. Garza, Won Kim, Darrell Woelk, Nat Ballou, Hyoung-Joo Kim: Data Model Issues for Object-Oriented Applications. ACM Trans. Inf. Syst. 5(1): 3-26(1987)
[CH80]: Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980)
[CH82]: Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982)
[Cha81]: Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62
[GJ79]: M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
[HS88a]: Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. J. Comput. Syst. Sci. 43(1): 219-267(1991)
[HS88b]: Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. PODS 1988: 39-51
[HS89]: Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359
[HTY88]: Richard Hull, Katsumi Tanaka, Masatoshi Yoshikawa: Behavior Analysis of Object-Oriented Databases: Method Structure, Execution Trees, and Reachability (Extended Abstract). FODO 1989: 372-388
[HU79]: John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
[Hul87]: ...
[Imm86]: Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986)
[KV88]: Gabriel M. Kuper, Moshe Y. Vardi: On the Complexity of Queries in the Logical Data Model (Extended Abstract). ICDT 1988: 267-280
[LRV88]: Christophe Lécluse, Philippe Richard, Fernando Vélez: O2, an Object-Oriented Data Model. SIGMOD Conference 1988: 424-433
[PSM87]: Alan Purdy, Bruce Schuchardt, David Maier: Integrating an Object Server with Other Worlds. ACM Trans. Inf. Syst. 5(1): 27-47(1987)
[RHDM86]: Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176
[Shi81]: David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981)
[Ull88]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents
[Var82]: Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146

Last update Thu May 24 04:43:19 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page