A CONTINGENCY APPROACH TO ESTIMATING RECORD SELECTIVITIES

The ability to accurately estimate record selectivities, the proportion of a file satisfying the query condition(s), is essential to selecting an efficient access path. In the past, both parametric and nonparametric methods for estimating record selectivity have been proposed. Parametric methods are parsimonious. However, they do not provide accurate estimates when the actual data do not fit the theoretical distribution these methods assume. In contrast, nonparametric methods can provide very accurate estimation, but require a huge amount of storage space. In this paper we present a contingency approach for estimating record selectivities rooted in the technique of fitting a hierarchy of models in discrete data analysis. We show that the approach satisfies the dual demands of a good estimation method: accuracy and economy in the use of storage space.