=Paper=
{{Paper
|id=Vol-1879/paper41
|storemode=property
|title=Repairing ABoxes through Active Integrity Constraints
|pdfUrl=https://ceur-ws.org/Vol-1879/paper41.pdf
|volume=Vol-1879
|authors=Christos Rantsoudis,Guillaume Feuillade,Andreas Herzig
|dblpUrl=https://dblp.org/rec/conf/dlog/RantsoudisFH17
}}
==Repairing ABoxes through Active Integrity Constraints==
https://ceur-ws.org/Vol-1879/paper41.pdf
Repairing ABoxes through active integrity constraints
Christos Rantsoudis, Guillaume Feuillade, and Andreas Herzig
IRIT, CNRS, Univ. Toulouse
Abstract. In the literature of database repairing, active integrity constraints have
provided a means of restoring integrity through a set of preferred update actions.
While this is a known issue in the database community, it has not yet been directly
applied to description logics. In this paper, we extend description logic TBoxes
by a similar set of preferred actions and tackle the problem of ABox repairing by
taking into account the new “active” TBox. For this, a mainly syntactic approach
is explored and a further, dynamic logic oriented, semantic approach is suggested
and briefly previewed.
Keywords: active integrity constraints, description logic, ABox repair
1 Introduction
In the database literature integrity constraints are usually considered to be universal
conditions or rules that must hold in any situation. When a database fails to satisfy such
constraints it has to be repaired in order to restore integrity. On a similar note, TBoxes
in description logic are usually created by a long and careful procedure, rendering them
of the highest priority for the ABoxes to abide by. In case of inconsistencies between
an ABox and a TBox, the ABox is usually the one that should be updated to conform
with the rules of the TBox [4, 16].
As a next step, active integrity constraints were introduced more recently in an effort
to provide preferred ways for preserving integrity [11, 6, 7, 5, 8, 9]. This was done by
extending the static integrity constraints by additional update actions, indicating to each
constraint some preferred ways to repair out of all the possible ones. In this paper,
we integrate the same idea to the TBoxes of description logic and investigate ways in
which ABoxes could be repaired according to new “active” TBoxes. We do this by first
defining an extension of the usual TBox, taking into account the operations add(A) and
remove(A), where A is an atomic concept. The intuition is that whenever an inclusion
of the form A u B v ⊥ appears inside the TBox, for atomic concepts A and B, then
the TBox should also indicate the preferred way that this should be repaired when the
constraint is violated in the ABox. While the problem is easier when an assertion of the
form a : AuB has to be updated to the assertion a : Au¬B, difficulties start to arise when
the conjunction of two concepts appears inside the scope of a quantifier. An example
of the latter is when having to update the assertion a : ∀R.(A u B) to the assertion
a : ∀R.(A u ¬B). The direction we pursue is clearly different from previous attempts to
encode integrity constraints into TBoxes, which differentiate the Knowledge Base (the
TBox and the ABox as a single set) from the set of integrity constraints, treating the
latter with a closed-worlds assumption and using different dedicated semantics [19, 18].
2 Christos Rantsoudis, Guillaume Feuillade, and Andreas Herzig
Married ≡ Person u ∃hasSpouse.Person
Divorced ≡ Person u ∃hadSpouse.Person u ¬∃hasSpouse.Person
Bachelor ≡ Person u ¬∃hadSpouse.Person u ¬∃hasSpouse.Person
Widowed ≡ Person u ∃hadSpouse.Deceased u ¬∃hasSpouse.Person
Bachelor u Married v ⊥
Divorced u Widowed v ⊥
Person v Married t Divorced t Bachelor t Widowed
Fig. 1. Example of a TBox
We give a simple example of a TBox in Figure 1, expressing the different defini-
tions of marital status. In this TBox it is clearly stated that someone cannot be identi-
fied as bachelor and married at the same time. Now an ABox containing the concept
Bachelor u Married in its assertions would clearly be inconsistent with respect to this
TBox and would have to be repaired. Dropping one of the two would solve this, howe-
ver one could argue that a person declared as both bachelor and married should only be
identified as married everywhere. Whereas one can achieve married status from being
a bachelor, a married person cannot ‘go back’ to being bachelor but can only become
divorced or widowed instead. Thus the dropping of the concept Bachelor whenever the
concept Bachelor u Married appears in an ABox should be the preferred update action.
In the same vein, since by the last constraint someone has to have a marital status, the
preferred update action would be to add the concept Bachelor to an individual invali-
dating this constraint, as in any other case the person would have to declare that he got
married, divorced or widowed. Finally, as a distinction between divorced and widowed
cannot be made without further information, the constraint Divorced u Widowed v ⊥
should not give any preference between the concepts Divorced and Widowed. The-
refore, as we witness by this example, there are sufficient logical reasons behind the
investigation on extensions of TBoxes, equipped with extra information on preferences
and ways to make use of them.
The paper will be presented as follows. In Section 2 we assume familiarity with
the basics of Description Logic and therefore only present a background on active inte-
grity constraints. Section 3 is where we present the ideas discussed above. We start by
defining the “active” TBox as an extension of the usual TBox in Section 3.1. We then
continue by first taking a syntactic approach in Section 3.2, exploring ways in which we
can reach a desired ABox that is repaired according to the preferences of the “active”
TBox. A somewhat brief semantic approach then follows in Section 3.3, using the pro-
grams of Dynamic Logic, based on the ideas that are previously explored. Finally, we
conclude in Section 4.
2 Background
We will use the basic description logic ALC and its extension ALCO with nominals
[1]. Furthermore, throughout the paper we impose the following conventions:
– we suppose that all ABoxes are consistent and that all TBoxes are consistent
– a TBox will contain only concept definitions and concept inclusions
Repairing ABoxes through active integrity constraints 3
– all TBoxes we talk about will be considered to be acyclic
– given a TBox, a constraint is any inclusion of concepts appearing inside the TBox
– we only work on a ‘simple’ kind of constraints, which we will call static constraints
and which will later be extended into active constraints
2.1 Active integrity constraints
In this subsection we present the basic notions around active integrity constraints mainly
as presented in [8]. In the database literature, databases are sets of propositional varia-
bles denoted by V. A static integrity constraint r is a formula L1 ∧ · · · ∧ Ln → ⊥ where
L1 , . . . , Ln are literals (i.e., propositional variables or negations of propositional varia-
bles) denoting that when a database satisfies all literals in the conjunction then it has to
be repaired in order to satisfy r. A set of static integrity constraints is usually denoted
by C. An update action is an expression of the form +p or −p, where p is a propositi-
onal variable, denoting the insertion or deletion of p in a database V. A set of update
actions U is consistent if it is not the case that both +p ∈ U and −p ∈ U for some
propositional variable p. A consistent set of update actions U is called a weak repair of
V achieving C if the update of V by U satisfies all the static constraints in C, formally:
V U |= C. Usually there are several ways to repair a database V in order to satisfy
V
a set of static integrity constraints C. A consistent set of update actions U is called a
repair or PMA repair of V achieving C if U is a weak repair of V achieving C that is
minimal with respect to set inclusion, i.e., there is no weak repair U 0 of V achieving
C such that U 0 ⊂ U. The term PMA repair indicates the close relation of repairs and
Winslett’s possible models approach to updating a database [20, 21, 15].
As a next step, active integrity constraints are an extension of static constraints by
additional update actions +p and −p for propositional variables p. They usually have
the form L1 ∧ · · · ∧ Ln → a1 ∨ · · · ∨ am , where a1 , . . . , am are update actions that indicate
which from the literals L1 , . . . , Ln should change in case L1 ∧ · · · ∧ Ln is satisfied. Of
course in this form active integrity constraints are not formulas, as the right part of
the expression is a disjunction of update actions rather than literals or propositional
variables. If r is an active integrity constraint of this form, we denote by body(r) the
formula L1 ∧ · · · ∧ Ln → ⊥ and by head(r) the set of update actions {a1 , . . . , am }. A set
of active integrity constraints is usually denoted by η.
Now let V be a database, η a set of active integrity constraints and U a consistent set
of update actions. An update action a ∈ U is founded if there is an active constraint r ∈ η
such that a ∈ head(r), V U |= body(r) and V (U \ {a}) 6|= body(r). A consistent set of
update actions U is founded if every update action a ∈ U is founded. Intuitively, when
a set of update actions U is founded then each a ∈ U provides a unique repair action
for the database V to satisfy a constraint r. Finally, let body(η) = {body(r) | r ∈ η}.
A set of update actions U is a founded weak repair of V by η if U is a weak repair of
V achieving body(η) and U is founded. A set of update actions U is a founded repair
of V by η if U is a PMA repair of V achieving body(η) and U is founded. Although
founded weak repairs and founded repairs do not necessarily exist and other forms of
repairs have to be sought, they provide the basic means for repairing a database taking
into account a set of active integrity constraints.
4 Christos Rantsoudis, Guillaume Feuillade, and Andreas Herzig
3 A new kind of ABox repairing
3.1 Integrating active constraints to the TBox
Similarly to how the active integrity constraints of Section 2.1 extend static constraints
by adding additional update actions to the head of each constraint, we define “active”
TBoxes to contain preferred update actions of the form add(A) and remove(A) for ato-
mic concepts A. We start by defining what exactly is a static constraint in this setting.
Definition 1. Let T be a TBox. A conjunctive constraint is any inclusion of the form
C1 u · · · u Cn v ⊥ appearing inside the TBox, where C1 , . . . , Cn are either atomic or
negation of atomic concepts. A static constraint is any inclusion appearing inside the
TBox that is either a conjunctive constraint or equivalent to a conjunctive constraint.
For example, in the TBox of Figure 1, all three of the inclusions
Bachelor u Married v ⊥, Divorced u Widowed v ⊥
Person v Married t Divorced t Bachelor t Widowed
are static constraints since the first two are conjunctive constraints whereas the third is
equivalent to the conjunctive constraint
Person u ¬Married u ¬Divorced u ¬Bachelor u ¬Widowed v ⊥.
We continue with the definition of an active constraint.
Definition 2. Let r be a static constraint. If r is not a conjunctive constraint, let r∗ be
the conjunctive constraint that is equivalent to r. An active constraint r0 is the extension
of r by either add(A) or remove(A) for some of the atomic concepts A appearing in r,
according to the following rules:
– add(A) can exist in r0 whenever ¬A is a literal on the conjunction of r (or r∗ ).
– remove(A) can exist in r0 whenever A is a literal on the conjunction of r (or r∗ ).
We use the symbol → (being part of the metalanguage) to differentiate between the
body(r0 ), which is r itself, and the head(r0 ), which is the set of update actions add(A)
and remove(A) for atomic concepts A. For instance, for a static constraint r of the form
¬A u B v ⊥, the following are the possible active constraints extending it:
r1 : ¬A u B v ⊥ → add(A)
r2 : ¬A u B v ⊥ → remove(B)
r3 : ¬A u B v ⊥ → add(A), remove(B)
The first two give a preference to one of the two concepts, while the third gives no
preference to any of them. We formalize all the above by the relation r r0 , where r is
0
a static constraint and r an active constraint extending it as described in Definition 2.
The next step is to generalize this construction to TBoxes. We extend the relation
and define “active” TBoxes as follows.
Repairing ABoxes through active integrity constraints 5
Married ≡ Person u ∃hasSpouse.Person
Divorced ≡ Person u ∃hadSpouse.Person u ¬∃hasSpouse.Person
Bachelor ≡ Person u ¬∃hadSpouse.Person u ¬∃hasSpouse.Person
Widowed ≡ Person u ∃hadSpouse.Deceased u ¬∃hasSpouse.Person
Bachelor u Married v ⊥ → remove(Bachelor)
Divorced u Widowed v ⊥ → remove(Divorced), remove(Widowed)
Person v Married t Divorced t Bachelor t Widowed → add(Bachelor)
Fig. 2. Example of an active TBox, based on the TBox of Figure 1
Definition 3. Let T be a TBox. A T is an active TBox extending T , viz. T A T , iff
for each static constraint r in T there is an active constraint r0 in A T such that r r0 .
In Figure 2 we see an example of an active TBox, based on the TBox of Figure 1
and the discussion about the preferred update actions in order to repair it. Finally, for
any active TBox A T we denote with static(A T ) the TBox T for which T AT
and say that an ABox A is consistent (respectively inconsistent) with respect to A T iff
A is consistent (respectively inconsistent) with respect to static(A T ).
In what follows, we present a syntactic and briefly a semantic approach, based on
Dynamic Logic, for the difficult task of repairing an ABox, inconsistent with respect
to an active TBox, taking into account preferred update actions, especially when the
inconsistencies appear inside the scope of a quantifier.
3.2 A syntactic approach
While updating to a simple ABox (i.e., an ABox whose assertions consist only of con-
cept literals) is quite straightforward, the update to an ABox having complex concepts
may not be easy (or even impossible) [12, 13, 17]. Consider for instance the active con-
straint r : A u B v ⊥ → remove(B) and an ABox which includes only the assertions
a : ∀ r. (A u B) and r(a, b) for two individuals a and b. We would then like to repair this
ABox with respect to r into the ABox having either a : ∀ r. A or a : ∀ r. (A u ¬B) as an
assertion for the individual a1 . From a semantic point of view, however, it is not clear
what set of update actions would achieve this goal, especially when the update actions
are defined only on the atomic level. In this subsection we investigate the direction of
how we could transform an initial ABox, inconsistent with respect to the active TBox,
to a repaired one conforming to the active constraints of the TBox. We mainly focus
on the syntactic procedure that leads to a repaired ABox and what this resulting ABox
would look like.
Consider that A T is the active TBox we are working with. We start by defining a
relation between two ABoxes, so that the second ABox is the outcome of applying a
1
Whereas the former seems like a better candidate for a repair (taking into account the open-
world nature of DLs) we do not give a preference to any of them as long as the inconsistencies
are eliminated. Regarding minimality of change, this will be defined syntactically to be the least
amount of syntactic changes made in the ABox, once again providing no preference between
the two.
6 Christos Rantsoudis, Guillaume Feuillade, and Andreas Herzig
small change to the first ABox. Define the set S A to consist of all concept symbols in
the ABox A and TBox A T . For A ∈ S A define the following:
– At = {A t B | B ∈ S A }
– Au = {A u B | B ∈ S A }
– A¬ = {¬A}
Furthermore, define:
– ΓA:A = At ∪ Au ∪ A¬
– ΓA = A∈S A ΓA:A
S
Intuitively, ΓA denotes the set of concepts that can be reached with one step from S A
using the three boolean constructors. Next, we write A [A | C] to denote the replacement
in A of some instances of the atomic concept A with the concept C. Then we define the
following relation.
Definition 4. Let A and A0 be ABoxes. Then A ∼1 A0 iff:
1. there is an atomic concept A ∈ S A and a concept C ∈ ΓA:A such that A0 = A [A | C]
or A = A0 [A | C].
2. A and A0 are semantically different from one another, i.e., there exists an interpre-
tation I such that I |= A and I 6|= A0 .
The relation ∼1 is clearly symmetric and irreflexive. The next step is to generalize
this definition to an n-step relation between two ABoxes.
Definition 5. Let A and A0 be ABoxes and n > 0. Then A ∼n A0 iff there are ABoxes
A1 , ..., An+1 such that:
1. A = A1 , An+1 = A0 and Ai ∼1 Ai+1 , ∀i ∈ {1, . . . , n}.
2. A1 , ..., An+1 are semantically different from one another, i.e., for any two Ai and
A j there exists an interpretation I such that I |= Ai and I 6|= A j .
3. there is no n0 < n with these two properties.
When A ∼n A0 we say that at least n steps are needed in order to reach the ABox
A from the ABox A. Note that while we may have A2 = A1 [A1 | C1 ] and A3 =
0
A2 [A2 | C2 ] and therefore A1 ∼1 A2 ∼1 A3 , we do not have A1 ∼3 A3 because of the
last constraint. Finally, let us define the relation A ∼ A0 to mean that A0 can be reached
from A by an arbitrary number of steps.
Definition 6. Let A and A0 be ABoxes. Then A ∼ A0 iff there exists n > 0 such that
A ∼n A0 .
Note that by construction, ∼ is symmetric but it is neither reflexive (A cannot be
semantically different from A) nor transitive (A ∼ A0 and A0 ∼ A but A A).
So we have a way to change an ABox syntactically to another one with the use of
the set ΓA by applying a finite number of times one-step changes to concept symbols
on each subsequent ABox. Furthermore, by construction the two ABoxes are always
Repairing ABoxes through active integrity constraints 7
semantically different from each other and there is always a shortest path of n > 0 steps
between them.
We can now utilize this construction in our effort of repairing an ABox with respect
to an active TBox. Let A and A T be an ABox and an active TBox respectively such
that A is inconsistent with respect to A T and let RnA = {A0 | A ∼n A0 } be the
set of ABoxes that can be reached from A by at least n steps. So for each n > 0
we have that the sets R1A , R2A , R3A , . . . are pairwise disjoint and their union is the set
RA = {A0 | A ∼ A0 } of ABoxes that can be reached from A by an arbitrary number of
steps. The next propositions give some important properties on the cardinality of these
sets.
Proposition 1. Let A and A T be an ABox and an active TBox respectively. Then for
each n > 0 the set RnA is finite.
Proof. Let’s start by noticing that since the ABox and the TBox are always finite, the
set S A containing their concept symbols is also finite. As a result, for each A ∈ S A the
sets At , Au and A¬ are also finite, since they are made up of disjunctions, conjunctions
and negations between symbols of S A . Then the set ΓA:A which is the union of the finite
sets At , Au and A¬ is also finite, for all A ∈ S A . It follows that the set ΓA of concepts
that can be reached with one step from S A is finite, since it comprises a finite union of
finite sets.
Let’s look initially at the set R1A . It comprises the ABoxes that are semantically
different and can be reached with one step from A. So by the definition, A0 ∈ R1A iff
A0 = A [A | C] or A = A0 [A | C] for some A ∈ S A , where C ∈ ΓA:A . But as the A ∈ S A
are finite and for each A the set ΓA:A is also finite, there is a finite number of ABoxes
such that A0 = A [A | C] or A = A0 [A | C]. As a result the set R1A is also finite. Next,
consider that the set RnA is finite for an arbitrary n > 0. It suffices to show that the set
0
A
Rn+1 is also finite. Let’s take an ABox A0 ∈ RnA and create the set R1A of ABoxes that
are semantically different and can be reached with one step from A0 . We already know
that this set is finite. But by hypothesis, the set of ABoxes A0 ∈ RnA is also finite and
0 0
thus the union A0 ∈RnA R1A is finite as well. It’s easy to see that Rn+1 A
⊆ A0 ∈RnA R1A
S S
since for each ABox A00 which is at least n + 1 steps away from A there is an ABox A0
which is at least n steps away from A such that A ∼n A0 and A0 ∼1 A00 . Thus the set
A
Rn+1 is also finite and the induction is complete.
Proposition 2. Let A and A T be an ABox and an active TBox respectively. Then the
set RA is finite.
Proof. We will only provide a sketch of the proof. It suffices to show that RA =
n=1 Rn for some m > 0. Since we have a finite number of concept symbols, there
Sm A
is only a finite number of semantically different concepts that can be expressed by these
symbols using the three boolean constructors. Furthermore, using these concepts in
combination with the role symbols of A there is a finite number of semantically dif-
ferent concepts that can reach a specific role depth. But since for all concepts the role
depth never changes between the ABox A and the ABoxes A0 ∈ RA , there will be a
set of ABoxes RnA for which each subsequent ABox constructed by the relation ∼1 will
have a semantically equivalent ABox belonging in a set RmA for m < n. In other words,
there is an m > 0 such that RnA = ∅ for all n > m and RA = m A
S
n=1 Rn .
8 Christos Rantsoudis, Guillaume Feuillade, and Andreas Herzig
Next we define a syntactic modification to be the update action needed in order to
reach an ABox A0 from an ABox A in one step using the set ΓA .
Definition 7. Let A, A0 and A T be two ABoxes and an active TBox respectively such
that A ∼1 A0 . The syntactic modification from A to A0 is the singleton set
0
A
UA = {A → C} if A0 = A [A | C]
0
A
UA = {C → A} if A = A0 [A | C]
where C ∈ ΓA:A .
Using this definition we can now define an update sequence to be the sequence of
syntactic modifications needed in order to reach an ABox A0 from an ABox A in n
steps using the set ΓA .
Definition 8. Let A, A0 and A T be two ABoxes and an active TBox respectively such
that A ∼n A0 . The update sequence from A to A0 is the sequence
A0
SA = UAA2
1
, UA
A3
2
, . . . , UA
An
n−1
, UA
An+1
n
where A1 , . . . , An+1 are the semantically different ABoxes as in Definition 5.
Finally, if an ABox A can be syntactically modified to the semantically different
A0
ABox A0 in at least n steps (i.e., if A ∼n A0 ) through the update sequence S A , we
0
write A S A = A .
A 0
Notice that up until now we have not made use of the ‘active’ part of the TBox
and only investigated the different ways to construct new ABoxes. The next step is to
indicate what it means for an ABox to be repaired with respect to the active TBox.
We will make use of similar notions that we already presented in Section 2.1 about
active integrity constraints to show the relation between the two settings. We start by
the definitions of weak repair and PMA repair.
Definition 9. Let A and T be an ABox and a TBox respectively such that A is incon-
sistent with respect to T .
0 0
A A
1. A weak repair of A achieving T is an update sequence S A such that A S A is
consistent with respect to T .
2. A PMA repair of A achieving T is a weak repair of A achieving T that is mini-
mal with respect to the number of steps needed, i.e., there is no weak repair of A
achieving T in fewer steps.
Next we define the notion of foundedness on the level of syntactic modifications
and on the level of update sequences.
Definition 10. Let A and A T be an ABox and an active TBox respectively such that
A0
A is inconsistent with respect to A T . A syntactic modification UA is founded if there
is an active constraint r on A T such that:
1. A is not consistent with respect to body(r).
Repairing ABoxes through active integrity constraints 9
2. A0 is consistent with respect to body(r).
A0
3. UA either adds or removes a concept according to the update actions in head(r).
0 0
A A
Furthermore, an update sequence S A is founded if for every U ∈ S A there is an active
constraint r on A T such that U is founded.
Finally, using the above definitions, we define founded weak repairs and founded
repairs as follows.
Definition 11. Let A and A T be an ABox and an active TBox respectively such that
A is inconsistent with respect to A T .
0 0
A A
1. An update sequence S A is a founded weak repair of A by A T if S A is a weak
A0
repair of A achieving static(A T ) and S A is founded.
A0 A0
2. An update sequence S A is a founded repair of A by A T if S A is a PMA repair
0
A
of A achieving static(A T ) and S A is founded.
Summing up, let A be an ABox and A T an active TBox such that A is inconsistent
with respect to A T . A repaired ABox with respect to A T is any ABox A0 ∈ RA such
A0
that S A is a founded weak repair of A by A T . A minimally repaired ABox with
A0
respect to A T is any ABox A0 ∈ RA such that S A is a founded repair of A by A T .
Since by Proposition 2 there is a finite number of ABoxes that we can construct step by
step from the initial ABox using the set ΓA , the sets of repaired and minimally repaired
ABoxes with respect to A T are also finite. This means that we can start from the set of
ABoxes R1A and continue searching all the sets RnA for n > 0 until we find a minimally
repaired ABox with respect to A T .
∗
Remark 1. If we are working on ALCO, let S A be the extension of S A such that it
also includes the nominals of the ABox A and TBox A T and define A∗t , A∗u , A∗¬ , ΓA:A
∗
and ΓA accordingly. We can then also extend all the definitions of this subsection to
∗
incorporate nominals and Propositions 1 and 2 are still valid.
We now return to the original example of Figures 1 and 2 and examine an ABox
(which is inconsistent with respect to this TBox) and one of its possible repairs. Let
A T be the active TBox of Figure 2. Let the ABox A, written in the language of ALC,
consist of the following assertions:
John : Person u Married u Bachelor u ∃ hasChild. (Divorced u Widowed)
Mary : Person u ¬Married u ¬Divorced u ¬Bachelor u ¬Widowed
A minimally repaired ABox A0 with respect to A T is the following:
John : Person u Married u ∃ hasChild. Divorced
Mary : Person u ¬Married u ¬Divorced u Bachelor u ¬Widowed
0
A
A founded repair of A by A T then is the update sequence S A = (U1 , U2 , U3 )
where U1 = {Married u Bachelor → Married}, U2 = {Divorced u Widowed →
Divorced} and U3 = {¬Bachelor → Bachelor}. Notice also that if we replace U1 by
10 Christos Rantsoudis, Guillaume Feuillade, and Andreas Herzig
0
U10 = {Bachelor → ¬Bachelor} and U2 by U20 = {Widowed → ¬Widowed} in S A A
, the
00
new update sequence S A = (U1 , U2 , U3 ) is also a founded repair of A by A T .
A 0 0
Finally, let us note that it may not be possible to acquire a founded repair in cases
where a concept is defined in the TBox and does not explicitly appear inside the ABox
but is inferred, as shown in the table below. Using the active TBox of the first column
we would not be able to provide a founded repair of any of the two ABoxes in the last
row. Given a more precise active TBox, however, this would not pose a problem. We
can witness this with the active TBox of the second column, which provides a founded
repair for the second assertion, and even more with the active TBox of the third column,
which provides a founded repair for both assertions.
A u B v ⊥ → remove(B) A u B v ⊥ → remove(B) A u E u F v ⊥ → remove(E)
B≡EuF B v E u F → remove(B) A u B v ⊥ → remove(B)
E u F v B → remove(E) B ≡ E u F
α: AuEuF or α : AuBuEuF
3.3 A semantic approach
In Dynamic Logic the most prominent role is that of the programs, which are usually
denoted by π. Formulas of the form hπi ϕ express the fact that “there is a possible exe-
cution of the program π after which ϕ is the case”. Many extensions and variants have
been proposed in the literature, with DL-PA (standing for Dynamic Logic of Propositi-
onal Assignments [14, 3, 2]) being recently utilised in the study of more dynamic ways
to repair databases taking into account a set of active integrity constraints [10]. In that
setting, atomic programs are update actions of the form p ← > and p ← ⊥ denoting
the insertion and the deletion of the propositional variable p.
Looking in a somewhat similar direction, but on the setting of Description Logic, a
logical next step would be to define the atomic programs to be of the form A(a) ← >
and A(a) ← ⊥, where A is an atomic concept and a an individual. Similar to DL-PA,
the atomic program A(a) ← > denotes the update of an ABox with the assertion a : A,
while A(a) ← ⊥ denotes the update with the assertion a : ¬A. For an ABox A, we
denote by |A | the set of interpretations I such that I |= A. Note that, although an ABox
may have several different syntactic forms, all of them are semantically equivalent and
are represented by the unique set |A |.
We use the following grammar in order to define arbitrary programs and formulas:
ϕ F C(a) | > | ⊥ | ¬ϕ | ϕ ∨ ϕ | hπiϕ
π F α | π; π | π ∪ π | π∗ | π− | ϕ?
where C(a) is a concept assertion and α an atomic program of the form A(a) ← > or
A(a) ← ⊥ for atomic concepts A and individuals a. The operators ; , ∪,∗ ,− and ? are
considered familiar from Propositional Dynamic Logic. The semantics of these formu-
las and programs are once again equivalent to the semantics of Propositional Dynamic
Logic with exceptions being the following:
|A | ∈ kC(a)k iff A |= C(a)
|A | ∈ khπi ϕk iff there exists A0 such that h|A |, |A0 |i ∈ kπk and A0 |= ϕ
Repairing ABoxes through active integrity constraints 11
h|A |, |A0 |i ∈ kαk iff |A0 | = |A | {α}
h|A |, |A |i ∈ kϕ?k iff A |= ϕ
where |A | {α} = {I {α} | I |= A} as defined in [17]. Using these semantics now
we can define the following programs, denoting the n-step and arbitrary-step syntactic
modifications of Section 3.2:
kmodn k = < |A | , |A0 | > such that A ∼n A0
kmodk = < |A | , |A0 | > such that A ∼ A0
In other words:
[ [ [ [
< Ii , Ii0 > ∈ kmodn k iff Ii |= A, Ii0 |= A0 and A ∼n A0
[ [ [ [
< Ii , Ii0 > ∈ kmodk iff Ii |= A, Ii0 |= A0 and A ∼ A0
Now, given a TBox T and an ABox A define le f t[r] to be the left side of the
constraint r in T , right[r] to be the right side of the constraint r in T and Ind(A) the
set of individuals in A. Then we define consistent(A, T ) to be the formula:
^
le f t[r](a) → right[r](a)
r∈T
a∈Ind(A)
denoting the fact that A |= consistent(A, T ) iff the ABox A is consistent with respect
to the TBox T .
Finally, let T and A be a TBox and an ABox respectively such that A is inconsis-
tent with respect to T . A repaired ABox A0 satisfying the constraints r in T could be
computed by the following semantic procedure:
h |A |, |A0 | i ∈ k mod ; consistent(A0 , T ) ? k
The next obvious step would be to continue this semantic investigation by taking
into account the active constraints of an active TBox and providing minimally repaired
ABoxes as well as their founded repairs through programs of Dynamic Logic.
4 Conclusion
In this paper we explored the ways in which active constraints, which originate from
the database community, could be integrated into the TBoxes of Description Logic.
Based on these “active” TBoxes, we then investigated a mainly syntactic approach of
transforming an ABox (inconsistent with an active TBox) step-by-step by syntactic
modifications to a repaired one, conforming to the preferred update actions found in the
active constraints of the extended TBox.
A semantic approach was also previewed, showing the ways in which programs
of Dynamic Logic could be useful in providing a semantic solution to this problem.
Although a brief one, it laid some foundations for future work, motivated by the way
DL-PA was utilised to provide new kinds of repairs in the database literature.
The most crucial thing though would be to make the landscape of active TBoxes and
the associated repairs more clear and intuitive. In this work, we provided a first (small)
step into this direction and believe that it is one that the description logic community
would find interesting enough to delve into.
12 Christos Rantsoudis, Guillaume Feuillade, and Andreas Herzig
References
1. Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The
Description Logic Handbook: Theory, Implementation, and Applications. Cambridge Uni-
versity Press (2003)
2. Balbiani, P., Herzig, A., Schwarzentruber, F., Troquard, N.: DL-PA and DCL-PC: model
checking and satisfiability problem are indeed in PSPACE. CoRR abs/1411.7825 (2014),
http://arxiv.org/abs/1411.7825
3. Balbiani, P., Herzig, A., Troquard, N.: Dynamic logic of propositional assignments: a well-
behaved variant of PDL. In: Kupferman, O. (ed.) Logic in Computer Science (LICS). IEEE
(2013)
4. Bienvenu, M., Bourgaux, C., Goasdoué, F.: Querying inconsistent description logic know-
ledge bases under preferred repair semantics. In: Brodley, C.E., Stone, P. (eds.) Proceedings
of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27 -31, 2014, Québec
City, Québec, Canada. pp. 996–1002. AAAI Press (2014), http://www.aaai.org/ocs/
index.php/AAAI/AAAI14/paper/view/8231
5. Caroprese, L., Greco, S., Zumpano, E.: Active integrity constraints for database consistency
maintenance. IEEE Trans. Knowl. Data Eng. 21(7), 1042–1058 (2009)
6. Caroprese, L., Trubitsyna, I., Zumpano, E.: View updating through active integrity con-
straints. In: Dahl, V., Niemelä, I. (eds.) ICLP. Lecture Notes in Computer Science, vol. 4670,
pp. 430–431. Springer (2007)
7. Caroprese, L., Truszczynski, M.: Declarative semantics for active integrity constraints. In:
de la Banda, M.G., Pontelli, E. (eds.) ICLP. Lecture Notes in Computer Science, vol. 5366,
pp. 269–283. Springer (2008)
8. Caroprese, L., Truszczynski, M.: Active integrity constraints and revision programming.
TPLP 11(6), 905–952 (2011)
9. Cruz-Filipe, L.: Optimizing computation of repairs from active integrity constraints. In: Bei-
erle, C., Meghini, C. (eds.) FoIKS. Lecture Notes in Computer Science, vol. 8367, pp. 361–
380. Springer (2014)
10. Feuillade, G., Herzig, A.: A dynamic view of active integrity constraints. In: Ferme, E.,
Leite, J. (eds.) European Conference on Logics in Artificial Intelligence (JELIA), Ma-
deira, 24/09/2014-26/09/2014. pp. 486–499. Springer, http://www.springerlink.com (septem-
bre 2014), http://oatao.univ-toulouse.fr/13171/
11. Flesca, S., Greco, S., Zumpano, E.: Active integrity constraints. In: Moggi, E., Warren, D.S.
(eds.) PPDP. pp. 98–107. ACM (2004)
12. Flouris, G., d’Aquin, M., Antoniou, G., Pan, J.Z., Plexousakis, D.: Special issue on onto-
logy dynamics. J. Log. Comput. 19(5), 717–719 (2009), http://dx.doi.org/10.1093/
logcom/exn046
13. Flouris, G., Plexousakis, D., Antoniou, G.: Updating dls using the AGM theory: A preli-
minary study. In: Horrocks, I., Sattler, U., Wolter, F. (eds.) Proceedings of the 2005 Inter-
national Workshop on Description Logics (DL2005), Edinburgh, Scotland, UK, July 26-28,
2005. CEUR Workshop Proceedings, vol. 147. CEUR-WS.org (2005), http://ceur-ws.
org/Vol-147/26-Flouris.pdf
14. Herzig, A., Lorini, E., Moisan, F., Troquard, N.: A dynamic logic of normative systems.
In: Walsh, T. (ed.) International Joint Conference on Artificial Intelligence (IJCAI). pp.
228–233. IJCAI/AAAI, Barcelona (2011), http://www.irit.fr/˜Andreas.Herzig/P/
Ijcai11.html
15. Herzig, A., Rifi, O.: Propositional belief base update and minimal change. Artificial Intelli-
gence Journal 115(1), 107–138 (Nov 1999), ../Herzig/P/aij99.html
Repairing ABoxes through active integrity constraints 13
16. Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M., Savo, D.F.: Inconsistency-tolerant seman-
tics for description logics. In: Hitzler, P., Lukasiewicz, T. (eds.) Web Reasoning and Rule Sy-
stems - Fourth International Conference, RR 2010, Bressanone/Brixen, Italy, September 22-
24, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6333, pp. 103–117. Springer
(2010), http://dx.doi.org/10.1007/978-3-642-15918-3_9
17. Liu, H., Lutz, C., Milicic, M., Wolter, F.: Foundations of instance level updates in expressive
description logics. Artificial Intelligence 175(18), 2170–2197 (2011)
18. Motik, B., Horrocks, I., Sattler, U.: Bridging the gap between OWL and relational databases.
J. Web Sem. 7(2), 74–89 (2009), https://doi.org/10.1016/j.websem.2009.02.001
19. Tao, J., Sirin, E., Bao, J., McGuinness, D.L.: Integrity constraints in OWL. In: Fox, M.,
Poole, D. (eds.) Proceedings of the Twenty-Fourth AAAI Conference on Artificial In-
telligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010. AAAI Press (2010),
http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1931
20. Winslett, M.A.: Reasoning about action using a possible models approach. In: Proc. 7th
Conf. on Artificial Intelligence (AAAI’88). pp. 89–93. St. Paul (1988)
21. Winslett, M.A.: Updating Logical Databases. Cambridge Tracts in Theoretical Computer
Science, Cambridge University Press (1990)