Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases

Abstract

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 significant 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 collecti...