Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
On accessing object-oriented databases: expressive power, complexity, and restrictions
Hull R., Su J. ACM SIGMOD Record18 (2):147-158,1989.Type:Article
Date Reviewed: Oct 1 1990

Four contributions to the area of object-oriented database (OODB) access compose this paper: (1) introduction of a formal framework for studying the power and complexity of OODB queries, (2) articulation and comparison of three alternative approaches for incorporating sets into OODBs, (3) a body of theoretical results concerning the expressive power and complexity of data access to OODBs that incorporate sets in three ways, and (4) description of a new relational query language, Algebra + pointwise recursion (ALG+pwrec).

In the introduction, the authors compare the expressive power of OODB queries and relational database queries using the natural correspondence between OODB and relational schemas. They devote a major portion of the paper to the explicit definition of various aspects of OODB, since the field is young and there is no widely accepted formalism.

The second contribution consists of three types of approaches: semantic database schemas and instances without multivalued attributes (which can have set-valued types); object-oriented database schemas (a semantic schema with methods, where methods cannot introduce new types into a schema); and an OODB imperative language (Smalltalk) or the existing programming language C. Operational semantics provided for method calls on OODB instances are based on method execution trees (METs), which provide a faithful copy of object-oriented system semantics. METs consist of three types: successful, aborted, and nonterminating. The data access model uses a simple correspondence between semantic, OODB, and relational schemas to introduce the notion of OODB access languages.

The authors’ third contribution defines hyper-exponential complexity, then defines elementary queries ( &xgr; ) to consist of the set of relational mappings having hyper-exponential complexity. In addition, computable queries ( C ) are defined to contain relational mappings computable by Turing machines ( &xgr; ⊂ C ) The authors then analyze three semantic approaches to set modeling: object-based semantics, value-based semantics, and the algebraic OODB model (which employs multivalued attributes instead of set-valued types, and method implementations that use relational algebra operators with no side effects). If the new operator is prohibited, the paper shows their respective time (space) complexity--PSPACE complexity for the object-based semantic approach, hyper-exponential complexity for the value-based approach, and PTIME complexity for the algebraic OODB approach.

The fourth contribution introduces a new relational query language, Algebra + pointwise recursion (ALG+pwrec). The paper shows that ALG+pwrec is a proper extension of relational algebra (and calculus) that permits some forms of transitivity and recursion; has the ability to perform generalized transitive closure operations, without reference structures outside the relational model; and is equivalent in expressive power to an algebraic OODB language specified in the paper.

I would recommend this well-written paper to anyone interested in OODB formalisms and semantic modeling. The semantic modeling time (space) complexity analysis restricted the use of the new operator. In order for this excellent body of work to have future general-purpose value, the new operator must be allowed, however.

Reviewer:  Felipe Carinõo Jr. Review #: CR114067
Bookmark and Share
 
Query Processing (H.2.4 ... )
 
 
Access Methods (H.2.2 ... )
 
 
Algebraic Approaches To Semantics (F.3.2 ... )
 
 
Query Formulation (H.3.3 ... )
 
 
Query Languages (H.2.3 ... )
 
 
Semantics (D.3.1 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Query Processing": Date
A correction of the termination conditions of the Henschen-Naqvi technique
Briggs D. Journal of the ACM 31(4): 711-719, 1984. Type: Article
Sep 1 1992
A compression technique to materialize transitive closure
Jagadish H. (ed) ACM Transactions on Database Systems 15(3): 558-598, 1990. Type: Article
Oct 1 1992
Efficient and optimal query answering on independent schemes
Atzeni P. (ed), Chan E. Theoretical Computer Science 77(3): 291-308, 1990. Type: Article
Nov 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy