=Paper=
{{Paper
|id=None
|storemode=property
|title=Knowledge Base Exchange
|pdfUrl=https://ceur-ws.org/Vol-745/paper_57.pdf
|volume=Vol-745
|dblpUrl=https://dblp.org/rec/conf/dlog/ArenasBC11
}}
==Knowledge Base Exchange==
https://ceur-ws.org/Vol-745/paper_57.pdf
Knowledge Base Exchange
Marcelo Arenas1 , Elena Botoeva2 , and Diego Calvanese2
1
Dept. of Computer Science, PUC Chile
marenas@ing.puc.cl
2
KRDB Research Centre, Free Univ. of Bozen-Bolzano, Italy
lastname@inf.unibz.it
Abstract. In this paper, we study the problem of exchanging knowledge between
two knowledge bases (KBs) connected through mappings, with a special interest
in exchanging implicit knowledge, not only data like in the traditional database
exchange setting. As representation formalism we use Description Logics (DL)
that exhibit a reasonable tradeoff between expressive power and complexity of
reasoning. Thus, we assume that the source and target KBs are given as a DL
TBox+ABox, while the mappings have the form of DL TBox assertions. We
study the problem of translating the knowledge in the source KB according to
these mappings. We define a general framework of KB exchange, and specify the
problems of computing and representing different kinds of solutions, i.e., target
KBs with specified properties, given a source KB and a mapping. We then de-
velop first results and techniques and study the complexity of KB exchange for
the case of DL-LiteRDFS , a DL that corresponds to the FOL fragment of RDFS.
1 Introduction
In data exchange, data structured under one schema (called source schema) must be
restructured and translated into an instance of a different schema (called target schema),
and the way in which this restructuring should occur is specified by means of a mapping
from the source schema to the target schema [5]. Such a problem has been studied
extensively in recent years, under various choices for the languages used to specify the
source and target schema, and the mappings [2]. While incomplete information in this
setting is introduced by the mapping layer (see also [6]), one fundamental assumption
in the works on data exchange is that the source is a (completely specified) database.
In this paper, we go beyond this setting, and consider data exchange in the case
where implicit knowledge is present in the source, by which new data may be inferred.
We follow the line of the work in [1], where a general framework for data exchange
is proposed, in which the source data may be incompletely specified, and thus (possi-
bly infinitely) many source instances are implicitly represented. The framework in [1]
in based on the general notion of representation system, as a mechanism to represent
multiple instances of a data schema, and considers the problem of incomplete data ex-
changes under mappings constituted by a set of tuple generating dependencies (tgds).
We refine that framework to the case where as a representation system we use De-
scription Logics (DL) knowledge bases (KBs) constituted by a TBox and an ABox,
and where mappings are sets of DL inclusions. While in the traditional data exchange
2 Marcelo Arenas, Elena Botoeva, and Diego Calvanese
setting, given a source instance and a mapping specification, (universal) solutions are
target instances derived from the source instance and the mapping, in our case solutions
are target DL KBs, derived from the source KB and the mapping. Besides a notion of
(universal) solution based on the correspondence between models of source and tar-
get KBs, we introduce also the weaker notion of (universal) CQ-solution, based on the
correspondence between answers to conjunctive queries over source and target KBs.
In our setting where we exchange DL KBs, in order to minimize the exchange (and
hence transfer and materialization) of explicit (i.e., ABox) information, we are inter-
ested in computing universal (CQ-)solutions that contain as much implicit knowledge
as possible. This leads us to define a new problem, called representability, whose goal
is to compute from a source TBox and a mapping, a target TBox that leads to a univer-
sal (CQ-)solution when it is combined with a suitable ABox computed from the source
ABox, independently of the actual source ABox.
We then develop first results and techniques for KB exchange and for the repre-
sentability problem in the case of KBs expressed in DL-LiteRDFS , a DL that corresponds
to the FOL fragment of RDFS. DL-LiteRDFS is a fragment of DL-LiteR [4] that does not
allow for existential quantification (i.e., concepts of the form ∃R) in the right-hand side
of concept inclusions, nor for disjointness assertions.
The paper is organized as follows. In Section 2 we give preliminary notions on DLs
and conjunctive queries (CQs). In Section 3 we define our framework of KB exchange.
In Section 4 we present the techniques for deciding the defined reasoning tasks. Finally,
in Section 5 we draw some conclusions and outline issues for future work.
2 Preliminaries
We introduce here the necessary notions about the description logic (DL) that we use in
this article, and about conjunctive queries, which we adopt as our query formalism.
2.1 DL-LiteR Knowledge Bases
The DLs of the DL-Lite family [4] of light-weight description logics are characterized
by the fact that reasoning can be done in polynomial time, and that data complexity of
reasoning and conjunctive query answering is in AC0 . We adopt here DL-LiteR , and
present now its syntax and semantics.
Let NC , NR , Na be sets of concept, role, and individual names, respectively, and
assume that A ∈ NC and P ∈ NR . In DL-LiteR , B and C are used to denote basic
and complex concept descriptions, respectively, and R and Q are used to denote basic
and complex roles, respectively. These concept and roles constructs are defined by the
following grammar:
R ::= P | P − B ::= A | ∃R
Q ::= R | ¬R C ::= B | ¬B
In the following, for a basic role R, we use R− to denote P − when R = P , and P
when R = P − .
Knowledge Base Exchange 3
A DL-LiteR TBox is a finite set of concept inclusions B v C and role inclusions
R v Q. A DL-LiteR ABox is a finite set of membership assertions of the form A(a) and
P (a, b), where a, b ∈ Na . A DL-LiteR KB K is a pair hT , Ai, where T is a DL-LiteR
TBox and A is a DL-LiteR ABox. As usual, TBoxes represent implicit knowledge,
while ABoxes represent the data.
In the following, we will also make use of a restricted form of DL-LiteR TBoxes.
A DL-LiteR TBox is said to be definite if there are only atomic concepts and atomic
roles on the right-hand side of its inclusions. In other words, a definite TBox may not
mention in its right-hand side a concept of the form ∃R, and may not contain concept
or role disjointness assertions. We call DL-LiteRDFS the fragment of DL-LiteR obtained
by considering only definite DL-LiteR TBoxes. Intuitively, DL-LiteRDFS corresponds to
the fragment of RDFS [3] that is embeddable in FOL (and hence in DLs).
The semantics of DL-LiteR is defined in the standard way. We just remark that
we use M OD(K) to denote the set of all models of KB K. From now on, we assume
that interpretations satisfy the standard name assumption, that is, we assume given a
fixed infinite set U of individual names, and we assume that for every interpretation
I = h∆I , ·I i, it holds that ∆I ⊆ U and aI = a for every a ∈ ∆I . Notice that this
implies the Unique Name Assumption (UNA), i.e., different individuals are interpreted
as different domain elements.
A signature Σ is a set of concept and role names. An interpretation I = h∆I , ·I i is
said to be an interpretation of Σ if it is defined exactly on the concept and role names in
Σ. Given a KB K, the signature Σ(K) of K is the alphabet of concept and role names
occurring in K, and K is said to be defined over (or simply, over) a signature Σ if
Σ(K) ⊆ Σ (and likewise for a TBox T , an ABox A, a concept inclusions B v C, a
role inclusions R v Q, and membership assertions A(a) and R(a, b)).
2.2 Conjunctive Queries and Certain Answers
A conjunctive query (CQ) over a signature Σ is a first-order formula of the form
q(x) = ∃y.conj (x, y), where x, y are tuples of variables and conj (x, y) is a con-
junction of atoms of the form: (1) A(t), with A a concept name in Σ and t either a
constant from U or a variable from x or y, or (2) P (t1 , t2 ), with P a role name in Σ
and ti (i = 1, 2) either a constant from U or a variable from x or y. In a conjunc-
tive query q(x) = ∃y.conj (x, y), x is the tuple of free variables Wn of q(x). A union of
conjunctive queries (UCQ) is a formula of the form: q(x) = i=1 ∃y i .conj i (x, y i ),
where each conji (x, y i ) is as before. A query q (either a CQ or a UCQ) is said to be a
query over a KB K if q is a query over a signature Σ and Σ ⊆ Σ(K).
Let q be a CQ ∃y1 · · · ∃y` .conj (x1 , . . . , xk , y1 , . . . , y` ) over a signature Σ and
I = h∆I , ·I i an interpretation of Σ. Then the answer of q over I, denoted by q I ,
is defined as the set of tuples (a1 , . . . , ak ) of elements from ∆I for which there ex-
ist a tuple (b1 , . . . , b` ) of elements from ∆I such that I satisfies Wn every conjunct in
conj (a1 , . . . , ak , b1 , . . . , b` ). Moreover, given a UCQSq = i=1 qi , the answer of q
n
over an interpretation I, denoted by q I , is defined as i=1 qiI . Finally, given a query q
(either a CQ or a UCQ) over T a KB K, the answer to q over K, denoted by cert(q, K),
is defined as cert(q, K) = I∈M OD(K) q I . Each tuple in cert(q, K) is called a certain
answer for q over K.
4 Marcelo Arenas, Elena Botoeva, and Diego Calvanese
Certain answers in DL-LiteR can be characterized through the notion of chase. We
call a chase a (possibly infinite) set of assertions of the form A(t), P (t, t0 ), where t, t0
are either individuals, or labeled nulls interpreted as not necessarily distinct domain el-
ements. For DL-LiteR KBs, we employ the notion of oblivious chase as defined in [4].
For such a KB hT , Ai, the chase of A w.r.t. T , denoted chaseT (A), is a chase ob-
tained from A by adding facts implied by inclusions in T , and introducing labeled nulls
whenever required by an inclusion with ∃R in the right-hand side (see [4] for details).
3 Exchanging Knowledge Bases
In this section, we introduce the knowledge exchange framework used in the paper.
The starting point to define this framework is the notion of mapping, which has been
shown to be of fundamental importance in the context of data exchange [5]. Formally,
a DL-LiteR -mapping (or just mapping) is a tuple M = (Σ1 , Σ2 , T12 ), where Σ1 , Σ2
are disjoint signatures and T12 is a DL-LiteR TBox whose inclusions are of the form:
(1) C1 v C2 , where C1 , C2 are complex concepts over Σ1 and Σ2 , respectively, and
(2) Q1 v Q2 , where Q1 and Q2 are complex roles over Σ1 and Σ2 , respectively.
Let M = (Σ1 , Σ2 , T12 ) be a mapping. Intuitively, mapping M specifies how a
knowledge base over the vocabulary Σ1 should be translated into a knowledge base
over the vocabulary Σ2 . This intuition is formalized in terms of the notion of solution,
which is defined as follows. Given an interpretation I1 of Σ1 and an interpretation
I2 of Σ2 , pair (I1 , I2 ) satisfies TBox T12 , denoted by (I1 , I2 ) |= T12 , if for each
concept inclusion C1 v C2 ∈ T12 , it holds that C1I1 ⊆ C2I2 , and for each role inclusion
Q1 v Q2 ∈ T12 , it holds that QI1 1 ⊆ QI2 2 . Moreover, given an interpretation I of Σ1 ,
S ATM (I) is defined as the set of interpretations J of Σ2 such that (I, J ) |= T12 , and
given a set X of interpretations of Σ1 , S ATM (X ) is defined as:
S
S ATM (X ) = I∈X S ATM (I).
Then the notion of solution under a mapping is defined as follows, by considering this
notion of satisfaction and the knowledge exchange framework proposed in [1].
Definition 1. Let M = (Σ1 , Σ2 , T12 ) be a mapping, K1 a KB over Σ1 , and K2 a KB
over Σ2 . Then K2 is said to be a solution for K1 under M if:
M OD(K2 ) ⊆ S ATM (M OD(K1 )).
That is, K2 is a solution for K1 under M if for every model I2 of K2 , there exists a
model I1 of K1 such that (I1 , I2 ) |= T12 .
Let M = (Σ1 , Σ2 , T12 ). A KB K1 over Σ1 can have an infinite number of solutions
under M. Thus, it is natural to ask what is a good solution for this knowledge base. Next
we introduce the notion of universal solution, which is a simple extension of the concept
of solution introduced in Definition 1, and is based on the notion of universal solution
introduced in [1].
Definition 2. Let M = (Σ1 , Σ2 , T12 ) be a mapping, K1 a KB over Σ1 , and K2 a KB
over Σ2 . Then K2 is said to be a universal solution for K1 under M if:
M OD(K2 ) = S ATM (M OD(K1 )).
Knowledge Base Exchange 5
In the preceding definition, KB K2 is considered to be a good solution for KB K1 under
mapping M as the models of K2 exactly correspond to the valid translations of the
models of K1 according to M. We illustrate Definitions 1 and 2 in an example.
Example 1. Let M = (Σ1 , Σ2 , T12 ), where Σ1 = {A1 , B1 }, Σ2 = {A2 , B2 }, and
T12 = {A1 v A2 , B1 v B2 }. Furthermore, assume that K1 = hT1 , A1 i, where
T1 = {B1 v A1 } and A1 = {B1 (a)}. Then the following knowledge bases over Σ2
are solutions for K1 under M:
K2 = hT2 , A2 i, where T2 = ∅, A2 = {B2 (a), A2 (a)}
K20 = hT20 , A02 i, where T20 = {B2 v A2 }, A02 = {B2 (a)}
Moreover, K2 is a universal solution for K1 under M, while K20 is not. In fact, if I2 is
an interpretation of Σ2 such that: ∆I2 = {a, b}, AI2 2 = {a}, and B2I2 = {a, b}, then
we have that I2 6∈ M OD(K20 ) since I2 does not satisfy inclusion B2 v A2 , but I2 ∈
S ATM (M OD(K1 )) since (I1 , I2 ) |= T12 for I1 ∈ M OD(K1 ) defined as ∆I1 = {a},
AI1 1 = {a} and B1I1 = {a}.
In the previous example, K20 is not a universal solution for K1 under M since inclusion
B2 v A2 cannot be deduced from the information in K1 and M. Or, more formally,
K20 is not a universal solution as B2 v A2 is not implied by hT1 ∪ T12 , A1 i. However,
K20 can also be considered as a solution of K1 that is desirable to materialize, as the
implicit knowledge in K2 (i.e., TBox T2 ) represents the implicit knowledge in K1 (i.e.,
TBox T1 ), given the way that concepts A1 and B1 have to be translated according to
mapping M. In fact, solution K20 is as good as solution K2 in terms of the information
that can be extracted from them by using some specific queries, but with the advantage
that K20 represents knowledge in a more compact way. In what follows, we introduce a
new class of good solutions that captures this intuition with respect to the widely used
fragment of CQs.
Definition 3. Let M = (Σ1 , Σ2 , T12 ) be a mapping, K1 = hT1 , A1 i a KB over Σ1 ,
and K2 a KB over Σ2 . Then K2 is said to be a CQ-solution for K1 under M if for every
CQ q over Σ2 , we have that cert(q, hT1 ∪ T12 , A1 i) ⊆ cert(q, K2 ).
Moreover, K2 is said to be a universal CQ-solution for K1 under M if for every CQ
q over Σ2 , we have that cert(q, hT1 ∪ T12 , A1 i) = cert(q, K2 ).
Notably, we have in Example 1 that both KB K2 and KB K20 are universal CQ-solutions
for KB K1 under mapping M.
A natural question at this point is what is the relationship between the notions of
solution presented in this section. The following proposition, which is straightforward
to prove, shows that the notion of (universal) CQ-solution is weaker than the notion of
(universal) solution.
Proposition 1. Let M = (Σ1 , Σ2 , T12 ) be a mapping, K1 a KB over Σ1 , and K2 a
KB over Σ2 . If K2 is a (universal) solution for K1 under M, then K2 is a (universal)
CQ-solution for K1 under M.
In this paper, we study several fundamental problems related to the notions of solution
presented here. These problems are formally introduced below.
6 Marcelo Arenas, Elena Botoeva, and Diego Calvanese
3.1 Knowledge Base Exchange: Reasoning Tasks
In the data exchange scenario [5], as well as in the knowledge exchange scenario [1],
the problem of materializing solutions has been identified as the fundamental problem
to solve. Given a class U of mappings (for example, the class of DL-LiteR -mappings)
and a DL L (for example, DL-LiteR ), the problem of computing solutions is defined as
follows for U and L:
PROBLEM : C OMP S OL(U, L)
INPUT : A mapping M ∈ U and an L-knowledge base K1 over Σ1
TO DO : Compute an L-knowledge base K2 over Σ2 such that K2 is a solu-
tion for K1 under M
Given a class U of mappings and a DL L, the computation problems
C OMP U NIV S OL(U, L), C OMP CQS OL(U, L), and C OMP U NIV CQS OL(U, L) are de-
fined exactly as above, but considering universal solutions, CQ-solutions, and universal
CQ-solutions instead of solutions, respectively.
In the rest of this paper, we study these problems, and some other fundamental
problems associated to them, for a restriction of the class of mappings introduced in
this section. More precisely, a mapping M = hΣ1 , Σ2 , T12 i is said to be definite if T12
is a DL-LiteRDFS TBox (recall the definition of definite TBoxes in Section 2.1). We use
Udef to denote the class of definite mappings. Then, as our first result, we obtained that
the chase can be used to compute universal solutions for definite mappings and DL-
LiteRDFS TBoxes. In what follows, let chaseT ,Σ (A) denote the projection of chaseT (A)
on the signature Σ.
Proposition 2. Let M = (Σ1 , Σ2 , T12 ) be a definite mapping and K1 = hT1 , A1 i a
DL-LiteRDFS KB over Σ1 . Then h∅, chaseT12 ,Σ2 (chaseT1 (A1 ))i is a universal solution
for K1 under M.
Thus, given that for definite mappings and DL-LiteRDFS TBoxes, the sets chaseT1 (A1 )
and chaseT12 ,Σ2 (chaseT1 (A1 )) are always finite and can be computed in polynomial
time [4], we obtain as a corollary of Propositions 1 and 2 that the problems of computing
solutions defined above can be solved in polynomial time for definite mappings and DL-
LiteRDFS TBoxes.
Corollary 1. C OMP S OL(Udef , DL-LiteRDFS ), C OMP U NIV S OL(Udef , DL-LiteRDFS ),
C OMP CQS OL(Udef , DL-LiteRDFS ), and C OMP U NIV CQS OL(Udef , DL-LiteRDFS ) can all
be solved in polynomial time.
Unfortunately, the solutions obtained by using Proposition 2 are of little interest to us
because the generated target ABoxes can be very large. Hence, we turn our attention to
the case of non-empty target TBoxes and, more specifically, to the problem of comput-
ing universal CQ-solutions that include as much implicit knowledge as possible. This
gives rise to the following separation properties.
Definition 4. Let M = (Σ1 , Σ2 , T12 ) be a mapping and T1 a TBox over Σ1 .
– T1 is representable in M if there exists a TBox T2 over Σ2 such that for every
ABox A1 over Σ1 , it holds that hT2 , chaseT12 ,Σ2 (A1 )i is a universal CQ-solution
for hT1 , A1 i under M. T2 is called a representation of T1 in M.
Knowledge Base Exchange 7
– T1 is weakly representable in M if there exists a mapping M? = (Σ1 , Σ2 , T12
?
)
? ? ?
such that T12 ⊆ T12 , T1 ∪ T12 |= T12 and T1 is representable in M .
The separation problems are interesting to us because a positive answer would mean
that we can construct the TBox of a solution by considering only the input TBox and
the mapping, independently of the input ABox. On the other hand, the ABox of the
solution can be found simply by translating the input ABox according to the rules in the
mapping (and the input TBox). We illustrate the notions just defined in the following
example.
Example 2. Let Σ1 = {A1 , B1 }, Σ2 = {A2 , B2 }, and T1 = {B1 v A1 }. If M =
(Σ1 , Σ2 , T12 ) with T12 = {A1 v A2 , B1 v B2 }, then we have that T2 = {B2 v A2 }
is a representation of T1 in M.
On the other hand, if M0 = (Σ1 , Σ2 , T12 0 0
) with T12 = {A1 v A2 }, then we have
that T1 is not representable in M : let A1 = {B1 (a)}, then chaseT120 ,Σ2 (A01 ) = ∅ and
0 0
for no TBox T20 , hT20 , chaseT120 ,Σ2 (A01 )i is a universal CQ-solution to hT1 , A01 i under
M0 . However, if we consider T12 ?
= T120
∪ {B1 v A2 }, we conclude that T1 is weakly
0 0 ? 0 ?
representable in M since T12 ⊆ T12 , T1 ∪ T12 |= T12 and T1 is representable in
0
M = (Σ1 , Σ2 , T12 ) (in fact, ∅ is a representation of T1 in M? ). Note, that T12
? ?
⊂ T12 .
00 00 00
Now, if M = (Σ1 , Σ2 , T12 ) with T12 = {A1 v A2 , B1 v B2 , C1 v B2 },
then again we have that T1 is not representable in M00 : let A001 = {B1 (a), C1 (c)},
then chaseT1200 ,Σ2 (A001 ) = {B2 (a), B2 (c)}. The query q() ← A2 (a) evaluates to true
00
in hT1 ∪ T12 , A001 i, hence in order for a TBox T200 to be a representation of T1 in M00 ,
it must contain the inclusion B2 v A2 . On the other hand, it implies that the query
q 0 () ← A2 (c) evaluates to true in hT200 , chaseT1200 ,Σ2 (A001 )i, whereas it evaluates to false
00
in hT1 ∪T12 , A001 i. However, again if we consider T12 ?? 00
= T12 ∪{B1 v A2 }, we conclude
00
that T1 is weakly representable in M .
4 Techniques for Deciding Representability
We address now the problem of deciding (weak) representability of a TBox in a map-
ping, for the case where TBoxes are expressed in DL-LiteRDFS and mappings are definite.
We start by showing some properties that characterize solutions in terms of chases.
In the following for two chases C1 and C2 , a homomorphism from C1 to C2 is a
mapping h from the individuals and labeled nulls in C1 to those in C2 such that (1) h is
the identity on the individuals, (2) if A(t) ∈ C1 then A(h(t)) ∈ C2 , and (3) if P (t, t0 ) ∈
C1 then P (h(t), h(t0 )) ∈ C2 . We write C1 → C2 if there is a homomorphism from C1 to
C2 , and C1 C2 if C1 → C2 and C2 → C1 .
From now on, we assume Σ1 and Σ2 as given, and for a mapping M = (Σ1 , Σ2 , T12 ),
we use simply M to denote also T12 . Then we have the following characterizations of
solutions in terms of chases, which are similar to the characterizations in [1].
Proposition 3. Let M be a definite mapping, K1 = hT1 , A1 i a DL-LiteRDFS KB over
Σ1 , and K2 = hT2 , A2 i a DL-LiteRDFS KB over Σ2 . If chaseM,Σ2 (chaseT1 (A1 )) →
chaseT2 (A2 ), then K2 is a CQ-solution for K1 under M.
8 Marcelo Arenas, Elena Botoeva, and Diego Calvanese
Corollary 2. Let M be a definite mapping, K1 = hT1 , A1 i a DL-LiteRDFS KB over Σ1 ,
and K2 = hT2 , A2 i a DL-LiteRDFS KB over Σ2 . Then K2 is a universal CQ-solution for
K1 under M if chaseM,Σ2 (chaseT1 (A1 )) chaseT2 (A2 ).
4.1 Checking Representability of a TBox in a Mapping
We address now the representability problem, which is to decide, given a TBox T1 over
Σ1 and a mapping M, whether T1 is representable in M (cf. Definition 4).
We start by considering the decision problem associated with representability:
Given a mapping M, a TBox T1 over Σ1 , and a TBox T2 over Σ2 , check whether T2
is a representation of T1 in M, i.e., for each ABox A1 over Σ1 , hT2 , chaseM,Σ2 (A1 )i
is a universal CQ-solution for hT1 , A1 i under M.
For definite mappings and DL-LiteRDFS TBoxes, the decision problem associated with
representability can be solved in two steps:
1. Check whether for each ABox A1 over Σ1 , hT2 , chaseM,Σ2 (A1 )i is a CQ-solution
for hT1 , A1 i under M.
2. Check whether for each ABox A1 over Σ1 and for each CQ q over Σ2 , we have
that cert(q, hT2 , chaseM,Σ2 (A1 )i) ⊆ cert(q, hT1 ∪ M, A1 i).
If both checks succeed, then T2 is a representation of T1 in M, otherwise it is not. We
develop now techniques to perform these two tests.
Step 1: Checking whether for each ABox A1 over Σ1 , hT2 , chaseM,Σ2 (A1 )i is a CQ-
solution for hT1 , A1 i under M.
We introduce now some notions that help us to characterize when a mapping is able to
“translate” the inclusions in T1 to the target TBox.
We use pn(X) to denote A if X is A, and P if X is ∃P , ∃P − , P , or P − . For X,
Y DL-LiteRDFS expressions, we say that X is compatible with Y if (i) pn(X) = pn(Y ),
and (ii) if X is ∃R, then Y is ∃R, R, or R− . For a DL-LiteRDFS inclusion α = X1 v X2 ,
we use lhs(α) to denote X1 , and rhs(α) to denote X2 . We say that α is left-compatible
(resp., right-compatible) with X, if X is compatible with lhs(α) (resp., rhs(α)).
Let M be a definite mapping, α = N1 v M1 a DL-LiteRDFS inclusion over Σ1 ,
and µ ∈ M left-compatible with M1 . Then the translation set of α and µ in M,
denoted M(α, µ, M), is the set of DL-LiteRDFS inclusions over Σ2 such that, if there
Table 1. Definition of M(α, µ, M). Ai , Ei are atomic concepts, Ri , Si are basic roles.
α µ ν β
A1 v E1 E1 v E2 A1 v A2 A2 v E2
∃R1 v E1 E1 v E2 ∃R1 v A2 A2 v E2
R1 v R2 ∃R2 v E2
R1 v S1 S1 v S2 R1 v R2 R2 v S2
∃S1 v E2 ∃R1 v A2 A2 v E2
R1 v R2 ∃R2 v E2
∃S1 − v E2 ∃R1 − v A2 A2 v E2
R1 v R2 ∃R2 − v E2
Knowledge Base Exchange 9
exists an inclusion ν in M left-compatible with N1 , then β ∈ M(α, µ, M), where β is
uniquely defined by α, µ, ν as shown in Table 1. When the mapping M is clear from
the context, we write M(α, µ). We say that α is redundant w.r.t. µ = M10 v M2 (in M)
if M2 v M2 ∈ M(α, µ). We explain these definitions in an example.
Example 3. Let α = S1 v R1 and µ = ∃R1 v A2 .
∃R1 µ A2
∃R1− R1
β0
ν 00 β
α
∃S1 E2
ν0
∃S1− S1
ν S2 ∃S2
∃S2−
Let ν = S1 v S2 and ν 0 = ∃S1 v E2 be in M. Then {∃S2 v A2 , E2 v A2 } ⊆
M(α, µ, M). If ν 00 = ∃S1 v A2 ∈ M, then α is redundant w.r.t. µ.
If none of ν, ν 0 and ν 00 is in M, then M(α, µ, M) is empty.
With these notions in place, we can characterize CQ-solutions in the context of the
representability problem.
Proposition 4. Let M be a definite mapping, T1 a DL-LiteRDFS TBox over Σ1 , and T2 a
DL-LiteRDFS TBox over Σ2 . Then for each ABox A1 , the KB hT2 , chaseM,Σ2 (A1 )i is a
CQ-solution for hT1 , A1 i under M if and only if for each inclusion α, s.t. T1 |= α, and
for each inclusion µ ∈ M left-compatible with rhs(α), there exists β ∈ M(α, µ) such
that T2 |= β.
Step 2: Checking whether for each ABox A1 over Σ1 , and for each CQ q over Σ2 , we
have that cert(q, hT2 , chaseM,Σ2 (A1 )i) ⊆ cert(q, hT1 ∪ M, A1 i).
Recall the definition of the translation set. Now, let β = N2 v M2 be a DL-LiteRDFS
inclusion over Σ2 , and ν ∈ M right-compatible with N2 . Then the reverse-translation
set of β and ν in M, denoted M− (β, ν, M), is the set of DL-LiteRDFS inclusions over
Σ1 such that, if there exists an inclusion µ in M right-compatible with M2 , then α ∈
M− (β, ν, M), where α is uniquely defined by β, ν, and µ as shown in Table 1.
Proposition 5. Let M be a definite mapping, T1 a DL-LiteRDFS TBox over Σ1 , and T2
a DL-LiteRDFS TBox over Σ2 . Then for each ABox A1 over Σ1 and for each CQ q over
Σ2 , cert(q, hT2 , chaseM,Σ2 (A1 )i) ⊆ cert(q, hT1 ∪ M, A1 i) if and only if for each
inclusion β, s.t. T2 |= β, and for each inclusion ν ∈ M right-compatible with lhs(β),
there exists α ∈ M− (β, ν), s.t. T1 |= α.
With the techniques for Steps 1 and 2 at hand, we are ready to characterize repre-
sentations.
10 Marcelo Arenas, Elena Botoeva, and Diego Calvanese
Corollary 3. Let M be a definite mapping, T1 a DL-LiteRDFS TBox over Σ1 , and T2 a
DL-LiteRDFS TBox over Σ2 . Then for each ABox A1 over Σ1 , hT2 , chaseM,Σ2 (A1 )i is a
universal CQ-solution for hT1 , A1 i under M iff
– for each inclusion α, s.t. T1 |= α, and for each inclusion µ ∈ M left-compatible
with rhs(α), there exists β ∈ M(α, µ) s.t. T2 |= β, and
– for each inclusion β, s.t. T2 |= β, and for each inclusion ν ∈ M right-compatible
with lhs(β), there exists α ∈ M− (β, ν), s.t. T1 |= α.
Now, we can check whether a given T1 is representable in a given M.
Theorem 1. Let M be a definite mapping and T1 a DL-LiteRDFS TBox over Σ1 . Then
we can check whether T1 is representable in M in polynomial time.
4.2 Checking Weak Representability
We can easily solve the weak representability problem for DL-LiteRDFS KBs even if the
mappings are arbitrary tgds, i.e., assertions of the form q1 → q2 , mapping a CQ q1 over
Σ1 to a CQ q2 over Σ2 of the same arity as q1 . We call such a mapping a tgd-mapping.
Let T1 be a DL-LiteRDFS TBox and M a tgd-mapping. We can enrich M by compiling
knowledge from T1 into it:
– Let q1 → q2 be a tgd in M, with q1 a CQ over Σ1 and q2 a CQ over Σ2 . Let the
UCQ Q1 = {q11 , . . . , q1k } be the perfect reformulation of q1 w.r.t. T1 (see, e.g., [4]).
Then we extend M with a tgd q1i → q2 for each q1i ∈ Q1 .
– We perform this for each tgd in M. The resulting mapping is denoted with M∗ .
Proposition 6. Let M be a tgd-mapping, T1 a DL-LiteRDFS TBox over Σ1 , and M∗
the mapping constructed as described above. Then for each ABox A1 over Σ1 , the KB
h∅, chaseM∗ ,Σ2 (A1 )i is a universal CQ-solution for hT1 , A1 i under M.
From this we immediately get:
Theorem 2. Let M be a definite mapping and T1 a DL-LiteRDFS TBox over Σ1 . Then T1
is weakly representable in M.
Thus, when the source KB is expressed in DL-LiteRDFS it is always possible to sepa-
rate data by enriching mappings, even if mappings are tgds. When M is a set of tgds,
the size of M∗ might be exponential in the size of M. If M is a DL-LiteRDFS mapping,
the size of M∗ is always polynomial in the size of M.
5 Conclusions
We have specialized the framework for KB exchange proposed in [1] to the case of
DLs, i.e., the source and target KBs are given as DL KBs and the mappings have the
form of DL TBox assertions. Moreover, we have defined a new reasoning problem: rep-
resentability of a TBox in a mapping, whose goal is to compute from a source TBox
and a mapping, a target TBox that leads to a universal (CQ-)solution when it is com-
bined with a suitable ABox computed from the source ABox, independently of the
Knowledge Base Exchange 11
actual source ABox. A variation of this problem, called weak representability, allows
for modification of the mapping, so that the source TBox becomes representable.
Then, we have developed first results and techniques for KB exchange and for the
representability problem in the case of mappings and KBs expressed in DL-LiteRDFS
(such mappings are called definite). DL-LiteRDFS is a fragment of DL-LiteR that does
not allow for existential quantification (i.e., concepts of the form ∃R) in the right-hand
side of concept inclusions, nor for disjointness assertions. It implies, first, that the chase
is always finite in DL-LiteRDFS , and, second, that KBs are always consistent. We have
shown the following results for definite mappings and DL-LiteRDFS KBs: (i) the prob-
lems of computing (universal) (CQ-)solutions can be solved in polynomial time; (ii) the
problem of representability of a TBox in a mapping is decidable in polynomial time;
(iii) every DL-LiteRDFS TBox is weakly representable in a definite mapping.
The main direction for future work is to extend the results to the case of full DL-
LiteR . This brings up the problem of labelled nulls in the chase, which becomes infinite
in general. Moreover, due to the possible presence of disjointness assertions in TBoxes,
consistency of the source and target KBs has to be checked.
Acknowledgments
The authors are grateful to Vladislav Ryzhikov and Evgeny Sherkhonov for helpful
discussions, and to the anonymous referees for many helpful comments. The authors
were supported by Marie Curie action “International Research Staff Exchange Scheme
(IRSES)”, FP7-PEOPLE-2009-IRSES, under grant number 24761. M. Arenas was also
supported by Fondecyt grant 1090565. E. Botoeva and D. Calvanese were also sup-
ported by the EU under the ICT Collaborative Project ACSI (Artifact-Centric Service
Interoperation), grant agreement number FP7-257593, and under the large-scale inte-
grating project (IP) OntoRule (ONTOlogies meet Business RULEs), grant agreement
number FP7-231875.
References
1. M. Arenas, J. Pérez, and J. L. Reutter. Data exchange beyond complete data. In Proc.
of the 30th ACM SIGACT SIGMOD SIGART Symp. on Principles of Database Systems
(PODS 2011), pages 83–94, 2011.
2. B. Barcelò. Logical foundations of relational data exchange. SIGMOD Record, 38(1):49–58,
2009.
3. D. Brickley and R. V. Guha. RDF vocabulary description language 1.0: RDF Schema. W3C
Recommendation, World Wide Web Consortium, Feb. 2004. Available at http://www.
w3.org/TR/rdf-schema/.
4. D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, and R. Rosati. Tractable reasoning
and efficient query answering in description logics: The DL-Lite family. J. of Automated
Reasoning, 39(3):385–429, 2007.
5. R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data exchange: Semantics and query
answering. Theoretical Computer Science, 336(1):89–124, 2005.
6. L. Libkin and C. Sirangelo. Data exchange and schema mappings in open and closed worlds.
J. of Computer and System Sciences, 77(3):542–571, 2011.