=Paper=
{{Paper
|id=None
|storemode=property
|title=Updating ABoxes in DL-Lite
|pdfUrl=https://ceur-ws.org/Vol-619/paper3.pdf
|volume=Vol-619
|dblpUrl=https://dblp.org/rec/conf/amw/CalvaneseKNZ10
}}
==Updating ABoxes in DL-Lite==
https://ceur-ws.org/Vol-619/paper3.pdf
Updating ABoxes in DL-Lite
Diego Calvanese, Evgeny Kharlamov ? , Werner Nutt, and Dmitriy Zheleznyakov
KRDB Research Centre, Free University of Bozen-Bolzano, Italy
calvanese,kharlamov,nutt,zheleznyakov@inf.unibz.it
Abstract. We study the problem of instance level (ABox) updates for Knowl-
edge Bases (KBs) represented in Description Logics of the DL-Lite family. DL-
Lite 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 draw-
backs. 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 ap-
proaches, and for each of them we develop a polynomial time algorithm to com-
pute ABox updates for the Description Logic DL-LiteF R .
1 Introduction
Ontology languages, and hence Description Logics (DLs), provide excellent mecha-
nisms for representing structured knowledge, and as such they have traditionally been
used for modeling at the conceptual level the static and structural aspects of applica-
tion domains [1]. In general, a DL ontology is structured in two parts, a TBox (where
‘T’ stands for terminological) containing general assertions about the domain (i.e., the
intensional knowledge, or schema, or constraints), and an ABox (where ‘A’ stands for
assertional) containing assertions about individual objects (i.e., the extensional knowl-
edge, or data). A family of DLs that has received great attention recently, due to its tight
connection with conceptual data models, such as the Entity-Relationship model and
UML class diagrams, is the DL-Lite family [2]. This family of DLs exhibits nice com-
putational properties, in particular when complexity is measured wrt the size of the data
stored in the ABox of a DL ontology [2, 3]. It is also at the basis of the tractable profiles
of OWL 2, the forthcoming edition of the W3C standard Web Ontology Language.
The reasoning services that have been investigated for the currently used DLs and
implemented in state-of-the-art DL reasoners [4], traditionally focus on so-called stan-
dard reasoning, both at the TBox level (e.g., TBox satisfiability, concept satisfiability
and subsumption wrt a TBox) and at the ABox level (e.g., knowledge base satisfiability,
instance checking and retrieval, and more recently query answering) [5, 6]. Recently,
however, the scope of ontologies has broadened, and they are now considered to be not
only at the basis of the design and development of information systems, but also for
providing support in the maintenance and evolution phase of such systems. Moreover,
ontologies are considered to be the premium mechanism through which services oper-
ating in a Web context can be accessed, both by human users and by other services.
?
The author is co-affiliated with INRIA Saclay, Île-de-France, Orsay.
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 on-
tology update operations [7, 8]. An update reflects the need of changing an ontology so
as to take into account changes that occur in the domain of interest represented by the
ontology. In general, such an update is represented by a set of formulas denoting those
properties that should be true after the change. In the case where the update causes an
undesirable interaction with the knowledge encoded in the ontology, e.g., by causing the
ontology to become unsatisfiable, the update cannot simply be added to the ontology.
Instead, suitable changes need to be made in the ontology so as to avoid the undesirable
interaction, e.g., by deleting parts of the ontology that conflict with the update. Differ-
ent choices are possible in general, corresponding to different update semantics, which
in turn give rise to different update results [9]. Moreover, it is necessary to understand
whether the desired update result can be represented at all as a KB in the DL at hand.
Previous work on updates in the context of DL ontologies has addressed ABox (or
instance level) update [7, 8, 10], where the update consists of a set of ABox assertions.
In [7] the problem is studied for DLs of the DL-Lite family, while [8] considers the case
of expressive DLs. Both works show that it might be necessary to extend the ontol-
ogy language with additional features/constructs in order to guarantee that the updated
ontology can be represented.
In this paper we also study ABox updates, specifically, for the case of DLs of the
DL-Lite family. There are two main families of approaches to updates: model and
formula-based [11]. In [7], Winslett’s semantics, which belongs to the former fam-
ily is adopted. We reconsider this semantics and show that ABox updates of DL-Lite
KBs cannot be expressed as a DL-Lite KB, in contrast to what claimed in [7]. In gen-
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
ABox updates, called Naive Semantics and Careful Semantics. Under both semantics,
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.
The Careful Semantics also allows us to capture models that are ruled out by the Naive
Semantics but are natural. For both semantics, we develop polynomial time algorithms
to compute updates for DL-LiteF R KBs.
2 Preliminaries
Description Logics (DLs) [12] are knowledge representation formalisms, tailored for
representing the domain of interest in terms of concepts and roles. In DLs, complex con-
cept and role expressions (or simply, concepts and roles), denoting respectively unary
and binary relation, are obtained starting from atomic concepts and roles by applying
suitable constructs. Concepts and roles are then used in a DL knowledge base to model
the domain of interest. Specifically, a DL knowledge base (KB) K = (T , A) is formed
by two distinct parts, a TBox T representing the intensional-level of the KB and an
ABox A providing information on the instance-level of the KB. In this paper we focus
on a family of DLs called DL-Lite [2], that corresponds to the tractable OWL 2 QL
profile of the Web Ontology Language OWL 2.
The logic of the DL-Lite family on which we focus here is DL-LiteF R , and when we
write just DL-Lite we mean any language of this family. DL-LiteF R has the following
constructs: (i) B ::= A | ∃R, (ii) C ::= B | ¬B, (iii) R ::= P | 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-LiteF R 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-LiteF R TBox T may include (i) concept inclu-
sion assertions B v C, (ii) role functionality assertions (funct R), and (iii) role inclu-
sion assertions R1 v R2 . The use of assertions (ii) and (iii) together leads in general to
a high complexity of reasoning [13, 3]. It can be avoided by imposing the following re-
striction [2]: if R1 v R2 appears in T , then neither (funct R2 ) nor (funct R2− ) appears
in T . Hence, when talking about DL-LiteF R KBs, we assume this syntactic restriction
is satisfied. For DL-LiteF R , satisfiability of a KB can be checked in polynomial-time in
(the size of the) TBox and in logarithmic-space in the size of the ABox [14, 3].
The semantics of a DL is given in terms of FOL interpretations. We consider in-
terpretations over a fixed countably infinite set ∆. An interpretation I is a function
·I assigning concepts C to subsets C I ⊆ ∆, and roles R to binary relations RI over
∆ in such a way that (¬B)I = ∆ \ B I , (∃R)I = {a | ∃a0 .(a, a0 ) ∈ RI }, and
(P − )I = {(a2 , a1 ) | (a1 , a2 ) ∈ P I }. Moreover, I assigns to each constant a an el-
ements of aI ∈ ∆, and aI1 6= aI2 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,
A(a) ∈ I if and only if a ∈ AI and P (a, b) ∈ I if and only if (a, b) ∈ P I .
An interpretation I is a model of an assertion D1 v D2 if D1I ⊆ D2I , and
of (funct R) if R is a function over ∆, i.e., for all o, o1 , o2 ∈ ∆ we have that
{(o, o1 ), (o, o2 )} ⊆ RI implies o1 = o2 . Also, I is a model of a membership as-
sertion B(a) if a ∈ B I , and of P (a, b) if (a, b) ∈ P I . For an assertion F , the fact
that I is a model of F is denoted by I |= F . As usual, I |= K if I |= F for ev-
ery 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 |= F if all models of K are also models of F . Simi-
larly for a set F of assertions. We say that an ABox A T -entails an ABox A0 , denoted
A |=T A0 if (T , A) |= A0 .
The deductive closure of a TBox T , denoted cl(T ), is the set of all inclusion and
functionality assertions entailed by T (i.e., F ∈ cl(T ) iff T |= F ). It is easy to see that
in DL-Lite cl(T ) is of quadratic size and computable in quadratic time in the size of T .
3 Problem Definition
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.
Consider for example a registry office’s KB, which contains information about mar-
ital status of people. Suppose that several married couples got divorced, and the update
U is a list of these newly divorced people. The new data may conflict with some asser-
tions in A. For example, if T says that nobody can be married to a person who is single,
A says that John is married to Mary, and Mary should become single due to U, then
John can not be married to Mary anymore. Therefore, in order to take U on board,
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 on-
tology 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 [7].
When dealing with updates, both in the knowledge management and the AI commu-
nities, it is generally accepted that the updated KB K0 should comply with the principle
of minimality of change [9, 11], which states that the KB should change as little as
possible if new information is incorporated. There are different approaches to updates,
suitable for particular applications, and the current belief is there is no general notion
of minimality that will “do the right thing” under all circumstances [11]. A number of
candidate semantics for update operators have appeared in the literature [11, 15–17];
they can be classified into two groups: model-based and formula-based. In order to un-
derstand what semantics is more appropriate for ABox updates, we now review both
model and formula-based approaches.
4 Model-Based Approach to Semantics
A number of model-based semantics for updates have been proposed in the litera-
ture [11]. Poggi et al. [7] proposed to use for ABox updates Winslett’s semantics [17],
and presented an algorithm, ComputeUpdate, to compute the updates for DL-LiteF .
This work was extended to DL-LiteF R [10]. We now recall the model-based seman-
tics, discuss whether it is suitable for our needs, and reconsider the result produced by
ComputeUpdate.
Under the model-based paradigm, the objects of change are individual models of K.
For a model I of K = (T , A), an update with U results in a set of models of U and T .
In order to update the KB K with U, one has to (i) update every model I of K with U
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 indi-
cates Winslett’s semantics, is the set of interpretations defined as follows:
{I 0 | I 0 ∈ Mod(T , U) and there is no I 00 ∈ Mod(T , U) s.t. I I 00 ( I I 0 },
{M } {S }
j hs m
J1 :
hs {N }
{M } U p r
j m
I:
{N } {N }
{M } {S }
p r hs
j m
J2 :
{N }
p r
Fig. 1. Winslett’s semantics is not expressible in DL-Lite
where containment I ⊆ I 0 and strict containment I ( I 0 between interpretations are
defined as usual (cf. [7]), and denotes the symmetric difference between sets. Note
that the non-existence of I 00 in the definition guarantees the minimality of change. Then,
the update of a KB (T , A) with U is the set of interpretations
S
w-upd(T , A, U) = I∈Mod(T ,A) w-updT (I, U).
Returning to a user the result of an update as a (possibly infinite) set of mod-
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).
Unfortunately, updates according to Winslett’s semantics are inexpressible in DL-
LiteF R , as illustrated by the following example.
Example 1. Consider a KB that describes a registry office’s ontology where a married
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-LiteF R KB K = (T , A):
T: M v ∃hs, ∃hs v M , ∃hs − v ¬S , ∃hs − 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.
Assume that Mary has decided to divorce her husband John, so the update U is
{S (m)}. 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) ∧
N (r ). Hence, each KB representing the update should entail the disjunction, but not
any of the single atoms. But this is impossible for a DL-Lite KB, because each such
KB that entails a disjunction of two atoms, also entails one of the disjuncts. This holds
because DL-Lite KBs can be expressed by a slightly extended Horn logic (see [18]).
Hence, this update cannot be represented by a DL-Lite ABox.
More precisely, each model J of the updated KB is of one of the three following
/ M J , and both Patty and Rachel are nuns, since they
kinds: (i) John is single, hence j ∈
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 |= 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 |= 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 |=
N (p)∨N (r ) and also J1 6|= N (p) and J2 6|= 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) |= N (p) ∨ N (r ),
and w-upd(T , A, U) 6|= N (p), and w-upd(T , A, U) 6|= N (r ). t
u
From the example we conclude:
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 |= ϕ
(resp., Ma |= ϕ), we also have Ma |= ϕ (resp., M |= ϕ). 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
of the algorithm and A0 |= U. Note that both Mod(T , A0 ) and w-upd(T , A, U) are sets
of models of the KB (T , U).
A consequence of Theorem 2 is that the algorithm ComputeUpdate, which always
outputs a DL-Lite ABox, cannot capture Winslett’s semantics exactly. As shown below,
ComputeUpdate is neither sound, nor complete. First, we briefly remind the reader of
the algorithm.
The algorithm ComputeUpdate takes as input a TBox T , an ABox A, and an update
U, such that both (T , A) and (T , U) are satisfiable. Then, it computes first the set N of
“contradictive” membership assertions F such that U |=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 |=T F 0 and
F0 ∈/ N ; (iii) if R(a, b) has been deleted, then ∃R(a) and ∃R− (b) are deleted as well.
The algorithm outputs A0 .
To show that ComputeUpdate is unsound, consider the KB and the update from
Example 1, and compute the updated KB K0 using the algorithm. It is easy to see that
K0 has the ABox consisting of N (p), N (r ), M (j ), S (m) and the old TBox T , whereas,
according to Winslett’s semantics in every model of w-upd(T , A, U) either N (p) or
N (r ) does not hold. Hence, w-upd(T , A, U) 6⊆ Mod(N (p), N (r )), and we conclude
that ComputeUpdate is unsound.
The following example shows the incompleteness.
Example 3. Consider the following DL-Lite KB K = (T , A) and update U:
T : M v ¬S , D v S; A: M (m); U: S (m),
J 0: I: J 00 :
{S , D} ? {M } U {S }
m m m
Fig. 2. Incompleteness of ComputeUpdate algorithm wrt Winslett’s semantics
where D stands for delighted person. The call ComputeUpdate(T , A, U) returns the
new ABox A0 = {S (m)}.
We will show that there is a model J 0 of (T , A0 ) such that J 0 ∈
/ w-upd(T , A, U).
We define J 0 as sketched in Figure 2, that is, Mary is single and delighted . Clearly,
J 0 is a model of T and A0 .
Now, assume there is I ∈ Mod(T , A) such that I J 0 is minimal, that is, there is no
J ∈ Mod(T , U) such that I J 00 ( I J 0 . We first conclude that m ∈ M I , since it
00
is stated by the original ABox, so m ∈/ S I and m ∈ / D I because of T . Additionally, we
I
can conclude that m ∈ / C for every concept C, different from M , S , and D, otherwise
0
m would be in C J according to the principle of minimality of change. Consider now
the interpretation J 00 := J 0 \ {D(m)}, which is obtained from J 0 by dropping m from
D. Then we have that I J 00 = {M (m), S (m)} ( {M (m), S (m), D(m)} = I J 0 .
Notice that J 00 ∈ Mod(T , U) as well. Hence, the symmetric difference I J 0 is not
minimal and J 0 ∈ / w-upd(T , A, U). t
u
Since ComputeUpdate is neither sound nor complete, we cannot use it for com-
puting either sound or complete approximations of ABox updates for DL-Lite wrt
Winslett’s semantics.
To sum-up on Winsletts’s semantics, we conclude that the semantics cannot be ex-
pressed 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 Formula-Based Approaches to Semantics
As a consequence of the observations made in the previous section, we consider now
formula-based approaches for establishing the semantics of updates in DL-Lite KBs.
5.1 Naive Semantics for Updates
A straightforward way of proceeding is to try to keep as many assertions as possible
that belong to the ABox or that are entailed by it via the TBox, without contradicting
the update. We start with a crucial observation that is at the heart of this approach.
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.
INPUT: TBox T , and ABoxes A, N each satisfiable with T
OUTPUT: finite set of membership assertions Aw
[1] Aw := A
[2] for each B1 (c) ∈ N do
[3] Aw := Aw \ {B1 (c)} and
[4] for each B2 v B1 ∈ cl(T ) do Aw := Aw \ {B2 (c)}
[5] if B2 (c) = ∃R(c) then
[6] for each R(c, d) ∈ Aw do N := N ∪ {R(c, d)}
[7] for each R1 (a, b) ∈ N do
[8] Aw := Aw \ {R1 (a, b)} and
[9] for each R2 v R1 ∈ cl(T ) do Aw := Aw \ {R2 (a, b)}
Fig. 3. Algorithm Weeding(T , A, N ) for DL-LiteF R
In other words, in DL-Lite, unsatisfiability of an ABox wrt a TBox is caused either
by a single ABox assertion, which will be a membership assertion for an unsatisfiable
concept or role, or by a pair of assertions contradicting either a disjointness or a func-
tionality assertion of the TBox.
Let T be a TBox, A an ABox, and U an update. We say that A is T -compatible with
U if (T , A ∪ U) is satisfiable. We also make use of the notion of closure of an ABox A
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) |= 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
{A0 ⊆ clT (A) | A0 is T -compatible with U}
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
T -compatible with U. Based on this, we define the naive update of (T , A) by U as
n-upd(T , A, U) := Anm ∪ U.
We exhibit now the algorithm NaiveUpdate, which computes n-upd(T , A, U). It
exploits the algorithm Weeding (see Figure 3), which takes as inputs a TBox T , an
ABox A, and a set N of membership assertions to be “deleted” from A. It deletes
from A (Lines [2]–[4]) all concept membership assertions B1 (c) ∈ N and also those
membership assertions B2 (c) that T -entail B1 (c). Then (Lines [5]–[6]), it detects role
membership assertions that T -entail B1 (c) and adds them to N . Finally (Lines [7]–[9]),
it deletes from the remaining A all membership assertions R1 (a, b) ∈ N and also those
assertions R2 (a, b) that T -entail R1 (a, b). As the result, Weeding returns the subset of
A that does not contain assertions from N and assertions that T -entail one of them.
The algorithm NaiveUpdate (see Figure 4) takes as inputs an ABox A, an update U,
and a TBox T . It detects (Lines [1]–[9]) conflicting assertions in the closure of A ∪ U
INPUT: TBox T , and ABoxes A, U each satisfiable with T
OUTPUT: finite set of membership assertions Au
[1] Au := clT (A ∪ U), U := clT (U), CA := ∅
[2] for each B v ¬B 0 ∈ cl(T ) do
[3] if {B(c), B 0 (c)} ⊆ Au then
[4] if B(c) ∈/ U then CA := CA ∪ {B(c)}
[5] otherwise CA := CA ∪ {B 0 (c)}
[6] for each (funct R) ∈ T do
[7] if {R(a, b), R(a, c)} ⊆ Au then
[8] if R(a, b) ∈/ U then CA := CA ∪ {R(a, b)}
[9] otherwise CA := CA ∪ {R(a, c)}
[10] Au := Weeding(T , Au , CA)
Fig. 4. Algorithm NaiveUpdate(A, U, T ) for DL-LiteF R
and stores them in CA: it first detects conflicts of the form B(c) and ¬B(c) (Lines [2]–
[5]), and then of the form R(a, b) and R(a, c) for a functional role R (Lines [7]–[9]).
Finally, the algorithm resolves the detected conflicts by means of Weeding (Line [10]).
We conclude with the correctness of the algorithm.
Theorem 6. Let (T , A) be a satisfiable DL-LiteF R 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
We start with an example that illustrates some drawbacks of Naive Semantics.
Example 7. Continuing our example with John and his spouse Mary, consider
T: ∃hs − v ¬S , ∃hs v M , M v ∃hs; A: M (j ), hs(j , m).
Assume Mary decided to divorce John, so the update U is {S (m)}. Consider the
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
Haley (denoted as h). The former situation is reflected by the model J1 , while the latter
one by the model J2 in Figure 5.
Note that the Naive Semantics (and, hence, the output of the algorithm NaiveUp-
date) captures only the model J2 , while we might be interested in a semantics that
captures both possibilities. t
u
As we see from the example, the situation when the updated KB entails unex-
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
∃x(hs(j , x) ∧ (x 6= m)), saying that John has a spouse different from Mary. This
j m
I: hs
{M }
h
J2 : hs
j m j m
J1 : {S } {M } {S }
Fig. 5. Comparison of the NaiveUpdate and CarefulUpdate algorithms. Darker gray color: models
captured by NaiveUpdate; lighter gray color: models captured by CarefulUpdate.
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 unexpect-
edly entailed from the updated KB.
We say that a formula is role-constraining if it is of the form ∃x(R(a, x) ∧ (x 6=
c1 ) ∧ · · · ∧ (x 6= cn )), where a and all ci s 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 |=T ϕ holds, then either A |=T ϕ or U |=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
{A0 ⊆ clT (A) | A0 is careful and A0 ∪ U is satisfiable}
has a unique maximal element wrt set inclusion.
Similarly, as to what we did for the Naive Semantics, we can exploit the maximal
set Acm of assertions (where c stands for careful), whose uniqueness is guaranteed by
Theorem 8, to define the careful update of (T , A) by U as
c-upd(T , A, U) := Acm ∪ 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 ∃R(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 Care-
fulUpdate (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 [1]). Then, it computes
the set UF of assertions, that cause unexpectedness in NaiveUpdate(A, U, T ), in two
stages: first it adds to UF all C(a) coming exclusively from A for which there is ∃R(a)
coming from U, such that C(a) and ∃R(a) together yields unexpectedness (Lines [2]–
[6]); second it adds to UF all ∃R(a) coming exclusively from A for which there is
C(a) coming exclusively from U, such that ∃R(a) and C(a) together yields unexpect-
edness (Lines [7]–[10]). Finally it removes UF from NaiveUpdate(A, U, T ) by means
of Weeding (Line [11]). We conclude with the correctness of the algorithm.
Theorem 9. Let (T , A) be a satisfiable DL-LiteF R KB and U an update such that
(T , U) is satisfiable. Then, CarefulUpdate(T , A, U) runs in polynomial time in the size
of T ∪ A ∪ U, and CarefulUpdate(T , A, U) = c-upd(T , A, U).
INPUT: TBox T , and ABoxes A, U each satisfiable with T
OUTPUT: finite set of membership assertions Au
[1] Au := NaiveUpdate(A, U, T ), UF := ∅
[2] for each ∃R(a) ∈ Prechase(U) do
[3] if R(a, b) 6∈ Au for any b then
[4] for each ∃R v ¬C ∈ cl(T ) do
[5] for each C(a) ∈ clT (A) \ clT (U) do
[6] UF := UF ∪ {C(a)}
[7] for each ∃R(a) ∈ Au \ Prechase(U) do
[8] if R(a, b) 6∈ Au for every b then
[9] if (∃R v ¬C) ∈ cl(T ) and C(a) ∈ clT (U) \ clT (A) for some a then
[10] UF := UF ∪ {∃R(a)}
[11] Au := Weeding(T , Au , UF)
Fig. 6. Algorithm CarefulUpdate(A, U, T ) for DL-LiteF R
5.3 Comparison of Semantics
We now discuss the differences between the Naive and Careful Semantics. The crucial
difference is in how the semantics “preserve” entailment of formulas. For disambigua-
tion we denote an updated ABox A0 computed under Naive Semantics as A0n and under
Careful Semantics as A0c .
Proposition 10. Let (T , A) be a DL-LiteF R KB and U an update. If U |=T ϕ, then
A0n |=T ϕ and A0c |=T ϕ, for any FOL formula ϕ. If U 6|=T ϕ and U 6|=T ¬ϕ, then
(i) if A |=T ϕ, then A0n |=T ϕ, when ϕ is an ABox assertion, and
(ii) if A 6|=T ϕ, then A0c 6|=T ϕ, when ϕ is an ABox assertion or role-constraining.
Note that Mod(T , An ) ⊆ Mod(T , Ac ) and Mod(T , An ) intersects with
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-LiteF R 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 [7] is correct.
Theorem 11. For projection-free DL-LiteF R KBs, Winslett’s, Naive, and Careful se-
mantics of ABox updates coincide, and ComputeUpdate computes the updates correctly.
6 Conclusion
We have studied ABox updates for Description Logics of the DL-Lite family. There
are two main families of approaches to updates: model and formula-based. We exam-
ined 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.
For both, we developed polynomial time algorithms to compute updates in DL-LiteF R .
Acknowledgements
The authors are supported by the EU FP7 project Ontorule (ICT-231875). The second
author is also supported by the ERC FP7 grant Webdam (agreement n. 226513).
References
1. Borgida, A., Brachman, R.J.: Conceptual modeling with description logics. [12] chapter 10
349–372
2. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning
and efficient query answering in description logics: The DL-Lite family. J. of Automated
Reasoning 39(3) (2007) 385–429
3. Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family and
relations. J. of Artificial Intelligence Research 36 (2009) 1–69
4. Möller, R., Haarslev, V.: Description logic systems. [12] chapter 8 282–305
5. Haarslev, V., Möller, R.: On the scalability of description logic instance retrieval. J. of
Automated Reasoning 41(2) (2008) 99–142
6. Calvanese, D., De Giacomo, G., Lenzerini, M.: Conjunctive query containment and answer-
ing under description logics constraints. ACM Trans. on Computational Logic 9(3) (2008)
22.1–22.31
7. De Giacomo, G., Lenzerini, M., Poggi, A., Rosati, R.: On instance-level update and erasure
in description logic ontologies. J. of Logic and Computation, Special Issue on Ontology
Dynamics 19(5) (2009) 745–770
8. Liu, H., Lutz, C., Milicic, M., Wolter, F.: Updating description logic ABoxes. In: Proc. of
KR 2006. (2006) 46–56
9. Eiter, T., Gottlob, G.: On the complexity of propositional knowledge base revision, updates
and counterfactuals. Artificial Intelligence 57 (1992) 227–270
10. Zheleznyakov, D.: Updating description logic knowledge bases. Master’s thesis, Faculty of
Computer Science, Free University of Bozen-Bolzano, Italy (2009)
11. Winslett, M.: Updating Logical Databases. Cambridge University Press (1990)
12. Baader, F., Calvanese, D., McGuinness, D., Nardi, D., Patel-Schneider, P.F., eds.: The De-
scription Logic Handbook: Theory, Implementation and Applications. Cambridge University
Press (2003)
13. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Data complexity of
query answering in description logics. In: Proc. of KR 2006. (2006) 260–270
14. Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Linking
data to ontologies. J. on Data Semantics X (2008) 133–173
15. Abiteboul, S., Grahne, G.: Update semantics for incomplete databases. In: Proc. of
VLDB’85. (1985)
16. Ginsberg, M.L., Smith, D.E.: Reasoning about action I: A possible worlds approach. Tech-
nical Report KSL-86-65, Knowledge Systems, AI Laboratory (1987)
17. Winslett, M.: A model-based approach to updating databases with incomplete information.
ACM Trans. on Database Systems 13(2) (1988) 167–196
18. Calvanese, D., Kharlamov, E., Nutt, W.: A proof theory for DL-Lite. In: Proc. of DL 2007.
Volume 250 of CEUR, ceur-ws.org. (2007) 235–242