Evaluating the size of queries on relational databases with non-uniform distribution and stochastic dependence
Silvio Salza, Mario Terranova · ACM SIGMOD Record · 1989
The paper deals with the problem of evaluating how the originality of the attributes of a relation, i.e. the number of distinct values in each attribute, is affected by relational operations that reduce the cardinality of the relation. This is indeed an interesting problem in research areas such as database design and query optimization. Some authors have shown that non uniform distributions and stochastic dependence significantly affect the originality of the attributes. Therefore the models that have been proposed in the literature, based on uniformity and independence assumptions, in several situation can not be conveniently utilized. In this paper we propose a probabilistic model that overcomes the need of the uniformity and independence assumptions. The model is exact for non uniform distributions when the attributes are independent, and gives approximate results when stochastic dependence is considered. In the latter case the analytical results have been compared with a simulation, and proved to be quite accurate.