Patent ID: 7512629
Filing Date: 2009-03-31
Classification: G06F,Y10S

Abstract:
1. 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, 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.