=Paper=
{{Paper
|id=Vol-477/paper-38
|storemode=property
|title=A Conflict-based Operator for Mapping Revision
|pdfUrl=https://ceur-ws.org/Vol-477/paper_26.pdf
|volume=Vol-477
|dblpUrl=https://dblp.org/rec/conf/dlog/QiJH09
}}
==A Conflict-based Operator for Mapping Revision==
https://ceur-ws.org/Vol-477/paper_26.pdf
A Conflict-based Operator for Mapping
Revision?
Guilin Qi, Qiu Ji, Peter Haase
Institute AIFB, University of Karlsruhe, Germany
{gqi,qiji,pha}@aifb.uni-karlsruhe.de
Abstract. Ontology matching is one of the key research topics in the
field of the Semantic Web. There are many matching systems that gener-
ate mappings between different ontologies either automatically or semi-
automatically. However, the mappings generated by these systems may
be inconsistent with the ontologies. Several approaches have been pro-
posed to deal with the inconsistencies between mappings and ontologies.
This problem is often called a mapping revision problem because we give
priority to ontologies when resolving inconsistencies. In this paper, we
first propose a conflict-based mapping revision operator and show that it
can be characterized by a logical postulate. We then provide an iterative
algorithm for mapping revision by using an ontology revision operator
and show that this algorithm defines a conflict-based mapping revision
operator. Three concrete ontology revision operators are given to in-
stantiate the iterative algorithm, which result in three different mapping
revision algorithms. We implement these algorithms and provide some
preliminary but interesting evaluation results.
1 Introduction
Next generation semantic applications are employed by a large number of on-
tologies, some of them constantly evolving. As the complexity of semantic appli-
cations increases, more and more knowledge is embedded in ontologies, typically
drawn from a wide variety of sources. This new generation of applications thus
likely relies on a set of distributed ontologies, typically connected by mappings.
One of the major challenges in managing these distributed and dynamic on-
tologies is to handle potential inconsistencies introduced by integrating multiple
distributed ontologies.
For inconsistency handling in single, centralized ontologies, several approaches
are known (see the survey in [7]). Recently, there are some works done on han-
dling inconsistency in distributed ontologies connected by mappings, where a
mapping between two ontologies is a set of correspondences between entities in
the ontologies. Given a distributed system which is a triple consisting of two
ontologies and a mapping between them, correspondences in the mapping can
?
This work is partially supported by the EU in the IST project NeOn
(http://www.neon-project.org/).
have different interpretations. For example, in Distributed Description Logics
(DDL) [3], a correspondence in a mapping is translated into two bridge rules
that describes the ”flow of information” from one ontology to another one. In
[13], the authors deal with the problem of mapping revision in DDL by remov-
ing some bridge rules which are responsible for the inconsistency. The idea of
their approach is similar to that of the approaches for debugging and repairing
terminologies in a single ontology. Mappings can also be interpreted as sets of
axioms in a description logic. A heuristic method for mapping revision is given
in [12]. However, this method can only deal with inconsistency caused by dis-
jointness axioms which state that two concepts are disjoint. Later on, Meilicke
et al. propose another algorithm to resolve the inconsistent mappings in [15].
The idea of their algorithm is similar to the linear base revision operator given
in [16]. However, both methods given in [12] and [15] lack of rationality analysis
w.r.t. logical properties.
In this paper, we first propose a conflict-based mapping revision operator
based on the notion of a “conflict set” which is a subset of the mapping that is
in conflict with ontologies in a distributed system. We then adapt a postulate
from belief revision theory [8] and show that our mapping revision operator can
be characterized by it (see Section 3). After that, in Section 4, we provide an iter-
ative algorithm for mapping revision by using a revision operator in description
logics and show that this algorithm results in a conflict-based mapping revision
operator. We define a revision operator and show that the iterative algorithm
based on it produces the same results as the algorithm given in [15]. This spe-
cific iterative algorithm has a polynomial time complexity if the satisfiability
check of an ontology can be done in polynomial time in the size of the ontology.
However, this algorithm may still be inefficient if the mapping contains a large
number of correspondences and the sizes of the ontologies are big because it
will need a large number of satisfiability checks over a large ontology. Therefore,
we provide an algorithm to implement an alternative revision operator based
on the relevance-based selection function given in [11] which can be optimized
by a module extraction technique given in [21]. Neither of the above proposed
revision operators removes minimal number of correspondences to resolve in-
consistencies. To better fulfil the principle of minimal change, we consider the
revision operator given in [18] which utilizes a heuristics based on a scoring func-
tion which returns the number of minimal incoherence-preserving sub-ontologies
(MIPS) that an axiom belongs to. Instantiating our iterative algorithm with
this existing revision operator results in a new conflict-based mapping revision
operator. Finally, we implement these algorithms and provide evaluation results
for comparing their efficiency and effectiveness in Section 5.
Relationship with belief revision This work is related to belief revision which has
been widely discussed in the literature [5, 10], especially to the theory of belief
base revision [10]. Our conflict-based mapping revision operator is inspired by
the internal revision operator given in [8] and the postulate used to characterize
our mapping revision operator is adapted from a postulate for internal revision
operator given in [8]. The problem of mapping revision is not exactly the same
as the problem of belief base revision because the mapping to be revised is
dependent of ontologies in the distributed system and each correspondence in
the mapping carries a confidence value which can be used to guide the revision.
Our iterative algorithm is inspired from the iterative revision algorithm given in
[17] and is tailored to produce a conflict-based revision operator.
2 Preliminaries
We assume that the reader is familiar with Description Logics (DL) and refer
to Chapter 2 of the DL handbook [1] for a good introduction. Our method is
independent of a specific DL language, and thus can be applied to any DL.
A DL-based ontology (or knowledge base) O = (T , R) consists of a set T
of concept axioms (TBox) and a set R of role axioms (RBox). Concept axioms
(or terminology axioms) have the form C v D, where C and D are (possibly
complex) concept descriptions built from a set of concept names and some con-
structors, and role axioms are expressions of the form RvS, where R and S are
(possibly complex) role descriptions built from a set of role names and some
constructors.
An interpretation I = (4I , ·I ) consists of a non-empty domain set 4I and an
interpretation function ·I , which maps from concepts and roles to subsets of the
domain and binary relations on the domain, respectively. Given an interpretation
I, we say that I satisfies a concept axiom C v D (resp., a role inclusion axiom
R v S) if C I ⊆DI (resp., RI ⊆ S I ). An interpretation I is called a model of
an ontology O, iff it satisfies each axiom in O. A concept C in an ontology O is
unsatisfiable if for each model I of O, C I = ∅. An ontology O is incoherent if
there exists an unsatisfiable concept in O.
Given two ontologies O1 and O2 , describing the same or largely overlapping
domains of interest, we can define correspondences between their elements.
Definition 1. [4] Let O1 and O2 be two ontologies, Q be a function that de-
fines sets of mappable elements Q(O1 ) and Q(O2 ). A correspondence is a 4-tuple
he, e0 , r, αi such that e ∈ Q(O1 ) and e0 ∈ Q(O2 ), r is a semantic relation, and α
is a confidence value from a suitable structure hD, ≤i, such as a lattice. Suppose
M is a set of correspondences, then M is a mapping between O1 and O2 iff for
all correspondences he, e0 , r, αi ∈ M we have e ∈ Q(O1 ) and e0 ∈ Q(O2 ).
In Definition 1, there is no restriction on function Q, semantic relation r and
domain D. In the mapping revision scenario, we often consider correspondences
between concepts and restrict r to be one of the semantic relations from the set
{≡, v, w}, and let D = [0.0, 1.0]. A mapping is a set of correspondences whose
elements are mappable.
Definition 2. [22] A distributed system is a triple D = hO1 , O2 , Mi, where O1
and O2 are ontologies and M is a mapping between them. We call O1 the source
ontology and O2 the target ontology.
Example 1. Take the two ontologies CRS and EKAW in the domain of conference
management systems as an example. They contain the following axioms:
crs : article v crs : document, crs : program v ¬crs : document,
ekaw : Paper v ekaw : Document, ekaw : Workshop Paper v ekaw : Paper
ekaw : Conference Paper v ekaw : Paper, ekaw : PC Member v ekaw : Possible Reviewer,
The correspondences in the mapping M between O1 and O2 are listed as follows:
m1 : hcrs : article, ekaw : Conference Paper, v, 0.65i
m2 : hekaw : Workshop Paper, crs : article, v, 0.65i
m3 : hekaw : Document, crs : program, v, 0.80i
m4 : hcrs : program, ekaw : Document, v, 0.80i
m5 : hcrs : document, ekaw : Document, v, 0.93i
Definition 3. [13] Let D = hO1 , O2 , Mi be a distributed system. The union
O1 ∪M O2 of O1 and O2 connected by M is defined as O1 ∪M O2 = O1 ∪ O2 ∪
{t(m) : m ∈ M} with t being a translation function that converts a correspon-
dence into an axiom in the following way: t(hC, C 0 , r, αi) = CrC 0 .
That is, we first translate all the correspondences in the mapping M into
DL axioms, then the union of the two ontologies connected by the mapping
is the set-union of the two ontologies and the translated axioms. Given D =
hO1 , O2 , Mi, we use U nion(D) to denote O1 ∪M O2 . Take a correspondence in
Example 1 as an example, we have t(hcrs:article, ekaw:Conference Paper, v, 0.65i)
= crs:article v ekaw:Conference Paper.
Definition 4. [12] Given a mapping M between two ontologies O1 and O2 , M
is consistent with O1 and O2 iff there exists no concept C in Oi with i ∈ {1, 2}
such that C is satisfiable in Oi but unsatisfiable in O1 ∪M O2 . Otherwise, M
is inconsistent. A distributed system D = hO1 , O2 , Mi is inconsistent if M is
inconsistent with O1 and O2 .
An inconsistent mapping is a mapping such that there is a concept that is satis-
fiable in a mapped ontology but unsatisfiable in the union of the two ontologies
together with the mapping. In Example 1, since ekaw:Workshop Paper is satisfi-
able in both O1 and O2 but unsatisfiable in O1 ∪M O2 , M is inconsistent. Note
that O1 ∪ O2 must be coherent if both O1 and O2 are coherent because they use
different name spaces.
Definition 5. A mapping revision operator ◦ is a function ◦hO1 , O2 , Mi =
hO1 , O2 , M0 i such that M0 ⊆ M, where O1 and O2 are two ontologies and
M is a mapping between them.
Our definition of a mapping revision operator is similar to the definition of a revi-
sion function given in [14]. When repairing the mapping in a distributed system,
we assume that ontologies are more reliable than the mapping and remove some
of correspondences in the mapping to restore consistency. This makes the prob-
lem of mapping repair like the problem of belief revision. Thus we call the prob-
lem of repairing mappings as mapping revision. This definition is very general
and allows mapping revision operators that result in unintuitive results. That is,
we can define two naive revision operators ◦F ull hO1 , O2 , Mi = hO1 , O2 , ∅i and
◦N ull hO1 , O2 , Mi = hO1 , O2 , Mi. In belief revision, the rationality of a revision
operator is often evaluated by logical postulates. In this work, we will define a
mapping revision operator and show that it can be characterized by a rational
logical postulate.
3 A Conflict-based Mapping Revision Operator
In this section, we propose a method for mapping revision based on the idea of
kernel contractions defined by Hansson in [9]. We adapt the notion of a minimal
conflict set of a distributed system given in [13] as follows.
Definition 6. Let hO1 , O2 , Mi be a distributed system. A subset C of M is
a conflict set for a concept A in Oi (i = 1, 2) if A is satisfiable in Oi but
unsatisfiable in O1 ∪C O2 . C is a minimal conflict set (MCS) for A in Oi if C is
a conflict set for A and there exists no C 0 ⊂ C which is also a conflict set for A
in Oi .
A minimal conflict set for a concept in one of the ontologies is a minimal subset
of the mapping that, together with the ontologies, is responsible for the unsat-
isfiability of the concept in the distributed system. It is similar to the notion of
a kernel in [9]. Note that if Oi (i = 1, 2) is incoherent, then it is meaningless to
define the notion of a MCS for an unsatisfiable concept. We use M CSO1 ,O2 (M)
to denote the set of all the minimal conflict sets for all unsatisfiable concepts
in O1 ∪C O2 . It corresponds to the notion of a kernel set in [9]. In Example 1,
M CSCRS,EKAW (M) = {{t(m1 ), t(m3 )}, {t(m2 ), t(m3 )}, {t(m3 ), t(m5 )}, {t(m1 ),
t(m2 ), t(m3 )}, {t(m2 ), t(m3 ), t(m5 )}}.
Hansson’s kernel contraction removes formulas in a knowledge base through
an incision function, which is a function that selects formulas to be discarded.
However, we cannot apply the notion of an incision function to mapping revision
directly because the mapping to be revised is dependent of ontologies in the
distributed system. Therefore, the problem of mapping revision is not exactly
the same as the problem of belief revision where the two knowledge bases may
come from different sources. Furthermore, each correspondence in the mapping
carries a confidence value which can be used to guide the revision.
Definition 7. An incision function σ is a function1 that for each distributed
system hO1 , O2 , Mi, we have
S
(i) σ(M CSO1 ,O2 (M)) ⊆ (M CSO1 ,O2 (M));
(ii) if ∅ 6= C ∈ M CSO1 ,O2 (M), then C ∩ σ(M CSO1 ,O2 (M)) 6= ∅;
(iii) if m = hC, C 0 , r, αi ∈ σ(M CSO1 ,O2 (M)), then there exists C ∈ M CSO1 ,O2 (M)
such that α = min{αi : hCi , C 0 i , ri , αi i ∈ C}.
1
A function is often assumed to be single-valued. However, in our definition, we do
not follow this assumption.
The first two conditions say that an incision function selects from each kernel set
at least one element. The third condition says that if a correspondence is selected
by an incision function, then there must exist a MCS C such that its confidence
value is the minimal confidence value of correspondences in C. Note that we do
not assume that a function is single-valued because it is a too strong requirement
that an incision function always selects the same set of correspondences to remove
when it is applied to the same distributed system twice.
We define our mapping revision operator based on an incision function.
Definition 8. A mapping revision operator ◦ is called a conflict-based mapping
revision operator if there exists an incision function σ such that:
◦hO1 , O2 , Mi = hO1 , O2 , M \ σ(M CSO1 ,O2 (M))i.
We provide the representation theorem for conflict-based mapping revision.
Before that, we need to define the notion of an inconsistency degree of a dis-
tributed system for a concept. Given a distributed system D = hO1 , O2 , Mi, a
concept A in Oi (i = 1, 2) is unsatisfiable in D if A is unsatisfiable in O1 ∪M O2 .
Definition 9. Given D = hO1 , O2 , Mi, the β-cut (resp. strict β-cut) set of D,
denoted as D≥β (resp. D>β ), is defined as D≥β = hO1 , O2 , {hC, C 0 , r, αi ∈ M :
α ≥ β}i (resp. D>β = hO1 , O2 , {hC, C 0 , r, αi ∈ M : α > β}i).
The β-cut set of D is a distributed system consisting of O1 , O2 and correspon-
dences in the mapping whose confidence values are greater than or equal to β.
It is adapted from the notion of cut set in possibilistic DL in [19]. In Example 1,
D>0.65 = hO1 , O2 , {t(m3 ), t(m4 ), t(m5 )}i.
Definition 10. Given D = hO1 , O2 , Mi, the inconsistency degree of D for a
concept A in Oi (i = 1, 2), denoted by Inc(D)A , is defined as Inc(D)A =
max{α : A is unsatisfiable in D≥α }. The inconsistency degree of D, denoted
as Inc(D), is defined as Inc(D) = max{α : there exists an unsatisfiable concept
in D≥α }.
It is easy to check that the inconsistency degree of a distributed system is the
maximum confidence value α such that the α-cut set of D is inconsistent under
some conditions. In Example 1, D≥0.93 is consistent but D≥0.8 is inconsistent
since ekaw:Workshop Paper is unsatisfiable. Thus, Inc(D) = 0.8.
Proposition 1. Given D = hO1 , O2 , Mi where at least one of Oi (i = 1, 2) is
coherent, suppose Inc(D) is its inconsistency degree, then we have Inc(D) =
max{α : D≥α is inconsistent}.
We give a postulate for mapping revision by generalizing the postulate (Rel-
evance) for the internal partial meet revision operator given in [8]. It says that
if a correspondence is removed from the mapping after revision, then it must be
in a conflict set of the mapping for a concept and the confidence degree attached
to it is minimal among all the confidence degrees in the conflict set.
Algorithm 1: An iterative algorithm for mapping revision
Data: A distributed system D = hO1 , O2 , Mi and a revision operator ?
Result: A repaired distributed system D? = hO1 , O2 , M? i
1 begin
2 if either O1 or O2 is incoherent then
3 return D
4 Rearrange the weights in M such that β1 >β2 >...>βl > 0;
5 Si := {t(hC, C 0 , r, αi) : hC, C 0 , r, αi∈M, α = βi }, i = 1, ..., l;
6 while M in D is inconsistent do
7 if βk = Inc(D) then
8 St := Sk \ (Sk ? (U nion(D)>βk ));
9 M := M \ {hC, C 0 , r, αi : t(hC, C 0 , r, αi) ∈ St , α = βk };
10 return D
11 end
(Relevance) suppose ◦hO1 , O2 , Mi = hO1 , O2 , M0 i, if m = hC, C 0 , r, αi ∈ M
and m 6∈ M0 , then there exist a concept A in Oi (i = 1, 2) and a subset S of M
such that A is satisfiable in hO1 , O2 , Si but is unsatisfiable in hO1 , O2 , S ∪ {m}i
and Inc(hO1 , O2 , S ∪ {m}i)A = α.
The following theorem shows that our conflict-based mapping revision oper-
ator can be characterized by the postulate (Relevance).
Theorem 1. The operator ◦ is a conflict-based mapping revision operator if and
only if it satisfies (Relevance).
Unlike revision operators given in [8], our conflict-based mapping revision oper-
ator is characterized by only one postulate. This is because the definition of a
conflict already gives some constrains on how we can repair a mapping. Accord-
ing to Definition 5, ontologies in the distributed systems are not changed and
revised mapping must be a subset of the original one. These two conditions cor-
respond to (Success) and (Inclusion) for revision operators given in [8]. Note that
the uniformity postulates in [8] which is used to ensure that a revision operator
is a single-valued function is not required for our mapping revision operator.
4 An Algorithm for Mapping Revision
In this section, we give an algorithm for mapping revision based on an ontology
revision operator and then present some concrete ontology revision operators.
4.1 Algorithm
We describe the idea of our algorithm (Algorithm 1) as follows. Given a dis-
tributed system D = hO1 , O2 , Mi, if either O1 or O2 is incoherent, then we
take D as the result of revision. That is, no change is needed. Suppose M =
{hCi , Ci0 , ri , αi i : i = 1, ..., n} where n is the number of correspondences in M.
Let us rearrange the weights of axioms in M such that β1 >β2 >...>βl > 0, where
βi (i = 1, ..., l) are all the distinct weights appearing in M. For each i ∈ {1, ..., l},
Si consists of translated axioms of correspondences in M which have the confi-
dence value βi . Suppose Inc(D) = βk . We revise Sk by U nion(D>βk ). Suppose
St is the axioms in Sk that are removed after revision of Sk by U nion(D>βk )
using the operator ?. We then remove the correspondences in M that have con-
fidence values βk and are mapped to axioms in St by the translation function t.
We iterate the revision process until the mapping becomes consistent.
In Algorithm 1, we need to compute the inconsistency degree of a distributed
system. This can be easily done by adapting the algorithm for computing the
inconsistency degree in [19] so we do not bother to provide it here.
We have not specified a revision operator in Algorithm 1. However, we require
that the revision operator ? used in the algorithm satisfy the following properties
which are similar to the postulates Inclusion, Success and core-retainment for
kernel revision operator given in [9]:
– Inclusion: O ? O0 ⊆ O ∪ O0 ;
– Success: O0 ⊆ O ? O0 ;
– Core-retainment: if φ ∈ O and φ 6∈ O ? O0 , then there exist a concept A in
O ∪ O0 and a subset Os of O, such that A is satisfiable in Os ∪ O0 but is
unsatisfiable in Os ∪ O0 ∪ {φ}.
We show that the revision operator obtained by Algorithm 1 is a conflict-
based mapping revision operator.
Theorem 2. Suppose ? satisfies Inclusion, Success and Core-retainment, and
◦ is a mapping revision operator such that, for any distributed system D, ◦(D) is
the result of Algorithm 1 with ? as an input parameter, then ◦ is a conflict-based
mapping revision operator.
4.2 Concrete revision operators
We first give a simple revision operator which is adapted from the linear base
revision operator given in [16]. By SORT we denote a procedure that for each
ontology O, arbitrarily ranks its elements as an ordered sequence (φ1 , ..., φn ).
Let O and O0 be two ontologies, and let SORT(O) = {φ1 , ..., φn }, the random
linear base revision operator, denoted as ◦linear , is defined inductively as follows
O ◦linear O0 = O0 ∪ S1 ∪ ... ∪ Sn , where Si is defined by S0 = O0 , Si = {φi } if
Si−1
{φi }∪O0 ∪ j=1 Sj is coherent, ∅ otherwise, for i ≥ 1. It is easy to check that this
revision operator satisfies conditions Inclusion, Success and Core-retainment. We
show that the algorithm given in [15] is a special case of our iterative algorithm
where the operator ◦linear is chosen.
Proposition 2. For any distributed system D = hO1 , O2 , Mi where O1 and
O2 are coherent, suppose D◦linear is the result of revision by Algorithm 1, then
D◦linear can be obtained by the algorithm given in [15] as well, and vice versa.
As shown in [15], their algorithm only needs at most n satisfiability check,
where n is the number of correspondences. Therefore, our iterative algorithm
REL REVISION(O, O0 ) CONF(C, O, O0 )
Input: Two ontologies O and O 0 Input: Two ontologies O and O 0 , and an
unsatisfiable concept C of O ∪ O 0
Output: A revised ontology O ? O 0 Output: A hitting set hs in O for C w.r.t. O 0
(1) Global : J ← ∅; (1) hs ← ∅ ;
(2) HS ← ∅; (2) while((O \ hs) ∪ O0 |= C v ⊥){
(3) for(C ∈ AllUnsatConcepts(O ∪ O0 )){ (3) J ← SINGLE CONFLICT(C, O \ hs, O0 );
(4) k ← 1; (4) J ← J ∪ {J}
(5) Ot ← hs ← ∅; (5) hs = hs ∪ {φ} for some φ ∈ J;
(6) while(sk (O ∪ O0 , C) 6= ∅){ (6) }
(7) Ot ← Ot ∪ sk (O ∪ O0 , C); (7) return hs;
(8) if(hs 6= ∅){
(9) if((O \ hs) ∪ O0 6|= C v ⊥)
(10) break;
(11) hs ← CONF(C, Ot ∩ (O \ hs), Ot ∩ O0 );
(12) HS ← HS ∪ hs;
(13) }else if(Ot |= C v ⊥){
(14) hs ← CONF(C, Ot ∩ O, Ot ∩ O0 );
(15) HS ← HS ∪ hs;
(16) }
(17) k ← k + 1;
(18) } (end while)
(19) } (end for)
(20) return (O \ HS) ∪ O0 ;
Table 1. Relevance-based mapping revision algorithm.
based on the revision operator ◦linear has a polynomial time complexity if the
satisfiability check can be done in polynomial time in the size of union of ontolo-
gies and the mapping. However, this algorithm randomly ranks correspondences
with the same confidence value, so its results may vary a lot if we run it for many
times. Furthermore, if the size of the union of ontoloiges and the mapping is big,
then the algorithm may still be inefficient because it will need a large number of
satisfiability checks over the union.
In the following, we present an algorithm REL REVISION (see Table 1) to
implement another concrete revision operator based on the relevance-based se-
lection function. The motivation behind the algorithm is that when choosing be-
tween two correspondences to remove, we always remove the one which is more
relevant to an unsatisfiable concept and thus is more likely to be problematic.
Given two axioms φ and ψ, φ is directly relevant to ψ iff there is an overlap
between the signature of φ and the signature of ψ, where the signature of an
axiom is the set of all concept names, role names and individual names appearing
in it. Based on the notion of direct relevance, we can extend it to relevance
relation between an axiom and an ontology. An axiom φ is relevant to an ontology
O iff there exists an axiom ψ in O such that φ and ψ are directly relevant.
Definition 11. Let O be an ontology, φ be an axiom and k be an integer. The
relevance-based selection function, written srel , is defined inductively as follows:
srel (O, φ, 0) = ∅
srel (O, φ, 1) = {ψ ∈ O : φ is directly relevant to ψ}
srel (O, φ, k) = {ψ ∈ O : ψ is directly relevant to srel (O, φ, k − 1)}, where k > 1.
We call srel (O, φ, k) the k-relevant subset of O w.r.t. φ. For convenience, we
define sk (O, φ) = srel (O, φ, k) \ srel (O, φ, k − 1) for k ≥ 1.
Our algorithm REL REVISION is based on Reiter’s Hitting Set Tree (HST)
algorithm [20]. Given a universal set U , and a set K = {s1 , ..., sn } of subsets
of U which are conflict sets, i.e. subsets of the system components responsible
for the error, a hitting set T for K is a subset of U such that si ∩ T 6= ∅ for all
1 ≤ i ≤ n. To adapt HST algorithm to deal with revision of ontologies in DLs,
we define the notion of a minimal conflict set of an ontology O for a concept C
w.r.t. another ontology O0 . A subset Os of O is called a minimal conflict set of
O for C w.r.t. O0 , if (1) C is unsatisfiable in Os ∪ O0 and (2) for any Ot ⊂ Os ,
C is satisfiable in Ot ∪ O0 . A more general definition of a minimal conflict set is
given in [2], where it is called a minimal axiom set.
In REL REVISION, we handle unsatisfiable concepts in the union of the
mapped ontologies and the ontology translated from the mapping one by one
until we resolve the inconsistency. For each unsatisfiable concept to be handled,
we first select axioms that are relevant to it iteratively by the relevance-based
selection function until the concept is unsatisfiable in these axioms. sk (O, C)
is the abbreviation of sk (O, C v ⊥). We find a hitting set for the selected
sub-ontologies by calling the procedure CONF and update the existing incom-
plete hitting set HS. We then add to the selected sub-ontologies those axioms
that are directly relevant to them and further expand the hitting set tree by
calling to procedure CONF. We continue this process until the inconsistency
is resolved. The procedure SINGLE CONFLICT computes a minimal conflict set
of O for C w.r.t. O0 . This kind of procedure can be found in the literature,
such as GETMUPS in [18]. It is possible that some axioms that are involved
in a conflict set are not selected by the selection function. Therefore, when
sk (O ∪ O0 , C) = ∅, we still have (O \ HS) ∪ O0 |= C v ⊥, then we set
sk (O∪O0 , C) = (O∪O0 )\srel (O∪O0 , C v ⊥, k−1). Note that our algorithm may
not remove minimal number of correspondences to resolve inconsistency because
we only expand one branch of the hitting set tree in a depth-first manner. This is
compensated by higher efficiency. Furthermore, although our algorithm does not
remove minimal number of correspondences, the removals of correspondences are
guided by a relevance-based selection function to improve the quality of removal.
It is easy to see that the revision operator obtained by REL REVISION satisfies
conditions Inclusion, Success and Core-retainment.
In REL REVISION, to resolve an unsatisfiable concept C in O ∪ O0 , we need
to compute some minimal conflict sets of O for C w.r.t. O0 . The time complexity
of REL REVISION depends on the DL under consideration. In the worst case,
i.e., all the minimal conflict sets of all the unsatisfiable concepts are disjoint, our
algorithm needs to compute all the minimal conflict sets for all the unsatisfiable
concepts, which is a hard task. For instance, the number of all the minimal
conflict sets for an unsatisfiable concept is exponential in the worst case for
lightweight ontology language EL+ [2]. However, this worst case complexity can
hardly happen. Our algorithm usually does not compute all the minimal conflict
sets for an unsatisfiable concept. Another complexity of our algorithm comes
from the computation of a minimal conflict set, which is as hard as satisfiability
checking of the underlying DL. Despite the high complexity of our algorithm,
fortunately, there is an optimization technique to improve its efficiency. That
is, for each unsatisfiable concept to be handled, we extract a so-called syntactic
locality-based module [6] from O ∪ O0 which contains all the minimal conflict
sets of O for C w.r.t. O0 . The module extraction step can be added between
line 6 and line 7 in REL REVISION. The correctness of our modified algorithm
is ensured by the fact that the locality-based module contains all the minimal
sub-ontologies of an ontology that are responsible for unsatisfiability of a concept
shown in in [21].
Example 2. To illustrate our iterative algorithm (i.e. Algorithm 1) based on
REL REVISION, we follow Example 1. First of all, we need to reorder all distinct
confidence values in a descending order β1 = 0.93 > β2 = 0.8 > β3 = 0.65
and the corresponding layers of correspondence axioms are S1 = {t(m5 )}, S2 =
{t(m3 ), t(m4 )} and S3 = {t(m1 ), t(m2 )} respectively. Then, we go into line 6
since M is inconsistent. We obtain the inconsistency degree of D as 0.8. So
k = 2. As we know that β2 = 0.8, we use U nion(D>0.8 ) to revise S2 and the
revision result is (S2 \ {t(m3 )}) ∪ U nion(D>0.8 ) according to REL REVISION (see
”Illustration of REL REVISION” below). Therefore, we remove m3 from M (see
line 9). Then we go to another iteration of the while loop. Since the modified M
becomes consistent when m3 is removed from it, the whole process of Algorithm 1
can be terminated and the result is D? = hO1 , O2 , M \ {m3 }i.
Illustration of REL REVISION: The input is O = S2 and O0 = U nion(D>0.8 ).
Suppose the first found unsatisfiable concept is article. We keep on selecting the
k-relevant axioms in O ∪ O0 w.r.t. the concept article until Ot = O ∪ O0 (i.e.
article becomes unsatisfiable in Ot ). Then we go to line 14 and get the minimal
conflict set {t(m3 )} of O w.r.t. O0 and a hitting set hs = {t(m3 )} (see ”Illustra-
tion of CONF” below). So HS = {t(m3 )}. After this, we go to another iteration
of the while loop. Since all the axioms in O have been selected, we can terminate
the process and return (S2 \ {t(m3 )}) ∪ U nion(D>0.8 ).
Illustration of CONF: The input is C = article, O = S2 and O0 =
U nion(D>0.8 ) for CONF. First of all, we compute a MCS J = {t(m3 )} in line
3. Since only one axiom in J, we get hs = {t(m3 )} in line 5. We return {t(m3 )}
and update J = {t(m3 )}.
5 Conclusions
In this paper, we discussed the problem of repairing inconsistent mappings in the
distributed systems. We first defined a conflict-based mapping revision operator
and provided a representation theorem for it. We then presented an iterative
algorithm for mapping revision in a distributed system based on a revision op-
erator in DLs and showed that this algorithm result in a conflict-based mapping
revision operator. We showed that the algorithm given in [15] can be encoded
as a special iterative algorithm. We also provided an algorithm to implement
an alternative revision operator based on the relevance-based selection function
given in [11] which can be optimized by a module extraction technique.
References
1. F. Baader, D. Calvanese, D. L. McGuinness, D. Nardi, and P. F. Patel-Schneider,
editors. The Description Logic Handbook: Theory, Implementation, and Applica-
tions. Cambridge University Press, New York, NY, USA, 2003.
2. F. Baader, R. Peñaloza, and B. Suntisrivaraporn. Pinpointing in the description
logic EL+ . In Proc. of KI, pages 52–67, 2007.
3. A. Borgida and L. Serafini. Distributed description logics: Assimilating information
from peer sources. Journal of Data Semantics, 1:153–184, 2003.
4. J. Euzenat and P. Shvaiko. Ontology Matching. Berlin; Heidelberg, Springer, 2007.
5. Peter Gardenfors. Knowledge in Flux-Modeling the Dynamic of Epistemic States.
The MIT Press, Cambridge, Mass, 1988.
6. B. Cuenca Grau, I. Horrocks, Y. Kazakov, and U. Sattler. Just the right amount:
extracting modules from ontologies. In Proc. of WWW, pages 717–726, 2007.
7. P. Haase and G. Qi. An analysis of approaches to resolving inconsistencies in
DL-based ontologies. In Proc. of IWOD, pages 97–109, 2007.
8. S. Ove Hansson. Reversing the levi identity. Journal of Philosophical Logic,
22(6):637–669, 1993.
9. S. Ove Hansson. Kernel contraction. Journal Symbolic Logic, 59(3):845–859, 1994.
10. Sven Ove Hansson. A Textbook of Belief Dynamics: Theory Change and Database
Updating. Kluwer Academic Publishers, 1999.
11. Z. Huang, F. van Harmelen, and A. ten Teije. Reasoning with inconsistent ontolo-
gies. In Proc. of IJCAI, pages 454–459, 2005.
12. C. Meilicke and H. Stuckenschmidt. Applying logical constraints to ontology
matching. In Proc. of KI, pages 99–113, 2007.
13. C. Meilicke, H. Stuckenschmidt, and A. Tamilin. Repairing ontology mappings. In
Proc. of AAAI, pages 1408–1413, 2007.
14. C. Meilicke, H. Stuckenschmidt, and A. Tamilin. Reasoning support for mapping
revision. Journal of Logic and Computation, 2008.
15. C. Meilicke, J. Völker, and H. Stuckenschmidt. Learning disjointness for debugging
mappings between lightweight ontologies. In Proc. of EKAW, pages 93–108, 2008.
16. B. Nebel. Base revision operations and schemes: Semantics, representation and
complexity. In Proc. of ECAI, pages 341–345, 1994.
17. G. Qi. A semantic approach for iterated revision in possibilistic logic. In Proc. of
AAAI, pages 523–528, 2008.
18. G. Qi, P. Haase, Z. Huang, Q. Ji, J. Z. Pan, and J. Völker. A kernel revision
operator for terminologies - algorithms and evaluation. In Proc. of ISWC, pages
419–434, 2008.
19. G. Qi, J. Z. Pan, and Qiu Ji. Extending description logics with uncertainty rea-
soning in possibilistic logic. In Proc. of ECSQARU, pages 828–839, 2007.
20. R. Reiter. A theory of diagnosis from first principles. Artificial Intelligence,
32(1):57–95, 1987.
21. B. Suntisrivaraporn, G. Qi, Q. Ji, and P. Haase. A modularization-based approach
to finding all justifications for OWL DL entailments. In Proc. of ASWC, pages
1–15, 2008.
22. A. Zimmermann and J. Euzenat. Three semantics for distributed systems and
their relations with alignment composition. In Proc. of ISWC, pages 16–29, 2006.