Query reformulation with constraints

Abstract

Let Σ ₁ , Σ ₂ be two schemas, which may overlap, C be a set of constraints on the joint schema Σ ₁ ∪ Σ ₂ , and q ₁ be a Σ ₁ -query. An (equivalent) reformulation of q ₁ in the presence of C is a Σ ₂ -query, q ₂ , such that q ₂ gives the same answers as q ₁ on any Σ ₁ ∪ Σ ₂ -database instance that satisfies C . In general, there may exist multiple such reformulations and choosing among them may require, for example, a cost model.