Georg Gottlob
email: georg.gottlob@comlab.ox.ac.uk.

P Senellart
email: pierre.senellart@telecom-paristech.fr.

Schema Mapping Discovery from Data Instances

Keywords: F.2.0 [Analysis of Algorithms and Problem Complexity]: General; H.2.5 [Database Management]: Heterogeneous Databases Languages, Theory Schema mapping, instance, complexity, match, data exchange

We introduce a theoretical framework for discovering relationships between two relational database instances over distinct and unknown schemata. This framework is grounded in the context of data exchange. We formalize the problem of understanding the relationship between two instances as that of obtaining a schema mapping so that a minimum repair of this mapping provides a perfect description of the target instance given the source instance. We show that this definition yields "intuitive" results when applied on database instances derived from each other with basic operations. We study the complexity of decision problems related to this optimality notion in the context of different logical languages and show that, even in very restricted cases, the problem is of high complexity.

INTRODUCTION

Main Problem Addressed. This paper deals with the automatic discovery of relational schema mappings based on existing data. In particular, we deal with the following main problem, and with closely related questions. Given a relational schema S, called the source schema, and a differently structured target schema T, and given an instance I of S, and an instance J of T, where we assume that J consists of an adequate "translation" of I to fit the target schema T, find an optimal translation function, i.e., a schema mapping that maps instances of S to instances of T, taking I to J. This main problem actually consists of two important sub-problems: (i) determining an appropriate formal framework in which schema mappings can be expressed and that allow one to numerically assess the quality of a schema mapping, and (ii) understanding the computational fundamentals of the automatic synthesis of schema mappings in that framework, in particular, complexity issues and algorithms. We do not provide a direct algorithm for deriving schema mappings from database instances, but we discuss a theoretical framework and complexity analysis that can be a first step toward it.

Importance of the Problem. Schema mapping discovery has been recognized as an issue of central relevance in various application and research contexts, for example, in the area of data exchange [START_REF] Fagin | Data exchange: Semantics and query answering[END_REF][START_REF] Kolaitis | Schema mappings, data exchange, and metadata management[END_REF], data integration [START_REF] Lenzerini | Data integration: a theoretical perspective[END_REF][START_REF] Haas | Clio grows up: from research prototype to industrial tool[END_REF], metadata management [START_REF] Bernstein | Applying model management to classical meta data[END_REF], and data extraction from the hidden Web, in particular, automated wrapper generation.

Schemata and dependencies, in a data exchange context, form metadata that need to be managed in a systematic and formal way. [START_REF] Bernstein | Applying model management to classical meta data[END_REF] argues for the definition, in such a setting, of operators on this metadata. Thus, [START_REF] Fagin | Composing schema mappings: Second-order dependencies to the rescue[END_REF]] and [START_REF] Fagin | Quasi-inverses of schema mapping[END_REF]] respectively propose ways to define the composition and inverse operators on schema mappings. Another operator of importance, which is actually closely related to the research proposed in the present paper, is the match operator [START_REF] Bernstein | Applying model management to classical meta data[END_REF]]: given two schemata and instances of these schemata, how to derive an appropriate set of dependencies between these schemata. More precisely, given two relational databases schemata S and T and instances I and J of these schemata, the problem is to find a schema mapping, that is, a finite set Σ of formulas in a given language L, such that (I, J) |= Σ, or such that (I, J) approximates in some sense a model of Σ. This problem is related to the techniques used for automatic schema matching in data exchange. Current methods of automated schema mapping generation, such as those described in [START_REF] Rahm | A survey of approaches to automatic schema matching[END_REF][START_REF] Haas | Clio grows up: from research prototype to industrial tool[END_REF], heavily rely on semantic meta-information about the schemata (names of concepts and relations, concrete data types, etc.). However, in many practical contexts such semantic meta-information is either not available or would require too much or too expensive human interaction. In those cases, the mere values of I and J constitutes the only information from which a mapping ought to be constructed. This important case, which has been barely studied, is addressed in the present paper. Obviously, such a study is also a first step towards schema matching systems that use both schema-based and data-based information.

In automated wrapper generation (e.g., from Web sources), the absence of suitable meta-information is a similar problem. Let us take a concrete example, namely that of extracting information from research publications databases on the Web. Consider for instance the list of publications by Jeffrey D. Ullman provided by DBLP 1 and Google Scholar 2 . A structural information extraction wrapper such as RoadRunner [START_REF] Crescenzi | Roadrunner: Towards automatic data extraction from large Web sites[END_REF]] can be applied on both pages (or set of pages obtained by following the Next links) to obtain relational data from these pages, without any metadata. The set of papers presented by both sources is not exactly the same, their organization is different (for instance, grouping by dates in DBLP),

• 3 some data is present in some source and not in the other (page numbers in DBLP, direct links to electronic versions of articles in Google Scholar), but both sources essentially present information about the same data. Using the mutual redundancy of these sources to detect the most appropriate schema mapping between them would enable us to wrap from one format of output to another. If the structure of one source is known, then this schema mapping would give us the core structure of the other one, in a fully automatic way.

Results. After stating in Section 2 some relevant definitions, in Section 3 of this paper we present a novel formal framework for defining and studying the automatic discovery of schema mappings. In this framework, schema mappings are-not surprisingly-expressed as source-to-target tuple generating dependencies (tgds). It is well known that tgds are suited for this task. However, we also introduce a cost function, that tells us how well a tgd does its job of translating the given source instance I into the given target instance J. This cost function takes into account (i) the size of the tgd, (ii) the number of repairs that have to be applied to the tgd in order for it to be valid and to perfectly explain all facts of J.

Of course, defining a cost function may be seen as a somewhat arbitrary choice. However, in Section 4, we give formal evidence of the appropriateness of the cost function, showing that it enjoys nice properties when I and J are derived from each other with elementary relational operations.

We study in Section 5 the computational complexity of the relevant problems. In particular, we show that computing the cost of a schema mapping lies at the third level of the polynomial hierarchy, while either fullness or acyclicity conditions reduce this complexity by one level. The problem is thus NP-complete for full acyclic tgds, and it remains NP-complete even in a very simple case where there is only one relation of arity 3 in the source schema, and one relation of arity 1 in the target schema. To see that, we use a lemma on the complexity of the Vertex-Cover problem in r-partite r-uniform hypergraphs, which is interesting in itself.

We finally discuss in Section 6 an extension and variants of this approach. We show in particular how the cost definition can be extended to a schema mapping expressed as an arbitrary first-order formula and discuss the complexity of the relevant problems. We also examine other choices for the cost function, which may seem simpler at first and closer to the existing notion of repair of a database in the literature [START_REF] References Arenas | Consistent query answers in inconsistent databases[END_REF]], but which are not appropriate to our context since they do not share the same "niceness" properties established in Section 4.

Related Work. We are not aware of any work with the same focus on a theoretical and systematic analysis of the complexity of deriving a schema mapping from instances, although, in spirit, the problem that we deal with here is similar to the one that inductive logic programming (ILP) [START_REF] Lavrač | Inductive Logic Programming: Techniques and Applications[END_REF] aims to solve. An approach to the complexity of ILP is presented in [START_REF] Gottlob | On the complexity of some inductive logic programming problems[END_REF]; the main differences with the work discussed here is the use of negative examples, the existence of a background knowledge, and the restriction to Horn clauses instead of arbitrary tgds.

The notion of repair appears in the context of inconsistent databases [START_REF] References Arenas | Consistent query answers in inconsistent databases[END_REF]] (with respect to some integrity constraint). In this work, consistent query answers are defined as the common answers to a query on minimal repairs of the database. Repairs use the addition or deletion of tuples to the database, something close to what is discussed in Section 6 and that we show inappropriate to our context. Besides, the focus is different: Arenas et al. suppose the integrity constraint fixed, while we are looking for an optimal schema mapping without any a priori.

Finally, note that the work presented here appeared in an abridged form in [Senellart and [START_REF] Senellart | On the complexity of deriving schema mappings from database instances[END_REF]. Most proofs appear here for the first time, as well as the formal statement of Theorem 4.1, the distinction between complexity for a language and the language of its repairs, and the various DP-hardness results.

PRELIMINARIES

We assume some countably infinite sets C of constants (denoted a, b, 0, 1, etc.) and V of variables (denoted x, y, z, etc.). We use the notation x to represent a vector of variables x 1 . . . x n . Constants appearing in formulas are here identified, as usual, with the domain elements they are interpreted by.

A (relational) schema is a finite set of pairs (R, n) where R is a relation name and n 1 the arity of the relation. An instance I of a relational schema S consists, for every (R, n) ∈ S, of a finite relation over C n . We occasionally denote R I the interpretation of the relation name R in the instance I (if |S| = 1, we shall make the confusion R I =I). In the following, we assume that the schemata are implicitly given whenever we are given an instance.

A language L is a subset of the set of formulas of first-order logic with equality and constants, and without function symbols (with its usual semantics). Given a language L, a schema mapping in L is a finite set of formulas in L. We are particularly interested in the following languages, given instances I, J with schemata S, T:

Relational calculus. L rc is the set of first-order formulas without constants or equalities, with relations symbols in S ∪ T.

Source-to-target tuple-generating dependencies. L tgd ⊂ L rc is the set of formulas of the form ∀x ϕ(x) → ∃y ψ(x, y) where: (i) ϕ(x) is a (possibly empty) conjunction of positive relation atoms, with relation symbols in S; (ii) ψ(x, y) is a conjunction of positive relation atoms, with relation symbols in T; (iii) all variables of x appear in ϕ(x). As for L rc , we assume that no constants or equality relations appear in the formulas. This choice is discussed in more detail in Section 3, when repairs of a tgd are introduced.

Acyclic tgds. L acyc ⊂ L tgd is the set of tgds such that (i) the hypergraph of the relations on the left hand-side is acyclic [START_REF] Beeri | Properties of acyclic database schemes[END_REF]; and (ii) the hypergraph of the relations on the right hand-side, considering only existentially quantified variables, is also acyclic. More precisely, the tgd is said to be acyclic if there are two forests F and F ′ (called the join forests) with each relation atom of ϕ(x) (respectively, of ψ(x, y)) a node of F (respectively, F ′ ), such that for all variables v ∈ x (respectively, v ∈ y), the subgraph of F (respectively, F ′ ) induced by the atoms of ϕ(x) (respectively, ψ(x, y)) that contain v is connected. Consider for

• 5 example the tgds:

θ 1 = ∀x R(x) → ∃y R(x, y) θ 2 = ∀x∀y∀z R(x, y) ∧ R(y, z) ∧ R(z, x) → R ′ (x, y, z)
The tgd θ 1 is acyclic, while θ 2 is not. Other equivalent definitions of acyclic hypergraphs are given in [START_REF] Beeri | Properties of acyclic database schemes[END_REF]]. Note that this notion of acyclicity is not related to the notion of weakly acyclic sets of tgds that has been much studied in the context of data exchange [START_REF] Fagin | Data exchange: Semantics and query answering[END_REF][START_REF] Kolaitis | Schema mappings, data exchange, and metadata management[END_REF].

Full tgds. L full ⊂ L tgd is the set of tgds without an existential qualifier on the right-hand side, that is, of the form

∀x ϕ(x) → ψ(x).
Acyclic full tgds. L facyc = L acyc ∩ L full is the set of full tgds such that the hypergraph of the relations on the left hand-side is acyclic.

We focus here on source-to-target tuple-generating dependencies (either arbitrary or with one of the restrictions mentioned above). Arbitrary tgds (and, in a lesser way, full tgds) have been at the basis of most works3 in the data exchange setting [START_REF] Fagin | Data exchange: Semantics and query answering[END_REF][START_REF] Kolaitis | Schema mappings, data exchange, and metadata management[END_REF]]. As we shall see in Section 5, acyclic full tgds have nice complexity results. We show in Section 6 how this work can be extended to arbitrary formulas of the relational calculus.

COST AND OPTIMALITY OF A TGD

We first introduce the two basic notions of validity and explanation that are at the basis of our framework. A schema mapping Σ explains a ground fact f in the target schema with respect to a source instance I if, for all instances K of the target schema such that (I, K) |= Σ, f ∈ K.

A schema mapping fully explains a target instance J with respect to a source instance I if it explains all facts of J with respect to I.

We have quite an asymmetric point of view about the pair of instances here; we do not require a full explanation of I by the facts of J, for instance. This asymmetry is quite common in the context of data exchange. For source-to-target tgds, note that Σ fully explains J with respect to I if and only if J is included in the result of the chase [START_REF] Fagin | Data exchange: Semantics and query answering[END_REF]] of I by Σ.

Example 3.3. Let us consider the following database instances I and J, on schemata {(R, 1)} and

{(R ′ , 2)}. R R ′ a b c d a a b b c a d d g h
We can imagine a number of schema mappings that more or less express the relationship between I and J:

Σ 0 = ∅ Σ 1 = {∀x R(x) → R ′ (x, x)} Σ 2 = {∀x R(x) → ∃y R ′ (x, y)} Σ 3 = {∀x∀y R(x) ∧ R(y) → R ′ (x, y)} Σ 4 = {∃x∃y R ′ (x, y)} Σ 5 = Σ 1 ∪ Σ 2
Σ 0 and Σ 4 seem pretty poor, here, as they fail to explain any facts of J, while there seems to be a definite connection (albeit with some noise) between I and J. Σ 3 explains most of the facts of J, but is far from being valid, since it also explains a large number of incorrect facts such as R ′ (a, b) or R ′ (b, d). Σ 1 , Σ 2 , and Σ 5 are more interesting. Σ 1 explains 3 facts of J, but also incorrectly predicts R ′ (c, c). Σ 2 fails to explain any facts of J, but explains most of them at least partially, in the sense that they are explained by a fact with an existentially quantified variable (a skolem); in addition, it is valid with respect to (I, J). Σ 5 combines the interesting features of Σ 1 and Σ 2 , with the downside of being larger. None of the schema mappings explain the last fact of J.

As there seems to be some noise in the operation that produced J from I, it is hard to say with certainty which schema mapping is optimal here, meaning that it reflects most closely the relationship between I and J. At any rate, however, Σ 1 , Σ 2 , and Σ 5 seem far better candidates than the other ones.

To define in a formal way our notion of optimality of a schema mapping, the basic idea is to get the simultaneous optimal for all three factors of interest (validity, explanation of the target instance, conciseness) by minimizing the size of: the original formula, plus all the local corrections that have to be done for the formula to be valid and to fully explain the target instance. This is close in spirit to the notion of Kolmogorov complexity and Kolmogorov optimal [START_REF] Li | An Introduction to Kolmogorov Complexity and Its Applications[END_REF]] (though we do not consider a Turing-complete language for expressing either the formula or the corrections, but much more limited languages). Definition 3.4. Given a schema mapping of tgds Σ ⊂ L tgd , we define the set of repairs of Σ, denoted repairs (Σ), as a set of finite sets of formulas, such that Σ ′ ∈ repairs (Σ) if it can be obtained from Σ by a finite sequence of the following operations:

Adding to the left-hand side of a tgd θ of Σ, with θ of the form ∀x ϕ(x) → ∃y ψ(x, y), a conjunction τ (x) of the form: i x i α i c i where α i is either = or =, x i is a variable from x and c i is a constant.

• 7

Adding to the right-hand side of a tgd θ of Σ, with θ as above, a formula τ ′ (x, y) of the form:

i     j x ij = c ′ ij   → y i = c i  
where x ij are variables from x, y i variables from y, and c ′ ij and c i constants. Adding to Σ a ground fact R(c 1 . . . c n ) where R is a relation of arity n, and c 1 . . . c n are constants.

The language of repairs L * of a language L is the language consisting of all formulas which can be obtained from formulas of L with these operations (along with all ground facts over the target schema).

In a repair of a tgd ∀x ϕ(x) ∧ τ (x) → ∃y ψ(x, y) ∧ τ ′ (x, y), the term τ (x) is responsible for correcting cases when the tgd is not valid, by adding additional constraints on the universal quantifier, whereas τ ′ (x, y) specifies the right-hand side of J, by giving the explicit value of each existentially quantified variable, in terms of the universally quantified variables.

Example 3.5. Consider the databases instances and schema mappings from Example 3.3. Two examples of repairs of Σ 2 = {∀x R(x) → ∃y R ′ (x, y)} are the following:

Σ ′ 2 = {∀x R(x) ∧ x = e → ∃y R ′ (x, y), R(d, f )} Σ ′′ 2 = {∀x R(x) → ∃y R ′ (x, y) ∧ (x = a → y = a) ∧ (x = b → y = b) ∧ (x = c → y = a) ∧ (x = d → y = d), R(g, h)} Σ ′
2 is not especially interesting with respect to I and J, since the condition R(x) ∧ x = e is never verified in I and R(d, f ) is not a fact in J. On the other hand, Σ ′′ 2 has nice properties: it is still valid with respect to (I, J) (this was already the case with Σ 2 ) and it fully explains J given I (this was not true for Σ 2 ). Σ ′′ 2 is then somehow a "perfect" repair of Σ 2 that corrects all problems with the original schema mapping. It is however quite long, since all conditions are enumerated one by one. In the following, we define the quality (or cost) of a schema mapping in terms of the size of its minimal "perfect" repair.

An interesting property of repairs is that they are reversible: Because all operations add constants to a language where constants do not exist, it is possible to compute (in linear time) the original schema mapping from a repair. Indeed, constants are only used for repairing formulas; in other words, we consider that the relationships that we need to find between the source and target instances are to be expressed with constant-free formulas, in order to abstract them as much as possible. Clearly, this is a simplifying assumption that could be lifted in future works. Note that this extension is not straightforward, however: It is not clear how to distinguish between constants which are rightfully part of the optimal schema mapping description and constants which are just used to correct some noise or missing data.

The notion of size of a schema mapping is easily defined as follows; we could also use a more classical definition in function of the number of symbols of a formula, without much difference in the theory.

Definition 3.6. The size of a first-order formula ϕ ∈ L * , denoted size(ϕ) is computed as follows:

The size of ϕ is the number of occurrences of variables and constants in ϕ (we stress that each variable and constant is counted as many times as it occurs in ϕ); occurrences of variables as arguments of quantifiers are not counted. If ϕ is a ground fact R(c 1 . . . c n ), then the size of ϕ is computed as if ϕ were the (equivalent) formula

∃x 1 . . . ∃x n R(x 1 . . . x n ) ∧ x 1 = c 1 ∧ • • • ∧ x n = c n . Therefore, size(ϕ) = 3n.
The size of a schema mapping is the sum of the size of its elements.

The refinement on ground facts is performed so that such facts are not "too cheap": the cost of R(c 1 . . . c n ) is the same as that of the corresponding repair of ∃x 1 . . . ∃x n R(x 1 . . . x n ), as will be illustrated in Example 3.9. This is not a major assumption, however, and it does not impact the results of this paper in a significant way. We are now ready to define the cost of a schema mapping, in terms of the size of its repairs: Definition 3.7. The cost of a schema mapping Σ, with respect to a pair of instances (I, J), is defined by:

cost (I,J) (Σ) = min Σ ′ ∈repairs(Σ) (I, J) |= Σ ′ and Σ ′ fully explains J size(Σ ′ ).
Note that cost (I,J) (Σ) may not be defined if the minimizing set is empty.

A schema mapping Σ ⊂ L is optimal in the language L, with respect to a pair of instances (I, J), if:

cost (I,J) (Σ) = min Σ ′ ⊂L Σ ′ finite cost (I,J) (Σ ′ ) .
It is indeed possible that cost (I,J) (Σ) is not defined. This is for instance the case for T = {(R ′ , 1)}, Σ = {∃x R ′ (x)} and J = ∅. However, this case is easily recognizable; in other cases we have a linear bound on the cost of a schema mapping: Proposition 3.8. There is an algorithm to check whether the cost of a schema mapping in L tgd is defined that is polynomial in the size of the target instance. If it is defined, the cost is bounded by a linear function of the size of the data and the schema mapping itself.

Proof. Let Σ be a schema mapping, I and J instances of the source and target schemata. Then the cost of Σ with respect to (I, J) is undefined if and only if it contains a tgd θ without a left-hand side (that is, of the form ∃y ψ(y)) and which is not valid in J, which can be tested in polynomial time in the size of J (this amounts to evaluating a conjunctive query over J).

To see this, we shall prove that in all other cases, there is a linear bound on cost (I,J) (Σ). Indeed, every tgd with a left-hand side can be canceled by adding an x = c term on the left-hand side, where x is a universally quantified variable and c a constant which does not appear in I. Moreover, all facts of J can be added to the repair of the tgd as ground facts. We then have the following bound on the cost of Σ:

cost (I,J) (Σ) size(Σ) + 2 |Σ| + 3r |J|
where r is the maximum arity of a target relation. This linear bound is interesting, since we can imagine to use local search algorithms to find the tgd with minimum cost, as long as we are able to compute in an efficient way the cost of a tgd. We shall see in Section 5, unfortunately, that even for a very restricted language computing the cost of a tgd is NP-complete.

Example 3.9. Let us go back to the instances and schema mappings of Example 3.3, compute their respective cost, and see which one is optimal.

Consider first

Σ 1 = {∀x R(x) → R ′ (x,
x)} and let us find its perfect repair of minimal size. Since Σ 1 incorrectly predicts R ′ (c, c), we need to add a condition on the left-hand side; " ∧ x = c" is enough, only invalidates this fact, and there is no correction whose size would be smaller. With this addition, Σ 1 becomes valid, but does not fully explain all facts of the target instance. The only way to fix this is to add the ground facts R ′ (c, a) and R ′ (g, h) to Σ 1 , to obtain a repair

Σ ′ 1 = {∀x R(x) ∧ x = c → R ′ (x, x), R ′ (c, a), R ′ (g, h)
} that is valid and fully explains the target instance. The discussion above shows that

Σ ′ 1 is of minimal size. This means cost (I,J) (Σ 1 ) = size(Σ ′ 1 ) = (3 + 2) + 2 • 3 • 2 = 17. Consider now Σ 4 = {∃x∃y R ′ (x, y)}.
Since the formula has no left-hand side, we only need to consider the last two repair operations: correcting existential qualifiers and adding ground facts. Adding one of the fact of J to Σ 4 yields an increase in the size of the formula of 3 × 2 = 6. On the other hand, we can obtain one of the fact of J by repairing the existential qualifiers with, say, " ∧ x = a ∧ y = a", for an increase in size of 4. The cost of Σ 4 is thus the sum of 2 (the original size of the formula), 4 (the size of the repair of the existential qualifiers, to predict one of the facts of J), 4 × 6 (the size of the remaining facts of J added as ground facts), that is, 30.

We obtain in this way (the computation is similar for the other schema mappings):

cost (I,J) (Σ 0 ) = 3 • 2 |J| = 30 cost (I,J) (Σ 1 ) = 3 + 2 + 2 • 3 • 2 = 17 cost (I,J) (Σ 2 ) = 3 + 4 • 4 + 3 • 2 = 25 cost (I,J) (Σ 3 ) = 4 + 4 + 4 • 3 • 2 = 32 cost (I,J) (Σ 4 ) = 2 + 4 + 4 • 3 • 2 = 30 cost (I,J) (Σ 5 ) = 3 + 2 + 3 + 4 + 3 • 2 = 18
The fact that Σ 4 has the same cost as Σ 0 is no coincidence, this is due to the choice we made for the cost of a ground fact. It appears that Σ 1 is the best of these schema mappings, with Σ 5 almost as good, and Σ 2 a little behind. We can show that Σ 1 is actually the optimal schema mapping, that is, there are no other schema mappings with lesser cost. To see this, note first that both g and h occur in J without occurring in R. This means R ′ (g, h) is necessarily added as ground fact in the repair of any schema mapping. Therefore, disregarding this ground fact, only repaired schema mappings of size less than size(Σ 1 ) -6 = 11 are of potential interest. We can then enumerate all such repaired schema mappings and show that none is valid and fully explains J.

At least on this simple example, our measure of cost seems reasonable. We will further justify it in Section 4.

The following decision problems arise naturally once given this notion of optimality. Each of them is defined for a given language L (L can for instance be L tgd or L * acyc ), and we shall investigate their complexity in Section 5.

Validity

Given instances I, J, and Σ ⊂ L, is Σ valid with respect to (I, J)?

Explanation

Given instances I, J, and Σ ⊂ L, does Σ fully explain J with respect to I?

Zero-Repair

Given instances I, J, and Σ ⊂ L, is cost (I,J) (Σ) equal to size(Σ)?

Cost

Given instances I, J, Σ ⊂ L, and an integer K 0, is cost (I,J) (Σ) less than or equal to K? Existence-Cost Given instances I, J and an integer K 0, does there exist Σ ⊂ L such that cost (I,J) (Σ) is less than or equal to K?

Optimality

Given instances I, J and Σ ⊂ L, is it true that Σ is optimal with respect to (I, J)?

JUSTIFICATION

In this section, we justify the definitions of the previous section by observing that, when instances I and J are derived from each other by elementary operators of the relational algebra, the optimal schema mapping, in L tgd , is the one that "naturally" describes this operator. Let r, r ′ be instances of relations. We consider the following elementary operators of the relational algebra: Projection π i (r) denotes the projection of r along its ith attribute. Selection σ ϕ (r), where ϕ is a conjunction of equalities and negated equalities between an attribute of r and a constant, denotes the selection of r according to ϕ. Note that we allow neither identities between attributes of r (this is the role of the join operation), nor disjunctions (they may be expressed using a combination of selection and union). Union r ∪ r ′ is the union of r and r ′ . Intersection r ∩ r ′ is the intersection of r and r ′ . Product r × r ′ is the cross product of r and r ′ . Join r ✶ ϕ r ′ is the join of r and r ′ according to ϕ, where ϕ is an equality between an attribute of r and an attribute of r ′ ; ϕ is omitted when the context makes it clear.

The relationship between a database instance I and the instance J obtained from I using one of these operators can often be (partially) expressed in a natural way by a tgd or a set of tgds, where I is the source instance and J the target instance

• 11 (and similarly when the source instance is expressed as the result of applying some operator to the target instance). For instance ∀x R 1 (x) ∧ R 2 (x) → R ′ (x) is naturally associated with the intersection operator. The only case when the relationship between I and J has no natural expression as a tgd is for the reciprocal of the union operator:

If I = R J 1 ∪ R J 2 , the natural formula for describing this relation is ∀x R(x) → R 1 (x) ∨ R 2 (x)
, which is not a tgd since we do not allow disjunction. In some cases, as tgds are not powerful enough to express the relationship, or as some information is lost, the correspondence is only partial. For instance, ∀x R(x) → R ′ (x) is the most natural tgd for the operation J = σ ϕ (I), but the tgd does not fully describe the selection.

We now state that, using the notion of optimality of a schema mapping with respect to a pair of instances described in the previous section, and with some simple restrictions on the considered instances, the optimal schema mapping for a pair of instances obtained from each other with an operator of the relational algebra is precisely the schema mapping that is naturally associated with the operator. This justifies the choice of this notion of optimality, at least in these elementary contexts. We shall see in Section 6 other choices for the cost function, that might seem more natural at first, but that fail to satisfy the same property. For clarity's sake, we first state this result in an informal way and illustrate it on the example of the join operator, before presenting it formally.

Theorem 4.1 (Informally stated). For any elementary operator γ of the relational algebra, the tgd naturally associated with this operator (when it exists) is optimal with respect to (I, γ(I)) (or (γ(J), J), depending on the considered case), if some basic assumptions are fulfilled: the instances are not of trivial size and there is no simpler relation between attributes than the one described by the operator.

Let us see what this means, and prove this result, for the join operator. Suppose J = R I 1 ✶ R I 2 (with R 1 and R 2 two binary relation symbols), and let us add the basic assumptions that π 1 (J) = π 2 (J), π 1 (J) = π 3 (J), π 2 (J) = π 3 (J). We have:

cost (I,J) ({∀x∀y∀z R 1 (x, y) ∧ R 2 (y, z) → R ′ (x, y, z)}) = 7
since this tgd is valid and explains all facts of J. The cost of the empty schema mapping, 9 |J|, is greater since J is not empty. The only remaining relevant schema mappings with lesser size (of 5) have a single relation symbol R 1 or R 2 on the left-hand-side. But this means that they either predict two identical columns in J (this is incorrect, and has to be fixed in a repair of the schema mapping, whose additional cost is at least 2), or use an existential quantifier on the right-hand size, which also has to be repaired. Now consider the case where

I = R ′ 1 J ✶ R ′ 2 J
, and let us suppose all three attributes π i (I) disjoint.

cost (I,J) ({∀x∀y∀z R(x, y, z) → R ′ 1 (x, y) ∧ R ′ 2 (y, z)}) = 7 + 6 (x, y) ∈ R ′ 1 J | ∀z (y, z) / ∈ R ′ 2 J + 6 (y, z) ∈ R ′ 2 J | ∀x (x, y) / ∈ R ′ 1 J . cost (I,J) (∅) = 6
|J| is greater than that as soon as I is not empty. As we assumed all three attributes of I disjoint, we can eliminate a number of schema mappings that do not produce any correct facts. The only remaining ones only have R ′ 1 (w 1 , w 2 ) or R ′ 2 (w 2 , w 3 ) terms on the right-hand size with those three variables either existentially quantified or appearing, respectively in the first, second or third position of a R(w 1 , w 2 , w 3 ) atom on the left-hand side. None of these schema mappings can explain the facts that the schema mapping above does not explain, and existential quantifiers have to be accounted for in repairs.

We can now state the result of Theorem 4.1 more formally:

Theorem 4.2 (Formally stated). The tgds presented in the last column of Table I are optimal with respect to (I, J), when I and J are as described (in order not to clutter the table, universal quantifiers on the front of tgds are not shown).

Proof. First observe that the size of a ground fact of arity n is the same as the size of any maximal repair of the tgd without a left-hand side ∃x 1 . . .

∃x n R(x ′ 1 . . . x ′ n ).
This means that we do not need to consider such tgds.

Projection. Suppose J = π 1 (I) with I = ∅. Then:

cost (I,J) ({∀x∀y R(x, y) → R ′ (x)}) = 3
since it is valid and fully explains all facts of J. We then only need to consider schema mappings of size strictly lesser than 3. The only relevant one is the empty schema mapping and cost (I,J) (∅) = 3 |J| = 3 |I| which is greater or equal to 3 as soon as I = ∅.

Consider now the case when

I = π 1 (J) with π 1 (J) ∩ π 2 (J) = ∅, |π 1 (J)| 2.
We have:

cost (I,J) ({∀x R(x) → ∃x R ′ (x, y)}) = 3 + 4 |I| + 3 • 2(|J| -|I|) = 3 -2 |I| + 6 |J|
(this is a valid schema mapping, but it fails to explain all facts of J; |I| facts can be explained by repairing the existential quantifier, all others must be given as ground facts). As we assume that attributes of J have disjoint domains, all schema mappings with a R ′ (w 1 , w 2 ) where w 2 is not existentially quantified do not explain any facts of J. The only remaining schema mapping of interest is then ∅, whose cost is 6 |J|, which is greater than 3 -2 |I| + 6 |J| as soon as |I| 2.

Selection.

If J = σ ϕ (I), with |σ ϕ (I)| size(ϕ)+2 3
(in the common case where ϕ is a single equality or negated equality, size(ϕ) = 2 and this condition amounts to |J| 2), we have:

cost (I,J) ({∀x R(x) → R ′ (x)}) size(∀x R(x) ∧ ϕ(x) → R ′ (x)) = 2 + size(ϕ).
The only other schema mapping which might have a lesser cost is ∅ and cost

(I,J) (∅) = 3 |J| = 3 |σ ϕ (I)|. Now, suppose I = σ ϕ (J) with σ ϕ (J) = ∅. Observe that cost (I,J) ({∀x R(x) → R ′ (x)}) = 2 + 3(|J| -|I|)
Journal of the ACM, Vol. V, No. N, Month 20YY.

• 13

Table I. Optimal tgds for elementary operations of the relational algebra S T Condition on I I and J Optimal schema mapping

Projection (R, 2) (R ′ , 1) I non-empty J = π1(I) R(x, y) → R ′ (x) (R, 1) (R ′ , 2) π1(J) ∩ π2(J) = ∅, |π1(J)| 2 I = π1(J) R(x) → ∃y R ′ (x, y) Selection (R, 1) (R ′ , 1) |σϕ(I)| size(ϕ)+2 3 J = σϕ(I) R(x) → R ′ (x) (R, 1) (R ′ , 1) σϕ(J) non-empty I = σϕ(J) R(x) → R ′ (x) Union (R1, 1), (R2, 2) (R ′ , 1) R1 I R1 I ∪ R2 I , R2 I R1 I ∪ R2 I J = R I 1 ∪ R I 2 R1(x) → R ′ (x), R2(x) → R ′ (x) Intersection (R1, 1), (R2, 1) (R ′ , 1) R I 1 ⊆ R I 2 , R I 2 ⊆ R I 1 , R I 1 ∩ R I 2 = ∅ J = R I 1 ∩ R I 2 R1(x) ∧ R2(x) → R ′ (x) (R, 1) (R ′ 1 , 1), (R ′ 2 , 1) R ′ 1 J ∩ R ′ 2 J non-empty I = R ′ 1 J ∩ R ′ 2 J R(x) → R ′ 1 (x) ∧ R ′ 2 (x) Product (R1, 1), (R2, 1) (R ′ , 2) R I 1 and R I 2 non-empty J = R I 1 × R I 2 R1(x) ∧ R2(y) → R ′ (x, y) (R, 2) (R ′ 1 , 1), (R ′ 2 , 1) R ′ 1 J and R ′ 2 J non-empty I = R ′ 1 J × R ′ 2 J R(x, y) → R ′ 1 (x) ∧ R ′ 2 (y) Join (R1, 2), (R2, 2) (R ′ , 3) πi(R I 1 ✶ R I 2 ) = πj (R I 1 ✶ R I 2 ) (i = j) J = R I 1 ✶ R I 2 R1(x, y) ∧ R2(y, z) → R ′ (x, y, z) (R, 3) (R ′ 1 , 2), (R ′ 2 , 2) πi(R ′ 1 J ✶ R ′ 2 J ) ∩ πj (R ′ 1 J ✶ R ′ 2 J ) = ∅ (i = j) R ′ 1 J ✶ R ′ 2 J non-empty I = R ′ 1 J ✶ R ′ 2 J R(x, y, z) → R ′ 1 (x, y) ∧ R ′ 2 (y, z) Journal of the ACM, Vol. V, No. N, Month 20YY.
is lesser than cost (I,J) (∅) = 3 |J| as soon as |I| = ∅.

Union. If J = R I 1 ∪ R I 2 with both relations strictly included in their union,

cost (I,J) ({∀x R 1 (x) → R ′ (x), ∀x R 2 (x) → R ′ (x)}) = 4
while the cost of each of these tgds alone is greater than 5. We also have:

cost (I,J) ({∀x R 1 (x) ∧ R 2 (x) → R ′ (x)}) = 3 + 3 R I 1 ∪ R I 2 -R I 1 ∩ R I 2 9.
Finally, the cost of the empty schema mapping is:

3 R I 1 ∪ R I 2 6.
Intersection. Suppose J = R I 1 ∩ R I 2 with neither of these relations containing the other one;

cost (I,J) ({∀x R 1 (x) ∧ R 2 (x) → R ′ (x)}) = 3. Neither {∀x R 1 (x) → R ′ (x)}, nor {∀x R 2 (x) → R ′ (x)},
nor the empty schema mapping, have a lesser cost as soon as both R I 1 and R I 2 contain facts not in the other one, and the intersection is not empty.

Consider now the case where

I = R ′ 1 I ∩ R ′ 2 I . Then: cost (I,J) ({∀x R(x) → R ′ 1 (x) ∧ R ′ 2 (x)}) = 3 + 3 R ′ 1 J + R ′ 2 J -2 |I| while cost (I,J) ({∀x R(x) → R ′ 1 (x)}) = 2 + 3 R ′ 1 J + R ′ 2 J -|I| cost (I,J) ({∀x R(x) → R ′ 2 (x)}) = 2 + 3 R ′ 1 J + R ′ 2 J -|I| cost (I,J) (∅) = 3 R ′ 1 J + R ′ 2 J .
The first schema mapping has a lower cost than the other ones as soon as I = ∅.

Product. In both cases, the cost of the schema mapping from Table I is 4 (it is valid and explains all facts of J) and, unless one of the instance is empty, no other schema mapping of lesser size is valid and explains all facts of J.

Join. This has already been shown.

These results could also be extended to the cases where we have relations of greater arity, but we would then require strong constraints, as the one we imposed for reciprocal join (that all attributes are disjoint), so as not to have any "hidden" relation between the different attributes. A weaker assumption that could be made is to use a notion of Kolmogorov randomness [START_REF] Li | An Introduction to Kolmogorov Complexity and Its Applications[END_REF]]: A database instance selected at random cannot have a description of length lower than its size, thanks to a simple counting argument. We can use such random instances to get a contradiction when we obtain a schema mapping that uses hidden relations between

• 15 attributes of relations in the instance to have a lower cost than the natural schema mapping. Using such random instances is not straightforward to formalize: in the case of a join, for instance, we probably do not want to consider instances for which the result of the join is empty, which almost always happens if we consider truly random instances.

One might also want to extend this result to arbitrary relational expressions. However, this is not direct. The first issue is that arbitrary relational algebra expressions might not be minimal, or that several different algebra expressions of the same size might be equivalent (think of projections pushed inside joins, for instance). Depending on the way these expressions are transformed into tgds, this non-minimality may be reflected on the schema mapping itself, and we definitely do not want to derive a non-minimal schema mapping. Secondly, composing several basic operations of the relational algebra will yield in most cases formulas that are not expressible as tgds (possibly requiring second-order formulas [START_REF] Fagin | Composing schema mappings: Second-order dependencies to the rescue[END_REF]). Finally, we need to be sure that there are no hidden dependencies inside the data that will make another schema mapping optimal, as discussed above. The conditions for that were relatively simple in the case of the basic operations of the relational algebra but would be much more involved in the case of arbitrary expressions.

COMPLEXITY STUDY

We now proceed to a study of the computational complexity of the different problems identified in Section 3, for the different subsets of L tgd that we presented in Section 2. We focus here on combined complexity (when K and Σ are part of the input to the problem in addition to I and J), since we are precisely reasoning about the schema mappings themselves, but we also present at the end of the section data complexity results. We first describe general relationships between the different problems, before giving a full characterization of their complexity for L facyc , the language of full acyclic tgds. We also consider the more general cases of L tgd , L full , and L acyc . Existence-Cost and Optimality are be discussed separately.

We briefly go over the standard notations used for the complexity classes that are of interest here [START_REF] Papadimitriou | Computational Complexity[END_REF]]. All complexity classes are displayed in bold font. PTIME is the class of problems solvable in polynomial time by a deterministic Turing machine. A problem is in NP (respectively, coNP) if it is solvable (respectively, if its complement is solvable) in polynomial time by a non-deterministic Turing machine. DP is defined as the class of all languages L that can be written as L = L 1 ∩ L 2 , where L 1 ∈ NP and L 2 ∈ coNP. The polynomial hierarchy is defined inductively as follows: Σ P 0 = Π P 0 = PTIME, and for all i 0, Σ P i+1 = NP Σ P i and Π P i+1 = coNP Σ P i where A B is the class of problems solvable by a Turing machine in class A with access to an oracle for a B-complete problem. Observe that Σ P 1 = NP and Π P 1 = coNP.

General Complexity Results

As the complexity of the different decision problems depends on the particular language considered, we add to the problem name a subscript identifying the considered language (say, Optimality tgd for the Optimality problem in L tgd ).

We use an asterisk to indicate the problem concerns schema mappings that include (5) Algorithm 2 is a non-deterministic algorithm for the complement of Optimality.

(6) Directly results from the fact that a formula of L is also a formula of L ′ . An important remark is that this property does not necessarily hold for Existence-Cost and Optimality, since both of them depend on the existence of a formula in the underlying language.

Note that for each language considered here, there is a linear-time algorithm for determining if a formula is in this language; this is obvious for all except L acyc and L facyc , and an algorithm from [START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF] gives a linear-time algorithm for the acyclicity of hypergraphs.

In the next sections, we shall investigate in detail the complexity of the different problems in each of the identified subsets of L tgd , starting from L tgd itself. A summary of all combined complexity results proved in the following, along with their direct consequences, is shown in Table II. The lower part of Table II gives references to the propositions used to derive the complexity results shown in the upper part; in the case where there are two references, the first one is for the upper bound, the second one for the lower bound.

Combined Complexity for Full Acyclic TGDs

Let us first investigate the combined complexity of Validity and Explanation in L facyc . We shall need additional notions on acyclic joins from [START_REF] Beeri | Properties of acyclic database schemes[END_REF][START_REF] Yannakakis | Algorithms for acyclic database schemes[END_REF]]. Note first that an acyclic full tgd ∀x ϕ(x) → ψ(x) that describes the relation between a pair of instances (I, J) can be seen, in the relational algebra, as a project-join expression over the source instance, π ψ (✶ ϕ (I)), ϕ expressing the join (which is, by hypothesis, acyclic) and ψ expressing the projection. Adding repaired formulas, of the form ∀x (ϕ(x) ∧ τ (x)) → ψ(x), means adding an additional selection: π ψ (σ τ (✶ ϕ (I))).

A full reducer of a join expression is a program which removes some tuples to the relations to be joined (by performing semi-joins) so that each relation can then be retrieved as a projection of the full join. Such a full reducer always exists in acyclic databases and can be obtained in polynomial time [START_REF] Bernstein | Using semi-joins to solve relational queries[END_REF]. The full reducer itself runs in polynomial time. Finally, note that a join tree of an acyclic join can be obtained in linear time [START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF]. [START_REF] Yannakakis | Algorithms for acyclic database schemes[END_REF]] proposes then Algorithm 3 for computing the result to a projectjoin expression on an acyclic database, that we reuse with slight modifications in our next proposition.

An important property of this algorithm is that, at all time, the size of the Algorithm 3 . Result to a project-join expression on an acyclic database (after [START_REF] Yannakakis | Algorithms for acyclic database schemes[END_REF]]) Input: An acyclic join expression ϕ, a project expression ψ, an instance I.

Output: π ψ (✶ ϕ (I)).

(a) Compute a full reducer of the relation instances, and apply it.

(b) Compute a join tree T of the acyclic expression. Each node of the tree initially contains the corresponding reduced relation instance. (c) For each subtree of T with root r, compute recursively for each child r ′ of r the join of r with r ′ , and project to the union of the variables appearing in ψ and the common variables of r and r ′ . Remove r ′ and replace node r with this result.

relation stored in node r of T is bounded by the original (reduced) size of r times the size of the final output. This means in particular that this algorithm computes in polynomial time the result to the project-join expression. Actually, the same algorithm can be applied when repaired formulas are considered, since the only selection performed is a conjunction of constraints (equality and negated equality) on a given variable: These selections can be pushed inside the join.

Proposition 5.2. Validity facyc * and Explanation facyc * are in PTIME.

Proof. We first consider Validity and then Explanation.

(1) First check that the ground facts of Σ are valid. Then we have to apply Algorithm 3 on each ϕ of Σ which is not a ground fact to check whether its output is included in J. This, however, may not lead to a polynomial-time algorithm, since Algorithm 3 is polynomial in the size of the join expression, the input, and the output. The solution is to take care, at each join step, that the output remains in the bound given in the discussion of Algorithm 3. Assume that at some point during a run of the algorithm, the size of a relation stored at node r goes over the bound of the original size of r multiplied by the size of J; this means that the final output of the algorithm is larger than J, i.e., it is not included in J and (I, J) |= ϕ. Otherwise, the computation is polynomial in the size of ϕ, I, and J, we can let the algorithm terminate and check then if the output is included in J.

(2) For each fact f of J, proceed as follows. If f appears as a ground fact in Σ, it is fully explained in Σ. Otherwise, for each formula of Σ which is not a ground fact, we apply a variant of the algorithm presented above to decide whether f is in the output of the original algorithm (once again, by pushing selections inside joins), as described in Corollary 4.1 of [START_REF] Yannakakis | Algorithms for acyclic database schemes[END_REF]].

Zero-Repair is then tractable in L facyc . One might hope that this tractability extends to Cost. Unfortunately, we now show the NP-hardness of Cost facyc , even for a very simple schema mapping. For this purpose, we shall first need a quite general result on the minimal size of a vertex cover in a r-partite r-uniform hypergraph (for r 3).

A hypergraph is r-partite if the set of vertices can be decomposed into an rpartition, such that no two vertices of the same partitioning subset are in a same hyperedge. It is r-uniform if all hyperedges have a cardinality of r. A vertex cover

• • • • • • x 1 x1 x 2 x2 x 3 x3 • • • • • • y 1 ȳ1 y 2 ȳ2 y 3 ȳ3 • • • • • • z 1 z1 z 2 z2 z 3 z3 Fig. 1. Example tripartite hypergraph corresponding to the 3SAT instance ¬z ∨ x ∨ y
of a hypergraph is a subset X of the set of vertices, such that for every hyperedge e, at least one of the elements of e is in X. In regular graphs, Vertex-Cover (determining whether there is a vertex cover of size K) is one of the most wellknown and useful NP-complete problems [START_REF] Garey | Computers And Intractability. A Guide to the Theory of NP-completeness[END_REF]. This obviously implies that Vertex-Cover is NP-hard in general r-uniform hypergraphs. Note that a 2-partite 2-uniform hypergraph is just a bipartite graph, and Vertex-Cover in bipartite graphs is PTIME, thanks to Kőnig's theorem [START_REF] Diestel | Graph Theory[END_REF][START_REF] Kőnig | Theorie der endlichen und unendlichen Graphen[END_REF]] which states that the maximal number of matchings in a bipartite graph is the minimum size of a vertex cover.

Lemma 5.3. The problem of, given an r-partite r-uniform hypergraph H and a constant K, determining whether there exists a vertex cover in H of size less than or equal to K is NP-complete for r 3.

Proof. This problem is clearly in NP: Just guess a set of vertices of size less than or equal to K and check in polynomial time whether it is a vertex cover. For the hardness part, we prove the case r = 3; there is an obvious reduction from this case to the same problem for other values of r. We use a reduction from 3SAT.

Note that this result appears in [START_REF] Ilie | Reducing the size of NFAs by using equivalences and preorders[END_REF], but the reduction presented there is not exhaustive (in particular, nothing is said about interdependencies between clauses, or the fact that the hypergraph is tripartite) and it is not clear whether the proof was indeed led to completion. We use here a proof inspired by the proof that 3-Dimensional-Matching is NP-hard in [START_REF] Garey | Computers And Intractability. A Guide to the Theory of NP-completeness[END_REF].

Let ϕ = n i=1 c i be an instance of 3SAT, where the c i 's are 3-clauses over some set x of variables. We build a tripartite 3-uniform hypergraph H = (V, E) (with vertex partition V = V 1 ∪V 2 ∪V 3 ) in the following way (see Figure 1 for an illustration when ϕ = ¬z ∨ x ∨ y). For each variable x ∈ x, we add 12 nodes and 6 hyperedges to H. 6 out of the 12 nodes are anonymous nodes which only appear in one hyperedge; they are denoted by •. The other nodes are denoted x 1 , x 2 , x 3 , x1 , x2 , x3 . Intuitively, Journal of the ACM, Vol. V, No. N, Month 20YY.

• 21

Table III. Local edges used in the proof of Lemma 5.3

V 1 V 2 V 3 x 1 • x3 • x 2 x3 x1 x 2 • x1 • x 3 • x2 x 3 x 1 x2 •
all x i 's are in a minimum covering if and only if a valuation satisfying ϕ maps x i to true (similarly with the xi 's and false). For each i, x i and xi belong to V i . The so-called local hyperedges are shown in Table III. Then, for each clause c i , we add a single global hyperedge which contains the vertices corresponding to the variables appearing in c i , while taking into account their position in the clause and whether they are negated. For instance, if c i = ¬z ∨ x ∨ y, we add a hyperedge (z 1 , x 2 , y 3 ). This ensures that the hypergraph remains tripartite. This reduction is polynomial. Let m be the cardinality of x. We now show that ϕ is satisfiable if and only if there is a vertex cover in H of size less than or equal to 3m (or, equivalently, if there is a minimum vertex cover of size less than or equal to 3m).

Suppose first that ϕ is satisfiable, and let ν be a valuation of x which satisfies ϕ. Let us consider the following set S of vertices of H: For each x ∈ x, we add to S, x 1 , x 2 and x 3 if ν(x) is true, x1 , x2 and x3 otherwise. S is of cardinality 3m. Observe that S covers all local hyperedges and, since ν satisfies ϕ, all global hyperedges.

Suppose now that there is a minimum vertex cover S of size less than or equal to 3m. Since anonymous vertices only appear in a single hyperedge, we can always assume that S does not contain any anonymous vertex (they can always be replaced by another vertex of the hyperedge). Let S i be, for each 1 i m, the subset of S containing only the vertices corresponding to the ith variable of x. It is easy to see that |S i | 3 for all i, for all local hyperedges to be covered, which means that |S i | = 3 since | S i | 3m. S i forms a vertex cover of the local sub-hypergraph corresponding to the ith variable of x (let us call it x) and must cover the hyperedges of this sub-hypergraph. But there are only two vertex covers of this sub-hypergraph of cardinality 3: Either S i contains all x k 's, or it contains all xk 's. We consider the valuation ν of the variables in x which maps x to true in the first case, to false in the second. Then, since S is a vertex cover of H, ν satisfies all the clauses of ϕ.

We now use this lemma to prove the NP-hardness of Cost facyc .

Proposition 5.4. Cost facyc is NP-hard.

Proof. We consider first the case where we only allow negated equalities x = c, and no equalities x = c, on the left-hand side of repairs of tgds, with x a universally quantified variable, as the proof is clearer.

We reduce the vertex cover problem in tripartite 3-uniform hypergraphs to Cost facyc . Let H be a tripartite 3-uniform hypergraph. We consider the following instance of Cost facyc : S = {(R, 3)} and R I is the representation of H as a three-column table, where each row corresponds to an edge, and each column to one of the sets of the tripartition of H;

T = {(R ′ , 1)} and J = ∅; Σ = {∀x 1 ∀x 2 ∀x 3 R(x 1 , x 2 , x 3 ) → R ′ (x 1
)} (this is obviously an acyclic tgd).

As J = ∅, any schema mapping fully explains J. This also means that the only repairs of Σ to be considered are the ones that add a "x i = c i " term to the left-hand side of the single element of Σ. A repair of Σ has to "cancel" somehow with these additions each tuple of R I . In other words, the cost of Σ is size(Σ) + 2r, where r is the minimal number of conjuncts in a formula of the form x i = c i , such that this formula is false for all tuples of R I . Such a formula expresses a vertex cover in H, and H has a vertex cover of size less than or equal to K if and only if cost (I,J) (Σ) size(Σ) + 2K, which concludes the proof in this case.

In the case where we allow arbitrary repairs, including x = c terms on the lefthand side of a tgd, the same proof does not work, since it suffices to choose an arbitrary constant c which does not appear in I for the term x 1 = c to cancel every tuple of R I . To fix this, we need to make prohibitive the addition of such a term to Σ in the following way: Let c ′ , and, for 1 i 3, 1 j K, c i,j be 3K + 1 fresh constants. We can always assume that K is linear in the size of the input of Cost facyc (otherwise, just replace K with the upper bound of Proposition 3.8). We consider the following slightly modified instance of Cost facyc : S = {(R, 3)} and R I = A ∪ B, where A is the representation of H as a threecolumn table, where each row corresponds to an edge, and each column to one of the set of the tripartition of H, and B is the set:

{ R(c 1j , c ′ , c ′ ) | 1 j K } ∪ { R(c ′ , c 2j , c ′ ) | 1 j K } ∪ { R(c ′ , c ′ , c 3j ) | 1 j K } ; T = {(R ′ , 3)} and J is the same as B if R is replaced by R ′ ; Σ = {∀x 1 ∀x 2 ∀x 3 R(x 1 , x 2 , x 3 ) → R ′ (x 1 , x 2 , x 3 )} (this is obviously an acyclic tgd).
This reduction is polynomial if K is linear in the size of the input, as assumed. Σ fully explains J and the repairs considered in the previous case do not change this.

Let now x i = c be a term with 1 i 3 and c some constant. Whatever the choice of c, the addition of this term to the tgd of Σ cancels at least K tuples of B, and hence, fails to explain at least K tuples of J (the best case is when c = c ′ ). Just observe that, as the cost of a ground fact, which is the only way to repair unexplained tuples, is 9, the size of any repair of Σ with such an x i = c term on the left-hand side is greater than or equal to size(Σ) + 9K. We keep the fact that cost (I,J) (Σ) size(Σ) + 2K if and only if H has a vertex cover of size less than or equal to K.

It is an open issue whether Cost is in PTIME for the very restricted case when the schema mapping consists of a single full tgd with a single binary relation symbol appearing once in the left-hand side.

• 23

Combined Complexity for TGDs

We now look at the complexity of the same problems in the more general case of L tgd .

Proposition 5.5.

(1 ) Validity tgd and Validity tgd * are Π P 2 -complete.

(2 ) Explanation tgd * is in NP.

Proof.

(1) Validity tgd * is clearly in Π P 2 . First check the validity of the ground facts. For the other formulas of Σ, guess a valuation of the variables of the left-hand side; if the left-hand side is false (can be decided in polynomial time), give up the guess. Otherwise, use the NP oracle to decide whether the right-hand side holds; if it does not, return false. For the hardness part, we use a reduction of ∀∃3SAT: the satisfiability of the formula ∀x∃y ϕ(x, y), where ϕ is a propositional formula in 3-CNF over x ∪ y. This problem is Π P 2 -complete [START_REF] Wrathall | Complete sets and the polynomial-time hierarchy[END_REF][START_REF] Schaefer | Completeness in the polynomial hierarchy, a compendium[END_REF]. Let ∀x∃y n i=1 c i (z i1 , z i2 , z i3 ) be an instance of ∀∃3SAT, where each c i is a 3-clause, and each z ij is one of the variables of x ∪ y. We consider then the following instance of Validity tgd : S = {(B, 1)} and I = {B(0), B(1)};

T = {(R 1 , 3) . . . (R 8 , 3)} and J is such that the R J i 's are the 8 distinct subsets of {0, 1}
3 of cardinality 7 (this corresponds to the 8 possible truth tables of a 3-clause); For each 1 i n, let 1 k i 8 be the unique integer such that c i (z i1 , z i2 , z i3 ) is true if and only if (z i1 , z i2 , z i3 ) ∈ R J ki (with the usual abuse of notation of identifying values of boolean variables and values in {0, 1}). We now define Σ as follows:

Σ = ∀x m i=1 B(x i ) → ∃y n i=1 R ki (z i1 , z i2 , z i3 ) .
This reduction is clearly polynomial and yields an instance of Validity tgd . Now we have:

(I, J) |= Σ ⇐⇒ ∀x m i=1 (x i = 0 ∨ x i = 1) → ∃y n i=1 c i (z i1 , z i2 , z i3 ) is true ⇐⇒ ∀x∃y ϕ(x, y) is true
(2) Let F be the set of facts of J which are not directly in Σ as ground facts. Guess |F | valuations of the variables on the left-and right-hand sides of the formulas of Σ which are not ground facts. If, for all 1 i |F |, there is some ϕ ∈ Σ such that the ith valuation of the left-hand side of ϕ holds in I (which can be decided in polynomial time) and the ith fact of F appears in the ith valuation of the right-hand side of ϕ, then return true.

Combined Complexity for Full TGDs

We then consider the language of full tgds, L full .

Proposition 5.6.

(1 ) Validity full and Validity full * are coNP-complete;

(2 ) Explanation full is NP-hard.

(3 ) Zero-Repair full is DP-hard.

Proof.

(1) Here is a non-deterministic polynomial-time algorithm for Validity full * . First check the validity of the ground facts of Σ. For the other formulas of Σ, guess a valuation of the universally quantified variables. If the left-hand side is true in I and the right-hand side false in J (both of which can be decided in polynomial time), return false. For the hardness part, we use a reduction from the problem of evaluating a boolean conjunctive query over a database, which is NP-complete [START_REF] Chandra | Optimal implementation of conjunctive queries in relational data bases[END_REF]. Let D be a relational database of schema U, and Q = ∃y ϕ(y) a boolean conjunctive query over U. We build an instance (I, J, Σ) of Validity full in the following way: S = U ∪ {(S, 1)}, I = D ∪ {S(1)}, T = {(S ′ , 1)}, J = ∅ and Σ = {∀y∀t ϕ(y) ∧ S(t) → S ′ (t)}. This reduction is polynomial, Σ ⊂ L full , and Σ is valid with respect to (I, J) if and only if Q is false in D.

(2) There is a straightforward reduction of the problem of deciding whether a tuple is in the result of a project-join expression in the relational algebra, which is a NP-complete problem [START_REF] Yannakakis | Algorithms for acyclic database schemes[END_REF]], to Explanation full . Alternatively, we can also use a reduction from 3SAT, as the one used next in the proof of the DP-hardness of Zero-Repair full .

(3) Let L = L 1 ∩ L 2 ∈ DP, with L 1 ∈ NP and L 2 ∈ coNP. As 3SAT is NP-complete, there is a polynomial-time reduction Θ 1 from L 1 to 3SAT; similarly, we noted in item (1) that the problem of evaluating a boolean conjunctive query over a database is NP-complete, therefore there is a reduction Θ 2 from L 2 to the complement of this problem. Let α be any input. α ∈ L if and only if Θ 1 (α) (an instance of 3SAT) is satisfiable and Θ 2 (α) (a conjunctive query over a relational database) evaluates to false. Let Θ 1 (α) = n i=1 c i (z i1 , z i2 , z i3 ), where the c i 's are 3-clauses over some set x of variables (and i,j z ij = x) and Θ 2 (α) = (D, U, Q = ∃y ϕ(y)), where D is a relational database of schema U and Q a boolean conjunctive query over U. We consider the following instance (I, J, Σ) of Zero-Repair full : S = {(R 1 , 3) . . . (R 8 , 3), (S 1 , 1), (S 2 , 1)}∪U (we assume without loss of generality that the R i and S j do not appear in U) and I such that: the R I i are the 8 distinct subsets of {0, 1} 3 of cardinality 7;

S I 1 = S I 2 = {a}; U I = D. T = {(S ′ 1 , 1), (S ′ 2 , 1)} and J = {S ′ 1 (a)}; For each 1 i n, let 1 k i 8 be the unique integer such that c i (z i1 , z i2 , z i3 ) is true if and only if (z i1 , z i2 , z i3 ) ∈ R I ki .
We then define Σ = {ψ 1 , ψ 2 } with:

ψ 1 =∀x∀t n i=1 R ki (z i1 , z i2 , z i3 ) ∧ S 1 (t) → S ′ 1 (t), ψ 2 =∀y∀t ϕ(y) ∧ S 2 (t) → S ′ 2 (t).
• 25

Observe that (I, J) |= ψ 1 and that the only tuple to explain in J can only be explained by ψ 1 . In other words, (I, J, Σ) is a solution of Zero-Repair full if and only if the following two conditions are satisfied: ψ 1 fully explains J with respect to I and (I, J) |= ψ 2 . But ψ 1 fully explains J with respect to I if and only if ϕ is satisfiable, while (I, J) |= ψ 2 if and only if Q is false in D. The reduction presented here is polynomial, and α ∈ L if and only if (I, J, Σ) is a solution of Zero-Repair full .

Combined Complexity for Acyclic TGDs

The last subset of L tgd that we consider here is L acyc .

Proposition 5.7.

(1 ) Validity acyc and Validity acyc * are coNP-complete.

(2 ) Explanation acyc * is NP-hard.

(3 ) Zero-Repair acyc * is DP-hard. (4 ) Explanation acyc * is in PTIME if, for all existentially quantified variables y and for all constants c, there is at most one term y = c appearing in each formula of the schema mapping. In particular, Explanation acyc is in PTIME.

Proof.

(1) -Let us first prove that Validity acyc * is in coNP. The validity of ground facts of Σ is trivial to check. Let θ be a formula of Σ which is not a ground fact. Recall that θ is of the form ∀x ϕ(x) ∧ τ (x) → ∃y ψ(x, y) ∧ τ ′ (x, y) with τ (x) a conjunction of terms expressing equality or negated equality between a variable of x and a constant, and τ ′ (x, y) of the form

τ ′ (x, y) = n i=1     mi j=1 x ij = c ′ ij   → y i = c i   .
Guess a valuation ν of the variables of x. If the left-hand side of θ is made false by this valuation, give up this guess. Otherwise, consider the formula

ξ = ∃y ψ(ν(x), y) ∧ τ ′ (ν(x), y)
where τ ′ (ν(x), y) is equivalent to a conjunction of terms of the form y = c with y ∈ y and c a constant. We can then check in polynomial time if J satisfies ξ using Algorithm 3. -To prove that Validity acyc is coNP-hard, we use a reduction of 3SAT. Let ϕ = n i=1 c i (z i1 , z i2 , z i3 ) be an instance of 3SAT, where the c i 's are 3-clauses over some set x = {x 1 . . . x m } of variables (and i,j z ij = x). We consider now the following instance of Validity acyc : S = {(B, 1)} and I = {B(0), B(1)}. T = {(A, 3), (F, 1), (R 1 , 4) . . . (R 8 , 4)}, F J = {0}, A J is the 0 and 1 truth table of the and operator, and each R J k is the following 4-ary relation of arity 8:

0 0 0 δk1 0 0 1 δk2 0 1 0 δk3 0 1 1 δk4 1 0 0 δk5 1 0 1 δk6 1 1 0 δk7 1 1 1 δk8
where δkj is 0 if k = j and 1 otherwise. For all 1 i n, let 1 k i 8 be the unique integer such that c i (z i1 , z i2 , z i3 ) is false if and only if (z i1 , z i2 , z i3 , 0) ∈ R J ki (with the usual abuse of notation of identifying values of boolean variables and values in {0, 1}). We then define:

Σ = ∀x 1 . . . ∀x m B(x 1 ) ∧ • • • ∧ B(x m ) → ∃y 1 . . . ∃y n ∃y ′ 1 . . . ∃y ′ n-1 F (y ′ n-1 ) ∧ n i=1 R ki (z i1 , z i2 , z i3 , y i ) ∧ A(y 1 , y 2 , y ′ 1 ) ∧ A(y ′ 1 , y 3 , y ′ 2 ) ∧ • • • ∧ A(y ′ n-2 , y n , y n-1 ) .
This transformation is polynomial. We prove that Σ ⊂ L acyc . First, remember that the acyclicity condition on the right-hand side of the tgd only concerns existentially quantified variables. Second, the y i 's are not sources of cycles since each only occurs in two relation atoms, one of which where they are the only existentially quantified variables. Finally, we can build a join tree for the y ′ i 's that consists in a simple chain, each relation atom A being a node of this chain. Now observe that Σ is valid with respect to (I, J) if and only if the following quantified propositional formula is true:

∀x ∃y ′ 1 . . . ∃y ′ n-1 ¬y ′ n-1 ∧ (c 1 (z 11 , z 12 , z 13 ) ∧ c 2 (z 21 , z 22 , z 23 ) → y ′ 1 ) ∧ (y ′ 1 ∧ c 3 (z 31 , z 32 , z 33 ) → y ′ 2 ) ∧ . . . ∧ (y ′ n-2 ∧ c n (z n1 , z n2 , z n3 ) → y ′ n-1
). This can be rewritten as:

∀x n i=1 c i (z i1 , z i2 , z i3 ) → ⊥ ≡ ¬ϕ.
In other words, Σ is valid with respect to (I, J) if and only if the original 3SAT instance is not satisfiable.

(2) We use once more a reduction from 3SAT. S = {(B, 1)} and I = {B(0), B(1)}; T = {(S, n)} and J = {S(1, . . . , 1)}; For all 1 i n, let τ i1 . . . τ i8 be the eight conjunctions of the form z i1 = b 1 ∧ z i2 = b 2 ∧ z i3 = b 3 such that each b k is either the constant 0 or 1, and c i (z i1 , z i2 , z i3 ) is true if any of these conjunctions holds. We then define:

• 27 Σ = ∀x 1 . . . ∀x m B(x 1 ) ∧ • • • ∧ B(x m ) → ∃y 1 . . . ∃y n S(y 1 . . . y n ) ∧ n i=1 8 j=1 (τ ij → y i = 1) .
Observe that Σ is valid with respect to (I, J). This transformation is polynomial, and Σ fully explains J with respect to I if and only if the original 3SAT instance is satisfiable.

(3) The problem of determining whether, given two instances ϕ 1 and ϕ 2 of 3SAT, the first is not satisfiable and the second is satisfiable, is a typical example of a DP-complete problem [START_REF] Papadimitriou | Computational Complexity[END_REF]]. We can reduce this problem to Zero-Repair acyc * in polynomial time, by combining the two reductions from 3SAT to the complement of Validity acyc * and from 3SAT to Explanation acyc * given respectively in items ( 1) and ( 2). The corresponding schemata, database instances, and schema mappings are obtained as the union of the schemata, database instances, and schema mappings of both reductions. One of the two formulas (let us call it ψ 1 ) comprising the resulting schema mapping Σ cannot contribute to the explanation of the target instance J, while the other (ψ 2 ) is valid. That means that Σ is valid and fully explains J if and only if ψ 1 is valid (or, after (1), if ϕ 1 is not satisfiable) and ψ 2 fully explains J (or, after (2), if ϕ 2 is satisfiable).

(4) Let f be a fact of J, we describe a polynomial algorithm for deciding whether f is explained by Σ. First, check if f is in the ground facts of Σ. Otherwise, for each atom R(z 1 . . . z k ) in the right-hand side of a formula θ ∈ Σ which is not a ground fact, such that R is the relation name appearing in f , do the following. We keep the same notations as above for the sub-formulas of θ. Observe that f is explained by the R(z 1 . . . z k ) atom of θ if and only if there is a valuation ν of the variables of x such that ν (ϕ(x) ∧ τ (x)) is true in I and, for all extensions ν ′ of ν to x ∪ y, ν ′ (τ ′ (x, y)) is true and ν ′ (R(z 1 . . . z k )) = f . This means that all variables of y appearing in R(z 1 . . . z k ) must also appear as the right-hand side of an implication of τ ′ (x, y) (otherwise, an extension ν ′ of ν such that ν ′ (R(z 1 . . . z k )) is not equal to f is possible). By the hypothesis we made, there is exactly one conjunct of τ ′ (x, y) where each variable of y appears. Let ρ(x) be the conjunction of the left-hand sides of these implications for all variables of y. Then f is explained by the R(z 1 . . . z k ) atom of θ if and only if the boolean query ∃x ϕ(x) ∧ τ (x) ∧ ρ(x) is true in the instance I. As τ (x) ∧ ρ(x) is a simple conjunction, we can first perform the corresponding selection on I, and then use Algorithm 3 to decide if the boolean query is true in I.

Note that, to prove the hardness of Explanation acyc * , we use the repairs themselves to encode the instance of a NP-hard problem: although the tgd itself is acyclic, its repairs are not. We could probably get polynomial algorithms for the same problems if we impose some acyclicity condition to repairs of a formula; this, however, would weaken our notion of optimality.

• G. Gottlob and P. Senellart

Combined Complexity of Existence-Cost and Optimality

With the help of Lemma 5.3, we show the intractability of Existence-Cost and Optimality, in all considered languages: Proposition 5.8. Existence-Cost (respectively, Optimality) is NP-hard (respectively, DP-hard) in the languages L tgd , L full , L acyc , L facyc , and in the language of repairs of each of these languages.

Proof. To prove this result, we use, as in the proof of Proposition 5.4, a reduction from the vertex cover problem in tripartite 3-uniform hypergraphs. The core of the reduction is the same for Existence-Cost and Optimality. Observe that a straightforward DP-complete problem obtained from this problem is that of knowing if, given two tripartite 3-uniform hypergraphs and two integers, the vertex cover of the first hypergraph is less than the first integer, and the vertex cover of the second hypergraph is greater than the second integer.

Let H = (V, E) be a tripartite 3-uniform hypergraph with N vertices and K an integer. We denote by τ (H) the minimum size of a vertex cover in H. Let α 1 an integer, to be defined further. Each vertex of V is seen as a constant of C. We also use 3(α + N ) additional constants c ik and c ′ jk with 1 i α, 1 j N , 1 k 3. We now consider the following schemata and instances:

S = {(R, 3)} and I = { R(c i1 , c i2 , c i3 ) | 1 i α } ∪ { R(c ′ i1 , c ′ i2 , c ′ i3 ) | 1 i N } ∪ { R(v, v ′ , v ′′ ) | e = (v, v ′ , v ′′ ) ∈ E } ; T = {(R ′ , 1), (S ′ , 3)} and J = { R ′ (c i1 ) | 1 i α } ∪ { S ′ (c i1 , c i2 , c i3 ) | 1 i α } ∪ { S ′ (c ′ i1 , c ′ i3 , c ′ i3 ) | 1 i N } . Let Σ 0 = {∀x R(x) → S ′ (x)}. Σ 0 is
valid, but fails to explain α tuples of J. Thus, cost (I,J) (Σ 0 ) = 6 + 3α (since the cost of a ground fact of arity 1 is 3, see Definition 3.6).

Let

Σ = {∀x R(x) → R ′ (x 1 ) ∧ S ′ (x)} (Σ ⊂ L facyc
). An argument very similar to the one of the proof of Proposition 5.4 shows that

cost (I,J) (Σ) = size(Σ) + 2τ (H) + 2N = 7 + 2τ (H) + 2N .
since S ′J guarantees that the size of any repair of Σ with an x = c term on the left-hand side is at least:

size(Σ) + 2 + 9(α + N -1) > size(Σ) + 9N > cost (I,J) (Σ) .
The idea now is to choose α such that τ (H) K if and only if cost (I,J) (Σ) cost (I,J) (Σ 0 ). This is the case if:

α = 2(K + N ) + 1 3 .
• 29

With this value of α, we have cost (I,J) (Σ 0 ) = 2(K + N ) + 7 and cost (I,J) (Σ) = 2τ (H) + N + 7, which yields the property we were looking for. However, 2(K + N ) + 1 may not be divisible by 3; in this case, we just transform the initial problem by observing that τ (H) = K if and only if τ (H ′ ) = K where H ′ is the tripartite 3-uniform hypergraph obtained from H by adding n new edges, each of which span 3 new vertices (this does not change the value of N mod 3). Up to such a transformation, we may then assume than 2(K + N ) + 1 is divisible by 3.

Let us now show that, for any schema mapping

Σ ′ ⊂ L * tgd , cost (I,J) (Σ ′ ) min cost (I,J) (Σ 0 ) , cost (I,J) (Σ) . (1)
This will conclude the proof, since we then have the following reductions, obviously polynomial and valid for any of the considered languages:

NP-hardness of Existence-Cost. We have τ (H) K if and only if there exists a schema mapping whose cost with respect to (I, J) is lesser than or equal to cost (I,J) (Σ 0 ) -1.

DP-hardness of Optimality. Let H be another tripartite 3-uniform hypergraph and K another integer. We use similar notations: Σ, Σ0 , Ĩ, etc. We assume without loss of generality that S, T, S, and T use different relation names, and that the constants in I and J on the one hand, and in Ĩ and J on the other, are disjoint. Then τ (H) K if and only if Σ is optimal with respect to (I, J), while τ ( H) K -1 if and only if Σ0 is not optimal with respect to ( Ĩ, J). This means that τ (H) K and τ ( H) K if and only if Σ ∪ Σ0 is optimal with respect to (I ∪ Ĩ, J ∪ J): indeed, since the relation names in S, T, S, and T are disjoint, cost (I∪ Ĩ,J∪ J) Σ ∪ Σ0 = cost (I,J) (Σ) + cost ( Ĩ, J) Σ0 .

Let us now show (1). Given a schema mapping Σ ′ ⊂ L * tgd , the schema mapping Σ ′′ ⊂ L tgd obtained by removing all repairs from Σ ′ is such that cost (I,J) (Σ ′ ) cost (I,J) (Σ ′′ ). This means we only need to consider schema mappings of L tgd .

Let Σ ′ be a non-empty schema mapping of L tgd . Observe that, as the constants c i1 are completely indistinguishable from each other, Σ ′ must either explain all or none of the facts of R ′J . We shall consider each case in turn.

-If Σ ′ does not explain any of the facts of R ′J , each of these must be accounted for in the repairs, by one of the following methods: adding ground facts (additional cost: 3 each); adding an unconditioned "x = c" term to a R ′ (x) atom where x is existentially quantified (additional cost: 2 each, but this can only be done once per R ′ (x) atom, whose size is 1, or this yields an inconsistent formula); adding a conditioned "τ → x = c" term to a R ′ (x) atom where x is existentially quantified (minimum additional cost: 4 each, since the size of τ is at least 2). Moreover, a repair of Σ ′ should also account for the facts of S ′J , either as explanations of Σ ′ (this cannot be done in a formula with size lesser than 6) or by enumerating all ground facts of S ′ (with a cost of 9(α + N ), which is greater than 6). This means that cost (I,J) (Σ ′ ) 3α + 6 = cost (I,J) (Σ 0 ). perhaps more intuitive, present the same properties and are thus adapted to our context.

We keep our notions of validity of a schema mapping, of full explanation of a database instance by a schema mapping, and of size of a schema mapping, and we want to consider alternative ways to characterize the cost of a given schema mapping. The first idea is to assign as the cost of a schema mapping the minimal number of tuples that have to be added or removed to the target instance J for the schema mapping to become valid and to fully explain J. (Each tuple may also be weighted by its arity, to get something closer to our original cost definition.) Thus, the cost of the empty schema mapping corresponds to the size of the target instance, as before, while the cost of a schema mapping that fully explains the target instance but also incorrectly explains some tuples is the (possibly weighted) number of such tuples. This sounds like a reasonable definition, but it presents an important problem: We lose the linear bound on the cost of a schema mapping in the size of the data and the schema mapping itself. Indeed, consider the following schema mapping, for a given n, where R is a source relation of arity 1 and R ′ a target relation of arity n:

{∀x 1 . . . ∀x n R(x 1 ) ∧ • • • ∧ R(x n ) → R ′ (x 1 , . . . , x n )} .
If J is empty, the cost of this schema mapping according to the definition given in this paragraph is |I| n (or n |I| n if we weight with the arity of the relations), which is exponential in the size of the schema mapping. This combinatorial explosion discourages all hopes of getting an optimal schema mapping by local search techniques. Besides, all the problems that we describe for the variant that we consider next also arise here.

An alternate definition of cost, close to the previous one but for which we still have a linear bound on the cost of a mapping is the following: The cost of a schema mapping Σ is the minimal number of tuples to add or remove from the source and target instances I and J so that Σ becomes valid and fully explains J. As before, we assume that we weight tuples by their arity; we could also choose to add an arbitrary constant weight to operations on J with respect to operations on I, or to deletion with respect to addition of tuples, without much difference. The linear bound is clear since we can just remove all tuples of I and of J for Σ to be valid and to fully explain J. However, there is still a fundamental problem with this definition, which can be seen by looking back at Section 4. We showed there that, for elementary operations of the relational algebra, the definition of optimality of Section 3 yielded the same as the intuitive tgds expressing these operations. This is not true any more here, however, in particular in the presence of selections and projections. For projections, this is due to the fact that a schema mapping that predicts existentially quantified tuples has a higher cost than the same schema mapping where these existentially quantified relation atoms are removed. We exhibit next a concrete example of database instances that illustrate the problem with selections.

Example 6.2. Let us consider instances I and J of the following schemata: S = {(P, 2)} and T = {(P ′ , 1)}, where: I contains a list of titles of publications (as first attribute) along with their kind: article , book , report , etc.; J contains a list of book titles. Let us assume that J and I contain the same book titles. In other words, J = π 1 (σ 2=book (I)). It is quite natural to expect Σ = {∀x∀y P (x, y) → P ′ (x)} as Journal of the ACM, Vol. V, No. N, Month 20YY.

• 35 the "optimal" schema mapping in the language of tgds for these database instances, and indeed, cost (I,J) (Σ) = 5 is minimal as soon as J is large enough and there is no hidden relation between the second attribute of I and J. Now, observe that with the variant proposed in the preceding paragraph, the cost will be: 3 + min (2 • (|I| -|J|), |J|) , which is, in all cases when there are more publications of another kind than book (a common situation), greater than the cost of the empty schema mapping, which is then the optimal schema mapping for these instances.

Thus, although our definition of optimality is a bit complex, it is much more adapted to the addressed problem than these simpler definitions, since it can capture such things as the worth of an existentially quantified relation atom, or the possibility of limiting the scope of a tgd with a simple selection.

CONCLUSION

We discussed a theoretical framework that addresses the problem of finding a schema mapping optimal with respect to a pair of database instances, based solely on the structure and occurrences of constants in the instances. We showed that this problem is DP-hard (in particular, both NP-hard and coNP-hard) even for a very restricted language, namely full acyclic tuple-generating dependencies. This is not unexpected, since it is well known that such learning problems have high complexity even in very simple cases (see, for instance, [START_REF] Gottlob | On the complexity of some inductive logic programming problems[END_REF]] for ILP). Such a study is still useful since (i) it provides a formal framework for the discovery of schema mappings; (ii) complexity lower bounds are useful to detect the source of the complexity; (iii) complexity upper bounds often give practical algorithms.

There are a number of open theoretical issues, especially on the computability and precise complexity of Optimality, but the most obvious direction for future work would be to connect such a theoretical framework with practical heuristics and approximation algorithm; in particular, the relation to inductive logic programming has to be explored. We believe that this is an especially important problem, and that discovering and understanding hidden relations in data is one of the most fundamental tasks of artificial intelligence. Other problems of interest would be to improve our complexity upper bounds by generalizing the notion of acyclicity to that of bounded hypertree width [START_REF] Gottlob | Hypertree decompositions and tractable queries[END_REF], and to look at the same problems when some fixed set of preconditions on instances is given. One can imagine for instance that some part of the schema mapping is known in advance, or that an approximate schema mapping has been discovered by a schema matching algorithm, and that we extend it using the framework developed in the paper. Finally, a potentially fruitful direction of research would be to explore the connection between the work presented here and other works on schema mapping operators [START_REF] Bernstein | Using semi-joins to solve relational queries[END_REF][START_REF] Fagin | Composing schema mappings: Second-order dependencies to the rescue[END_REF][START_REF] Fagin | Quasi-inverses of schema mapping[END_REF]]: Is the composition (in the sense of [START_REF] Fagin | Composing schema mappings: Second-order dependencies to the rescue[END_REF]) of two schema mappings from I to J and J to K optimal with respect to I and K? Are there cases when our framework can be used to minimize the representation of such a schema mapping? Is it possible (and perhaps easier) to find the optimal schema mapping from J and I and then construct its quasi-inverse [START_REF] Fagin | Quasi-inverses of schema mapping[END_REF]] as an optimal schema schema mapping from I to J? Note that works on data exchange usually consider additional dependencies in addition to source-to-target tgds (egds, source-only tgds, etc.), and that more expressive languages for schema mappings may be required (e.g., second-order tgds in the case of [START_REF] Fagin | Composing schema mappings: Second-order dependencies to the rescue[END_REF], tgds with constants and inequalities for [START_REF] Fagin | Quasi-inverses of schema mapping[END_REF]).

  Definition 3.1. A schema mapping Σ is valid with respect to a pair of instances (I, J) if (I, J) |= Σ. Definition 3.2. A (ground) fact in a schema S is a tuple R(c 1 . . . c n ) where c 1 . . . c n ∈ C and R is a relation of S with arity n.

  Complement of Optimality (non-deterministic) given A Cost for Cost Input: Instances I, J, schema mapping Σ. Output: Answer to the complement of Optimality. (a) Use A Cost a logarithmic number of times to compute K = cost (I,J) (Σ) (we make use on the linear bound of Proposition 3.8). (b) Guess a set of formulas Σ ′ of total size less than K. (c) Check that Σ ′ is in L. Otherwise, give up this guess. (d) Apply A Cost on (Σ ′ , K -1); if the result is true, return true.

Table II .

 II Combined complexity results and corresponding proofs

					• 19
		Combined complexity bounds
		L * tgd , L tgd	L * full , L full	L acyc *	L acyc	L * facyc , L facyc
	Validity	Π P 2 -complete coNP-complete coNP-complete	coNP-complete	PTIME
	Explanation	NP-complete	NP-complete	NP-complete	PTIME	PTIME
	Zero-Repair	Π P 2 -complete	DP-complete	DP-complete	coNP-complete	PTIME
	Cost	Σ P 3 , Π P 2 -hard	Σ P 2 , DP-hard	Σ P 2 , DP-hard	Σ P 2 , (co)NP-hard	NP-complete
	Existence-Cost Σ P 3 , NP-hard	Σ P 2 , NP-hard	Σ P 2 , NP-hard	Σ P 2 , NP-hard	NP-complete
	Optimality	Π P 4 , DP-hard	Π P 3 , DP-hard	Π P 3 , DP-hard	Π P 3 , DP-hard	Π P 2 , DP-hard
			Proofs
		L * tgd , L tgd	L * full , L full	L acyc *	L acyc	L * facyc , L facyc

• G.

Gottlob and P. Senellart

Journal of the ACM, Vol. V, No. N, Month 20YY, Pages 1-0??.

Journal of the ACM, Vol. V, No. N, Month 20YY.

The other important class of dependencies, namely equality generating dependencies, is less appropriate to this context.Journal of the ACM, Vol. V, No. N, Month 20YY.

ACKNOWLEDGMENTS

We would like to thank Serge Abiteboul and Yann Ollivier for their input and feedback about this work. We also want to acknowledge the anonymous referees for their valuable comments.

Georg Gottlob's work was supported by EPSRC grant EP/E010865/1 "Schema Mappings and Automated Services for Data Integration and Exchange". Gottlob also gratefully acknowledges a Royal Society Wolfson Research Merit Award, which allowed him to host Pierre Senellart. Pierre Senellart's work was supported by the European Research Council grant Webdam (under FP7), grant agreement 226513.

Algorithm 1. Cost (non-deterministic) given A Zero-Repair for Zero-Repair Input: Instances I, J, schema mapping Σ, K 0. Output: Answer to Cost. (a) Let K ′ be the minimum between K and the upper bound of Proposition 3.8. (b) Guess a set of formulas Σ ′ of total size less than or equal to K ′ . (c) Check that Σ ′ is a repair of Σ. Otherwise, give up this guess. (d) Apply A Zero-Repair on Σ ′ ; if the result is true, return true. repairs (for instance, Zero-Repair full * for the Zero-Repair problem in L * full ). We have the following elementary relationships between these problems, that can be used to derive complexity results for one problem from complexity results for another one.

Proposition 5.1. For any language L ⊆ L * tgd :

(1 ) Zero-Repair = Validity ∩ Explanation.

(2 ) There is a polynomial-time reduction of Validity to Zero-Repair.

(3 ) There is a polynomial-time reduction of Zero-Repair to Cost. (4 ) Given an algorithm A Zero-Repair for Zero-Repair in L * and a polynomialtime algorithm for determining if a formula is in L, there are non-deterministic algorithms for Cost and Existence-Cost in L that run by using once the algorithm A Zero-Repair , with an additional polynomial-time cost. (5 ) Given an algorithm A Cost for Cost and a polynomial-time algorithm for determining if a formula is in L, there is a non-deterministic algorithm for the complement of Optimality that runs by using a logarithmic number of times the algorithm A Cost , with an additional polynomial-time cost. (6 ) If L ⊆ L ′ , for any problem among Validity, Explanation, Zero-Repair and Cost, there is a constant-time reduction from the problem in L to the problem in L ′ . This is in particular true for reductions from the problem in L to the problem in L * .

Proof.

(1) By definition, cost (I,J) (Σ) size(Σ). Because the size of a repaired formula is always greater than the original formula, the only case when the equality occurs is when the original formula is valid and fully explains J.

(2) Let (I, J, Σ) be an instance of Validity. Let Σ ′ be the union of Σ and of all ground facts of J. Obviously, Σ ′ fully explains J with respect to I. That means that cost (I,J) (Σ ′ ) = size(Σ ′ ) if and only if Σ ′ is valid with respect to (I, J). As the ground facts of Σ ′ do not change its validity, cost (I,J) (Σ ′ ) = size(Σ ′ ) if and only if Σ is valid with respect to (I, J).

(3) Just take K = size(Σ), which is computable in linear time.

(4) Consider the non-deterministic algorithm for Cost shown as Algorithm 1. The algorithm for Existence-Cost is very similar, just replace the bound on K with the cost of the empty schema mapping, and step (c) by a check that Σ ′ is in L * (this can be done in polynomial time by hypothesis). Note that the bound of cost (I,J) (∅) on the guess is critical, since otherwise the guess would be of size K, and thus exponential in the length of the representation of K. -In the case where Σ ′ explains all facts of R ′J , there is a tgd θ ∈ Σ ′ such that θ explains all facts of R ′ J, and θ is necessarily of the form:

is valid in I since ϕ does not contain anything else than relation atoms R(w 1 , w 2 , w 3 ) with all x i 's necessarily in the ith position, and other variables existentially quantified. That means that R ′ (v) is an incorrect fact implied by the tgd. As we saw earlier, adding an x = c term on the left-hand side of θ has prohibitive cost. The only way to cancel these facts is then as in the proof of Proposition 5.4. Finally, a repair of θ must also explain all facts of S ′J , either as facts explained by θ itself (then, size(ϕ) 3), or by enumerating ground facts of S ′J , with a cost of 9(α + N ) > 3.

We have therefore:

Note that the same proof does not work in the case of L rc :

} may have a lower cost for some instances than Σ (for instance if H is a hypergraph where all nodes have a degree greater than 1).

Data Complexity

As far as data complexity is concerned, the situation is simpler, since we do not have any difference in complexity for all four subsets of L tgd . The results are presented summarized in Table IV.

Journal of the ACM, Vol. V, No. N, Month 20YY.

• 31 (4 ) For some fixed value of Σ, Cost facyc is NP-hard.

(5 ) For some fixed value of Σ, the problem Optimalityin L tgd , L full , L acyc , L facyc and the language of repairs of each of these is DP-hard.

Proof.

(1) If k is the number of quantified variables in a first-order formula ϕ in prenex normal form, it is easy to see that checking whether ϕ is valid in a database of size n is O(n k ).

(2) Each formula of Σ is either a ground fact, or of the form ∀x (ϕ(x) ∧ τ (x)) → ∃y (ψ(x, y) ∧ τ ′ (x, y)) with τ and τ ′ propositional combinations of terms expressing equalities between a variable and a constant. For each fact f of J, first check if it appears as a ground fact Σ; otherwise, for each valuation of x ∪ y (there is a constant number of such valuations, since Σ is fixed), check whether the left-hand side holds, and f is a consequence of the right-hand side.

(3) We can just enumerate all schema mappings of L * tgd whose size is lower than K, and check in polynomial time if they are valid and fully explain the target instance.

(4) This results from the proof of Proposition 5.4.

(5) This results from the proof of Proposition 5.8.

Unsurprisingly, in terms of data complexity, the different problems appear to be somewhat more tractable than in terms of combined complexity, even though Cost facyc is still NP-hard for a fixed Σ. Note, however, that since the objective is the discovery of schema mappings from database instances, the schema mapping itself is the object of interest. This is different from the traditional setting of query answering over databases, for instance, where it makes sense of reasoning about a fixed query and a varying dataset. In that sense, it seems to us that combined complexity results are more meaningful here.

EXTENSION AND VARIANTS

We study in this section some extensions of our optimality notion to (i) formulas of the full relational calculus; (ii) other apparently simpler functions of cost.

Extension to the Relational Calculus

We can extend the definitions of Section 3 to the language L rc of relational calculus, by the following adaptation of the notion of repair.

A repair of a schema mapping Σ ⊂ L rc is a set of formulas obtained from Σ by a finite sequence of the following operations:

-Replacing in a formula of Σ a sub-formula ∀x ϕ(x, y) (we also assume that ϕ does not start with a ∀ symbol, and that the sub-formula is not preceded by a ∀ symbol) by ∀x τ (x, z) → ϕ(x, y) where z is the set of variables free in ϕ and τ is a boolean formula over terms w = c of the following form:

with z ij variables from z, x i variables from x, α i either = or =, and c ′ ij and c i constants.

-Replacing in a formula of Σ a sub-formula ∃x ψ(x, y) (we also assume that ψ does not start with a ∃ symbol, and that the sub-formula is not preceded by a ∃ symbol) by ∃x ψ(x, y) ∧ τ ′ (x, z) where z is the set of variables free in ψ and τ ′ is a boolean formula over terms w = c of the following form:

with z ij variables from z, x i variables from x, and c ′ ij and c i constants. -Adding to Σ a ground fact R(c 1 . . . c n ) with R a relation of the target schema of arity n, and c 1 . . . c n constants.

We can check that this definition amounts to the same as Definition 3.4 if we restrict ourselves to L tgd . We can then use the same definitions of the size and cost of a formula, and consider the same decision problems. It is easy to see that the results of Proposition 5.1 still hold. We have the following complexity results: Proposition 6.1.

(1 ) Validity rc * and Validity rc * are PSPACE-complete;

(2 ) Explanation rc * is co-recursively enumerable;

(3 ) Explanation rc and Zero-Repair rc are not recursive.

Proof.

(1) -Let us first show that Validity rc * is in PSPACE. Let ϕ ∈ Σ. If ϕ is a ground fact, this is trivial. Otherwise, we first rewrite ϕ in prenex normal form

where each α i is either ∃ or ∀. Let C be the set of constants appearing in I and J, along with n distinct constant ⊥ 1 . . . ⊥ n . It can be shown that we do not need to consider valuations of the x 1 . . . x n into other constants. For each valuation ν of x 1 . . . x n into C, it is decidable in polynomial time whether (I, J) |= ψ (ν(x 1 ), ..., ν(n n )). We then enumerate all valuations, enumerating recursively all valuations of x i+1 while keeping x i fixed, and remembering for each 1 i n + 1 a single value ok i which is equal to:

in the current valuation ν, 0 otherwise; If α i = ∃: the maximum of ok i+1 and the preceding value of ok i (and the preceding value is reset to 0 whenever the valuation of x i-1 is changed).

If α i = ∀: the preceding value of ok i , multiplied par the current value of ok i+1 (and the preceding value is reset to 1 whenever the valuation of x i-1 is changed). The algorithm returns true if, after enumerating all valuations, all ok i 's are equal to 1. Otherwise, the algorithm returns false. This is obviously a PSPACE algorithm, and it returns true if and only if (I, J) |= ϕ. We can run the same algorithm in sequence on all ϕ ∈ Σ.

-The PSPACE-hardness of Validity rc comes from a polynomial-time reduction of QSAT (also known as QBF), which is PSPACE-complete [START_REF] Papadimitriou | Computational Complexity[END_REF][START_REF] Stockmeyer | Word problems requiring exponential time[END_REF]. Let ϕ = α 1 x 1 . . . α n x n ψ(x 1 . . . x n ) be an instance of Journal of the ACM, Vol. V, No. N, Month 20YY.

• 33 QSAT (the α i 's are either existential or universal quantifiers, and ψ(x 1 . . . x n ) is a propositional formula in CNF with variables x 1 . . . x n ). Let S = {(B, 1), (T, 1), (F, 1)}, T = ∅, I = {B(0), B(1), T (1), F (0)} and J = ∅. We rewrite inductively the quantified propositional formula ϕ into a first-order formula ξ in the following way:

From the CNF propositional formula ψ(x 1 . . . x n ), we obtain a first-order formula with all free variables by replacing every positive literal x i with T (x i ) and every negative literal ¬x i with F (x i ).

A ∀x i θ i subformula with universal quantification is rewritten as ∀x i (B(x i ) → θ i ).

A ∃x i θ i subformula with existential quantification is rewritten as ∃x i (B(x i ) ∧ θ i ). Then (I, J) |= {ξ} if and only if ϕ is true.

(2) To see that Explanation rc * is co-recursively enumerable, just enumerate all instances K of the target schema, and whenever they are such that (I, J) |= Σ (which is decidable, see just above), see if they contain K. If this is not the case, we can conclude that Σ does not fully explain J with respect to I.

(3) The uncomputability comes from a reduction of the satisfiability of the relational calculus, which is not recursive [START_REF] Trakhtenbrot | Impossibility of an algorithm for the decision problem in finite classes[END_REF][START_REF] Di Paola | The recursive unsolvability of the decision problem for the class of definite formulas[END_REF]. The reduction is the same for both problems Explanation rc and Zero-Repair rc . Let ϕ be a formula of the relational calculus over a schema U. Consider the following instance of Explanation rc (this is also an instance of Zero-Repair rc ):

Observe that (I, J) |= Σ, therefore (I, J, Σ) is a solution of Explanation rc if and only if it is a solution of Zero-Repair rc . Now, (I, J, Σ) is a solution of Explanation rc if and only if, for all K such that (I, K) |= Σ, R ′ (a) is a fact of K. This is the case if and only if ϕ is not satisfiable.

Interestingly, the computability of Optimality rc remains open. It seems to be a "harder" problem than Zero-Repair rc , but as there is no simple reduction between them, we cannot even be sure that Optimality rc is not recursive. We do not even know whether it is recursively enumerable or co-recursively enumerable (but Cost rc * and Existence-Cost rc * are both co-recursively enumerable because of the co-recursive enumerability of Zero-Repair rc * ).

Note that a related problem is studied in [START_REF] Fletcher | On the data mapping problem[END_REF]], where it is shown that determining whether there exists a schema mapping in L rc that is valid and explain all facts of the target instance is coNP and co-graph-isomorphism-hard. In the case of L * rc , such a mapping obviously always exists since one can enumerate all ground facts of the target instance.

Variants of the Cost Function

The definition of repairs and cost that we presented in Section 3 may appear, at first, unnecessarily complicated. We argued in Section 4 for a justification of this notion by showing that it has nice properties with respect to instances that are derived from each other with elementary operations of the relational algebra. We consider in this section two alternative definitions of cost and optimality of a schema mapping with respect to database instances, and show that neither, although simpler and


The last version of this communication is now available as a chapter: http://halshs.archivesouvertes.fr/halshs-00536597/fr/ La version définitive de cette communication est désormais disponible sous la forme d'un chapitre d'ouvrage : http://halshs.archives-ouvertes.fr/halshs-00536597/fr/