Data exchange (DE) [5, 3] and data coordination [1, 2, 6] are two important settings that were introduced previously in the literature to resolve the problem of integrating information that resides in di erent sources. A DE setting moves data residing in independent applications, which refer to the same object using the same name, and accesses it through a new target schema. However, a data coordination setting allows the access of data residing in independent sources and that possibly belong to di erent sets of vocabularies, without necessarily exchanging it and while maintaining autonomy. Although a data coordination setting provides users with an amalgamated view of related information, this solution is not enough for applications that require a view of related information using a uni ed set of vocabularies for periodic reporting and decision making. We introduce a general data exchange (GDE) setting that extends DE settings to allow collaboration at the instance level, using a mapping table M , that speci es for each constant value in the source, the set of related (or corresponding) constant values in the target.1 We show in this paper that a GDE setting can be formalized using the knowledge exchange framework introduced in [4]. It allows us to store a target knowledge base (KB) which consists of a subset of the explicit data exchanged that is necessary to infer the full set of exchanged information using a set t of FO sentences. We identify in our work the class of \best" KBs to materialize and we de ne the set of certain answers. A (DE) setting [5, 3] is a tuple S = (S; T; st), where S is a source schema, T is a target schema, S and T do not have predicate symbols in common, and st consists of a set of source-to-target tuple-generating dependencies (st-tgds) that establish the relationship between source and target schemas. A st-tgd is a FOsentence of the form: 8x8y ( (x; y) ! 9z (x; z)); where (x; y) and (x; z) are conjunctions of relational atoms over S and T respectively. Let Const and Var be in nite and disjoint sets of constants and nulls, respectively. We consider in our
1 We consider in this work a particular interpretation of related data in a mapping table; that is, a source element is always uniquely identi ed by at least one target element. work \complete" source instances I of S, where it holds that dom(I) Const and do not contain missing data in the form of nulls. However, a target instance J of T, is allowed to contain null values, and it holds that dom(J ) Const [ Var;
A knowledge base [
Mapping tables [
A GDE setting S = (S; T; M; st) extends a DE setting with (1) a binary relation symbol M that appears neither in S nor in T, and that is called a source-to-target mapping; and (2) st that consists of a set of mapping st-tgds, which are FO sentences of the form: 8x8y8z ( (x; y) ^ (x; z) ! 9w (z; w)); where (a) (x; y) and (z; w) are conjunctions of relation symbols over S and T respectively, and (b) (x; z) is a conjunction of relation symbols that only use the st-mapping relation symbol M. We denote st-mapping tables by M .
In a GDE setting, source KBs are of the form ((I [ fM g); s = ;), which
correspond to data in the source instance I and the st-mapping table M . On
the other hand, the target KBs are of the form ((J [ fM g); t) where t is a
set of FO sentences, of type f ull tgds (which are tgds that do not use
existential quantication). We formalize the notion of a (universal) GDE KB-solution,
extending the notion of knowledge exchange (universal) solution in [
Intuitively, in a GDE setting S, C is the sole set of target values that can capture correctly the set of source values exchanged to a target instance. Therefore, intuitively a GDE KB-solution J in S has a domain dom(J ) C [ Var. We de ne t as the following set of full tgds over a schema T [ fM; Relatedg, where Related is a fresh binary table: 1. For each T 2 T [ fMg of arity n and 1 i n:
8x1 8xn(T (x1; : : : ; xi; : : : ; xn) ! Related(xi; xi)). 2. 8x8y8z(M(z; x) ^ M(z; y) ^ C(x) ! Related(x; y)). 3. For each T 2 T of arity n: 8x1; y1 8xn; yn (T (x1; : : : ; xn) ^ Vin=1 Related(xi; yi) ! T (y1; : : : ; yn)).
In a GDE setting, we de ne \best" solutions formally following [
We adapt the notion of a certain answer in the usual DE setting to the GDE setting. Formally, let S be a GDE setting, I a source instance, M an st-mapping table, and Q a conjunctive query over T. The set of certain answers of Q over I and M and under S, denoted certainS((I [ fM g); Q), corresponds to the set of tuples of constants that belong to the evaluation of Q over KT, for each GDE KB-solution J for I and M and K 2 Mod((J [ fMg); t). Finally, generating certainS((I [ fM g); Q) is in Logspace. 5
An interesting extension for this work would be de ning a GDE setting with a target that contains egds and tgds constraints. Also, investigating GDE in a peer-to-peer setting might add interesting challenges to the problem.