On accessing object-oriented databases: expressive power, complexity, and restrictions

Reviewer: Felipe Carino

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.<__?__Pub Fmt eos-space> 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 x 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 x ?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 <__?__Pub Fmt italic>new<__?__Pub Fmt /italic> 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<__?__Pub Caret> 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.