Proposition 4. 4. The schema mapping defined by the first-order sentence "x$y"z(Rxz ® Syz) is closed under target
homomorphisms, admits universal solutions, and allows for
conjunctive query rewriting, but is not definable by any finite
set of s-t tgds.
Can Proposition 4. 3 be turned to a characterization of
schema mappings specified by an infinite set of s-t tgds? The
next observation shows that this is not possible.
Proposition 4. 5. The schema mapping defined by the
following infinite set of s-t tgds does not admit universal
solutions:
{"x(Px ® y1 . . . yn(Rxy1 Ù Ry1y2 Ù . . . Ù Ryn−1yn) ) | n ³ 0}
Proof. (Hint) It is easy to see that no solution for I = {Pa}
can be universal. Here, the assumption that all instances
(hence all solutions) are finite is of the essence. ❑
Proposition 4. 4 implies that additional properties must
be considered in order to characterize the schema mappings that are definable by a finite set of s-t tgds. It turns out
that the addition of n-modularity, for some n > 0, yields such
a characterization.
Theorem 4. 6. For all schema mappings M, the following are
equivalent:
1. M is definable by a finite set of s-t tgds.
2. M is closed under target homomorphisms, admits universal solutions, allows for conjunctive query rewriting,
and is n-modular for some n > 0.
We conclude this section by commenting briefly on
additional characterizations presented in the previous
version of this paper.
17 Observe that the condition of
allowing for conjunctive query rewriting differs in nature
from the other structural conditions: while the latter are
model-theoretic conditions, the former refers to a certain
syntactically defined class of queries. Thus, it is natural to ask: can the condition of allowing for conjunctive
query rewriting be replaced by a condition of model-theoretic character? To this effect, we consider the notion of
reflecting source homomorphisms, which states, roughly,
that every homomorphism between source instances I, I¢
extends to a homomorphism from any universal solution
of I to any universal solution of I¢. We show that the structural characterizations of LAV dependencies in Theorem
4. 1 and of s-t tgds in Theorem 4. 6 hold with the condition of allowing for conjunctive query rewriting replaced
by that of reflecting source homomorphisms. Further,
we pursue characterizations where one assumes that the
schema mapping is first-order definable to start with. We
establish that, for all schema mappings M definable by
a first order sentence, M is definable by a finite set of
GAV dependencies if and only if M is closed under target homomorphisms, admits universal solutions, reflects
source homomorphisms, and is closed under target intersection. The proof makes essential use of the sophisticated machinery developed by Rossman16 for proving
the preservation-under-homomorphisms theorem in the
finite.
5. comPlexi TY of DefinABili TY
Our characterizations provide tools for testing whether
a schema mapping defined in one language can also be
defined in another language. For example, our results
imply that a schema mapping defined by a finite set of s-t
tgds is definable by a finite set of GAV dependencies if and
only if it is closed under target intersection: furthermore, it
is definable by a finite set of LAV dependencies if and only
if it is closed under union. Here, we pinpoint the
computational complexity of testing definability in the different
languages.
First, assume that the input to the problem is a finite
set of s-t tgds. The results are summarized in the following
table.
input schema
mapping
s-t tgds
s-t tgds
GAV dependencies
lAV dependencies
Desired schema
mapping
GAV dependencies
lAV dependencies
lAV dependencies
GAV dependencies
complexity of
definability
NP-complete
NP-complete
PTiME
NP-complete
The proofs also yield effective methods for constructing an equivalent schema mapping in the smaller language
whenever it exists. Our proofs are based on reductions from
definability problems to the entailment problem for s-t tgds;
given two schema mappings M1, M2, specified by a finite
set of s-t tgds, is it the case that whenever (I, J) Î M1 also
(I, J) Î M2 We show that the latter problem in NP-complete;
moreover, it is in PTIME if M1 is specified by LAV dependencies and M2 by GAV dependencies.
It is also natural to consider the problem of testing
whether a schema mapping specified by a first-order
sentence is definable in one of the schema-mapping
languages studied here. This problem, however, turns
out to be undecidable no matter what schema-mapping
language we consider (s-t tgds, GAV dependencies, or
LAV dependencies). This can be easily proved using the
undecidability of satisfiability for first-order sentences in
the finite.
18
6. Discussion AnD oPen PRoBlems
The work presented here has methodological implications for the study of schema mappings. Concretely, our
structural characterizations delineate the exact set of tools
available in the study of schema mappings specified in
particular languages. For example, consider the language
of LAV dependencies. A perusal of the literature reveals
that earlier results about schema mappings specified by
a finite set of LAV dependencies made systematic use of
the fact that such schema mappings are closed under target homomorphisms, admit universal solutions, allow for
conjunctive query rewriting, and are closed under union.
The structural characterization given in Theorem 4. 1,
in effect, turns the tables around and asserts that these