(a) Closure under target
J1 Ç J2
(b) Closure under target
(c) Closure under union
certain answers query certainM(q) is definable by a union
of conjunctive queries over the source schema. In other
words, there is a union q¢ of conjunctive queries over the
source schema such that certainM(q)(I) = q¢(I), for every
source instance I.
The first two conditions of closure under target homomorphisms and admitting universal solutions go very well
together. As was observed in Fagin et al.,
7 if a schema mapping is closed under target homomorphisms and admits
universal solutions, then, for every source instance I, the
(typically infinite) space of all solutions of I w.r.t. M can
be completely described by just a single target instance J,
namely, by any universal solution J for I. This is so because
if J is universal for I and M is closed under target homomorphisms, then for every target instance J¢, we have that
J¢ is a solution for I if and only if there is a homomorphism
h: J ® J¢ that is constant on adom(I). We mention in passing
that these two conditions together also imply the existence
of core universal solutions, which are the smallest universal solutions (see Fagin et al.
8). Thus, these two conditions
lie at the foundation of data exchange. The third condition
of allowing for conjunctive query rewriting is important in
the context of data integration, since it implies that the certain answers of unions of conjunctive queries over the target are computable in polynomial time (in the sense of data
It is well known that all three conditions of closure
under target homomorphisms, admitting universal
solutions, and allowing for conjunctive query rewriting
are possessed by every schema mapping M definable by
a finite set of s-t tgds. Closure under homomorphisms
follows easily from the definitions; admitting universal solutions was shown in Fagin et al.
7 using the chase
procedure. In the case of GAV dependencies, a union of
conjunctive queries over the target is easily transformed
to a union of conjunctive queries over the source by simply replacing each target relation symbol P by a union of
conjunctive queries over the source that defines P. In the
case of arbitrary s-t tgds, allowing for conjunctive query
rewriting is proved by first “decomposing” the given s-t
tgds into GAV dependencies and to LAV dependencies,
and then applying results from Abiteboul and Duschka1
and Duschka and Genesereth.
6 We collect these results
into one theorem.
Theorem 3. 4. Every schema mapping definable by a
finite set of s-t tgds is closed under target homomorphisms,
admits universal solutions, and allows for conjunctive query
Next, we define three additional properties of schema
Definition 3. 5. Let M be a schema mapping.
• Closure Under target intersection: We say that M is
closed under target intersection if for all source instances
I and all target instances J1, J2 if (I, J1) Î M and
(I, J2) Î M, then also (I, J1 Ç J2) Î M. (See Figure 5b.)
• Closure Under Union: We say that M is closed under
union if (0/, 0/) Î M, and for all (I1, J1) Î M, and (I2, J2)
Î M, we have that also (I1È I2, J1ÈJ2) Î M. (See
• n-Modularity: Let n be a positive integer. We say that M is
n-modular if whenever a pair (I, J) does not belong to M,
there is a sub-instance I ' Í I such that |adom (I¢)| £ n and
(I¢, J) does not belong to M.
Intuitively, a schema mapping is closed under union if
solutions can be constructed in a “modular” fashion, i.e., on
a tuple-by-tuple basis. Similarly, n-modularity asserts that if
(I, J) Ï M, then there is a concise explanation for this fact;
this property can also be viewed as a relaxation of closure
We now give several useful propositions about the properties we just introduced.
Proposition 3. 6. Let M be a schema mapping.
• If M is definable by a finite set of GAV dependencies, then
M is closed under target intersection.
• If M is definable by a finite set of LAV dependencies, then
M is closed under union.
• If M is definable by a finite set of s-t tgds, then M is
n-modular for some n ≥ 1.
Proof. The first two parts follow easily from the definitions. For the third part, assume that M is a schema
mapping definable by a finite set S of s-t tgds. Let n be the
maximum number of variables occurring in the left-hand
side of the s-t tgds in S. We claim that M is n-modular.
Assume that (I, J) Ï M. Then there is some s-t tgd "x(f(x) ®
$yy (x, y) ) from S and a tuple a of values from adom(I) such
that (I, J) |= f(a) Ù Ø$yy(a, y). Now, let I¢ be the sub-instance
of I containing only the values a. Then, it is still the case that
(I¢, J) |= f (a) Ù Ø$yy(a, y), and hence (I¢, J) Ï M. ❑
4. lAnGuAGe cHARAc TeRizATions
This section contains the main technical results of the
paper, which yield structural characterizations of the various schema-mapping languages considered in earlier sections. We begin with schema mappings specified by LAV