Optimization of queries using relational algebraic theta-semijoin operator

The method of claim I wherein said query is a decision support query.

A computer programming language query optimizer comprising

• means for receiving a computer database language query;
• and
• means for generating at least one relational algebraic expression by employing at least one equivalence rule involving the multiset version of the relational algebraic theta-semijoin operator, said expression being equivalent to said query.

A computer processor programmed to perform method steps for optimizing an SQL query, said method steps comprising

• generating at least one relational algebraic expression by employing at least one equivalence rule involving the multiset version of the relational algebraic theta-semijoin operator, said expression equivalent to said query;
• and
• performing cost-based algebraic optimization of said algebraic expressions, said cost-based algebraic optimization using at least one cost formula for said theta-semijoin operator.

A program storage device embodying a computer program to perform method steps comprising:

• receiving an SQL query;
• and
• generating at least one relational algebraic expression by employing at least one equivalence rule involving the multiset version of the relational algebraic theta-semijoin operator, said expression equivalent to said SQL query.

A storage device embodying a collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator, said rules input to software employing relational algebraic expressions, said expressions responsive to a computer language database query.

An apparatus for determining equivalence of SQL queries, comprising

• means for accepting at least two SQL queries;
• and
• means for generating at least one relational algebraic expression by employing at least one equivalence rule involving the multiset version of the theta-semijoin operator, said generated expressions equivalent to respective queries.

A storage device embodying a collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator, said rules input to software employing relational algebraic expressions, said expressions responsive to a computer language database query, said multiset version defined as ##EQU56## where R1 and R2 denote relations, .theta.(t.sub.2) denotes the predicate .theta. with attributes of R.sub.2 replaced by their values from tuple t.sub.2.

A storage device embodying a collection of equivalence rules involving the multiset version of the relational algebraic theta-semijoin operator, said rules input to software employing relational algebraic expressions, said expressions responsive to a computer language database query, said rules including rule ##EQU57## where E (with or without subscripts) denotes relational expressions, .theta. (with or without subscripts) denotes predicates, .sub..theta. denotes the .theta.-join operator, and .sub..theta. denotes the .theta.-semijoin operator.