Patent ID: 8135701

Claim:
A computer-based method implemented in a query optimizer to incorporate partial information about multivariate distributions in a constrained optimization form, said method comprising: modeling one or more multivariate distributions based on available statistical information in a probability space; modeling one or more multivariate distributions for which no statistical information is available via a constrained optimization approach and entropy maximization over said probability space; estimating cardinality based on all available statistical information and both of said modeled distributions during cardinality estimation, and outputting said estimated cardinality, wherein said method further comprises a preprocessing step, said preprocessing comprising: partitioning a predicate space into independent components of nonintersecting knowledge based on both available knowledge and additional information about relevance of selectivities within each component; identifying, a priori, one or more atoms b for which input knowledge T implies that selectivity x b is zero, and excluding such atoms in computations of said constrained optimization approach, wherein selectivity x b is deduced to be zero: only (a) when s x =0 for X∈T, then x b =0 for all atoms b∈C(X), where s x is the selectivity of predicate p x and C(X) is the set of all atoms contributing to predicate p x , or (b) when two sets of atoms A and B with B⊂A have the same selectivity, i.e., by utilizing the equation Σ b∈B x b =Σ b∈A x b , then x b =0 for b∈A\B.