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.