Incoherence as a Basis for Measuring the Quality of Ontology Mappings Christian Meilicke and Heiner Stuckenschmidt Computer Science Institute University of Mannheim, Germany {christian,heiner}@informatik.uni-mannheim.de Abstract. Traditionally, the quality of ontology matching is measured using pre- cision and recall with respect to a reference mapping. These measures have at least two major drawbacks. First, a mapping with acceptable precision and recall might nevertheless suffer from internal logical problems that hinder a sensible use of the mapping. Second, in practical situations reference mappings are not avail- able. To avoid these drawbacks we introduce quality measures that are based on the notion of mapping incoherence that can be used without a reference mapping. We argue that these measures are a reasonable complement to the well-known measures already used for mapping evaluation. In particular, we show that one of these measures provides a strict upper bound for the precision of a mapping. 1 Introduction Assessing the quality of alignments is an important aspect of ontology matching. A number of different measures have been proposed for this purpose. According to [4] it can be distinguished between compliance measures, measures concerned with system usability, and performance measures that focus on runtime or memory requirements. A compliance measure compares a set of correspondences with a gold standard which should be the complete set of all correct correspondences. The most prominent com- pliance measures are precision and recall which have been adapted from information retrieval to the field of schema and ontology matching [1]. As complement to these measures we propose a family of measures based on the definition of mapping incoher- ence. These measures do not fall in one of the above mentioned categories, but should be categorized as formal or logic-based measures. Compared to the widely used measures of precision and recall, the measures that will be proposed in this paper do not rely on the existence of a gold standard (also referred to as reference mapping). Contrary to this, they measure internal properties of a mapping based on the semantics of the ontologies aligned via the mapping. This makes our approach applicable in matching scenarios where we do not have a gold standard. Measuring the incoherence of a mapping is motivated by the idea that the incoherence of a mapping will hinder its sensible use even though it might contain a significant amount of correct correspondences. Although we introduce incoherence as a new dimension for quantifying mapping quality, there is a non-obvious relation to traditional measures. In particular, we show that we can use one of the suggested measures to compute a strict upper bound for the precision of a mapping. This result is surprising at first sight and shows the significance of the overall approach. In the following section we discuss related work on quality measures for mappings and explain how our approach extends existing work. In section 3 we recall and refine the theory of mapping incoherence as basis for the following sections. Before introduc- ing incoherence measures, we discuss some problems caused by mapping incoherence which justify the importance of measuring incoherence (section 4). In particular, we explain the effects of incoherence with respect to the application scenario of data trans- formation and query processing. In section 5 we introduce four incoherence measures divided in two groups. Measures of the first group are concerned with the impact of incoherence, while measures of the second group are used to measure the effort of re- pairing an incoherent mapping. Finally, we show that one of these measures can be used to compute a strict upper bound for mapping precision (section 6) followed by some concluding remarks (section 7). 2 Related Work Several suggestions have been made to extend and introduce new evaluation measures to the field of ontology matching. In [2] Ehrig and Euzenat introduce relaxed precision and recall. Their work is motivated by the idea that a correspondence of a mapping M might not be totally incorrect even though it is not contained in reference mapping R. Thus, it can be measured how close a correspondence is to a similar one in R. Amongst others they suggest to measure the correction effort to transform such a correspondence into a correct one. We pick up this idea and suggest measuring incoherence based on the effort necessary to remove all causes of incoherence from M. In [3] Euzenat intro- duces semantic precision and recall. These measures are based, roughly speaking, on comparing the (bounded) deductive closure of R and M instead of a direct compari- son. Such an approach requires the use of logical reasoning where both correspondences and ontologies are considered. While Euzenat focuses on the entailment of correspon- dences, our approach accounts that certain combinations of correspondences result in incoherence. Measuring mapping incoherence is closely related to measuring and repairing on- tology incoherence. Thus, we adapted some of the measures defined by Qi and Hunter in [11]. Later we will show how to reduce the incoherence of a mapping M to con- cept unsatisfiability in an ontology that results from merging the ontologies matched via M. An obvious way of measuring mapping incoherence is thus based on counting the number of unsatisfiable concepts in the merged ontology. As proposed in [6], it can be distinguished between root and derived unsatisfiable concepts. Accordant to [11], we pick up this distinction and distinguish between two types of measuring the impact of incoherence based on concept unsatisfiability. In previous work [8, 9] we have developed and tested strategies to repair incoherent ontology mappings.1 These strategies rely on discarding individual correspondences from an incoherent mapping M to finally arrive at a coherent submapping M∗ ⊆ M. 1 Notice that in previous work we misleadingly used the notion of inconsistency instead of incoherence. Precise definitions of these notions are given in [5]. Clearly, such a strategy should remove a minimal set of correspondences. This approach leads to an incoherence measure that indicates the effort of repairing incoherent map- pings in numbers of correspondences to be removed. Moreover, it has been emphasized that the confidence value of a correspondence plays an important role in mapping re- pairing. Thus, we distinguish between a cardinality based measure and a confidence based measure. Both measures quantify the effort of revising an incoherent mapping. 3 Foundations According to Euzenat and Shvaiko [4] a correspondence can be defined as a semantic relation between ontological entities annotated with a confidence value. Definition 1 (Correspondence and Mapping). Given ontologies O1 and O2 , let Q be a function that defines sets of matchable elements Q(O1 ) and Q(O2 ). A correspondence between O1 and O2 is a 4-tuple he, e0 , r, ni such that e ∈ Q(O1 ) and e0 ∈ Q(O2 ), r is a semantic relation, and n is a confidence value from a suitable structure hD, 6i. A mapping between O1 and O2 is a set of correspondences between O1 and O2 . Definition 1 allows to capture a wide class of correspondences by varying what is admissible as matchable element, semantic relation, and confidence value. In this work we consider correspondences between named concepts and properties. We also restrict correspondences to match entities of the same type, i.e. both e and e0 have to be concepts or both have to be properties. We also restrict r to be ≡, v or w, i.e. we only focus on equivalence and subsumption correspondences. Finally, we assume that the confidence value, which can be seen as a measure of trust in the fact that the correspondence holds, is represented numerically on D = [0.0, 1.0]. As argued in [8] and [9] the semantics of a mapping M between ontologies O1 and O2 can be defined in the context of merging O1 and O2 via M. In this section we focus on technical aspects and postpone the discussion on adequacy and implications to the next section. A merged ontology contains the axioms of O1 and O2 as well as the correspondences of M translated into axioms of the merged ontology. Definition 2 (Merged ontology). Let O1 and O2 be ontologies (finite sets of axioms). The merged ontology O1 ∪Mt O2 of O1 and O2 connected by M is defined as O1 ∪Mt O2 = O1 ∪ O2 ∪ {t(x) | x ∈ M} with t being a translation function that maps correspondences to axioms. Notice that in O1 and O2 a concept or property might have the same local name. To refer without ambiguity in the context of a merged ontology to an entity e which origins from Oi we use prefix notation i#e in the following. There is a straightforward way to translate concept correspondences and property correspondences into DL axioms. We refer to the corresponding translation function as natural translation tn . Definition 3 (Natural Translation). Given correspondence c = h1#e, 2#e 0 , r, ni be- tween ontologies O1 and O2 , the natural translation tn of c is defined as  1#e ≡ 2#e 0 if r =≡  tn (c) 7→ 1#e v 2#e 0 if r =v 1#e w 2#e 0 if r =w  Now let us briefly recall the notion of ontology incoherence. An ontology O is incoherent, iff there exist an unsatisfiable concept in O. Analogous, a mapping M be- tween O1 and O2 is called incoherent due to t, if there exists an unsatisfiable concept i#Ci∈{1,2} in O1 ∪Mt O2 that is satisfiable in Oi . If there exists such a concept, its unsatisfiability must have (at least partially) been caused by M. Definition 4 (Incoherence of a Mapping). Given a mapping M between ontologies O1 and O2 and a translation function t. If there exists a concept i#C with i ∈ {1, 2} such that O1 ∪Mt O2 |= ⊥ w i#C and Oi 6|= ⊥ w i#C then M is incoherent with respect to O1 and O2 due to t. Otherwise M is coherent with respect to O1 and O2 due to t. Obviously, the incoherence of a mapping is strongly affected by our choice of t. In the following we use t = tn as translation function. Notice that it is possible to define an al- ternative translation function. In particular, it will turn out that the measures introduced in section 5 are independent of this choice with respect to their applicability, although their results are affected by the choice of the translation function. 4 The Importance of Mapping Coherence One might argue, that mapping coherence is only important in a very specific appli- cation scenario like reasoning in a merged ontology. In the following we show that incoherence has a negative effect on a wide range of relevant applications. In [10] four different purposes of using ontology mappings have been distinguished. A more fine- grained distinction has been proposed in [4], but most of these scenarios can be sub- sumed under one of these use cases. – Frameworks. Mappings are described in frameworks on an abstract level indepen- dent of an intended use. – Terminological Reasoning. Mappings are used to perform reasoning across aligned ontologies. – Data Transformation. Data from one ontology is transferred into the terminology of another ontology based on the knowledge encoded in a mapping. – Query Processing. Queries formulated with respect to a certain ontology are trans- lated into the terminology of a different ontology. The Frameworks use case is about describing mappings on an abstract level. Since we try to argue for the applicability of our approach in a practical context, it is of minor interest and will not be discussed. It is obvious that incoherence is undesirable in the Terminological Reasoning case as incoherence will lead to inconsistency of the whole ontology when instances are added to unsatisfiable concepts. Inconsistency, however, disables meaningful reasoning as everything can be derived from an inconsistent on- tology. It is less obvious that coherence is important for the Data Transformation and Query Processing use cases. In the following, we show that an incoherent mapping will lead to serious errors in the context of data translation and query processing. 4.1 Data Transformation To better understand the effects of incoherence in the context of Data Transformation let us consider the following example. Suppose there are two companies C1 and C2 . Both use different ontologies, say O1 and O2 , to describe human resources and related topics. Now it happens that C2 takes over C1 . C2 decides to migrate all instance data of O1 into O2 . O1 will no longer be maintained. A terminological mapping M between O1 and O2 has to be created to migrate the instances of O1 to O2 in a fully automated way. Fragments of ontologies O1 and O2 are depicted in figure 1. We refer to these frag- ments throughout the whole section without explicitly mentioning it in the following. Data Transformation can be roughly described as the following procedure. 1. For all instances a of O1 create a copy a0 of this instance in O2 . 2. For all concept correspondences h1#e, 2#e 0 , r, ni ∈ M with r ∈ {≡, v} and for all instances a with O1 |= 1#e(a) add axiom 2#e 0 (a0 ) to O2 . 3. For all property correspondences h1#e, 2#e 0 , r, ni ∈ M with r ∈ {≡, v} and for all instances a, b with O1 |= 1#e(a, b) add axiom 2#e 0 (a0 , b0 ) to O2 . In the following we refer to the ontology resulting from migrating instances from Oi to Oj based on mapping M as Oj ∪ M(Oi ). At first sight, mapping coherence seems to be irrelevant with respect to this use case, because we do not copy any of the termi- nological axioms into Oj . Consider the following correspondences to understand why this impression is deceptive. h1#Person, 2#Person, ≡, 1.0i (1) h1#ProjectLeader , 2#Project, v, 0.6i (2) Let now mapping M contain correspondence (1) and (2). M is incoherent, due to the fact that in O1 ∪Mt O2 concept 1#ProjectLeader becomes unsatisfiable. Concepts 2#Project and 2#Person are disjoint and due to M concept 1#ProjectLeader is subsumed by both of them, resulting in its unsatisfiability. Suppose now, there exists an instance a with 1#ProjectLeader (a). Applying the migration rules results in a new in- stance a0 with 2#Project(a0 ) and 2#Person(a0 ). Due to the disjointness of 2#Project and 2#Person there exists no model for O2 ∪ M(O1 ) and thus O2 ∪ M(O1 ) is an inconsistent ontology. Opposed to our first impression there seems to be a tight link between the incoherence of M and the inconsistency of O2 ∪ M(O1 ). Contrary to this, mappings can be constructed, where such a direct link cannot be detected. Let M, for example, contain correspondences (3) and (4). M is incoherent due to the unsatisfiability of 2#ProductLine in the merged ontology. h1#Deadline, 2#TimedEvent, v, 0.9i (3) h1#ProjectDeadline, 2#ProductLine, w, 0.7i (4) Now we have to acknowledge that both O2 ∪ M(O1 ) and O1 ∪ M(O2 ) do not become inconsistent. But what happens if we first transfer all instances x of O2 to O1 ∪ M(O2 ) and then again transfer the x0 instances of O1 ∪ M(O2 ) to O2 ∪ M(O1 ∪ M(O2 ))? Fig. 1. Fragments of ontologies O1 (on the left) and O2 (on the right). A square represents a concept, an ellipse a property, subsumption is represented by indentation. Domain and range of a property are restricted to be the concepts connected by the accordant arrow. Dashed horizontal lines represent disjointness between concepts. Given some instance a with O2 |= 2#ProductLine(a) after the first step we have the counterpart of a, namely a0 , with O1 ∪ M(O2 ) |= 1#ProjectDeadline(a0 ) by ap- plying correspondence (4) and can derive O1 ∪ M(O2 ) |= 1#Deadline(a0 ). After the second step we have O2 ∪ M(O1 ∪ M(O2 )) |= 2#TimedEvent(a00 ) by applying cor- respondence (3). We expect that adding axiom a = a00 does not affect the consistency of O2 ∪ M(O1 ∪ M(O2 )). But O2 ∪ M(O1 ∪ M(O2 )) now implies 2#ProductLine(a) as well as 2#Event(a). Since 2#ProductLine and 2#Event are defined to be disjoint, there exists no model for O2 ∪ M(O1 ∪ M(O2 )). Again, we find a strong link between mapping incoherence and inconsistency after instance migration. 4.2 Query Processing In the following we revisit a variant of the example given above to better understand the use case of Query Processing. Again, company C2 takes over C1 . But this time both O1 and O2 are maintained. Instead of migrating all instances from O1 to O2 queries are rewritten at runtime to enable information integration between O1 and O2 . A termino- logical mapping is the key for information integration. It is used for processing queries and generating result sets which contain data from both ontologies. As we are con- cerned with theoretical issues, we argue on an abstract level instead of discussing e.g. characteristics of a SPARQL implementation. A query language for DL based knowl- edge bases should at least support instance retrieval for complex concept descriptions. Depending on the concrete query language there might be a complex set of rewriting rules. At least, it must contain variants of the following two rules. R1 : Let i#C and i#D be concept descriptions in the language of Oi . If Oi |= i#C ≡ i#D, then query q can be transformed into an equivalent query by replacing all occurrences of i#C by i#D. R2 : Let i#C and j#D be concept descriptions in the language of Oi , respectively Oj . If there exists a correspondence hi#C , j#D, ≡, ni ∈ M, then query q can be transformed into an equivalent query by replacing all occurrences of i#C by j#D. Suppose we query for the name of all project leaders, formally speaking we are inter- ested in the instances of ∃1#hasName −1 .1#ProjectLeader . To receive instances of both O1 and O2 we have to rewrite the query for O2 . Now let M contain correspon- dences (5), (6), and (7). h1#hasName, 2#name, ≡, 0.9i (5) h1#Project, 2#Project, ≡, 1.0i (6) h1#manages, 2#managerOf , ≡, 0.7i (7) Suppose that O1 contains axiom 1#ProjectLeader ≡ ∃1#manages.1#Project. We exploit this axiom by applying R1 . Now for every concept and property name that occurs in ∃1#hasName −1 .∃1#manages.1#Project, there exists a direct counterpart in O2 specified in M. By applying R2 we thus finally end with a concept description in the language of O2 . ∃1#hasName −1 .1#ProjectLeader (8) R1 −1 ⇐⇒ ∃1#hasName .∃1#manages.1#Project (9) R2 −1 ⇐⇒ ∃2#name .∃2#managerOf .2#Project (10) What happens if we process the query based on this concept description to O2 ? As result we receive the empty set. The range of 2#managerOf is concept 2#ProductLine, and 2#ProductLine is defined to be disjoint with 2#Project. Thus, for logical reasons there exists no instance of concept description (10) in O2 . This problem is obviously caused by the incorrectness of correspondence (7). But the incorrectness of (7) does not only affect the query under discussion. It also causes mapping M to become incoherent, because in the merged ontology O1 ∪Mt O2 con- cept 1#ProjectLeader becomes unsatisfiable due to its equivalence with concept de- scription ∃1#manages.1#Project. This time we find a strong link between mapping incoherency and the incorrectness of a query result due to processing the mapping. 5 Measuring Incoherence The definition of mapping incoherence given above is a boolean criterion that only dis- tinguishes between coherent and incoherent mappings. Contrary to this, an incoherence measure should satisfy m(O1 , O2 , M) > m(O1 , O2 , M0 ) if M has a higher degree of incoherence than M0 . At the moment we might have an intuitive understanding of different degrees of incoherence, but a precise definition has to be given in the follow- ing subsections. Up to now, we define an incoherence measure to satisfy the following constraint. Definition 5 (Incoherence Measure). Let M be a mapping between ontologies O1 and O2 and let t be an translation function. An incoherence measure mt maps O1 , O2 , and M to a value in [0, 1] such that mt (O1 , O2 , M) = 0 iff M is coherent with respect to O1 and O2 due to t. In the following we distinguish between effect-based and revision-based measures. The former are concerned with the negative impact of mapping incoherence. The latter measure the effort necessary to revise a mapping by removing incoherences. Both ap- proaches make it possible to extend the boolean property of incoherence to a continuous measure of its degree. 5.1 Measuring the Impact of Incoherence The first measure to be introduced is based on the idea of counting unsatisfiable con- cepts. It is an adaption of an ontology incoherence measure introduced in [11]. Before we proceed, we need to agree on some abbreviations and naming conventions. Definition 6. Let O be an ontology. Then CO(O) refers to the set of named concepts in O and US (O) = {C ∈ CO(O) | O |= C v ⊥} refers to the set of unsatisfiable concepts in O. Contrary to measuring incoherences in ontologies, we have to distinguish between two types of concept unsatisfiability in the merged ontology: There are unsatisfiable concepts in O1 ∪Mt O2 which have already been unsatisfiable in O1 , respectively O2 , while there are unsatisfiable concepts which have been satisfiable in O1 , respectively O2 . We are interested in the latter concepts. In particular, we compare the number of these concepts with the number of all named concepts satisfiable in O1 or O2 . Definition 7 (Unsatisfiability Measure). Let M be a mapping between ontologies O1 and O2 , and let t be a translation function. Unsatisfiability measure mtsat is defined by |US (O1 ∪Mt O2 ) \ (US (O1 ) ∪ US (O2 ))| mtsat (O1 , O2 , M) = |CO(O1 ∪Mt O2 ) \ (US (O1 ) ∪ US (O2 ))| This measure can be criticised for the following reason. Suppose again, we have an incoherent mapping M for ontologies O1 and O2 depicted in figure 1. Suppose that due to M concept 1#Person becomes unsatisfiable in the merged ontology. As a conse- quence concept 1#ProjectLeader becomes unsatisfiable, too. By applying definition 7 we thus measure both direct impact (unsatisfiability of 1#Person) and indirect impact (unsatisfiability of 1#ProjectLeader ) of M, even though we might only be interested in the direct impact. The distinction between root and derived unsatisfiability, as intro- duced in [6], solves this problem. A precise definition requires us to recall the notion of a MUPS, defined in [12], which is minimal unsatisfiability preserving sub-TBox. Definition 8 (MUPS). Let O be an ontology, let T ⊆ O be the TBox of O, and let C ∈ US (O). A set T 0 ⊆ T is a minimal unsatisfiability preserving sub-TBox (MUPS) in T for C if C is unsatisfiable in T 0 and C is satisfiable in every T 00 ⊂ T 0 . The set of all MUPS with respect to C is referred to as mups(O, C ). A MUPS for a concept C can be seen as a minimal explanation of its unsatisfi- ability. Whenever there exists another unsatisfiable concept D such that the minimal explanation of C ’s unsatisfiability also explains the unsatisfiability of D then C is re- ferred to as derived unsatisfiable concept, because one reason for C ’s unsatisfiability is the unsatisfiability of D. Definition 9 (Derived and Root Unsatisfiability). Let O be an ontology and let C ∈ US (O). C is a derived unsatisfiable concept if there exists D 6= C ∈ US (O) such that there exist M ∈ mups(O, C ) and M 0 ∈ mups(O, D) with M ⊇ M 0 . Otherwise C is a root unsatisfiable concept. The set of derived unsatisfiable concepts of O is referred to as US D (O) and the set of root unsatisfiable concepts is referred to as US R (O). Similar to the unsatisfiability measure we can now introduce the root unsatisfiabil- ity measure by considering only root unsatisfiable concepts instead of all unsatisfiable concepts in the merged ontology. Definition 10 (Root Unsatisfiability Measure). Let M be a mapping between ontolo- gies O1 and O2 , and let t be a translation function. Root unsatisfiability measure mtrsat is defined by |US R (O1 ∪Mt O2 ) \ (US (O1 ) ∪ US (O2 ))| mtrsat (O1 , O2 , M) = |CO(O1 ∪Mt O2 ) \ (US (O1 ) ∪ US (O2 ))| Obviously, we have mtsat (O1 , O2 , M) ≥ mtrsat (O1 , O2 , M) for each mapping M between two ontologies O1 and O2 . As argued above, the mtrsat measure has to be preferred. Nevertheless, a non trivial algorithm is required to compute the set of root unsatisfiable concepts as described in [6] which makes the application of this measure more expensive from a computational point of view. 5.2 Measuring the Effort of Mapping Revision The second type of measure is concerned with the effort of revising incoherent map- pings. We use the term revision to describe the process of removing correspondences from an incoherent mapping until a coherent submapping has been found. If a revision is conducted by a domain expert we would, for example, be able to measure the time necessary. Since we want our measure to be computable without any human interven- tion, we thus have to think of an automated strategy to revise a mapping. Such a strategy should obviously remove a minimum number of correspondences, because we would like to keep as much information in the mapping as possible. The following measure is based on this idea and compares the number of correspondences that would be removed by such a strategy with the number of all correspondences in the mapping. Definition 11 (Maximum Cardinality Measure). Let M be a mapping between on- tologies O1 and O2 , and let t be a translation function. Maximum cardinality measure mtcard is defined by |M \ M0 | mtcard (O1 , O2 , M) = |M| where M0 ⊆ M is coherent with respect to O1 and O2 due to t and there exists no M00 ⊆ M with |M00 | > |M0 | such that M00 is coherent with respect to O1 and O2 due to t. Suppose there are incoherent mappings M1 and M2 with |M1 | = |M2 | = 10. Fur- ther suppose, according to the naming convention in definition 11, we have |M01 | = 8 and |M02 | = 7. Thus, we have mtcard (O1 , O2 , M1 ) = 0.2 and mtcard (O1 , O2 , M2 ) = 0.3. But now suppose that all of the correspondences in M1 have the same confidence value, say 1. Contrary to this, M2 differs with respect to the confidence value of its correspondences. In particular, it turns out that all of the three correspondences that have been removed have a very low confidence value compared to the remaining corre- spondences. The following definition introduces the maximum trust measure which is similar to the maximum cardinality measure but accounts for differences in the confi- dence distribution. Definition 12 (Maximum Trust Measure). Let M be a mapping between ontologies O1 and O2 , and let t be a translation function. Further, let conf : M → [0, 1] be a function that maps a correspondence on its confidence value. Maximum trust measure mttrust is defined by P conf (c) c∈M\M0 mttrust (O1 , O2 , M) = P conf (c) c∈M where M0 ⊆ MP P to O1 and O2 due to t and there exists no is coherent with respect M00 ⊆ M with c∈M00 conf (c) > c∈M0 conf (c) such that M00 is coherent with respect to O1 and O2 due to t. This measure is derived from the algorithm already described in [9] which can be used to compute M0 for a specific type of mappings. Namely, one-to-one mappings that contain only correspondences expressing equivalences between concepts. We also used it in the context of mapping extraction [8]. Its application is motivated by the idea that M \ M0 mainly contains incorrect correspondences given an appropriate confi- dence distribution. We adapted this idea to introduce the mttrust measure as confidence weighted complement to the mtcard measure. Notice that computing both of these measures requires to solve computational hard problems. On the one hand only full-fledged reasoning guarantees completeness in de- tecting unsatisfiability. On the other hand the underlying problem is the optimization problem of finding a hitting set H ⊆ M of minimal cardinality (respectively minimal confidence total) over the set all of minimal incoherent subsets of M. This problem is known to be NP-complete [7]. Nevertheless, first experiments indicate that both mea- sures can be computed in acceptable time for small and medium sized ontologies. 6 Truth and Coherence In the following we are concerned with an important interrelation between the classical compliance measure of precision and the maximum cardinality measure of incoherence. Philosophically speaking, we are interested in how far an incoherent mapping can truly express semantic relations between ontological entities. Accordant to [1], the precision of a mapping can be defined as follows. Definition 13 (Precision). Given a mapping M between ontologies O1 and O2 , let R be a reference mapping between O1 and O2 . The precision of M with respect to R is defined as precision(M, R) = |M ∩ R| / |M|. In section 4 we argued that an incoherent mapping M causes different kinds of problems when applied in a realistic scenario. More precisely, it is the incorrectness of a correspondence that causes both the problem as well as the incoherence. Even though incorrect correspondences not necessarily result in incoherence, we can be sure that an incoherent mapping contains at least one incorrect correspondence. Thus, a well-modeled reference mapping R will be coherent due to each translation function t compatible with the mapping semantics accepted by the person who created R. The following proposition corresponds to this consideration. Proposition 1 (Incoherence and Precision). Let R be a reference mapping between O1 and O2 . Further let mapping M be incoherent and let R be coherent with respect to O1 and O2 due to translation function t. Then we have precision(M, R) < 1. Proof. Given the coherence of R, it can be concluded that every subset of R is coherent, too. Since M is incoherent, it is thus no subset of R, i.e M \ R 6= ∅. We conclude that M ∩ R ⊂ M. It follows directly precision(M, R) < 1. Notice that automatically generated mappings normally do not have a precision of 1. Thus, the application of proposition 1 is only of limited benefit. Nevertheless, it can be generalized in a non trivial way by exploiting the definition of the maximum cardinality measure (definition 11). This generalization allows us to compute a non trivial upper bound for mapping precision without any knowledge of R. Proposition 2 (Upper Bound for Precision). Let M be a mapping and R be a refer- ence mapping between O1 and O2 . Further let R be coherent with respect to O1 and O2 due to translation function t. Then we have precision(M, R) ≤ 1−mtcard (O1 , O2 , M). Proof. Accordant to definition 11 let M0 ⊆ M be the coherent subset of M with maximum cardinality. Further let be M∗ = M ∩ R, i.e. M∗ consist of all correct correspondences in M. Since M∗ is a subset of R and R is coherent with respect to O1 and O2 due to t, we conclude that M∗ is also coherent. It follows that |M∗ | ≤ |M0 |, because otherwise M0 would not be the coherent submapping of maximum cardinality contrary to definition 11. In summary, the following inequation holds. |M ∩ R| |M∗ | |M0 | |M0 \ M| precision(M, R) = = < =1− = mtcard (O1 , O2 , M) |M| |M| |M| |M| Proposition 2 reveals an important interrelation between coherence and precision. The counterpart of mapping precision is the measure of recall. At first glimpse it seems that recall and coherence describe independent properties of a mapping. Nevertheless, there exists a non trivial relation between recall and coherence that allows to derive comparative statements about the relative recall of two overlapping mappings in some cases. Although this interrelation is not as significant as the the one expressed in propo- sition 2, further theoretical considerations are required. The utility of proposition 2 in the evaluation process essentially depends on the dis- tance between the upper bound and the actual value of mapping precision. In particular, measuring low values for the mtcard measure will lead to a poor differentiation with respect to the precision that has to be expected. In initial experiments, not included in this paper due to lack of space, first results indicate that the upper bound for mapping precision strongly varies and can be used to filter out highly imprecise mappings. 7 Conclusion In this paper, we have discussed the notion of incoherence of ontology mappings and its role in the assessment of automatically created mappings. There are two main con- clusions of this work. First, we conclude that incoherence is an important aspect of mapping quality as incoherent mappings have undesirable effects on most relevant ap- plication scenarios as we have demonstrated in section 4. Second, appropriate measures of incoherence can help to assess the quality of a mapping even if no reference map- ping is available and thus precision and recall cannot be determined. In particular, the measure of incoherence provided in definition 11 provides a strict upper bound for the precision of a mapping and can therefore be used as a guideline for estimating the per- formance of matching systems. In future work experimental studies will show in how far the proposed measures can be effectively applied in the evaluation process.2 Acknowledgement The work has been partially supported by the German Science Foun- dation (DFG) in the Emmy Noether Programme under contract STU 266/3-1. References 1. Hong-Hai Do, Sergey Melnik, and Erhard Rahm. Comparison of schema matching evalua- tions. In Proc. of the GI-Workshop Web and Databases, Erfurt, Germany, 2002. 2. Marc Ehrig and Jerome Euzenat. Relaxed precision and recall for ontology matching. In Proc. of the K-Cap 2005 Workshop on Integrating Ontology, Banff, Canada, 2005. 3. Jerome Euzenat. Semantic precision and recall for ontology alignment evaluation. In Proc. of th 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, 2007. 4. Jerome Euzenat and Pavel Shvaiko. Ontology Matching. Springer, 2007. 5. Peter Haase and Guilin Qi. An analysis of approaches to resolving inconsistencies in DL- based ontologies. In Proc. of the International Workshop on Ontology Dynamics, Innsbruck, Austria, 2007. 6. Aditya Kalyanpur, Bijan Parsia, Evren Sirin, and James Hendler. Debugging unsatisfiable classes in OWL ontologies. Journal of Web Semantics, 2005. 7. Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations. Plenum, 1972. 8. Christian Meilicke and Heiner Stuckenschmidt. Analyzing mapping extraction approaches. In Proc. of the ISWC 2007 Workshop on Ontology Matching, Busan, Korea, 2007. 9. Christian Meilicke and Heiner Stuckenschmidt. Applying logical constraints to ontology matching. In Proc. of the 30th German Conference on Artificial Intelligence, Osnabrück, Germany, 2007. 10. Natasha Noy and Heiner Stuckenschmidt. Ontology alignment: An annotated bibliography. In Semantic Interoperability and Integration, Dagstuhl, Germany, 2005. 11. Guilin Qi and Anthony Hunter. Measuring incoherence in description logic-based ontologies. In Proc. of the 6th International Semantic Web Conference, 2007. 12. Stefan Schlobach and Ronald Cornet. Non-standard reasoning services for the debugging of description logic terminologies. In Proc. of 18th International Joint Conference on Artificial Intelligence, Acapulco, Mexico, 2003. 2 A first beta-version of our system supporting the measures mtsat , mtcard , and mttrust based on a slightly modified natural translation can be obtained on request.