Semantic query optimization using value correlation

A method for optimizing queries to a database, the database comprising a first table (T1) having a primary key (PK) column and a first correlated value column (CV1) and a second table (T2) having a foreign key (FK) column related to the primary key column of the first table and a second correlated value column (CV2), the method comprising

• joining T1 to the T2 using PK=FK as the join condition to produce a join result having rows, each row including a value from CV1 and a value from CV2;
• creating an initial running constraint (RC), the initial running constraint comprising a null range;
• producing a derived constraint rule (DCR) having the following form:
• ( PK = FK ) → ⁢ ( CV 2 + C 1 ⁢ A ≤ CV 1 ≤ CV 2 + C 2 ⁢ A ) ⋃ ⁢ ( CV 2 + C 1 ⁢ B ≤ CV 1 ≤ CV 2 + C 2 ⁢ B ) ⋃ ⁢ … ⁢ ( CV 2 + C 1 ⁢ N ≤ CV 1 ≤ CV 2 + C 2 ⁢ N ) ;
• where C1A, C2A, C1B, C2B, . . . C1N and C2N are constants, “→” means “implies,” and each parenthesized term on the right-hand side of the above equation represents an interval;
• by performing the following processing for each row in the join result computing a new constraint (NEW), having a range;
• and
• modifying RC by forming a union of the range of NEW with the range of RC.

A computer program, stored on a tangible storage medium, for use in optimizing queries to a database, the database comprising a first table (T1) having a primary key (PK) column and a first correlated value column (CV1) and a second table (T2) having a foreign key (FK) column related to the primary key column of the first table and a second correlated value column (CV2), the program comprising executable instructions that cause a computer to

• join T1 to the T2 using PK=FK as the join condition to produce a join result having rows, each row including a value from CV1 and a value from CV2;
• create an initial running constraint (RC), the initial running constraint comprising a null range;
• produce a derived constraint rule (DCR) having the following form:
• (PK=FK)→CV2+C1≦CV1≦CV2+C2
• where C1 and C2 are constants, and “→” means “implies;”
• by performing the following processing for each row in the join result compute a new constraint (NEW), having a range;
• and
• modify RC by merging the range of NEW with the range of RC.