Ontology matching is one of the key research topics in the field of the Semantic Web. There are many matching systems that generate mappings between different 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 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 instantiate the iterative algorithm, which result in three different 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 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 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 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 iterative 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 specific 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 inconsistencies. To better fulfil 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 conflict-based mapping revision operator. Finally, we implement these algorithms and provide evaluation results for comparing their efficiency and effectiveness in Section 5.
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.
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 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 R S, where R and S are (possibly complex) role descriptions built from a set of role names and some constructors.
An interpretation I = ( I , • I ) consists of a non-empty domain set I 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 D (resp., a role inclusion axiom 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 {≡, , }, and let D = [0.0, 1.0]. A mapping is a set of correspondences whose elements are mappable.
: m ∈ M} with t being a translation function that converts a correspondence into an axiom in the following way:
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. Definition 4. [12] Given a mapping M between two ontologies
An inconsistent mapping is a mapping such that there is a concept that is satisfiable 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-
where O 1 and O 2 are two ontologies and M is a mapping between them.
Our definition of a mapping revision operator is similar to the definition 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 definition is very general and allows mapping revision operators that result in unintuitive results. That is, we can define two naive revision operators
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.
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.
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 unsatisfiability of the concept in the distributed system. It is similar to the notion of a kernel in [9]. Note that if O i (i = 1, 2) is incoherent, then it is meaningless to define the notion of a MCS for an unsatisfiable concept. We use M CS O1,O2 (M) to denote the set of all the minimal conflict sets for all unsatisfiable concepts in O 1 ∪ C O 2 . It corresponds to the notion of a kernel set in [9]. In Example 1,
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.
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:
We provide the representation theorem for conflict-based mapping revision. Before that, we need to define the notion of an inconsistency degree of a distributed system for a concept. Given a distributed system
The β-cut set of D is a distributed system consisting of O 1 , O 2 and correspondences 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, 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.
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 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.
Data:
The following theorem shows that our conflict-based mapping revision operator can be characterized by the postulate (Relevance).
Unlike revision operators given in [8], our conflict-based mapping revision operator 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. According 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 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.
In this section, we give an algorithm for mapping revision based on an ontology revision operator and then present some concrete ontology revision operators.
We describe the idea of our algorithm (Algorithm 1) as follows. Given a dis-
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}, S i consists of translated axioms of correspondences in M which have the confidence value β i . Suppose Inc(D) = β k . We revise S k by U nion(D >β k ). Suppose S t is the axioms in S k that are removed after revision of S k by U nion(D >β k ) using the operator . We then remove the correspondences in M that have confidence values β k and are mapped to axioms in S t 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]:
We show that the revision operator obtained by Algorithm 1 is a conflictbased mapping revision operator.
• 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.
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 O be two ontologies, and let SORT(O) = {φ 1 , ..., φ n }, the random linear base revision operator, denoted as • linear , is defined inductively as follows
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 = O 1 , O 2 , M where O 1 and O 2 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 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 ontologies 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 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 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 s rel , is defined inductively as follows:
We call s rel (O, φ, k) the k-relevant subset of O w.r.t. φ. For convenience, we define
Our algorithm REL REVISION is based on Reiter's Hitting Set Tree (HST) algorithm [20]. Given a universal set U , and a set K = {s 1 , ..., s n } 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 s i ∩ T = ∅ 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. [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. s k (O, C) is the abbreviation of s k (O, C ⊥). We find 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 conflict set of O for C w.r.t. O . 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
⊥, then we set s k (O∪O , C) = (O∪O )\s rel (O∪O , C ⊥, 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 ∪ O , we need to compute some minimal conflict sets of O for C w.r.t. O . 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 ∪ O which contains all the minimal conflict sets of O for C w.r.t. O . 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 S 1 = {t(m 5 )}, S 2 = {t(m 3 ), t(m 4 )} and S 3 = {t(m 1 ), t(m 2 )} 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 S 2 and the revision result is (S 2 \ {t(m 3 )}) ∪ U nion(D >0.8 ) according to REL REVISION (see "Illustration of REL REVISION" below). Therefore, we remove m 3 from M (see line 9). Then we go to another iteration of the while loop. Since the modified M becomes consistent when m 3 is removed from it, the whole process of Algorithm 1 can be terminated and the result is
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 operator 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.
This work is partially supported by the EU in the IST project NeOn (http://www.neon-project.org/).
(1) hs ← ∅ ; (2) HS ← ∅;
(2) while(
Ot ← hs ← ∅;
(5) hs = hs ∪ {φ} for some φ ∈ J;