Estimating nested selectivity in object-oriented and object-relational databases

A search condition in object-oriented/object-relational queries consists of nested predicates, which are predicates on path expressions. In this paper, we propose a new technique for estimating selectivity for nested predicates. Selectivity of a nested predicate, nested selectivity, is defined as the ratio of the number of the qualified objects of the starting class in the path expression to the total number of objects of the class. The new technique takes into account the effects of direct representation of the many-to-many relationship and the partial participation of objects in the relationship. These two features occur frequently in object-oriented/object-relational databases, but have not been properly handled in the conventional selectivity estimation techniques. For the many-to-many relationship, we generalize the block-hit function proposed by S.B. Yao to allow the cases that an object belongs to more than one block. For the partial participation, we propose the concept of active objects and extend our technique for total participation to handle active objects. We also propose efficient methods for obtaining statistical information needed for our estimation technique. We finally analyze the accuracy of our technique through a series of experiments and compare with the conventional ones. The experiment results showed that there was a significant inaccuracy in the estimation by the conventional ones, confirming the advantage of our technique.