CANONICAL ABSTRACTION FOR OUTERJOIN OPTIMIZATION

A system, apparatus, and program storage device implementing a method of optimizing queries used for searching a computerized database, wherein the method comprises providing a query comprising a sequence of inner joins and outerjoins; and rewriting the query by producing a sequence of outer Cartesian products for the query; producing a sequence of nullification operations on the query; and producing a sequence of best match operations on the query. The method further comprises optimizing the query using a query execution plan for processing the rewritten query, wherein the query execution plan expands a search space in the database for which the rewritten query may be run.