Patent ID: 7512629

Claim:
A computer-implemented method for a database, given a set of input selectivities {Sx: XÎµT}, wherein T represents a knowledge set, the method comprising: partitioning a predicate index set N with respect to said input selectivities, wherein a number of said partitions is at least one, wherein the input selectivities can be single or multivariate; and wherein a constant Î¼: is chosen such that the cardinality of each partition N 1 , N 2 , . . . , N k follows |N i |â‰¦Î¼ for each iÎµ{1,2, . . . , k}; adjusting said input selectivities to obtain a mutually consistent set of selectivities, wherein each partition set of selectivities is adjusted separately and treated as a separate unit; wherein said adjusting step comprises associating two slack variables with each constraint of said constrained optimization problem, except for the constraint corresponding to an S Ï† minimizing said adjusting of said input selectivities; wherein said minimizing step comprises minimizing a total sum of said slack variables; and combining the selectivity estimates in the separate partitions using an independence assumption, S x =Î iÎµ{1,2, . . . , k} S xâˆ©N 1 for XÎµ2 n ; wherein said given set of input selectivities is not mutually consistent; and said adjusted selectivities are mutually consistent and yield a set of satisfiable constrained optimization problem.