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.
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 [
As a next step, active integrity constraints were introduced more recently in an e ort
to provide preferred ways for preserving integrity [
latter with a closed-worlds assumption and using di erent dedicated semantics [
tions of marital status. In this TBox it is clearly stated that someone cannot be identified 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
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 invalidating 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. Therefore, as we witness by this example, there are su cient logical reasons behind the investigation on extensions of TBoxes, equipped with extra information on preferences and ways to make use of them.
the basics of Description Logic and therefore only present a background on active integrity 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”
2
We will use the basic description logic ALC and its extension ALCO with nominals
[
Active integrity constraints
as presented in [
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 fa1; : : : ; amg. A set of active integrity constraints is usually denoted by .
of update actions. An update action a 2 U is founded if there is an active constraint r 2 such that a 2 head(r), V U j= body(r) and V (U n fag) 6j= body(r). A consistent set of update actions U is founded if every update action a 2 U is founded. Intuitively, when a set of update actions U is founded then each a 2 U provides a unique repair action for the database V to satisfy a constraint r. Finally, let body( ) = fbody(r) j r 2 g.
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.
3.1
Integrating active constraints to the TBox
by adding additional update actions to the head of each constraint, we define “active”
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.
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 ?:
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 di erentiate 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)
preference to any of them. We formalize all the above by the relation r r0, where r is a static constraint and r0 an active constraint extending it as described in Definition 2.
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 A T and say that an ABox A is consistent (respectively inconsistent) with respect to A T i A is consistent (respectively inconsistent) with respect to static(A T ).
cept literals) is quite straightforward, the update to an ABox having complex concepts
may not be easy (or even impossible) [
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
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. 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 2 S A define the following: – At = fA t B j B 2 S Ag – Au = fA u B j B 2 S Ag – A: = f:Ag
– –
A:A = At [ Au [ A:
A = SA2S A A:A
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 j 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 i : 1. there is an atomic concept A 2 S A and a concept C 2 A:A such that A0 = A [A j C] or A = A0 [A j C]. 2. A and A0 are semantically di erent from one another, i.e., there exists an interpretation I such that I j= A and I 6j= A0.
this definition to an n-step relation between two ABoxes.
Definition 5. Let A and A0 be ABoxes and n > 0. Then A A1; :::; An+1 such that: n A0 i there are ABoxes 1. A = A1; An+1 = A0 and Ai 1 Ai+1; 8i 2 f1; : : : ; ng. 2. A1; :::; An+1 are semantically di erent from one another, i.e., for any two Ai and
A j there exists an interpretation I such that I j= Ai and I 6j= 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 A0 from the ABox A. Note that while we may have A2 = A1 [A1 j C1] and A3 = A2 [A2 j 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 A n A0.
A0 i there exists n > 0 such that
Note that by construction, is symmetric but it is neither reflexive (A cannot be semantically di erent from A) nor transitive (A A0 and A0 A but A A).
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 semantically di erent from each other and there is always a shortest path of n > 0 steps between them.
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 = fA0 j A n A0g 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 = fA0 j A A0g 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 2 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 2 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 di erent and can be reached with one step from A. So by the definition, A0 2 R1A i A0 = A [A j C] or A = A0 [A j C] for some A 2 S A, where C 2 A:A. But as the A 2 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 j C] or A = A0 [A j C]. As a result the set R1A is also finite. Next, consider that the set RnA is finite for an arbitrary n > 0. It su ces to show that the set RnA+1 is also finite. Let’s take an ABox A0 2 RnA and create the set R1A0 of ABoxes that are semantically di erent 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 2 RnA is also finite and thus the union SA02RnA R1A0 is finite as well. It’s easy to see that RnA+1 SA02RnA R1A0 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 Rn+1 is also finite and the induction is complete.
A 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 su ces to show that RA = Snm=1 RnA for some m > 0. Since we have a finite number of concept symbols, there is only a finite number of semantically di erent 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 different 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 2 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 = Snm=1 RnA.
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 UA0 = fA ! Cg if
A UAA0 = fC ! Ag if
A0 = A [A j C] A = A0 [A j C] where C 2 A:A.
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
S A0 = UAA12 ; UA3 ; : : : ; UAn ; UAn+1
A A2 An 1 An where A1; : : : ; An+1 are the semantically di erent ABoxes as in Definition 5.
Finally, if an ABox A can be syntactically modified to the semantically di erent ABox A0 in at least n steps (i.e., if A n A0) through the update sequence S AA0 , we write A S AA0 = A0.
and only investigated the di erent 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.
Definition 9. Let A and T be an ABox and a TBox respectively such that A is inconsistent with respect to T . 1. cAownseiastkenretpwaiitrhorfesApeaccthtoievTi n.g T is an update sequence S AA0 such that A S AA0 is 2. A PMA repair of A achieving T is a weak repair of A achieving T that is minimal with respect to the number of steps needed, i.e., there is no weak repair of A achieving T in fewer steps.
Definition 10. Let A and A T be an ABox and an active TBox respectively such that A is inconsistent with respect to A T . A syntactic modification UA0 is founded if there is an active constraint r on A T such that: A 1. A is not consistent with respect to body(r). 2. A0 is consistent with respect to body(r). 3. UA0 either adds or removes a concept according to the update actions in head(r).
A Furthermore, an update sequence S A0 is founded if for every U 2 S A0 there is an active constraint r on A T such that U is fAounded. A
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 . 1. An update sequence S A0 is a founded weak repair of A by A T if S A0 is a weak
A A repair of A achieving static(A T ) and S A0 is founded.
A 2. An update sequence S A0 is a founded repair of A by A T if S A0 is a PMA repair
A A of A achieving static(A T ) and S A0 is founded.
A
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 2 RA such that S A0 is a founded weak repair of A by A T . A minimally repaired ABox with
A respect to A T is any ABox A0 2 RA such that S AA0 is a founded repair of A by A T .
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 At; Au; A:; A:A and accordingly. We can then also extend all the definitions of this subsection to
A incorporate nominals and Propositions 1 and 2 are still valid.
(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 9 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 9 hasChild: Divorced Mary : Person u :Married u :Divorced u Bachelor u :Widowed A founded repair of A by A T then is the update sequence S A0 = (U1; U2; U3) A where U1 = fMarried u Bachelor ! Marriedg; U2 = fDivorced u Widowed ! Divorcedg and U3 = f:Bachelor ! Bachelorg. Notice also that if we replace U1 by U10 = fBachelor ! :Bachelorg and U2 by U20 = fWidowed ! :Widowedg in S A0 , the A new update sequence S A00 = (U10; U20; U3) is also a founded repair of A by A T .
A
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 E u F B v E u F ! remove(B) A u B v ? ! remove(B)
E u F v B ! remove(E) B E u F : A u E u F or : A u B u E u F 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
execution 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
Propositional Assignments [
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 jA j the set of interpretations I such that I j= A. Note that, although an ABox may have several di erent syntactic forms, all of them are semantically equivalent and are represented by the unique set jA j.
' F C(a) j > j ? j :' j ' _ ' j h i'
F j ; j [ j j j '? 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 formulas and programs are once again equivalent to the semantics of Propositional Dynamic
jA j 2 kC(a)k i A j= C(a)
jA j 2 kh i 'k i there exists A0 such that hjA j; jA0ji 2 k k and A0 j= '
where jA j f g = fI f g j I j= Ag as defined in [
< [ Ii; [ Ii0 > 2 kmodnk i [ Ii j= A; [ Ii0 j= A0 and A n A0 < [ Ii; [ Ii0 > 2 kmodk i [ Ii j= A; [ Ii0 j= 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) a2Irn2dT(A) denoting the fact that A j= consistent(A; T ) i 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 inconsistent with respect to T . A repaired ABox A0 satisfying the constraints r in T could be computed by the following semantic procedure:
h jA j; jA0j i 2 k mod ; consistent(A0; T ) ? k
into account the active constraints of an active TBox and providing minimally repaired
4
the database community, could be integrated into the TBoxes of Description Logic.
of Dynamic Logic could be useful in providing a semantic solution to this problem.