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