State of the art ontology matching techniques are limited to detect simple correspondences between atomic concepts and properties. Nevertheless, for many concepts and properties atomic counterparts will not exist, while it is possible to construct equivalent complex concept and property descriptions. We define a correspondence where at least one of the linked entities is non-atomic as complex correspondence. Further, we introduce several patterns describing complex correspondences. In particular, we focus on methods for automatically detecting complex correspondences. These methods are based on a combination of basic matching techniques. We conduct experiments with different datasets and discuss the results.
or property description, is referred to as complex correspondence in the following. As
main contribution of this paper we suggest an automated pattern based approach to
detect certain types of complex correspondences and study its performance by applying
it on different datasets. Even though different researchers were concerned with similar
topics (see [
We first discuss related work centered around the notion of a complex correspondence in Section 2. We then present four patterns of complex correspondences in Section 3. In Section 4 we suggest the algorithms we designed to detect occurrences of these patterns. Each of these algorithms is described as a conjunction of conditions, which are easy to check by basic matching techniques. In Section 5 we apply the algorithms on two datasets from the OAEI and show that the proposed techniques can be used to detect a significant amount of complex correspondences. We end with a conclusion in Section 6. 2
Complex matching is a well known topic in database schema matching. In [
In [
In [
Furthermore, in [
Regarding ontology matching, there are a few matchers trying to find complex
correspondences based on machine learning approaches (see [
In the following we propose four patterns for complex correspondences that, due to a preparatory study, we expect to occur frequently within ontology matching problems. We first report about our preparatory study, followed by a detailed presentation of each pattern. Each pattern is also explained by an example depicted in Figure 1. Without explicitly mentioning it, we will refer to Figure 1 throughout this section. Further we use O1 and O2 to refer to two aligned ontologies, and we use prefix notation i#C to refer to an entity C from ontology Oi.
First of all we had to collect different types of complex correspondences. We
considered the examples found in [
The first three patterns are very similar, nevertheless, it will turn out that different
algorithms are required to detect concrete complex correspondences. In accordance with
[
Class by Attribute Type pattern (CAT) This pattern occurs very often when we have disjoint sibling concept. In such a situation the same pattern can be used to define each of the sibling concepts.
Formal Pattern: 1#A 92#R:2#B Example: 1#PositiveReviewedPaper
92#hasEvaluation:2#Positive With respect to the ontologies depicted in Figure 1 we can construct correspondences of this type for the concepts Positive-, Neutral-, and NegativeReviewedPaper.
to make use of the inverse 2#R 1 of property 2#R, since we want to define 1#A as subconcept of 2#R’s range.
Example: 2#Researcher 2#B u 92#R 1 :> 1#Person u 91#researchedBy 1 :> Given an ontology which contains a property and its inverse property as named entities, it is possible to describe the same correspondences as Class by Attribute Type pattern and as Class by Inverse Attribute Type pattern. Nevertheless, an inverse property might often not be defined as atomic entity in the ontology or might be named in a way which makes a correct matching harder.
Class by Attribute Value pattern (CAV) While in the Class by Attribute Type pattern membership to a concept was a necessary condition, we now make use of nominals defined by concrete data values.
Formal Pattern: 1#A 92#R:f: : :g (where f: : :g is a set of concrete data values) Example: 1#submittedPaper 92#submission:ftrueg Another typical example is the distinction between LateRegisteredParticipant and EarlyRegisteredParticipant. In particular, the boolean variant of the pattern occurs to distinguish between complementary subclasses. However, in general there might be more than two relevant values. The following correspondence is a more complex example: 1#StudentPassedExam 92#hasExamScore:fA; B ; C ; D g.
Property Chain pattern (PC) 5 In the following we assume that in O1 property 1#author relates a paper to the name of its author, while in O2 2#author relates a paper to its author and the datatype property 2#name relates a person to its name. Under these circumstances a chain of properties in O2 is equivalent to an atomic property in O1.
Example: 1#author 2#P 2#Q 2#hasAuthor
2#name
Conventional matching systems focus only on correspondences between atomic
entities. Therefore, a matcher might detect a similarity between 1#R and 2#P and one
between 1#R and 2#Q , but will finally decide to output the one with higher
similarity. This observation already indicates that state of the art matching techniques can
5 Correspondence patterns library [
The techniques we are using for detecting complex correspondences are based on combinations of both linguistic and structural methods. In the following we shortly list and describe these approaches. The structural techniques require the existence of a reference alignment R that consists of simple equivalence correspondences between atomic concepts. In particular, it would also be possible to use a matcher generated (and partially incorrect) alignment, but in our first experiments we wanted to avoid any additional source of error.
Structural Criteria To decide whether two or more entities are related via complex
correspondences, information about their position in the ontology hierarchy is
required. Therefore, we have to check whether two concepts are in a subclass resp.
superclass relation, or are even equivalent concepts. It might also be important to
know if two concepts are non overlapping, disjoint concepts. Properties are
connected to the concepts hierarchy via domain and range restrictions, which are thus
also important context information. All of these notions are clearly defined within
a single ontology, however, we extend these notions to a pair of aligned ontologies.
1#C is also referred to as a subconcept of 2#D if there exists a correspondence
1#C 0 = 2#D 0 2 R such that O1 j= 1#C 1#C 0 and O2 j= 2#D 0 2#D .
Syntactical Criteria The most efficient methods used in ontology matching are based
on string comparisons e.g. comparing concept id (the fragment of the concepts URI)
resp. label to compute a similarity between ontological elements. We also make
use of this basic method by computing a similarity measure between normalized
strings based on the Levenshtein measure [
Data type Compatibility Two data types are compatible if one data type can be translated into the other and vice versa. This becomes relevant whenever datatype properties are involved. We determined compatibility in a wide sense. E.g. data type String is compatible to every other data type while Date is not compatible to Boolean. 6 Even experts tend to avoid the introduction of complex correspondences. The property chain 1#R 2#P 2#Q, for example, is sometimes reflected by one (two) correspondence(s) 1#R 2#P or (and) 1#R 2#Q. See for example the reference alignment for OAEI benchmark test case 301 where 101#date 301#hasYear and 101#year 301#hasYear which should be replaced by 101#date 101#year 301#hasYear .
A more detailed description can be found in [
Class by Attribute Type pattern A correspondence 1#A 92#R:2#B of the CAT type is generated by our algorithm, if all following conditions hold. 1. The string that results from removing the head noun from the label of 1#A is similar to the label of 2#B . 2. There exists a class 2#C that is a superclass of 2#B , range of 2#R and has also a label similar to 2#R. 3. The domain of 2#R is a superclass of 1#A due to R.
Notice that these conditions are a complete description of our approach for detecting the CAT pattern. The following example will clarify why such a straightforward approach works.
With respect to the ontologies depicted in Figure 2 our approach will detect that 1#Accepted Paper 92#hasDecision:2#Acceptance. The label of Accepted Paper can be split up into prefix Accepted and head noun Paper. On the one hand the string Accepted is similar to Acceptance, but on the other hand Accepted Paper = Acceptance is not contained in R. Object property hasDecision accomplishes all conditions required by our algorithm: Acceptance has a superclass Decision which is the range of hasDecision and the labels Decision and hasDecision are similar. Moreover the domain of hasDecision is a superclass of Accepted Paper due R, which contains correspondence 1#Paper = 2#Paper .
Class by Inverse Attribute Type pattern A correspondence 1#A of the CAT 1 type is generated if all following conditions hold. 2#B u92#R 1 :>
2. There exists a concept 2#B which both is a proper subset of the range of 2#R 3. and which is, due to the R, a superclass of 1#A.
Notice that for the CAT pattern we did not demand similarity between 1#A and 2#R. This is related to the fact that the label of a property often describes some aspects of its range and not its domain (e.g. hasAuthor relates a paper to its author). Thus, the label of a property is relevant for the inverse pattern CAT 1. The other two conditions are related to structural aspects and filter out candidates that are caused by accidental string similarities.
Class by Attribute Value pattern Although above we described the pattern CAV in general, our algorithm will only detect the boolean variant of this pattern. A correspondence 1#A 92#R:ftrueg is generated by our algorithm, if all following conditions hold. 1. The range of the datatype property 2#R is Boolean. 2. In the following the label of 1#A is split into its head noun hn(1#A) and the remaining part of the label :hn(1#A). Again, :hn(1#A) is split into a first part :hn1(1#A) and a remaining part :hn2(1#A). (a) hn(1#A) is similar to the label of 2#R’s domain. (b) :hn(1#A) is similar to the label of 2#R.
(c) :hn1(1#A) is similar to the label of 2#R. 3. The domain of 2#R is a superclass of 1#A due to R.
Given a non-boolean datatype property range, more sophisticated techniques are required to decide which set of values is adequate for which concept. In our case this distinction is based on condition 2c. If the similarity value does not exceed a certain threshold, we generate 1#A 92#R:ffalseg instead of 1#A 92#R:ftrueg. An example detected in our experimental study is 1#Early Registered Participant 92#earlyRegistration:ftrueg exploiting 1#Participant 2#Participant in R. Property Chain pattern A correspondence 1#R ated, if all following conditions hold. 2#P
1. Due to R, the domain of 1#R is a subclass or superclass of the domain of 2#P . 2. The range of 2#P is a subclass or superclass of the domain of 2#Q . 3. Datatype properties 1#R and 2#Q have a compatible data range. 4. The labels of 1#R and 2#P are similar. 5. The label of 2#Q is name or is contained in the label of 1#R resp. vice versa. Due to the condition that range of 2#P and domain of 2#Q are in a superclass relation, the successive application of the properties can be ensured. Often 1#R maps a class onto a name, therefore especially properties which are labeled with name are potential mapping candidates. An example for this pattern has already been given in the previous section. With respect to Figure 1 we have 1#R = 1#author , 2#P = 2#hasAuthor , 2#Q = 2#name. The property 1#author relates a paper to the name of its author, 2#hasAuthor relates a paper to its author and 2#name an author to its name. Thus, a chain of properties is required to express 1#author in the terminology defined by O2.
A second set of conditions aims to cover a different naming strategy. The first three conditions are the same as above, but the last ones have to be replaced as follows.
5. The labels of 2#P and its range or the labels of the properties 2#P and 2#Q are similar.
An example, depicted in Figure 4, of a property chain that fulfills these conditions: 1#hasYear = 2#date 2#year where 2#date is an object property with 2#Date as abstract range.
For all patterns of the class by and property chain family we additionally check for each candidate correspondence whether there exists a constituent that already occurs in the reference alignment. In this case we trust the simple correspondence in the reference alignment and do not generate the complex correspondence. 5
The algorithms described in the previous section have been implemented in a matching
tool available at http://dominique-ritze.de/complex-mappings/. We
applied our tool on three datasets referred to as CONFERENCE 1, CONFERENCE 2 and
BENCHMARK. These datasets have been taken from corresponding tracks of the
Ontology Alignment Evaluation Initiative (OAEI). As BENCHMARK we refer to the matching
tasks #301 - #304 of the OAEI Benchmark track. We abstained from using the other test
cases, because they are generated by systematic variations of the #101 ontology, which
do not exceed a certain degree of structural difference. The CONFERENCE 1 dataset
consists of all pairs of ontologies for which a reference alignment is available.
Additionally, we used the reference alignment between concepts created for the experiments
conducted in [
Correct Correspondences (true positives) CAT & CAT 1 PC P
Incorrect Correspondences (false positives) CAT & CAT 1 PC P
Table 1 gives an overview on the results of our experiments. We carefully analyzed all generated correspondences and divided them in correct (true positives) and incorrect ones (false positives). One might first notice that we did not include a column for the CAV pattern. Unfortunately, only two correct and one incorrect correspondence of this type have been detected in the CONFERENCE 1 dataset. Remember that we only focused on boolean datatype properties. A more general strategy might result in higher recall. Nevertheless, to our knowledge all correspondences of the boolean CAV have been detected and even with low thresholds only one incorrect correspondence accrued.
Obviously there is a clear distinction between different datasets. While our matching system detected correct complex correspondences of class by types in the CONFERENCE datasets, none have been detected in the BENCHMARK dataset. Nearly the same holds vice versa. This is based on the fact that the ontologies of the BENCHMARK dataset are dedicated to the very narrow domain of bibliography and do not strongly vary with respect to their concept hierarchy, while differences can be found with regard to the use of properties. The CONFERENCE ontologies on the other hand have very different conceptual hierarchies.
Correspondences of the pattern CAT and CAT 1 can be found in both CONFERENCE 1 & 2 datasets. As expected we find the typical relation between precision and recall on the one hand and the chosen threshold on the other hand: low thresholds cause low precision of approx 30% and allow to detect a relatively high number of correct correspondences. A nearly balanced ratio between true and false positives is reached with a threshold of 0:8.
For the PC pattern a threshold of 0:6 results in 18 correct and 21 incorrect correspondences. Surprisingly, the number of correct correspondences does not decrease with increasing threshold, although the number of incorrect correspondences decreases significantly. This is based on the fact that the relevant entities occurring in the PC pattern are very often not only similar but identical after normalization (e.g. concept Date and property date). This observation indicates that there is still room for improvement by choosing different thresholds for different patterns.
Another surprising result is the high number of false property chains in the CONFERENCE 1 and in particular in the CONFERENCE 2 dataset compared to the BENCHMARK dataset. Due to the existence of a reference alignment with high coverage of properties for the BENCHMARK dataset many incorrect property chains have not been generated. Their constituents already occurred in simple correspondence of the reference alignment. The same does not hold for the CONFERENCE datasets. There are many properties that have no counterpart in one of the other ontologies.
Our experimental study points to the problem of evaluating the quality of a complex alignment. Due to the fact that complex correspondences are missing in the reference alignments, our results cannot be compared against a gold standard, resulting in missing recall values. Even though it might be possible to construct a complete reference alignment for a finite number of patterns, it will be extremely laborious to construct a complete reference alignment, which contains all non-trivial complex correspondences. Nevertheless, a comparison against the size of the simple reference alignments might deliver some useful insights. The number of property correspondences in the union of all BENCHMARK reference alignments is 139 (only 63 concept correspondences), while we could find 17 additional property chains with our approach. For the CONFERENCE datasets we counted 275 concept correspondences (only the CONFERENCE 1 dataset comprised additionally 12 property correspondences). Here we detected 12 complex correspondences of different class by types. These results indicate that the proposed complex ontology matching strategy increased recall by approx. 4% with respect to concept correspondences and by approx. 10% with repect to property correspondences.
Interpreting these results, we have to keep in mind that the generation of complex correspondences is much harder compared to the generation of simple correspondences. While a balanced rate of correct and incorrect correspondences will not be acceptable for simple matching tasks, a similar result is positive with respect to the complex matching task which we tackle with our approach. 6
We proposed a pattern based approach to detect different types of complex correspondences. Our approach does not rely on machine learning techniques, which require the availability of instance correspondences. On the contrary, it is based on state of the art matching techniques and additionally exploits an input alignment which consists of simple correspondences. In an experimental study we have shown that our approach, which is simply based on checking conditions specific to a particular pattern, is sufficient to detect a significant amount of complex correspondences, while the number of false positives is relatively low, if considering that complex correspondences are quite hard to detect.
Although first results are promising, we know that the task of verifying the correctness of complex correspondences requires human interaction. A pattern based approach, as proposed in this paper, will in most cases fail to generate highly precise alignments. This is based on the fact that the generation of complex correspondences is significantly harder compared to the task of generating simple correspondences. Suppose, given concept AcceptedPaper of O1, a user is searching in O2 for an equivalent concept. First of all, there are as much simple hypotheses available as there are atomic concepts in O2. The situation changes dramatically when there exists no atomic counterpart and a complex correspondence is required. The search space explodes and it becomes impossible for a human expert to evaluate each possible combination. We know that the proposed patterns covers only a small part of an infinite search space. Nevertheless, this small part might still be large enough to find a significant fraction of those correspondences that will not be detected at all without a supporting system.
Acknowledgment The work has been partially supported by the German Science Foundation (DFG) under contract STU 266/3-1 and STU 266/5-1 and by the IGA VSE grant no. 20/08 ”Evaluation and matching ontologies via patterns”.