Although many of the problems that must be solved by an object-oriented database system are similar to problems solved by relational systems, there are also many problems that are unique. In particular, an object query can include a path expression to traverse a number of related collections. The order of collection traversals given by the path expression may not be the most efficient to process the query. This generates a critical problem for object query optimizer to select an algorithm to process the query based on direct navigation or various combinations of joins . This paper studies the different algorithms to process path expressions with predicates, including depth first navigation, forward and reverse joins. Using a cost model, it then compares their performances in different cases, according to memory size, selectivity of predicates, fan out between collections, etc.. It also presents a heuristic-based algorithm to find profitable n-ary operators for traversing collections, thus reducing the search space of query plans to process a query with a qualified path expression. An implementation based on the O2 system demonstrates the validity of the results.
Key Words: Object-Oriented Databases, Paths, Query Optimization, Forward and Reverse Join, Search Space, Cost model.
Authors : Georges Gardarin, Jean-Robert Gruser and Zhao-Hui Tang
Query processing is one of the most critical issues in
Object-Oriented DBMSs. Extensible optimizers with efficient search
strategies require a cost model to select the most efficient execution
plans. In this paper we propose and partially validate a generic cost-model
for Object-Oriented DBMSs. The storage model and its access methods support clustered and nested collections, links, and path indexes. Queries may involve complex predicates with qualified path expressions. We propose a method for estimating the number of block accesses to clustered collections and a parameterized execution model for evaluating predicates. We estimate the costs of path expression traversals in different cases of physical clustering of the supporting collections. The model is validated through experiments with the O2 DBMS.
Authors : Georges Gardarin, Jean-Robert Gruser and Zhao-Hui Tang
Postscript Version
Query processing is one of the most critical issues in
Object Oriented Database Management System. In this paper we present a cost-model for cost-driven query optimizer in a Object Oriented database where object clustering is permitted. We propose an execution model for evaluating predicate with path expression and we study the costs of path expression evaluation in different cases of physical grouping of these collections.
Authors : Jean-Robert Gruser and Zhao-Hui Tang
Postscript Version
Flora is a language for implementing object-oriented
databases. As such, it is not
intended to be a user language, but rather,
an intermediate language capable of supporting a variety
of higher-level languages and applications.
Flora provides a very
general data model with complex values and complex objects, constructs for
specifying data storage, and
a functional-style action language that incorporates set processing operations
and a user-defined function capability. Thus, Flora provides the
building blocks that allow the calling language to appropriately model
higher-level constructs such as classes and inheritance, and to build complex
queries in a manner that readily supports various optimization schemes.
Authors : D. Florescu, Jean-Robert Gruser, M. Novak, P. Valduriez and M. Ziane
Postscript Version
