Estimating nested selectivity in object-oriented databases
Wan-Sup Cho, Wook-Shin Han, Ki-Hyung Hong, Kyu-Young Whang · 2000
A searc h condition in object-oriented queries consists of nested predicates, eac h of which is a predicate on a path expression.In this paper, w e present a new selectivit y estimation technique for nested predicates.Selectivity of a nested predicate, neste d selectivity, is de ned as the ratio of the number of quali ed 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 eects of direct representation of manyto-many relationships.Many-to-many relationships frequently occur in object-oriented databases, but have n o t been properly handled in con ven tional selectivit yestimation techniques.F or many-to-many relationships, we generalize the block-hit function originally proposed by B. Yao allowing the cases where one object belongs to more than one block.The most signi cant advantage of our technique is that the accuracy of the estimation is far enhanced with only a small additional overhead.We present an ecient method for obtaining the statistical information that is needed for our estimation technique.We analyze the accuracy of our estimation technique and compare the result with those of conven tional ones.The experimental result shows there is a signi cant d eviation in the estimation obtained by c o n ven tional ones, con rming the advan tage of our technique.