Traditionally, the quality of ontology matching is measured using precision 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 available. 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.
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 compliance 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 incoherence. 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 introducing 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 transformation 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 repairing 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).
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 introduces semantic precision and recall. These measures are based, roughly speaking, on comparing the (bounded) deductive closure of R and M instead of a direct comparison. Such an approach requires the use of logical reasoning where both correspondences and ontologies are considered. While Euzenat focuses on the entailment of correspondences, our approach accounts that certain combinations of correspondences result in incoherence.
Measuring mapping incoherence is closely related to measuring and repairing ontology 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 concept 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.
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 mappings 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 repairing. Thus, we distinguish between a cardinality based measure and a confidence based measure. Both measures quantify the effort of revising an incoherent mapping.
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 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 e have to be concepts or both have to be properties. We also restrict r to be ≡, or , 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 O 1 and O 2 can be defined in the context of merging O 1 and O 2 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 O 1 and O 2 as well as the correspondences of M translated into axioms of the merged ontology.
Definition 2 (Merged ontology). Let O 1 and O 2 be ontologies (finite sets of axioms). The merged ontology
with t being a translation function that maps correspondences to axioms.
Notice that in O 1 and O 2 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 O i 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 t n . Definition 3 (Natural Translation). Given correspondence c = 1#e, 2#e , r, n between ontologies O 1 and O 2 , the natural translation t n of c is defined as
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 between O 1 and O 2 is called incoherent due to t, if there exists an unsatisfiable concept
If there exists such a concept, its unsatisfiability must have (at least partially) been caused by M.
Obviously, the incoherence of a mapping is strongly affected by our choice of t. In the following we use t = t n as translation function. Notice that it is possible to define an alternative 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.
One might argue, that mapping coherence is only important in a very specific application 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 finegrained distinction has been proposed in [4], but most of these scenarios can be subsumed under one of these use cases.
-Frameworks. Mappings are described in frameworks on an abstract level independent 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 translated 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 ontology. 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.
To better understand the effects of incoherence in the context of Data Transformation let us consider the following example. Suppose there are two companies C 1 and C 2 . Both use different ontologies, say O 1 and O 2 , to describe human resources and related topics. Now it happens that C 2 takes over C 1 . C 2 decides to migrate all instance data of O 1 into O 2 . O 1 will no longer be maintained. A terminological mapping M between O 1 and O 2 has to be created to migrate the instances of O 1 to O 2 in a fully automated way.
Fragments of ontologies O 1 and O 2 are depicted in figure 1. We refer to these fragments throughout the whole section without explicitly mentioning it in the following. Data Transformation can be roughly described as the following procedure. In the following we refer to the ontology resulting from migrating instances from O i to O j based on mapping M as O j ∪ M(O i ). At first sight, mapping coherence seems to be irrelevant with respect to this use case, because we do not copy any of the terminological axioms into O j . Consider the following correspondences to understand why this impression is deceptive.
Let now mapping M contain correspondence (1) and (2 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.
1#Deadline, 2#TimedEvent, , 0.9
(3) 1#ProjectDeadline, 2#ProductLine, , 0.7
as well as 2#Event(a). Since 2#ProductLine and 2#Event are defined to be disjoint, there exists no model for O 2 ∪ M(O 1 ∪ M(O 2 )). Again, we find a strong link between mapping incoherence and inconsistency after instance migration.
In the following we revisit a variant of the example given above to better understand the use case of Query Processing. Again, company C 2 takes over C 1 . But this time both O 1 and O 2 are maintained. Instead of migrating all instances from O 1 to O 2 queries are rewritten at runtime to enable information integration between O 1 and O 2 . A terminological 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 concerned 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 knowledge 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.
, then query q can be transformed into an equivalent query by replacing all occurrences of i#C by i#D. R 2 : Let i#C and j#D be concept descriptions in the language of O i , respectively O j . If there exists a correspondence i#C , j#D, ≡, n ∈ 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 interested in the instances of ∃1#hasName −1 .1#ProjectLeader . To receive instances of both O 1 and O 2 we have to rewrite the query for O 2 . Now let M contain correspondences ( 5), (6), and ( 7).
1#hasName, 2#name, ≡, 0.9 (5) 1#Project, 2#Project, ≡, 1.0 (6) 1#manages, 2#managerOf , ≡, 0.7
Suppose that O 1 contains axiom 1#ProjectLeader ≡ ∃1#manages.1#Project. We exploit this axiom by applying R 1 . Now for every concept and property name that occurs in ∃1#hasName −1 .∃1#manages.1#Project, there exists a direct counterpart in O 2 specified in M. By applying R 2 we thus finally end with a concept description in the language of O 2 .
What happens if we process the query based on this concept description to O 2 ? 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 O 2 . 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 O 1 ∪ M t O 2 concept 1#ProjectLeader becomes unsatisfiable due to its equivalence with concept description ∃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.
The definition of mapping incoherence given above is a boolean criterion that only distinguishes between coherent and incoherent mappings. Contrary to this, an incoherence measure should satisfy m
has a higher degree of incoherence than M . At the moment we might have an intuitive understanding of different degrees of incoherence, but a precise definition has to be given in the following 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 O 1 and O 2 and let t be an translation function. An incoherence measure m t maps O 1 , O 2 , and M to a value in
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 approaches make it possible to extend the boolean property of incoherence to a continuous measure of its degree.
The first measure to be introduced is based on the idea of counting unsatisfiable concepts. 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. 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 O 1 ∪ M t O 2 which have already been unsatisfiable in O 1 , respectively O 2 , while there are unsatisfiable concepts which have been satisfiable in O 1 , respectively O 2 . 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 O 1 or O 2 .
Definition 7 (Unsatisfiability Measure). Let M be a mapping between ontologies O 1 and O 2 , and let t be a translation function. Unsatisfiability measure m t sat is defined by
This measure can be criticised for the following reason. Suppose again, we have an incoherent mapping M for ontologies O 1 and O 2 depicted in figure 1. Suppose that due to M concept 1#Person becomes unsatisfiable in the merged ontology. As a consequence 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 introduced 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.
Let O be an ontology, let T ⊆ O be the TBox of O, and let C ∈ US (O). A set T ⊆ T is a minimal unsatisfiability preserving sub-TBox (MUPS) in T for C if C is unsatisfiable in T and C is satisfiable in every T ⊂ T . 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 unsatisfiability. 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 referred to as derived unsatisfiable concept, because one reason for C 's unsatisfiability is the unsatisfiability of D. Similar to the unsatisfiability measure we can now introduce the root unsatisfiability 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 ontologies O 1 and O 2 , and let t be a translation function. Root unsatisfiability measure m t rsat is defined by
for each mapping M between two ontologies O 1 and O 2 . As argued above, the m t rsat 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.
The second type of measure is concerned with the effort of revising incoherent mappings. 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 intervention, 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. M 2 ) = 0.3. But now suppose that all of the correspondences in M 1 have the same confidence value, say 1. Contrary to this, M 2 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 correspondences. The following definition introduces the maximum trust measure which is similar to the maximum cardinality measure but accounts for differences in the confidence distribution.
Definition 12 (Maximum Trust Measure). Let M be a mapping between ontologies O 1 and O 2 , 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 m t trust is defined by
where M ⊆ M is coherent with respect to O 1 and O 2 due to t and there exists no
This measure is derived from the algorithm already described in [9] which can be used to compute M 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 \ M mainly contains incorrect correspondences given an appropriate confidence distribution. We adapted this idea to introduce the m t trust measure as confidence weighted complement to the m t card 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 detecting 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 measures can be computed in acceptable time for small and medium sized ontologies.
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 O 1 and O 2 , let R be a reference mapping between O 1 and O 2 . 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 O 1 and O 2 . Further let mapping M be incoherent and let R be coherent with respect to O 1 and O 2 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 = ∅. 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 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 proposition 2, further theoretical considerations are required.
The utility of proposition 2 in the evaluation process essentially depends on the distance between the upper bound and the actual value of mapping precision. In particular, measuring low values for the m t card 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.
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 conclusions of this work. First, we conclude that incoherence is an important aspect of mapping quality as incoherent mappings have undesirable effects on most relevant application 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 mapping 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 performance 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 Foundation (DFG) in the Emmy Noether Programme under contract STU 266/3-1.