In data exchange, one is typically given a source database instance and a mapping between a source schema and a target schema. The goal then is to materialize a target database instance that corresponds to the source instance and the mapping. In this setting source data is explicitly given, that is, every fact that is true in it is explicitly mentioned in the source database instance.
Knowledge bases typically consist of some explicit knowledge -like in database instances -and some implicit knowledge, usually given in the form of rules that specify how to derive knowledge not explicitly stored. In [5], Arenas et al. introduced the setting of knowledge exchange, where one is given a source knowledge base and a mapping between a source schema and a target schema, and the goal is to materialize a target knowledge base, that is, both explicit and implicit knowledge.
While the question of what constitutes a "good" solution to a data exchange problem has been the topic of research in recent years [11], the question of what constitutes a "good" solution to a knowledge exchange problem is rather new. In particular, there are now two components, explicit and implicit knowledge, which play rather different roles in what we expect from them.
In [5], two especially desirable properties of the target knowledge base were identified. First, one generally wants to minimize explicit knowledge, thus generating as much knowledge by rules as possible. Second, in typical knowledge-based systems (such as those based on RDFS, OWL, or general description logics), the explicit knowledge changes frequently, but the implicit knowledge remains constant over a longer time. Hence, it is desirable to let the target implicit knowledge only depend on the implicit knowledge at the source and the mapping between source and target. Thus, knowledge exchange effectively becomes a two-stage process:
1. materialize target implicit knowledge, given only the source implicit knowledge and the source-to-target mapping; and 2. materialize target explicit knowledge w.r.t. the materialized implicit knowledge, which should be as small as possible.
Here, we focus on the former, and thus say that such target implicit knowledge "represents" the source implicit knowledge under a given mapping. Two such notions of "representation" were introduced recently: safety [5] and Q-representability [3,4], where Q is a query language. In this work, we introduce the very broad notion of general representability that captures safety as a special case and lays the foundation to the study of representability in a broad setting, in particular with the goal of extending our work to Q-representability. To achieve this, general representability is not limited to knowledge exchange, but based on arbitrary schema mappings. As an essential tool for this study, we develop conditions on schema mapping languages under which notions of equivalence important to our investigation coincide.
Organization. In Section 2, we define the necessary preliminaries. We start introducing general representability in Section 3. Then, in Section 4, we show how to capture safety.
In Section 5, we introduce notions of equivalence towards capturing Q-representability.
We conclude in Section 6.
We assume some familiarity with database theory and data exchange (cf., e.g., [1,6]). A schema S is a set of relation symbols, each having a fixed arity. An instance I ∈ Inst(S) assigns to each relation symbol R a relation R I of the corresponding arity. We denote by dom(I) the set of all constants that occur in a relation of I. We assume instances to be finite and, thus, dom(I) is finite.
A schema mapping M (or just mapping) from a source schema S 1 to a target schema S 2 is a subset of Inst(S 1 ) × Inst(S 2 ). 4 The composition of two mappings, symbolized by •, is defined as the composition of binary relations [9]. M and M are equivalent, written M ≡ M , if they are equal as binary relations (M = M ). Besides, we write M M for M ⊆ M . We later use the notion of a mapping M "based on" some logical formalism. By that we mean that there exists a set Σ of dependencies from that formalism s.t. M = {(I, J) | (I, J) Σ}. As these specific formalisms are not the focus of this paper, we refer to e.g. [5] for formal details and definitions. We say that Σ is over a schema S if all relation symbols occurring in Σ are from S. For a set of instances I ⊆ Inst(S), the set of solutions of I under M is Sol M (I) = {J | (I, J) ∈ M and I ∈ I}. A single instance I ∈ Inst(S 1 ) is treated as a singleton set {I} wherever applicable, e.g. Sol M (I) = Sol M ({I}).
In this paper we deal with knowledge bases in a very general way treating them as mappings over a single schema. A general knowledge base over a schema S is represented simply as a mapping M from S to S such that, intuitively, if I represents the explicit knowledge, then Sol M (I) represents all possible completions of I where the implicit knowledge has been made explicit. For keeping schema specifications brief, a subscripted mapping M i is always from schema S i to S i , and a mapping M ij is always from schema S i to S j .
Intuitively, given mappings M 1 , M 2 and M 12 , we say that M 2 "represents" M 1 under M 12 if the following equivalence is fulfilled:
In the context of knowledge exchange, M 1 and M 2 can be seen as the mappings responsible for generating the completions discussed in the preliminaries, and M 12 as the mapping used for transferring data. The condition ( †) is very strong. In particular, M 12 must already transfer enough of the source data for such an M 2 to exist. A very critical point is that we require "logical" equivalence, i.e, for every source instance all the solutions must coincide. It can be demonstrated in simple examples that this requirement is too strong to be widely applicable.
Less strict notions of representability have been studied in recent research, namely safety [5] in the context of full tuple-generating dependencies [8], and Q-representability -where Q stands for a class of queries -in the context of description logics [3,4]. We therefore introduce general representability, a very weak notion of representability which allows us to study relaxed notions of representability in a very general setting. Definition 1. Let ≡ χ be an equivalence relation on schema mappings. If there exist mappings M 1 and M 12 such that
The intuition behind this definition is the following: M 2 may not be the "ideal" representation as defined by equation ( †). Though, if through keeping small parts of M 1 and by slightly extending M 12 we can show equivalence, this may be good enough for a given application. In particular, it might not be possible to completely remove M 1 , but we may have to keep a "part" of M 1 , namely M 1 . Second, it might not be possible to use M 12 , but we may need a slightly "extended" mapping M 12 . Of course, to study representability in a general setting, we do not formally constrain in this definition how these "parts" and "extensions" must look like. The third way we may adapt our equation to some application is by using an appropriate equivalence relation ≡ χ , e.g., by using the so-called data exchange equivalence [7] if our application is related to data exchange. Given this general definition, one has a lot of freedom in choosing M 1 and M 12 . In particular, by choosing M 1 = M 1 and M 12 = M 12 , even the identity mapping
On the other end of the spectrum, there is a clear "best" kind of general representation M 2 , namely if one can choose M 1 = Id 1 = {(I, I) | I ∈ Inst(S 1 )} and M 12 = M 12 . If these two equalities hold, we speak of a strong χ-representation. We thus described what one could consider "trivial" and "best" representations, however there is much room between those two extremes.
For example, it is reasonable to require that while M 1 • M 12 should be able to be more restrictive than M 12 , it should not be more restrictive than M 1 • M 12 together. Altogether, one can thus require that:
When these conditions hold, we talk about a weak χ-representation. We intend to use weak χ-representations for characterizing Q-representability in future work.
The intuition behind the notion of weak representability is to offer an intermediate amount of freedom between strong representations and unconstrained general representations. In particular, the witness (M 1 , M 12 ) has to be at least as restrictive as the witness of a strong representation (M 1 • M 12 M 12 ) and at most as restrictive as the witness of a "trivial" representation (M 1 • M 12 M 1 • M 12 ). These conditions allow to rule out problematic behaviour that may occur in a general setting, but not in the context of e.g. Q-representability.
An orthogonal restriction is to allow either only a source-to-target witness M 12 or only a source witness M 1 in Definition 1, giving rise to the notions of source-to-target χ-representation (M 1 = Id 1 ) and source χ-representation (M 12 = M 12 ). Formally, M 2 is a source-to-target χ-representation of M 1 under M 12 if M 2 is a general χrepresentation witnessed by the pair of mappings (Id 1 , M 12 ). Source χ-representation can be defined similarly by requiring (M 1 , M 12 ) as the witness in Definition 1. Note that while for some situations M 1 or M 12 suffice, the interplay between them can become important, in particular when putting restrictions on the classes of mappings used. In the next section we use source-to-target χ-representations to characterize safety.
In this section, we show that the notion of safety, which was developed in [5] in the context of knowledge exchange, can be characterized by the notion of general representation introduced in the previous section. In what follows, we assume that a knowledge base K = (I, Σ) over a schema S is given by an instance I of S, called the explicit knowledge, and a set Σ of dependencies over S, called the implicit knowledge. Moreover, we associate to Σ a mapping Map(Σ) = {(I, J) | I, J ∈ Inst(S), I ⊆ J and J Σ}. Finally, we define the set of models of K = (I, Σ) as Mod(K) = Sol Map(Σ) (I).
In order to define the notion of safety proposed in [5], we need to introduce some terminology. Given a set I of instances of a schema S, we define Min(I) as the set of minimal instances in I under the subset relation, that is, as {I ∈ I | there is no I ∈ I such that I I}. Moreover, given a mapping M from a schema S 1 to a schema S 2 and knowledge bases K 1 = (I 1 , Σ 1 ), K 2 = (I 2 , Σ 2 ) over S 1 and S 2 , respectively, K 2 is called a minimal knowledge-base solution for K 1 under M if Min(Mod(K 2 )) = Min(Sol M (Mod(K 1 ))) [5]. With these concepts, we can formally define the notion of safety.
). Let M be a schema mapping from a schema S 1 to a schema S 2 , and Σ 1 , Σ 2 be sets of dependencies over S 1 and S 2 , respectively. Then Σ 2 is said to be safe for Σ 1 under M, if for every instance I 1 of S 1 , there exists an instance I 2 of S 2 such that (I 2 , Σ 2 ) is a minimal knowledge-base solution for (I 1 , Σ 1 ) under M.
In order to capture safety by using the notion of general representability, we first need to choose the appropriate notion of equivalence to be used in equation ( ‡). It is clear that the notion of minimality plays a major role in Definition 2, thus equivalence with respect to minimal solutions is a natural choice. More precisely, for I ∈ Inst(S 1 ), we define MinSol M (I) = Min(Sol M (I)) and say that M 12 ≡ MinSol M 12 if for every I ∈ Inst(S 1 ), it holds that MinSol M12 (I) = MinSol M 12 (I).
It is important to notice that the original definition of safety given in [5] only considered full tuple-generating dependencies (that is, Σ 1 and M in Definition 2 were required to be based on these dependencies). A consequence of this restriction is that only mappings that are absolutely consistent, in the sense defined in [2], were considered in the original definition of safety. So when capturing this notion we focus on this class of mappings. More precisely, a mapping M from a schema S 1 to a schema S 2 is said to be absolutely consistent if for every I ∈ Inst(S 1 ), it holds that Sol M (I) = ∅. Then we have that: Proposition 1. Let Σ 1 , Σ 2 be sets of dependencies over schemas S 1 and S 2 , respectively, and assume that M 12 is a mapping such that Map(Σ 1 ) • M 12 is absolutely consistent. Then Σ 2 is safe for
It follows that safety as defined in [5] can be captured by source-to-target MinSolrepresentability, as M 1 • M 12 is absolutely consistent in the definition given in [5] (since M 1 and M 12 are required to be based on full tuple-generating dependencies in [5]). Interestingly, the previous result also holds for mappings based on tuple-generating dependencies with terminating chase.
To capture notions like safety or Q-representability within the framework of general representability, one of the key ingredients is choosing the right notion of equivalence of mappings. In this section, we present the first steps towards the development of some appropriate notions of equivalence of mappings, which connect minimal solutions (used to characterize safety in Proposition 1) to notions of equivalence relevant for Q-representability.
A key role in this connection is played by a generalization of the widely used notion of universal solution [6], which is defined next. Let I be a set of instances, I 1 , I 2 ∈ I, and let C be a set of constants. A homomorphism from I 1 to I 2 that is constant on C is a function h : dom(I 1 ) → dom(I 2 ) such that for all c ∈ (C ∩ dom(I 1 )) we have that h(c) = c, and for all (x 1 , . . . , x n ) ∈ R I1 we have that (h(x 1 ), . . . , h(x n )) ∈ R I2 . We write I 1 C I 2 if such an h exists. We say that
Universal solutions are defined as the minimum elements of a set I of solutions up to equivalence under homomorphisms, while the elements of Hom C (I) are defined as the minimal elements of I up to equivalence under homomorphisms. Furthermore, given a pair I 1 , I 2 of instances of a schema S and a set C of constants, we say that I 1 is a C-core of I 2 if [10,8]: (1) I 1 is a sub-instance of I 2 , (2) I 2 C I 1 , and (3) there is no homomorphism from I 2 to a proper sub-instance of I 1 that is the identity on C. Then let Core C (I) = {I ∈ Inst(S) | I is a C-core of some I ∈ I}.
We are now ready to define the notions of equivalence of mappings studied in this section. For I ∈ Inst(S 1 ) and mapping M from S 1 , we define HomSol M (I) = Hom dom(I) (Sol M (I)) and CoreHomSol M (I) = Core dom(I) (HomSol M (I))). Moreover, M 12 ≡ CoreHomSol M 12 if for all I ∈ Inst(S 1 ) we have that CoreHomSol M12 (I) = CoreHomSol M 12 (I). Next we introduce conditions on mappings that allow us to relate the newly introduced notion to the notion of MinSol we used before. Definition 3. Let M be a mapping from a schema S 1 to a schema S 2 . Then: M is domain-full if for all I ∈ Inst(S 1 ) and J ∈ HomSol M (I), there exists J ∈ HomSol M (I) such that J ⊆ J and dom(J ) ⊆ dom(I); M is founded if for all I ∈ Inst(S 1 ) and J ∈ Sol M (I), there exists J ∈ HomSol M (I) such that J dom(I) J; and M admits core-solutions if for all I ∈ Inst(S 1 ) we have CoreHomSol M (I) ⊆ Sol M (I).
Proposition 2. Let M and M be mappings from a schema S 1 to a schema S 2 such that M is domain-full, founded, and admits core-solutions. Then it holds that M ≡ MinSol M iff M ≡ CoreHomSol M . So for safety as originally defined in [5], we thus know that the following holds: Corollary 1. Let Σ 1 be a set of full tgds over a schema S 1 , Σ 2 a set of dependencies over a schema S 2 and M 12 a mapping from S 1 to S 2 based on full s-t tgds. Then Σ 2 is safe for Σ 1 under M 12 iff Map(Σ 2 ) is a source-to-target CoreHomSol-representation of Map(Σ 1 ) under M 12 .
We have not yet developed a similar result for the notion of Q-representability. But towards that, we studied the connection between equivalence based on CoreHomSol and notions based on query languages relevant for Q-representability, that we introduce next. We assume that a k-ary query q over a schema S is a function that maps every instance I of S to a k-ary relation q(I) contained in dom(I) k . Moreover, given a set I of instances of S and a k-ary query q over S, the set of certain answers of q over I, denoted by cert q (I), is defined as I∈I q(I). Let Q be a class of queries, and M, M be mappings from a schema S 1 to a schema S 2 . In the spirit of [7], we say that M ≡ Q M if for all q ∈ Q over S 2 and I ∈ Inst(S 1 ), it holds cert q (Sol M (I)) = cert q (Sol M (I)). A k-ary query q over a schema S is said to be closed under homomorphisms if for every pair of instances I 1 , I 2 of S, tuple (a 1 , . . . , a k ) ∈ q(I 1 ) and homomorphism h from I 1 to I 2 , it holds that (h(a 1 ), . . . , h(a k )) ∈ q(I 2 ). Let CHQ be the class of queries that are closed under homomorphisms, and UCQ be the class of unions of conjunctive queries.
Again, to formally state the relations between notions of equivalence of mappings, we define some natural conditions and the necessary terminology. We use notation I 1 ∼ =C I 2 to indicate that there exists an isomorphism from I 1 to I 2 that is the identity on C, and we use notation I 1 ↔ C I 2 to indicate that I 1 C I 2 and I 2 C I 1 . Besides, we use notation I 1 ∼ = I 2 as a shorthand for I 1 ∼ = ∅ I 2 . Definition 4. Let M be a mapping from a schema S 1 to a schema S 2 . Then: M is closed under isomorphisms if for all I 1 , I 2 ∈ Inst(S 1 ) and J 1 , J 2 ∈ Inst(S 2 ), if J 1 ∈ Sol M (I 1 ) and (I 1 , J 1 ) ∼ = (I 2 , J 2 ), then J 2 ∈ Sol M (I 2 ); M is target domain-independent if for all I ∈ Inst(S 1 ) and J 1 , J 2 ∈ HomSol M (I), it holds that dom(J 1 ) ∩ dom(I) = dom(J 2 ) ∩ dom(I); and M has a finite base if for every I ∈ Inst(S 1 ), it holds that HomSol M (I) is finite up to ↔ dom(I) .
Theorem 1. Let M, M be mappings from a schema S 1 to a schema S 2 , such that M, M are closed under isomorphisms, founded and target domain-independent. Then M ≡ CHQ M iff M ≡ CoreHomSol M As a corollary of the proof of Theorem 1, we have the following for ≡ UCQ , the most studied notion of equivalence in the context of Q-representability: Corollary 2. Let M, M be mappings from a schema S 1 to a schema S 2 , such that M, M are closed under isomorphisms, are founded, are target domain-independent and have a finite base. Then M ≡ UCQ M iff M ≡ CoreHomSol M .
In this paper, we introduced the framework of general representability that allows us to study notions of representability like safety and Q-representability. We introduced notions of equivalence suitable for capturing safety, and defined conditions under which these characterizations apply. In particular, we were able to capture safety as originally defined. We also started introducing the necessary machinery for studying Q-representability, with a focus on the UCQ and the more general CHQ case.
As future work, we intend to capture Q-representability, and continue using the framework of general representability to develop notions of representation both for specific applications like knowledge exchange as well as in the general case. The study of the conditions and notions of equivalence we introduced will also be an interesting endeavor in its own right, as it allows us to find candidates for conditions which schema mapping formalisms should satisfy.