Towards General Representability in Knowledge Exchange

Abstract

M. Arenas was supported by Fondecyt grant #1110287, J. Pe´rez was supported by Fondecyt grant #11110404, the research of E. Sallinger is supported by the Austrian Science Fund (FWF):P25207-N23.

Introduction

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. 2

Preliminaries

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 2 Inst(S) assigns to each relation symbol R a relation RI 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 S1 to a target schema S2 is a subset of Inst(S1) Inst(S2).4 The composition of two mappings, symbolized by , is defined as the composition of binary relations [ 9 ]. M and M0 are equivalent, written M M0, if they are equal as binary relations (M = M0). Besides, we write M M0 for M M0. 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 = f(I; J ) j (I; J ) g. 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 SolM(I) = fJ j (I; J ) 2 M and I 2 Ig. A single instance I 2 Inst(S1) is treated as a singleton set fIg wherever applicable, e.g. SolM(I) = SolM(fIg).

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 SolM(I) represents all possible completions of I where the implicit knowledge has been made explicit. For keeping schema specifications brief, a subscripted mapping Mi is always from schema Si to Si, and a mapping Mij is always from schema Si to Sj . 4 To adapt to the knowledge exchange setting [ 5 ], we do not explicitly consider labeled nulls in target instances, however the concept is preserved as constants only occurring in a target instance are essentially treated as labeled nulls in data exchange [ 6 ].

General Representability

Intuitively, given mappings M1, M2 and M12, we say that M2 “represents” M1 under M12 if the following equivalence is fulfilled:

M1

M12

M12

M2: In the context of knowledge exchange, M1 and M2 can be seen as the mappings responsible for generating the completions discussed in the preliminaries, and M12 as the mapping used for transferring data. The condition (y) is very strong. In particular, M12 must already transfer enough of the source data for such an M2 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 M1? and M1?2 such that

M1

M12

? M1 The intuition behind this definition is the following: M2 may not be the “ideal” representation as defined by equation (y). Though, if through keeping small parts of M1 and by slightly extending M12 we can show equivalence, this may be good enough for a given application. In particular, it might not be possible to completely remove M1, but we may have to keep a “part” of M1, namely M1?. Second, it might not be possible to use M12, but we may need a slightly “extended” mapping M1?2. 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 M1? and M1?2. In particular, by choosing M1? = M1 and M1?2 = M12, even the identity mapping M2 = Id2 = f(I; I) j I 2 Inst(S2)g is a general representation of M1 under M12. On the other end of the spectrum, there is a clear “best” kind of general representation M2, namely if one can choose M1? = Id1 = f(I; I) j I 2 Inst(S1)g and M1?2 = M12. 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 M1? M1?2 should be able to be more restrictive than M12, it should not be more restrictive than M1 M12 together. Altogether, one can thus require that: and

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 (M1; M1?2) has to be at least as restrictive as the witness ? ooff aa s“ttrroivnigalr”erperperseesnetnattiaotino(n M(M1? 1 MM1?212 MM121?) anMda1?t2m).oTshteasserceostnrdicittiivoensasaltlhoewwtoitnreusles 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 M1?2 or only a source witness M1? in Definition 1, giving rise to the notions of source-to-target -representation (M1? = Id1) and source -representation (M1?2 = M12). Formally, M2 is a source-to-target -representation of M1 under M12 if M2 is a general representation witnessed by the pair of mappings (Id1; M1?2). Source -representation ? can be defined similarly by requiring (M1; M12) as the witness in Definition 1. Note that while for some situations M1? or M12 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. 4

Characterizing 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( ) = f(I; J ) j I; J 2 Inst(S); I J and J g. Finally, we define the set of models of K = (I; ) as Mod(K) = SolMap( )(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 fI 2 I j there is no I0 2 I such that I0 ( Ig. Moreover, given a mapping M from a schema S1 to a schema S2 and knowledge bases K1 = (I1; 1), K2 = (I2; 2) over S1 and S2, respectively, K2 is called a minimal knowledge-base solution for K1 under M if Min(Mod(K2)) = Min(SolM(Mod(K1))) [ 5 ]. With these concepts, we can formally define the notion of safety.

Definition 2 ([ 5 ]). Let M be a schema mapping from a schema S1 to a schema S2, and 1, 2 be sets of dependencies over S1 and S2, respectively. Then 2 is said to be safe for 1 under M, if for every instance I1 of S1, there exists an instance I2 of S2 such that (I2; 2) is a minimal knowledge-base solution for (I1; 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 (z). 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 2 Inst(S1), we define MinSolM(I) = Min(SolM(I)) and say that M12 MinSol M012 if for every I 2 Inst(S1), it holds that MinSolM12 (I) = MinSolM012 (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 S1 to a schema S2 is said to be absolutely consistent if for every I 2 Inst(S1), it holds that SolM(I) 6= ;. Then we have that: Proposition 1. Let 1, 2 be sets of dependencies over schemas S1 and S2, respectively, and assume that M12 is a mapping such that Map( 1) M12 is absolutely consistent. Then 2 is safe for 1 under M12 iff Map( 2) is a source-to-target MinSolrepresentation of Map( 1) under M12.

It follows that safety as defined in [ 5 ] can be captured by source-to-target MinSolrepresentability, as M1 M12 is absolutely consistent in the definition given in [ 5 ] (since M1 and M12 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. 5

On the Equivalence of Mappings

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, I1; I2 2 I, and let C be a set of constants. A homomorphism from I1 to I2 that is constant on C is a function h : dom(I1) ! dom(I2) such that for all c 2 (C \ dom(I1)) we have that h(c) = c, and for all (x1; : : : ; xn) 2 RI1 we have that (h(x1); : : : ; h(xn)) 2 RI2 . We write I1 C I2 if such an h exists. We say that I1 C I2 if I1 C I2 and I2 6 C I1. Then let HomC(I) = fI 2 I j there is no I0 2 I such that I0 C Ig. Universal solutions are defined as the minimum elements of a set I of solutions up to equivalence under homomorphisms, while the elements of HomC(I) are defined as the minimal elements of I up to equivalence under homomorphisms. Furthermore, given a pair I1; I2 of instances of a schema S and a set C of constants, we say that I1 is a C-core of I2 if [ 10, 8 ]: (1) I1 is a sub-instance of I2, (2) I2 C I1, and (3) there is no homomorphism from I2 to a proper sub-instance of I1 that is the identity on C. Then let CoreC(I) = fI 2 Inst(S) j I is a C-core of some I0 2 Ig.

We are now ready to define the notions of equivalence of mappings studied in this section. For I 2 Inst(S1) and mapping M from S1, we define HomSolM(I) = Homdom(I)(SolM(I)) and CoreHomSolM(I) = Coredom(I)(HomSolM(I))). Moreover, M12 CoreHomSol M012 if for all I 2 Inst(S1) we have that CoreHomSolM12 (I) = CoreHomSolM012 (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 S1 to a schema S2. Then: M is domain-full if for all I 2 Inst(S1) and J 2 HomSolM(I), there exists J 0 2 HomSolM(I) such that J 0 J and dom(J 0) dom(I); M is founded if for all I 2 Inst(S1) and J 2 SolM(I), there exists J 0 2 HomSolM(I) such that J 0 dom(I) J ; and M admits core-solutions if for all I 2 Inst(S1) we have CoreHomSolM(I) SolM(I). Proposition 2. Let M and M0 be mappings from a schema S1 to a schema S2 such that M is domain-full, founded, and admits core-solutions. Then it holds that M MinSol M0 iff M CoreHomSol M0.

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 S1, 2 a set of dependencies over a schema S2 and M12 a mapping from S1 to S2 based on full s-t tgds. Then 2 is safe for 1 under M12 iff Map( 2) is a source-to-target CoreHomSol-representation of Map( 1) under M12.

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 certq(I), is defined as TI2I q(I). Let Q be a class of queries, and M, M0 be mappings from a schema S1 to a schema S2. In the spirit of [ 7 ], we say that M Q M0 if for all q 2 Q over S2 and I 2 Inst(S1), it holds certq(SolM(I)) = certq(SolM0 (I)). A k-ary query q over a schema S is said to be closed under homomorphisms if for every pair of instances I1; I2 of S, tuple (a1; : : : ; ak) 2 q(I1) and homomorphism h from I1 to I2, it holds that (h(a1); : : : ; h(ak)) 2 q(I2). 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 I1 =C I2 to indicate that there exists an isomorphism from I1 to I2 that is the identity on C, and we use notation I1 $C I2 to indicate that I1 C I2 and I2 C I1. Besides, we use notation I1 = I2 as a shorthand for I1 =; I2.

Definition 4. Let M be a mapping from a schema S1 to a schema S2. Then: M is closed under isomorphisms if for all I1; I2 2 Inst(S1) and J1; J2 2 Inst(S2), if J1 2 SolM(I1) and (I1; J1) = (I2; J2), then J2 2 SolM(I2); M is target domain-independent if for all I 2 Inst(S1) and J1; J2 2 HomSolM(I), it holds that dom(J1) \ dom(I) = dom(J2) \ dom(I); and M has a finite base if for every I 2 Inst(S1), it holds that HomSolM(I) is finite up to $dom(I). Theorem 1. Let M, M0 be mappings from a schema S1 to a schema S2, such that M, M0 are closed under isomorphisms, founded and target domain-independent. Then M CHQ M0 iff M CoreHomSol M0

As a corollary of the proof of Theorem 1, we have the following for

studied notion of equivalence in the context of Q-representability:

UCQ, the most

Corollary 2. Let M, M0 be mappings from a schema S1 to a schema S2, such that M, M0 are closed under isomorphisms, are founded, are target domain-independent and have a finite base. Then M UCQ M0 iff M CoreHomSol M0. 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.

References

1. Abiteboul , S. , Hull , R. , Vianu , V. : Foundations of Databases. Addison-Wesley ( 1995 )

2. Amano , S. , Libkin , L. , Murlak , F. : XML schema mappings . In: PODS . pp. 33 - 42 ( 2009 )

3. Arenas , M. , Botoeva , E. , Calvanese , D. : Knowledge base exchange . In: DL ( 2011 )

4. Arenas , M. , Botoeva , E. , Calvanese , D. , Ryzhikov , V. , Sherkhonov , E.: Exchanging description logic knowledge bases . In: KR ( 2012 )

5. Arenas , M. , Pe´rez, J., Reutter , J.L. : Data exchange beyond complete data . In: PODS . pp. 83 - 94 ( 2011 )

6. Fagin , R. , Kolaitis , P.G. , Miller , R.J. , Popa , L. : Data exchange: semantics and query answering . Theor. Comput. Sci . 336 ( 1 ), 89 - 124 ( 2005 )

7. Fagin , R. , Kolaitis , P.G. , Nash , A. , Popa , L. : Towards a theory of schema-mapping optimization . In: PODS . pp. 33 - 42 ( 2008 )

8. Fagin , R. , Kolaitis , P.G. , Popa , L. : Data exchange: getting to the core . ACM Trans. Database Syst . 30 ( 1 ), 174 - 210 ( 2005 )

9. Fagin , R. , Kolaitis , P.G. , Popa , L. , Tan , W.C. : Composing schema mappings: Second-order dependencies to the rescue . ACM Trans. Database Syst . 30 ( 4 ), 994 - 1055 ( 2005 )

10. Hell , P. , Nesetril , J.: The core of a graph . Discrete Mathematics 109 ( 1-3 ), 117 - 126 ( 1992 )

11. Hernich , A. , Schweikardt , N.: Logic and data exchange: Which solutions are ”good” solutions? In: LOFT . pp. 61 - 85 ( 2008 )