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}
}

BibTeX

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

BibTeX

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 BibTeX , 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) BibTeX
[AH87b]: Tim Andrews, Craig Harris: Combining Language and Database Advances in an Object-Oriented Development Environment. OOPSLA 1987: 430-440 BibTeX
[AV88]: Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250 BibTeX
[BCD89]: François Bancilhon, Sophie Cluet, Claude Delobel: A Query Language for the O₂ Object-Oriented Database System. DBPL 1989: 122-138 BibTeX
[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) BibTeX
[CH80]: Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[CH82]: Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
[Cha81]: Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62 BibTeX
[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
BibTeX
[HS88a]: Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. J. Comput. Syst. Sci. 43(1): 219-267(1991) BibTeX
[HS88b]: Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. PODS 1988: 39-51 BibTeX
[HS89]: Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359 BibTeX
[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 BibTeX
[HU79]: John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
BibTeX
[Hul87]: ...
[Imm86]: Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX
[KV88]: Gabriel M. Kuper, Moshe Y. Vardi: On the Complexity of Queries in the Logical Data Model (Extended Abstract). ICDT 1988: 267-280 BibTeX
[LRV88]: Christophe Lécluse, Philippe Richard, Fernando Vélez: O2, an Object-Oriented Data Model. SIGMOD Conference 1988: 424-433 BibTeX
[PSM87]: Alan Purdy, Bruce Schuchardt, David Maier: Integrating an Object Server with Other Worlds. ACM Trans. Inf. Syst. 5(1): 27-47(1987) BibTeX
[RHDM86]: Arnon Rosenthal, Sandra Heiler, Umeshwar Dayal, Frank Manola: Traversal Recursion: A Practical Approach to Supporting Recursive Applications. SIGMOD Conference 1986: 166-176 BibTeX
[Shi81]: David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX
[Ull88]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Var82]: Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

Referenced by

Marc Andries, Luca Cabibbo, Jan Paredaens, Jan Van den Bussche: Applying an Update Method to a Set of Receivers. PODS 1995: 208-218
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents
Jan Van den Bussche, Dirk Van Gucht, Gottfried Vossen: Reflective Programming in the Relational Algebra. PODS 1993: 17-25
Jan Van den Bussche, Dirk Van Gucht: A Hierarchy of Faithful Set Creation in Pure OODB's. ICDT 1992: 326-340
Karl Denninghoff, Victor Vianu: The Power of Methods With Parallel Semantics. VLDB 1991: 221-232
Jan Van den Bussche, Jan Paredaens: The Expressive Power of Structured Values in Pure OODB's. PODS 1991: 291-299
Marc Gyssens, Jan Paredaens, Dirk Van Gucht: A Graph-Oriented Object Database Model. PODS 1990: 417-424
Serge Abiteboul, Paris C. Kanellakis, Emmanuel Waller: Method Schemas. PODS 1990: 16-27
Richard Hull, Jianwen Su: On Bulk Data type Constructors and Manipulation Primitives: A Framework for Analyzing Power and Complexity. DBPL 1989: 396-410

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]