Bounding the cardinality of aggregate views through domain-derived constraints

Accurately estimating the cardinality of aggregate views is crucial for logical and physical design of data warehouses. This paper proposes an approach based on cardinality constraints, derived a-priori from the application domain, which may bound either the cardinality of a view or the ratio between the cardinalities of two views. We face the problem by first computing satisfactory bounds for the cardinality, then by capitalizing on these bounds to determine a good probabilistic estimate for it. In particular, we propose a bounding strategy which achieves an effective trade-off between the tightness of the bounds produced and the computational complexity. © 2002 Elsevier Science B.V. All rights reserved.