Patent Document ID: 7685086
Application ID: 11842828
Patent Flag: 1

Claim One:
1. An article of manufacture having computer readable storage medium comprising computer readable program code which when executed by a computer implements a computer-based method to perform query optimization by automatically finding and exploiting hidden, fuzzy algebraic constraints in a database, said medium comprising: (a) computer readable program code constructing one or more candidates of form C=(a 1 , a 2 , P, ⊕), wherein a 1 and a 2 are numerical attributes associated with column values of data in said database, P is a pairing rule, and ⊕ is any of the following algebraic operators: +, −, ×, or /; (b) computer readable program code constructing, for each candidate identified in (a), an algebraic constraint AC=(a 1 , a 2 , P, ⊕, I 1 ,. .. , I k ) by applying any of, or a combination of the following techniques to a sample of column values: statistical histogramming, segmentation, or clustering, where I 1 ,. .. , I k is a set of disjoint intervals and k≧1, (c) computer readable program code performing query optimization using said constructed algebraic constraints and outputting results of said query optimization, and wherein one or more pruning rules are used to limit said number of constructed candidates and said pairing rule P represents either a trivial pairing rule ø R or a join between tables R and S and said pruning rules comprise any of, or a combination of the following: pairing rule P is of form R.a=S.b or of the form ø R , and the number of rows in either table R or table S lies below a specified threshold value; pairing rule P is of form R.a=S.b with a εK and the number of distinct values in S.b divided by the number of values in R.a lies below a specified threshold value, wherein K is a set comprising key-like columns among all columns in said database; pairing rule P is of form R.a=S.b, and one or both of R and S fails to have an index on any of its columns; or pairing rule P is of form R.a=S.b with a εK, and S.b is a system-generated key.