Predicate transformation and factoring to provide additional optimization paths

Predicate transformation and factoring increases the number of choices available to the query processor. It adds optimizable clauses to a query by extracting clauses from blocks of predicates linked with or into clauses linked by and. The additional optimized clauses mean there are more access paths available for query execution. The original or predicates are retained to ensure query correctness.

During predicate transformation:

Simple predicates (joins, search arguments, and in lists) that are an exact match in each or clause are extracted. In the query in step 3, below, this clause matches exactly in each block, so it is extracted:
```
t.pub_id = p.pub_id
```
between clauses are converted to greater-than-or-equal and less-than-or-equal clauses before predicate transformation. The sample query uses between 15 in both query blocks (though the end ranges are different). The equivalent clause is extracted by step 1:
```
price >=15
```
Search arguments on the same table are extracted; all terms that reference the same table are treated as a single predicate during expansion. Both type and price are columns in the titles table, so the extracted clauses are:
```
(type = "travel" and price >=15 and price <= 30)
or
(type = "business" and price >= 15 and price <= 50)
```
in lists and or clauses are extracted. If there are multiple in lists for a table within a blocks, only the first is extracted. The extracted lists for the sample query are:
```
p.pub_id in (“P220”, “P583”, “P780”)
or
p.pub_id in (“P651", “P066", “P629”)
```
Since these steps can overlap and extract the same clause, duplicates are eliminated.

Each generated term is examined to determine whether it can be used as an optimized search argument or a join clause. Only those terms that are useful in query optimization are retained.

The additional clauses are added to the query clauses specified by the user.

For example, all clauses optimized in this query are enclosed in the or clauses:
```
       select p.pub_id, price
from publishers p, titles t
where (
     t.pub_id = p.pub_id
     and type = “travel"
     and price between 15 and 30
     and p.pub_id in (“P220", “P583", “P780")
     )
or  (
     t.pub_id = p.pub_id
     and type = “business"
     and price between 15 and 50
     and p.pub_id in (“P651", “P066", “P629")
     )
```

Predicate transformation pulls clauses linked with and from blocks of clauses linked with or, such as those shown above. It extracts only clauses that occur in all parenthesized blocks. If the example above had a clause in one of the blocks linked with or that did not appear in the other clause, that clause would not be extracted.