We study the problem of instance level (ABox) updates for Knowledge Bases (KBs) represented in Description Logics of the DL-Lite family. DLLite is at the basis of OWL 2 QL, one of the tractable fragments of OWL 2, the recently proposed revision of the Web Ontology Language. We examine known works on updates that follow the model-based approach and discuss their drawbacks. Specifically, the fact that model-based approaches intrinsically ignore the structural properties of KBs, leads to undesired properties of updates computed according to such semantics. Hence, we propose two novel formula-based approaches, and for each of them we develop a polynomial time algorithm to compute ABox updates for the Description Logic DL-LiteFR.
Ontology languages, and hence Description Logics (DLs), provide excellent
mechanisms for representing structured knowledge, and as such they have traditionally been
used for modeling at the conceptual level the static and structural aspects of
application domains [
putational properties, in particular when complexity is measured wrt the size of the data
stored in the ABox of a DL ontology [
The reasoning services that have been investigated for the currently used DLs and
implemented in state-of-the-art DL reasoners [
Supporting all these activities, makes it necessary to equip DL systems with additional
kinds of inference tasks that go beyond the traditional ones, most notably that of
ontology update operations [
interaction, e.g., by deleting parts of the ontology that conflict with the update.
Different choices are possible in general, corresponding to different update semantics, which
in turn give rise to different update results [
instance level) update [
formula-based [
eral, we argue that the fact that model-based approaches to update ignore structural properties of KBs may make them inappropriate for ABox updates. As a consequence, we explore formula-based approaches to update and propose two novel semantics for
the properties of DL-Lite guarantee that there is a unique maximal set of assertions that are entailed by the original ABox (and TBox) and that do not conflict with the update.
to compute updates for DL-LiteFR KBs. 2
Description Logics (DLs) [
on a family of DLs called DL-Lite [
write just DL-Lite we mean any language of this family. DL-LiteFR has the following constructs: (i) B ::= A j 9R, (ii) C ::= B j :B, (iii) R ::= P j P , where A denotes an atomic concept, B a basic concept, C a general concept, P an atomic role, and R a basic role. In the following, R denotes P when R = P , and P when R = P .
A DL-LiteFR ABox A is a set of membership assertions of the form: B(a) and
P (a; b), where a and b are constants. The active domain of A, denoted adom(A), is the
set of all constants occurring in A. A DL-LiteFR TBox T may include (i) concept
inclusion assertions B v C, (ii) role functionality assertions (funct R), and (iii) role
inclusion assertions R1 v R2. The use of assertions (ii) and (iii) together leads in general to
a high complexity of reasoning [
terpretations over a fixed countably infinite set . An interpretation I is a function
in such a way that (:B)I = n BI , (9R)I = fa j 9a0:(a; a0) 2 RI g, and (P )I = f(a2; a1) j (a1; a2) 2 P I g. Moreover, I assigns to each constant a an elements of aI 2 , and a1I 6= a2I whenever a1 6= a2, i.e., we adopt the unique name assumption. W.l.o.g., we consider each constant a to be interpreted as itself, i.e., aI = a, i.e., we adopt standard names. We also consider interpretations as sets of atoms, that is,
of (funct R) if R is a function over , i.e., for all o; o1; o2 2 we have that f(o; o1); (o; o2)g RI implies o1 = o2. Also, I is a model of a membership assertion B(a) if a 2 BI , and of P (a; b) if (a; b) 2 P I . For an assertion F , the fact that I is a model of F is denoted by I j= F . As usual, I j= K if I j= F for every F of K, and Mod(T ; A) denotes the set of all such models. A KB is satisfiable if Mod(T ; A) 6= ;. We write K j= F if all models of K are also models of F . Similarly for a set F of assertions. We say that an ABox A T -entails an ABox A0, denoted A j=T A0 if (T ; A) j= A0.
3
Let K = (T ; A) be a KB and U a set of (TBox and/or ABox) assertions, called an update. What we want to study is how to “incorporate” the assertions U into K, that is, to perform an update of K. In this paper we consider only updates at the ABox level (ABox updates), that is, when U consists of ABox assertions only.
ital status of people. Suppose that several married couples got divorced, and the update
tions in A. For example, if T says that nobody can be married to a person who is single,
one should resolve the conflicts between the old information in K and the new data in
U . This could be done in two ways: by modification of T or of A. In our example, we
can either relax constraints in T , so that even singles keep their spouses (that is, we
restructure the ontology, not to mention it is counterintuitive in our example), or delete
from A the information about former spouses of people who are currently single (that
is, we update the registry office’s database). It seems unintuitive to restructure the
ontology whenever new conflicting data arrives. Indeed, in most cases, to resolve conflicts
that arise due to changes at the instance level, it is probably more appropriate to change
the instance level rather than the intensional level. In other words, we assume that the
updated KB K0 should be of the form K0 = (T ; A0) and computing an ABox update
results in a new ABox A0 that together with the original TBox T expresses the result of
the update operation. This assumption is also made in [
When dealing with updates, both in the knowledge management and the AI
communities, it is generally accepted that the updated KB K0 should comply with the principle
of minimality of change [
ture [
tics, discuss whether it is suitable for our needs, and reconsider the result produced by ComputeUpdate.
For a model I of K = (T ; A), an update with U results in a set of models of U and T .
and then (ii) take the set of models that is the union of the sets of resulting models.
The updated interpretation I with U wrt T , denoted w-updT (I; U ), where w indicates Winslett’s semantics, is the set of interpretations defined as follows: fI0 j I0 2 Mod(T ; U ) and there is no I00 2 Mod(T ; U ) s.t. I I00 ( I
J1: J2: fM g
j
fM g
hs
p
p
j
fN g
hs
r
r
m
fN g
m
fS g
where containment I I0 and strict containment I ( I0 between interpretations are
defined as usual (cf. [
w-upd(T ; A; U ) = SI2Mod(T ;A) w-updT (I; U ):
els is in general not possible. What we want is to return a KB that describes exactly this set of models. We say that a KB (T ; A0) represents the update w-upd(T ; A; U ) if Mod(T ; A0) = w-upd(T ; A; U ).
person is a person who has a spouse, and every person who is a spouse is neither a single person, nor a nun. Moreover, John is married to Mary , and Patty and Rachel are nuns. It can be expressed as a DL-LiteFR KB K = (T ; A): T : M v 9hs, 9hs v M , 9hs v :S , 9hs v :N , M v :S ; A: M (j ), hs(j ; m), N (p), N (r ); where the concept M stands for married , S for single, and N for nun, the role hs for hasspouse, the constant j for John, m for Mary , p for Patty , and r for Rachel . In the following we always use this convention for acronyms to save space.
fS (m)g. We will show that for K and U , the resulting update under Winslett’s semantics (seen as a set of interpretations) satisfies the disjunction N (p) _ N (r ), but not N (p) ^
any of the single atoms. But this is impossible for a DL-Lite KB, because each such
because DL-Lite KBs can be expressed by a slightly extended Horn logic (see [
More precisely, each model J of the updated KB is of one of the three following kinds: (i) John is single, hence j 2= M J , and both Patty and Rachel are nuns, since they were nuns in every model of the original KB and, due to the principle of minimality of change, they have to remain nuns. In other words, J j= N (p) ^ N (r ). (ii) John is a married person, and his wife is not Mary, but another woman, say Haley. In this case, both Patty and Rachel are still nuns, as in (i), that is, J j= N (p) ^ N (r ) again. (iii) John is married and his wife is either Patty, or Rachel. In this case, his new spouse cannot stay nun any longer, as it is in the models J1 and J2 in Figure 1, thus, J j= N (p)_N (r ) and also J1 6j= N (p) and J2 6j= N (r ) . Note that it is not the case that John is married to both Patty and Rachel, since such a model J 0 is not minimally different from any model of the original KB. Consequently, w-upd(T ; A; U ) j= N (p) _ N (r ), and w-upd(T ; A; U ) 6j= N (p), and w-upd(T ; A; U ) 6j= N (r ). tu
Theorem 2. DL-Lite is not closed wrt ABox updates under Winslett’s semantics.
To discuss the consequences of Example 1 and Theorem 2, we need the following notions. Given a DL KB K0 and two sets M, Ma of models of K0, we say that Ma is a complete (or sound) approximation of M if Ma M (resp., M Ma). Intuitively, completeness (resp., soundness) means that for every FOL formula ' such that M j= ' (resp., Ma j= '), we also have Ma j= ' (resp., M j= '). According to this notion, we say that an algorithm that computes updates is complete (or sound), if Mod(T ; A0) is a complete (resp., sound) approximation of w-upd(T ; A; U ), where A0 is the output 0 = U . Note that both Mod(T ; A0) and w-upd(T ; A; U ) are sets of the algorithm and A j of models of the KB (T ; U ).
outputs a DL-Lite ABox, cannot capture Winslett’s semantics exactly. As shown below,
“contradictive” membership assertions F such that U j=T :F . Using N , it constructs a set A0 as follows: (i) it initializes A0 to A [ U ; (ii) it deletes from A0 each assertion F in N , and for each such F , it inserts into A0 all assertions F 0 such that F j=T F 0 and F 0 2= N ; (iii) if R(a; b) has been deleted, then 9R(a) and 9R (b) are deleted as well.
according to Winslett’s semantics in every model of w-upd(T ; A; U ) either N (p) or
that ComputeUpdate is unsound.
Example 3. Consider the following DL-Lite KB K = (T ; A) and update U : T :
M v :S ;
D v S ;
A : fM g m
U
J 00: fS g m where D stands for delighted person. The call ComputeUpdate(T ; A; U ) returns the new ABox A0 = fS (m)g.
We will show that there is a model J 0 of (T ; A0) such that J 0 2= w-upd(T ; A; U ).
is stated by the original ABox, so m 2= S I and m 2= D I because of T . Additionally, we cmanwcoounlcdlubdeeinthCatJm0 a2=ccCoIrdfionrgetvoetrhyecpornicnecpipt lCe ,odfimffeinreimntaflritoymoMfc,hSan,gaen.dCDon,soitdheerrwn oiswe the interpretation J 00 := J 0 n fD (m)g, which is obtained from J 0 by dropping m from D . Then we have that I J 00 = fM (m); S (m)g ( fM (m); S (m); D (m)g = I J 0.
puting either sound or complete approximations of ABox updates for DL-Lite wrt
To sum-up on Winsletts’s semantics, we conclude that the semantics cannot be expressed by DL-Lite KBs and hence is inconvenient to adopt in the context of DL-Lite. In principle, since all model-based approaches focus on the models of a KB and not on the actual structure of the KB, they suffer from flexibility when dropping the assertions as far as some notion of minimality of change between models is kept (in Example 1, the assertion N (p) was dropped from J1). These approaches are agnostic to the structural properties of KBs, which may lead to undesired results. 5
5.1
Naive Semantics for Updates
Lemma 4. Let (T ; A) be a DL-Lite KB. If (T ; A) is unsatisfiable, then there is a subset A0 A with at most two elements, such that (T ; A0) is unsatisfiable.
TBox T , and ABoxes A, N each satisfiable with T
finite set of membership assertions Aw
INPUT:
OUTPUT:
[
Fig. 3. Algorithm Weeding(T ; A; N ) for DL-LiteFR
wrt a TBox T , denoted clT (A), which is the set of all membership assertions F over the constants in adom(A) such that (T ; A) j= F . Then, Lemma 4 implies the following result.
Theorem 5. Let T be a DL-Lite TBox, A an ABox, and U an update, and suppose that both (T ; A) and (T ; U ) are satisfiable. Then, the set fA0
clT (A) j A0 is T -compatible with U g has a unique maximal element wrt set inclusion.
Thus, for every ABox A and every update U , we can find a maximal set Anm of assertions (where m stands for maximal and n for naive) in clT (A), such that Anm is
n n-upd(T ; A; U ) := Am [ U :
exploits the algorithm Weeding (see Figure 3), which takes as inputs a TBox T , an
from A (Lines [
INPUT: TBox T , and ABoxes A, U each satisfiable with T
OUTPUT: finite set of membership assertions Au
[
Fig. 4. Algorithm NaiveUpdate(A; U ; T ) for DL-LiteFR
and stores them in CA: it first detects conflicts of the form B(c) and :B(c) (Lines [
Theorem 6. Let (T ; A) be a satisfiable DL-LiteFR KB and U an update such that (T ; U ) is satisfiable. Then NaiveUpdate(T ; A; U ) runs in polynomial time in the size of T [ A [ U , and NaiveUpdate(T ; A; U ) = n-upd(T ; A; U ). 5.2
Careful Semantics for Updates
T : 9hs v :S , 9hs v M , M v 9hs; A: M (j ), hs(j ; m).
model I of K (see Figure 5) that precisely reflects what is in the ABox of the KB, and let us update I. Since Mary is single now, the state of John is changed and he has not spouse Mary anymore. We do not have any explicit information about the situation with John, hence, we can make two assumptions. We can assume that John now is single too. We can also assume that John still has a spouse, some other woman, say
date) captures only the model J2, while we might be interested in a semantics that captures both possibilities. tu
pected information, that is, information coming neither from the original KB, nor from the update, may be counterintuitive. In our example, the unexpected information is 9x(hs(j ; x) ^ (x 6= m)), saying that John has a spouse different from Mary . This J1: fM g j m fS g
J2: j
hs fM g h m fS g information has a specific form: it restricts the possible values in the second component of the role hs. Our next semantics prohibits these role restrictions from being unexpectedly entailed from the updated KB.
We say that a formula is role-constraining if it is of the form 9x(R(a; x) ^ (x 6= c1) ^ ^ (x 6= cn)), where a and all cis are constants. Let T be a TBox, A an ABox, and U an update. A subset A1 A is careful if for every role-constraining formula ', if A1 [ U j=T ' holds, then either A j=T ' or U j=T ' holds.
Theorem 8. Let T be a DL-Lite TBox, A an ABox, and U an update, and suppose that both (T ; A) and (T ; U ) are satisfiable. Then, the set fA0
clT (A) j A0 is careful and A0 [ U is satisfiableg has a unique maximal element wrt set inclusion.
set Acm of assertions (where c stands for careful), whose uniqueness is guaranteed by
c c-upd(T ; A; U ) := Am [ U :
We exhibit now the algorithm CarefulUpdate, which computes c-upd(T ; A; U ). The
prechase of an ABox A wrt a TBox T , denoted PrechaseT (A), is a subset of clT (A)
obtained as follows: one removes from clT (A) all the assertions of the form 9R(a),
whenever there is an assertion of the form R(a; c) in clT (A), for some constant c. The
prechase is needed to detect unexpected role-restricting formulas. The algorithm
CarefulUpdate (see Figure 6) takes as input an ABox A, an update U , and a TBox T . It
first computes the update operation wrt Naive Semantics (Line [
edness (Lines [
INPUT: TBox T , and ABoxes A, U each satisfiable with T
OUTPUT: finite set of membership assertions Au
[
Fig. 6. Algorithm CarefulUpdate(A; U ; T ) for DL-LiteFR 5.3
Comparison of Semantics
difference is in how the semantics “preserve” entailment of formulas. For disambiguation we denote an updated ABox A0 computed under Naive Semantics as A0n and under
Proposition 10. Let (T ; A) be a DL-LiteFR KB and U an update. If U j=T ', then A0n j=T ' and A0c j=T ', for any FOL formula '. If U 6j=T ' and U 6j=T :', then (i) if A j=T ', then A0n j=T ', when ' is an ABox assertion, and (ii) if A 6j=T ', then A0c 6j=T ', when ' is an ABox assertion or role-constraining.
w-upd(T ; A; U ), but in general neither Mod(T ; Ac) w-upd(T ; A; U ), nor w-upd(T ; A; U ) Mod(T ; Ac) holds.
Updating KBs Without Projections. We say that a DL-LiteFR KB is projection-free
if no concept inclusion and no concept membership assertion contains an occurrence of
a role symbol, that is, domains and ranges of roles do not appear in the KB (though role
inclusions may appear). The following theorem shows that for such KBs all semantics
we have considered coincide and the ComputeUpdate algorithm of [
are two main families of approaches to updates: model and formula-based. We examined the former family and concluded that these approaches are not fully appropriate for ABox updates, since the updates are in general not expressible in DL-Lite. Thus, we examined formula-based approaches and proposed two novel semantics for ABox updates, called Naive Semantics and Careful Semantics, which are closed for DL-Lite.
Acknowledgements