A Con°ict-based Operator for Mapping Revision?

Abstract

Ontology matching is one of the key research topics in the ¯eld of the Semantic Web. There are many matching systems that generate mappings between di®erent ontologies either automatically or semiautomatically. However, the mappings generated by these systems may be inconsistent with the ontologies. Several approaches have been proposed 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 ¯rst propose a con°ict-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 de¯nes a con°ict-based mapping revision operator. Three concrete ontology revision operators are given to instantiate the iterative algorithm, which result in three di®erent mapping revision algorithms. We implement these algorithms and provide some preliminary but interesting evaluation results.

-

Next generation semantic applications are employed by a large number of ontologies, some of them constantly evolving. As the complexity of semantic applications 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 ontologies 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 handling 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 di®erent interpretations. For example, in Distributed Description Logics (DDL) [ 3 ], a correspondence in a mapping is translated into two bridge rules that describes the "°ow of information" from one ontology to another one. In [ 13 ], the authors deal with the problem of mapping revision in DDL by removing 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 disjointness 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 ¯rst propose a con°ict-based mapping revision operator based on the notion of a \con°ict set" which is a subset of the mapping that is in con°ict 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 iterative algorithm for mapping revision by using a revision operator in description logics and show that this algorithm results in a con°ict-based mapping revision operator. We de¯ne a revision operator and show that the iterative algorithm based on it produces the same results as the algorithm given in [ 15 ]. This speci¯c iterative algorithm has a polynomial time complexity if the satis¯ability check of an ontology can be done in polynomial time in the size of the ontology. However, this algorithm may still be ine±cient 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 satis¯ability 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 inconsistencies. To better ful¯l the principle of minimal change, we consider the revision operator given in [ 18 ] which utilizes a heuristics based on a scoring function 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 con°ict-based mapping revision operator. Finally, we implement these algorithms and provide evaluation results for comparing their e±ciency and e®ectiveness 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 con°ict-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 con¯dence 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 con°ict-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 speci¯c 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 constructors, 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 satis¯es a concept axiom C v D (resp., a role inclusion axiom R v S) if CI µDI (resp., RI µ SI ). An interpretation I is called a model of an ontology O, i® it satis¯es each axiom in O. A concept C in an ontology O is unsatis¯able if for each model I of O, CI = ;. An ontology O is incoherent if there exists an unsatis¯able concept in O.

Given two ontologies O1 and O2, describing the same or largely overlapping domains of interest, we can de¯ne correspondences between their elements. De¯nition 1. [ 4 ] Let O1 and O2 be two ontologies, Q be a function that de¯nes sets of mappable elements Q(O1) and Q(O2). A correspondence is a 4-tuple he; e0; r; ®i such that e 2 Q(O1) and e0 2 Q(O2), r is a semantic relation, and ® is a con¯dence 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 i® for all correspondences he; e0; r; ®i 2 M we have e 2 Q(O1) and e0 2 Q(O2).

In De¯nition 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 f´; v; wg, and let D = [0:0; 1:0]. A mapping is a set of correspondences whose elements are mappable.

De¯nition 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 De¯nition 3. [ 13 ] Let D = hO1; O2; Mi be a distributed system. The union O1 [M O2 of O1 and O2 connected by M is de¯ned as O1 [M O2 = O1 [ O2 [ ft(m) : m 2 Mg with t being a translation function that converts a correspondence into an axiom in the following way: t(hC; C0; r; ®i) = CrC0. That is, we ¯rst 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.

De¯nition 4. [ 12 ] Given a mapping M between two ontologies O1 and O2, M is consistent with O1 and O2 i® there exists no concept C in Oi with i 2 f1; 2g such that C is satis¯able in Oi but unsatis¯able 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¯able in a mapped ontology but unsatis¯able in the union of the two ontologies together with the mapping. In Example 1, since ekaw:Workshop Paper is satis¯able in both O1 and O2 but unsatis¯able in O1 [M O2, M is inconsistent. Note that O1 [ O2 must be coherent if both O1 and O2 are coherent because they use di®erent name spaces.

De¯nition 5. A mapping revision operator ± is a function ±hO1; O2; Mi = hO1; O2; M0i such that M0 µ M, where O1 and O2 are two ontologies and M is a mapping between them.

Our de¯nition of a mapping revision operator is similar to the de¯nition of a revision 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 problem of mapping repair like the problem of belief revision. Thus we call the problem of repairing mappings as mapping revision. This de¯nition is very general and allows mapping revision operators that result in unintuitive results. That is, we can de¯ne two naive revision operators ±F ullhO1; O2; Mi = hO1; O2; ;i and ±NullhO1; 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 de¯ne a mapping revision operator and show that it can be characterized by a rational logical postulate. 3

A Con°ict-based Mapping Revision Operator

In this section, we propose a method for mapping revision based on the idea of kernel contractions de¯ned by Hansson in [ 9 ]. We adapt the notion of a minimal con°ict set of a distributed system given in [ 13 ] as follows.

De¯nition 6. Let hO1; O2; Mi be a distributed system. A subset C of M is a con°ict set for a concept A in Oi (i = 1; 2) if A is satis¯able in Oi but unsatis¯able in O1 [C O2. C is a minimal con°ict set (MCS) for A in Oi if C is a con°ict set for A and there exists no C0 ½ C which is also a con°ict set for A in Oi.

A minimal con°ict 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 unsatis¯ability 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 de¯ne the notion of a MCS for an unsatis¯able concept. We use M CSO1;O2 (M) to denote the set of all the minimal con°ict sets for all unsatis¯able concepts in O1 [C O2. It corresponds to the notion of a kernel set in [ 9 ]. In Example 1, M CSCRS;EKAW (M) = fft(m1); t(m3)g; ft(m2); t(m3)g; ft(m3); t(m5)g; ft(m1); t(m2); t(m3 g

) ; ft(m2); t(m3); t(m5)gg.

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 di®erent sources. Furthermore, each correspondence in the mapping carries a con¯dence value which can be used to guide the revision. De¯nition 7. An incision function ¾ is a function1 that for each distributed system hO1; O2; Mi, we have (i) ¾(M CSO1;O2 (M)) µ S(M CSO1;O2 (M)); (ii) if ; 6= C 2 M CSO1;O2 (M), then C \ ¾(M CSO1;O2 (M)) 6= ;; (iii) if m = hC; C0; r; ®i 2 ¾(M CSO1;O2 (M)), then there exists C 2 M CSO1;O2 (M) such that ® = minf®i : hCi; C0i; ri; ®ii 2 Cg. 1 A function is often assumed to be single-valued. However, in our de¯nition, we do not follow this assumption.

The ¯rst 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 con¯dence value is the minimal con¯dence 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 de¯ne our mapping revision operator based on an incision function. De¯nition 8. A mapping revision operator ± is called a con°ict-based mapping revision operator if there exists an incision function ¾ such that:

±hO1; O2; Mi = hO1; O2; M n ¾(M CSO1;O2 (M))i: in D¸®g.

We provide the representation theorem for con°ict-based mapping revision. Before that, we need to de¯ne the notion of an inconsistency degree of a distributed system for a concept. Given a distributed system D = hO1; O2; Mi, a concept A in Oi (i = 1; 2) is unsatis¯able in D if A is unsatis¯able in O1 [M O2. De¯nition 9. Given D = hO1; O2; Mi, the ¯-cut (resp. strict ¯-cut) set of D, denoted as D¸¯ (resp. D>¯ ), is de¯ned as D¸¯ = hO1; O2; fhC; C0; r; ®i 2 M : ® ¸ ¯gi (resp. D>¯ = hO1; O2; fhC; C0; r; ®i 2 M : ® > ¯gi).

The ¯-cut set of D is a distributed system consisting of O1, O2 and correspondences in the mapping whose con¯dence 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; ft(m3); t(m4); t(m5)gi.

De¯nition 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 de¯ned as Inc(D)A = maxf® : A is unsatis¯able in D¸®g. The inconsistency degree of D, denoted as Inc(D), is de¯ned as Inc(D) = maxf® : there exists an unsatis¯able concept It is easy to check that the inconsistency degree of a distributed system is the maximum con¯dence 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 unsatis¯able. 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) = maxf® : D¸® is inconsistentg.

We give a postulate for mapping revision by generalizing the postulate (Relevance) 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 con°ict set of the mapping for a concept and the con¯dence degree attached to it is minimal among all the con¯dence degrees in the con°ict 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 := ft(hC; C0; r; ®i) : hC; C0; r; ®i2M; ® = ¯ig; i = 1; :::; l; 6 while M in D is inconsistent do 7 if ¯k = Inc(D) then 8 St := Sk n (Sk ? (Union(D)>¯k )); 9 M := M n fhC; C0; r; ®i : t(hC; C0; r; ®i) 2 St; ® = ¯kg; 10 11 end

return D (Relevance) suppose ±hO1; O2; Mi = hO1; O2; M0i, if m = hC; C0; r; ®i 2 M and m 62 M0, then there exist a concept A in Oi (i = 1; 2) and a subset S of M such that A is satis¯able in hO1; O2; Si but is unsatis¯able in hO1; O2; S [ fmgi and Inc(hO1; O2; S [ fmgi)A = ®.

The following theorem shows that our con°ict-based mapping revision operator can be characterized by the postulate (Relevance).

Theorem 1. The operator ± is a con°ict-based mapping revision operator if and only if it satis¯es (Relevance).

Unlike revision operators given in [ 8 ], our con°ict-based mapping revision operator is characterized by only one postulate. This is because the de¯nition of a con°ict already gives some constrains on how we can repair a mapping. According to De¯nition 5, ontologies in the distributed systems are not changed and revised mapping must be a subset of the original one. These two conditions correspond 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 distributed 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 = fhCi; Ci0; ri; ®ii : i = 1; :::; ng 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 2 f1; :::; lg, Si consists of translated axioms of correspondences in M which have the con¯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¯dence 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 speci¯ed 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 Á 2 O and Á 62 O ? O0, then there exist a concept A in O [ O0 and a subset Os of O, such that A is satis¯able in Os [ O0 but is unsatis¯able in Os [ O0 [ fÁg.

We show that the revision operator obtained by Algorithm 1 is a con°ictbased mapping revision operator.

Theorem 2. Suppose ? satis¯es 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 con°ict-based mapping revision operator. 4.2

Concrete revision operators

We ¯rst 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) = fÁ1; :::; Áng, the random linear base revision operator, denoted as ±linear, is de¯ned inductively as follows O ±linear O0 = O0 [ S1 [ ::: [ Sn, where Si is de¯ned by S0 = O0, Si = fÁig if fÁig[O0 [Sij¡=11 Sj is coherent, ; otherwise, for i ¸ 1. It is easy to check that this revision operator satis¯es 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 satis¯ability check, where n is the number of correspondences. Therefore, our iterative algorithm REL REVISION(O; O0) Input: Two ontologies O and O0 based on the revision operator ±linear has a polynomial time complexity if the satis¯ability check can be done in polynomial time in the size of union of ontologies and the mapping. However, this algorithm randomly ranks correspondences with the same con¯dence 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 ine±cient because it will need a large number of satis¯ability 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 selection function. The motivation behind the algorithm is that when choosing between two correspondences to remove, we always remove the one which is more relevant to an unsatis¯able concept and thus is more likely to be problematic.

Given two axioms Á and Ã, Á is directly relevant to à i® 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 i® there exists an axiom à in O such that Á and à are directly relevant. De¯nition 11. Let O be an ontology, Á be an axiom and k be an integer. The relevance-based selection function, written srel, is de¯ned inductively as follows: srel(O; Á; 0) = ; srel(O; Á; 1) = fà 2 O : Á is directly relevant to Ãg srel(O; Á; k) = fà 2 O : à is directly relevant to srel(O; Á; k ¡ 1)g, where k > 1.

We call srel(O; Á; k) the k-relevant subset of O w.r.t. Á. For convenience, we de¯ne sk(O; Á) = srel(O; Á; k) n 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 = fs1; :::; sng of subsets of U which are con°ict 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 de¯ne the notion of a minimal con°ict set of an ontology O for a concept C w.r.t. another ontology O0. A subset Os of O is called a minimal con°ict set of O for C w.r.t. O0, if (1) C is unsatis¯able in Os [ O0 and (2) for any Ot ½ Os, C is satis¯able in Ot [ O0. A more general de¯nition of a minimal con°ict set is given in [ 2 ], where it is called a minimal axiom set.

In REL REVISION, we handle unsatis¯able 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 unsatis¯able concept to be handled, we ¯rst select axioms that are relevant to it iteratively by the relevance-based selection function until the concept is unsatis¯able in these axioms. sk(O; C) is the abbreviation of sk(O; C v ?). We ¯nd a hitting set for the selected sub-ontologies by calling the procedure CONF and update the existing incomplete 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 con°ict 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 con°ict set are not selected by the selection function. Therefore, when sk(O [ O0; C) = ;, we still have (O n HS) [ O0 j= C v ?, then we set sk(O [O0; C) = (O [O0)nsrel(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-¯rst manner. This is compensated by higher e±ciency. 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 satis¯es conditions Inclusion, Success and Core-retainment.

In REL REVISION, to resolve an unsatis¯able concept C in O [ O0, we need to compute some minimal con°ict 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 con°ict sets of all the unsatis¯able concepts are disjoint, our algorithm needs to compute all the minimal con°ict sets for all the unsatis¯able concepts, which is a hard task. For instance, the number of all the minimal con°ict sets for an unsatis¯able 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 con°ict sets for an unsatis¯able concept. Another complexity of our algorithm comes from the computation of a minimal con°ict set, which is as hard as satis¯ability checking of the underlying DL. Despite the high complexity of our algorithm, fortunately, there is an optimization technique to improve its e±ciency. That is, for each unsatis¯able concept to be handled, we extract a so-called syntactic locality-based module [ 6 ] from O [ O0 which contains all the minimal con°ict 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 modi¯ed algorithm is ensured by the fact that the locality-based module contains all the minimal sub-ontologies of an ontology that are responsible for unsatis¯ability 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 con¯dence values in a descending order ¯1 = 0:93 > ¯2 = 0:8 > ¯3 = 0:65 and the corresponding layers of correspondence axioms are S1 = ft(m5)g, S2 = ft(m3); t(m4)g and S3 = ft(m1); t(m2)g 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 n ft(m3)g) [ 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 modi¯ed 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 n fm3gi.

Illustration of REL REVISION: The input is O = S2 and O0 = U nion(D>0:8). Suppose the ¯rst found unsatis¯able 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 unsatis¯able in Ot). Then we go to line 14 and get the minimal con°ict set ft(m3)g of O w.r.t. O0 and a hitting set hs = ft(m3)g (see "Illustration of CONF" below). So HS = ft(m3)g. 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 n ft(m3)g) [ 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 = ft(m3)g in line 3. Since only one axiom in J , we get hs = ft(m3)g in line 5. We return ft(m3)g and update J = ft(m3)g. 5

Conclusions

In this paper, we discussed the problem of repairing inconsistent mappings in the distributed systems. We ¯rst de¯ned a con°ict-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 operator in DLs and showed that this algorithm result in a con°ict-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 Applications . Cambridge University Press, New York, NY, USA, 2003 .

2. F. Baader , R. Pen~aloza, and B. Suntisrivaraporn . Pinpointing in the description logic EL+ . In Proc. of KI , pages 52 { 67 , 2007 .

3. A. Borgida and L. Sera ¯ni. 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 ontologies . 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Äolker, 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Äolker. 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 reasoning in possibilistic logic . In Proc. of ECSQARU , pages 828 { 839 , 2007 .

20. R. Reiter . A theory of diagnosis from ¯rst principles . Arti¯cial Intelligence , 32 ( 1 ): 57 { 95 , 1987 .

21. B. Suntisrivaraporn , G. Qi , Q. Ji , and P. Haase . A modularization-based approach to ¯nding all justi¯cations 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 .