
Chapter 7: Foundations of Semantic Query Optimization 253
must hold also. Let F' be a replacement of F as performed in Step 2. If F'
holds in DB* then F must hold and so G must hold in DB*. If DB does not
satisfy G F, then there must be a counterexample, which must also occur
for one of the replacements of F. The case where G is empty is similar.
Finally, Step 3 involves the generation of relations by generative integrity
constraints; hence equivalence is maintained. •
For the rest of this paper we will assume that we are dealing with struc-
tured databases. We will also assume that the axioms (of IDB) are compiled.
This means that all the intensiona ...