While there are numerous tools for ontology matching, most approaches provide only little information about the true nature of the correspondences they discover, restricting themselves on the mere links between matching concepts. However, many disciplines such as ontology merging, ontology evolution or data transformation, require more-detailed information, such as the concrete relation type of matches or information about the cardinality of a correspondence (oneto-one or one-to-many). In this study we present a new approach where we denote additional semantic information to an initial ontology mapping carried out by a state-of-the-art matching tool. The enriched mapping contains the relation type (like equal, is-a, part-of) of the correspondences as well as complex correspondences. We present di erent linguistic, structural and background knowledge strategies that allow semi-automatic mapping enrichment, and according to our rst internal tests we are already able to add valuable semantic information to an existing ontology mapping.
Ontology matching plays a key role in data integration
and ontology management. With the ontologies getting
increasingly larger and more complex, as in the medical or
biological domain, e cient matching tools are an important
prerequisite for ontology matching, merging and evolution.
There are already various approaches and tools for
ontology matching, which exploit most di erent techniques like
lexicographic, linguistic or structural methods in order to
identify the corresponding concepts between two ontologies
[
These tools are able to highly reduce the e ort of
manual ontology mapping, but most approaches solely focus on
detecting the matching pairs between two ontologies,
without giving any speci c information about the true nature
of these matches. Thus, a correspondence is commonly
regarded an equivalence relation, which is correct for a
correspondence like (zip code, postal code), but incorrect for
correspondences like (car, vehicle) or (tree trunk, tree), where
is-a resp. part-of would be the correct relation type. This
restriction is an obvious shortcoming, because in many cases
a mapping should also include further kinds of
correspondences, such as is-a, part-of or related. Adding these
information to a mapping is generally bene cial and has been
shown to considerably improve ontology merging [
An example is given in Fig. 1, which depicts the basic idea of our approach. While we get a simple alignment as input, with the mere links between concepts (above picture), we return an enriched alignment with the relation type annotated to each correspondence (lower picture). As we will point out in the course of this study, we use di erent linguistic methods and background knowledge in order to nd the relevant relation type. Besides this, we have to distinguish between simple concepts (as "O ce Software") and complex concepts, which contain itemizations like "Monitors and Displays", and which need a special treatment for relation type detection.
Another issue of present ontology matchers is their restriction to (1:1)-correspondences, where exactly one source concept matches exactly one target concept. However, this can occasionally lead to inaccurate mappings, because there may occur complex correspondences where more than one source element corresponds to a target element or vice versa, as the two concepts rst name and last name correspond to a concept name, leading to a (2:1)-correspondence. We will show in section 5 that distinguishing between one-to-one and one-to-many correspondences plays an important role in data transformation, and that we can exploit the results from the relation type detection to discover such complex matches in a set of (1:1)-matches to add further knowledge to a mapping.
In this study we present di erent strategies to assign the relation types to an existing mapping and demonstrate how complex correspondences can be discovered. Our approach, which we refer to as Enrichment Engine, takes an ontology mapping generated by a state-of-the-art matching tool as input and returns a more-expressive mapping with the relation type added to each correspondence and complex correspondences revealed. According to our rst internal tests, we recognized that even simple strategies already add valuable information to an initial mapping and may be a notable gain for current ontology matching tools.
Our paper is structured as follows: We discuss related work in section 2 and present the architecture and basic procedure of our approach in section 3. In section 4 we present di erent strategies to determine the relation types in a mapping, while we discuss the problem of complex correspondence detection in section 5. We nally conclude in section 6.
Only a few tools and studies regard di erent kinds of
correspondences or relationships for ontology matching.
SMatch [
Taxomap [
The LogMap tool [
Several further studies deal with the identi cation of
semantic correspondence types without providing a complete
tool or framework. An approach utilizing current search
engines is introduced in [
Unlike relation type determination, the complex
correspondence detection problem has hardly been discussed so
far. It was once addressed in [
One remarkable approach is iMAP [
While the approaches presented in this section try to achieve both matching and semantic annotation in one step, thus often tending to neglect the latter part, we will demonstrate a two-step architecture in which we rst perform a schema mapping and then concentrate straight on the enrichment of the mapping (semantic part). Additionally, we want to analyze several linguistic features to provide more qualitative mappings than obtained by the existing tools, and nally develop an independent system that is not restricted to schema and ontology matching, but will be differently exploitable in the wide eld of date integration and data analysis.
As illustrated in Fig. 2 our approach uses a 2-step
architecture in which we rst calculate an ontology mapping
(match result) using our state-of-the-art matching tool
COMA 3.0 (step 1) [
Our 2-step approach for semantic ontology matching o ers di erent advantages. First of all, we reduce complexity compared to 1-step approaches that try to directly determine the correspondence type when comparing concepts in O1 with concepts in O2. For large ontologies, such a direct matching is already time-consuming and error-prone for standard matching. The proposed approaches for semantic matching are even more complex and could not yet demonstrate their general e ectiveness.
Secondly, our approach is generic as it can be used for di erent domains and in combination with di erent matching tools for the rst step. We can even re-use the tool in di erent elds, such as entity resolution or text mining. On the other hand, this can also be a disadvantage, since the enrichment step depends on the completeness and quality of the initially determined match result. Therefore, it is important to use powerful tools for the initial matching and possibly to ne-tune their con guration.
The basics of the relation type detection, on which we focus in this study, can be seen in the right part of Fig. 2. We provide 4 strategies so far (Compound, Background Knowledge, Itemization, Structure), where each strategy returns the relation type of a given correspondence, or "undecided" in case no speci c type can be determined. In the Enrichment step we thus iterate through each correspondence in the mapping and pass it to each strategy. We eventually annotate the type that was most frequently returned by the strategies (type computation). In this study, we regard 4 distinct relation types: equal, is-a and inv. is-a (composition), part-of and has-a (aggregation), as well as related.
There are two problems we may encounter when computing the correspondence type. First, all strategies may return Strategy Compounding Background K.
Itemization Structure equal
X X is-a X X X X part-of
related X X
X "undecided". In this case we assign the relation type "equal", because it is the default type in the initial match result and possibly the most likely one to hold. Secondly, there might be di erent outcomes from the strategies, e.g., one returns is-a, one equal and the others undecided. There are di erent ways to solve this problem, e.g., by prioritizing strategies or relation types. However, we hardly discovered such cases so far, so we currently return "undecided" and request the user to manually specify the correct type.
At the present, our approach is already able to fully assign relation types to an input mapping using the 4 strategies, which we will describe in detail in the next section. We have not implemented strategies to create complex matches from the match result, but will address a couple of conceivable techniques in section 5.
We have implemented 4 strategies to determine the type of a given correspondence. Table 1 gives an overview of the strategies and the relation types they are able to detect. It can be seen that the Background Knowledge approach is especially valuable, as it can help to detect all relationship types. Besides, all strategies are able to identify is-a correspondences.
In the following let O1; O2 be two ontologies with c1; c2 being two concepts from O1 resp. O2. Further, let C = (c1; c2) be a correspondence between two concepts (we do not regard the con dence value in this study). 4.1
In linguistics, a compound is a special word W that
consists of a head WH carrying the basic meaning of W , and
a modi er WM that speci es WH [
In the following, let A, B be the literals of two concepts of a correspondence. The Compound Strategy analyzes whether B ends with A. If so, it seems likely that B is a compound with head A, so that the relationship B is-a A (or A inv. is-a B) is likely to hold. The Compound approach allows us to identify the three is-a correspondences shown in Figure 1 (below).
We added an additional rule to this simple approach: B is only considered a compound to A if length(B) length(A) 3, where length(X) is the length of a string X. Thus, we expect the supposed compound to be at least 3 characters longer than the head it matches. This way, we are able to eliminate obviously wrong compound conclusions, like stable is a table, which we call pseudo compounds. The value of 3 is motivated by the observation that typical nouns or adjectives consist of at least 3 letters. 4.2
Background knowledge is commonly of great help in
ontology matching to detect more di cult correspondences,
especially in special domains. In our approach, we intend to
use it for relation type detection. So far, we use WordNet
3.0 to determine the relation that holds between two words
(resp. two concepts). WordNet is a powerful dictionary and
thesaurus that contains synonym relations (equivalence),
hypernym relations (is-a) and holonym relations (part-of)
between words [
Although WordNet has a limited vocabulary, especially with regard to speci c domains, it is a valuable source to detect the relation type that holds between concepts. It allows an excellent precision, because the links in WordNet are manually de ned, and contains all relation types we intend to detect, which the other strategies are not able to achieve. 4.3
In several taxonomies we recognized that itemizations appear very often, and which cannot be processed with the previously presented strategies. Consider the correspondence ("books and newspapers", "newspapers"). The compound strategy would be mislead and consider the source concept a compound, resulting in the type "is-a", although the opposite is the case (inv. is-a). WordNet would not know the word "books and newspapers" and return "undecided".
Itemizations thus deserve special treatment. We rst split each itemization in its atomic items, where we de ne an item as a string that does not contain commas, slashes or the words "and" and "or".
We now show how our approach determines the correspondence types between two concepts C1; C2 where at least one of the two concepts is an itemization with more than one item. Let I1 be the item set of C1 and I2 the item set of C2. Let w1; w2 be two words, with w1 6= w2. Our approach works as follows: 1. In each set I remove each w1 2 I which is a hyponym of w2 2 I. 2. In each set I, replace a synonym pair (w1 2 I; w2 2 I) 3. Remove each w1 2 I1, w2 2 I2 if there is a synonym pair (w1; w2). 4. Remove each w2 2 I2 which is a hyponym of w1 2 I1.
(a) If I1 = ;; I2 = ;: equal (b) If I1 = ;; jI2j
If I2 = ;; jI1j (c) If jI1j 1; I2 1: is-a 1: inverse is-a
The rationale behind this algorithm is that we remove items from the item sets as long as no information gets lost. Then we compare what is left in the two sets and come to the conclusions presented in step 5.
Let us consider the concept pair C1 = "books, ebooks, movies, lms, cds" and C2 ="novels, cds". Our item sets are I1 = fbooks; ebooks; movies; f ilms; cdsg, I2 = fnovels; cdsg. First, we remove synonyms and hyponyms within each set, because this would cause no loss of information (steps 1+2). We remove f ilms in I1 (because of the synonym movies) and ebooks in I1, because it is a hyponym of books. We have I1 = fbooks; movies; cdsg ; I2 = fnovels; cdsg. Now we remove synonym pairs between the two item sets, so we remove cds in either set (step 3). Lastly, we remove a hyponym in I1 if there is a hypernym in I2 (step 4). We remove novel in I2, because it is a book. We have I1 = fbooks; moviesg ; I2 = ;. Since I1 still contains items, while I2 is empty, we conclude that I1 speci es something more general, i.e., it holds C1 inverse is-a C2.
If neither item set is empty, we return "undecided" because we cannot derive an equal or is-a relationship in this case. 4.4
The structure strategy takes the structure of the ontologies into account. For a correspondence between concepts Y and Z we check whether we can derive a semantic relationship between a father concept X of Y and Z (or vice versa). For an is-a relationship between Y and X we draw the following conclusions:
For a part-of relationship between Y and X we can analogously derive: The approach obviously utilizes the semantics of the intraontology relationships to determine the correspondence types for pairs of concepts for which the semantic relationship cannot directly be determined. 4.5
We tested our strategies and overall system on 3 usergenerated mappings in which each correspondence was tagged with its supposed type. After running the scenarios, we checked how many of the non-trivial relations were detected by the program. The 3 scenario consisted of about 350 .. 750 correspondences. We had a German-language scenario (product catalogs from online shops), a health scenario (diseases) and a text annotation catalog scenario (everyday speech).
Compounding and Background Knowledge are two independent strategies that separately try to determine the relation type of a correspondence. In our tests we saw that Compounding o ers a good precision (72 .. 97 %), even without the many exocentric and pseudo-compounds that exist. By contrast, we recognized only moderate recall, ranging from 12 to 43 %. Compounding is only able to determine is-a relations, however, it is the only strategy that invariably works.
Background Knowledge has a low or moderate recall (10 .. 50 %), depending on the scenario at hand. However, it o ers an excellent precision being very close to 100 % and is the only strategy that is able to determine all relation types we regard. As matter of fact, it did not work on our Germanlanguage example and only poorly in our health scenario.
Structure and Itemization strategy depend much on the given schemas and are thus very speci c strategies to handle individual cases. They exploit the Compound and Background Knowledge Strategy and are thus not independent. Still, they were able to boost the recall to some degree.
We realized that the best result is gained by exploiting all strategies. Currently, we do not weight the strategies, however, we may do so in order to optimize our system. We nally achieved an overall recall between 46 and 65 % and precision between 69 and 97 %.
Schema and ontology matching tools generally calculate (1:1)-correspondences, where exactly one source element matches exactly one target element. Naturally, either element may take part in di erent correspondences, as in (name, rst name) and (name, last name), however, having these two separate correspondences is very imprecise and the correct mapping would rather be the single correspondence ( ( rst name, last name), (name)). These kind of matches are called complex correspondences or one-to-many correspondences.
The disambiguation between a complex correspondence
or 2 (or more) one-to-one correspondences is an inevitable
premise for data transformation where data from a source
database is to be transformed into a target database, which
we could show in [
There are proprietary solutions that allow to manually
create transformation mappings including complex
correspondences, such as Microsoft Biztalk Server [
We already developed simple methods that exploit the structure of the schemas to transform several (1:1)-correspondences into a complex correspondence, although these approaches will fail in more intricate scenarios. We used the structure of the schemas and the already existing (1:1)matches to derive complex correspondences. Fig. 3 demonstrates this approach. There are two complex correspondences in the mapping, ( (First Name, Last Name), (Name)) and ( (Street, City, Zip Code, Country), Address), represented by simple (1:1)-correspondences. Our approach was able to detect both complex correspondences. The rst one (name) was detected, because rst name and last name cannot be mapped to one element at the same time, since the name element can only store either of the two values. The second example (address) is detected since schema data is located in the leaf nodes, not in inner nodes. In database schemas we always expect data to reside in the leaf nodes, so that the match (Address, Address) is considered unreasonable.
In the rst case, our approach would apply the concatenation function, because two values have to be concatenated to match the target value, and in the second case the split function would be applied, because the Address values have to be split into the address components (street, city, zip code, country). The user needs to adjust these functions, e.g., in order to tell the program where in the address string the split operations have to be performed.
This approach was mostly based on heuristics and would only work in simple cases. Now that we are able to determine the relation types of (1:1)-matches, we can enhance this original approach. If a node takes part in more than one composition relation (part-of / has-a), we can conclude that it is a complex correspondence and can derive it from the (1:1)-correspondences. For instance, if we have the 3 correspondences (day part-of date), (month part-of date), (year part-of date) we could create the complex correspondence ( (day, month, year), date).
We have not implemented this approach so far, and we assume that detecting complex correspondences and the correct transformation function will still remain a very challenging issue, so that we intend to investigate additional methods like using instance data to allow more e ectiveness. However, adding these techniques to our existing Enrichment Engine, we are able to present a rst solution that semiautomatically determines complex correspondences, which is another step towards more precise ontology matching, and an important condition for data transformation.
We presented a new approach to semantically enrich ontology mappings by determining the concrete relation type of a correspondence and detecting complex correspondences. For this, we developed a 2-step architecture in which the actual ontology matching and the semantic enrichment are strictly separated. This makes the Enrichment Engine highly generic so that it is not designed for any speci c ontology matching tool, and moreover, can be used independently in various elds di erent from ontology matching, such as data transformation, entity resolution and text mining.
In our approach we developed new linguistic strategies to determine the relation type, and with regard to our rst internal tests even the rather simple strategies already added much useful information to the input mapping. We also discovered that some strategies (Compounding, and to a less degree Itemization and Structure) are rather independent from the language of the ontologies, so that our approach provided remarkable results both in German and Englishlanguage ontologies.
One important obstacle is the strong dependency to the initial mapping. We recognized that matching tools tend to discover equivalence relations, so that di erent non-equivalence correspondences are not contained by the initial mapping, and can thus not be detected. It is future work to adjust our tool COMA 3.0 to provide a more convenient input, e.g., by using relaxed con gurations. A particular issue we are going to investigate is the use of instance data connected with the concepts to derive the correct relation type if the other strategies (which operate on the meta level) fail. This will also result in a time-complexity problem, which we will have to consider in our ongoing research.
Our approach is still in a rather early state, and there is still much space for improvement, since the implemented strategies have di erent restrictions so far. For this reason, we will extend and ne-tune our tool in order to increase e ectiveness and precision. Among other aspects, we intend to improve the structure strategy by considering the entire concept path rather than the mere father concept, to add further background knowledge to the system, especially in speci c domains, and to investigate further linguistic strategies, for instance, in which way compounds also indicate the part-of relation. Next to relation type detection, we will also concentrate on complex correspondence detection in data transformation to provide further semantic information to ontology mappings.