Patent ID: 7277873

Claim:
A computer-based method to perform query optimization by automatically finding and exploiting hidden, fuzzy algebraic constraints in a database, said method comprising the steps of: (a) 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) constructing, for each candidate identified in (a), an algebraic constraint AC=(a 1 a 2 , P, ⊕, I 1 , . . . , I k ) by applying a segmentation technique, where I 1 , . . . , I k is a set of disjoint intervals and k≧1, said step of constructing algebraic constraint further comprising the steps of: constructing a sample set W C of an induced set Ω c , wherein P is a join predicate between tables R and S and Ω C ={r.a 1 ⊕ r.a 2 :r ∈ R}when the pairing rule P is a trivial rule ø R and Ω C ={r.a 1 ⊕ s.a 2 :r ∈ R, s ∈ S, and (r,s) satifies P}; sorting n data points in said sampled set W C in increasing order as x 1 ≦x 2 ≦. . . ≦x n and constructing a set of disjoint intervals I 1 , . . . , I k such that data in sample W C falls within one of said disjoint intervals, wherein segmentation for constructing said set of disjoint intervals is specified via a vector of indices (i(1), i(2), . . . , i(k)) and the j th interval is given by I i =[x i(j−1)+1 ,x i(j) ] and length of Ij, denoted by Lj, is given by L j =x i(j−1)+1 ; and wherein the function for optimizing cost associated with said segmentation is c ⁡ ( S ) = wk + ( 1 - w ) ⁡ [ 1 Δ ⁢ ∑ J = 1 k ⁢ ⁢ L j ] with w being a fixed weight between 0 and 1 and a segmentation that minimizes c is defined by placing adjacent points x l and x l+1 in the same segment if and only if x l+1 -x l <d*, where d* =Δ(w/(1−w)), and wherein said constructed algebraic constraints are used in query optimization.