Patent ID: 7136850

Claim:
A method for estimating a selectivity of a query containing at least one column-associated condition related to column attributes of a relational database table, the method comprising: (a) generating a dataset by sampling a plurality of queries applied against the database, wherein the dataset includes a plurality of query conditions and information related to combinations of said query conditions, wherein step (a) further includes: (a.1) generating a dataset including queries q j , j=1, . . . N, wherein each query includes a plurality of column-associated conditions c jk , k=1, . . . M j , N, M being integer variables, wherein step (a.1) further includes: (a.1.1) storing a cardinality C of an elementary operation associated with a column-associated condition c jk , (a.1.2) storing a count of query-qualifying database records reflecting the correlation between the database table column attributes referred to in each elementary operation, (b) determining at least one regression function that reflects correlations between particular query conditions based on said dataset, (c) determining a table-specific estimate of a cardinality of a query based upon the regression function serving as a data mining model, wherein step (c) further includes: (c.1) calculating a cardinality estimate CE of said query with the following formula: CE = ∑ i = 1 , … ⁢ ⁢ L ⁢ ⁢ f ⁡ ( Z i ) wherein f(Z i ) is the regression function, CE is a total of correlations between the plurality of combinations of elementary operations used in said sampled queries, and Z i is a frequency of occurrence for one or more column-associated conditions c jk , and wherein said regression function is updated using said data mining model.