Optimizing Boolean Expressions in Object-Bases
Alfons Kemper, Guido Moerkotte, Michael Steinbrunn · MADOC (University of Mannheim) · 1992
In this paper we address the problem of optimizing the evaluation of boolean expressions in the context of object-oriented data modelling. We develop a new heuristic for optimizing the evaluation sequence of boolean expressions based on selectivity and cost estimates of the terms constituting the boolean expression. The quality and efficiency of the heuristic is evaluated based on a quantitative analysis which compares our heuristic with the optimal, but infeasible algorithm and other known methods. The heuristic is based on the selectivity and evaluation-cost estimates of the terms of which the boolean expression is composed. Deriving these inputs of the heuristics, i.e., the selectivity and cost estimates, is then addressed. We use an adaptation of well-known sampling for estimating the selectivity of terms. The cost estimation is much more complex than in the relational context due to the possibility of invoking functions within a boolean expression. We develop the decapsulation me...