Task-Oriented Complex Ontology Alignment: Two Alignment Evaluation Sets

Abstract

Simple ontology alignments, largely studied, link one entity of a source ontology to one entity of a target ontology. One of the limitations of these alignments is, however, their lack of expressiveness which can be overcome by complex alignments. Although different complex matching approaches have emerged in the literature, there is a lack of complex reference alignments on which these approaches can be systematically evaluated. This paper proposes two sets of complex alignments between 10 pairs of ontologies from the well-known OAEI conference simple alignment dataset.

The methodology for creating the alignment sets is described and takes into account the use of the alignments for two tasks: ontology merging and query rewriting. The ontology merging alignment set contains 313 correspondences and the query rewriting one 431. We report an evaluation of state-of-the art complex matchers on the proposed alignment sets.

1 Introduction

Ontology matching is an essential task for the management of the semantic heterogeneity in open environments. The matching process aims at generating a set of correspondences (i.e., an alignment) between the entities of different ontologies. Two ‘paradigms’ organise the field. While approaches generating simple correspondences are limited in expressiveness by linking single entities, complex matching approaches are able to generate correspondences which better express the relationships between entities of different ontologies. Earlier works have introduced the need for complex alignments [15, 35]. Different approaches for generating such complex alignments have been proposed in the literature. While the proposal of [23, 24] relies on correspondence patterns, the one in [13] uses knowledge-rules in Markov-Logic Networks. Those in [20, 21, 36] rely on statistical methods and correspondence patterns and the one in [18] deals with genetic programming. Finally, the approach in [22] uses path-finding algorithms combined with statistical techniques. Despite the progress in the field, there is a lack of reference alignment sets on which the complex approaches can be systematically evaluated. Most efforts on evaluation are still dedicated to the matching approaches dealing with simple alignments. Systematic evaluation of them has been carried out over the last fifteen years in the context of the Ontology Alignment Evaluation Campaigns (OAEI)¹. Even though this well-known campaign proposes a task-oriented benchmark (the OA4QA track [28]), it does not propose a complex alignment benchmark.

This paper proposes two alignment sets to extend the OAEI conference track dataset [3, 37] with complex alignments for two task purposes: ontology merging and query rewriting. The methodology for creating the alignment sets is described and takes into account the use of the alignments for the two targeted tasks. Here we extend the work presented in [31, 33] by enriching the alignment sets with new pairs of ontologies and by considering the task for which the alignment is needed. We also extend the work in [33] and by adding an evaluation of three systems [13, 23, 24]. We extend the evaluation of the work in [31] by adding a new system described in [13] and by evaluating all the three systems on the ten pairs of ontologies for each alignment set.

The paper is organised as follows. After giving the background on ontology matching (Sect. 2) and discussing related work (Sect. 3), we describe the methodology to create the alignments (Sect. 4), the alignments themselves and their use for the evaluation of approaches (Sect. 5). We conclude with a discussion on the proposal.

2 Background

In this paper, the complex correspondences are described using the $\mathcal {DL}$ syntax and the ontologies are graphically represented using the diagrammatic logic formalism defined in [29].

Fig. 1.

Fragment of two heterogeneous ontologies.

2.1 Complex Alignments

Ontology matching [8] is the process of generating an alignment A between two ontologies: a source ontology $o_1$ and a target ontology $o_2$. A is directional, denoted $A_{o_1 \rightarrow o_2}$. $A_{o_1 \rightarrow o_2}$ is a set of correspondences. Each correspondence is a triple $\langle e_{o_1},e_{o_2},r\rangle$. $e_{o_1}$ and $e_{o_2}$ are the members of the correspondence: they can be single ontology entities (classes, object properties, data properties, instances, values) of respectively $o_1$ and $o_2$ or constructions of these entities using constructors or transformation functions. r is a relation, e.g., equivalence ($\equiv$), subsumption ($\sqsubseteq$, $\sqsupseteq$), or disjointedness ($\perp$) between $e_{o_1}$ and $e_{o_2}$.

The ontologies used in the following examples are illustrated in Fig. 1. We consider two types of correspondences depending on the type of their members:

• if the correspondence is simple, both $e_{o_1}$ and $e_{o_2}$ are atomic entities: one single entity is matched with another single entity, e.g., $o_1$:Person $\equiv$ $o_2$:Human is a simple correspondence.

• if the correspondence is complex, at least one of $e_{o_1}$ or $e_{o_2}$ involves a constructor or a transformation function. For example,

  • 1. $o_1$:authorOf $\equiv$ $o_2$:writtenBy$^{-}$ is a complex correspondence with the inverseOf constructor.

  • 2. $o_1$:AcceptedPaper $\equiv$ $\exists$ $o_2$:acceptedBy.$\top$ is a complex correspondence with the existential constructor.

  • 3. $o_2$:name is the concatenation of the $o_1$:firstname and $o_1$:lastname is a complex correspondence with a transformation function².

A complex alignment contains at least one complex correspondence. We will refer to approaches that generate simple alignments as simple matchers and to approaches that generate complex alignments as complex matchers.

2.2 Tasks Involving Complex Ontology Alignments

Ontology alignments are the basis for various tasks, from data translation, query rewriting, ontology merging to ontology versioning. These tasks all serve the purpose of interoperability. Here, we assume that the different tasks may have different correspondence expressiveness needs. We chose to focus this study on two tasks:

• Ontology merging is the process of creating a new ontology from two aligned ontologies (e.g., $o_1$ and $o_2$). The correspondences of the alignment are transformed into axioms of the resulting ontology. For decidability reasons, the expressiveness of the correspondences for ontology merging has to be $\mathcal {SROIQ}$ [11]. For ontology merging, the Alignment API [5] can deal with complex alignments by translating an alignment into OWL axioms.

• Query rewriting is the process of transforming a query expressed with the terms of $o_1$ with the terms of $o_2$ using an alignment between $o_1$ and $o_2$. The correspondences of the alignment are used as rules to rewrite the original query (written for $o_1$). For query rewriting, there is no expressiveness constraint. Various systems such as [4, 16, 30] deal with complex correspondences for SPARQL query rewriting.

For example, the correspondence stating that $o_2$:name is equivalent to the concatenation of $o_1$:firstname and $o_1$:lastname (Fig. 1) is not applicable for ontology merging but is adequate for query rewriting.

3 Related Work

This paper focuses on two aspects of the ontology matching field, the approaches for generating complex correspondences and the evaluation of these approaches (on complex correspondences and task-oriented). We discuss state-of-the-art approaches on these two aspects leaving besides matching of other kind of schemata.

3.1 Complex Ontology Matchers

The complex matchers can be classified according to use of ontology-level or instance-level knowledge. A second axis of classification is whether the matchers rely on correspondence patterns, defined by Scharffe [25] as “templates of ontology correspondences that occur quite often”. We classify the complex matchers on these two axis. In the first group, the approaches rely on correspondence patterns and on ontology-level knowledge only. The approaches in [23, 24] propose a set of matching conditions to detect correspondences that fit a set of patterns, The conditions are based on the labels of the ontologies entities, the structures of these ontologies and the compatibility of the data-types of data-properties.Both approaches take a simple reference alignment as input. The approach in [24] uses linguistic evidence whereas the one in [23] mostly relies on string similarity.

In the second group, the approaches do not rely on correspondence patterns and do not require instance-level knowledge: KAOM (Knowledge-Aware Ontology Matching) [13] is a system which uses Markov Logic Networks as a probabilistic framework for ontology matching. The Markov Logic formulae use the entities of the two ontologies (source and target) as constants, the relations between entities and the input knowledge rules as evidence. The knowledge rules can be axioms of an ontology or they can be specified by the user.

Approaches which rely on correspondence patterns and require instance-level knowledge are: the ones in [20, 21, 36] which use statistical information based on the linked instances to find class by attribute-value correspondences [36], conjunctions of attribute-value pairs [20] or attribute-value = attribute-set-of-values correspondences [21].

Approaches not relying on correspondence patterns and require instance-level knowledge are: the one in [18] which uses genetic programming on instances to find correspondences with transformation functions between two knowledge bases. The one in [22] uses a path-finding algorithm to find correspondences between two knowledge bases with common instances. The correspondences found by this approach are of the form property path = property path.

The different approaches discussed above are generic in the sense that they generate alignments regardless to a specific task.

3.2 Evaluation of Matchers

Alignments generated by matchers can be evaluated in different ways [6]. One way consists in comparing alignments to reference ones (gold standard). However, constructing such references is a time-consuming task. In the lack of such resources, alternatives include manual labelling on sample alignments, alignment coherence measurements [17] and checking the conservativity principle violation of alignments [27]. Furthermore, the quality of a matcher can be assessed regarding its suitability for a specific task or application [10, 12, 28]. Finally, alternative approaches for validating alignments consider the generation of natural language questions to support end-users in the validation task [1] or validation of correspondences using graph-based algorithms in a semi-automatic way [26].

While matching evaluation has been focused on simple alignments, complex evaluation has been addressed to a lesser extent. Although a large spectrum of matching cases are proposed in the OAEI, e.g., involving synthetically generated or real case datasets with large or domain-specific ontologies, these datasets are limited to alignments with simple correspondences.

A notable alignment set has been proposed between biology ontologies in [19]. In opposite to “classical” alignments, the correspondences of these alignments, called “compound alignments” involve entities from more than two ontologies. For example, $o_1$:A $\equiv$ $o_2$:B $\sqcap$ $o_3$:C is a compound correspondence. We consider these correspondences as complex since one of its member contains a constructor but it is out of the scope of our study.

In the context of complex ontology matching where reference alignments are scarce, the evaluation of most approaches is done by manually calculating the precision of the correspondences generated by the systems. The approaches in [21, 23, 24, 36] manually classified the output correspondences (or a subset of them) into true positives and false positives to calculate the precision. The approaches in [23, 24] were tested on the ontologies of the OAEI conference and benchmark tracks (the simple reference alignment being used as input). The approaches in [21, 36] were tested on Linked Open Data (LOD) repositories with large amounts of linked instances such as Yago, DBpedia, Geonames, etc.

With respect to the few complex alignment sets, most of them have been created to evaluate specific complex matching approaches. In order to evaluate the recall of his approach [36] proposed an algorithm to create an evaluation data set. This data set is composed of a synthetic ontology containing 50 classes with known Class-by-attribute-value (a correspondence pattern) correspondences with DBpedia and 50 classes with no known correspondences with DBpedia. Both ontologies are populated with the same instances. The approach of [21] estimated their recall based on the recurring pattern between DBpedia and Geonames: $\exists$ dbpedia:country. $\equiv$ $\exists$ geonames:countryCode. where is a country instance of DBpedia such as dbpedia:Spain and is a country code such as “ES”. They estimated the number of occurrences of this pattern between these ontologies and calculated the recall based on this estimation. The approach of [22] manually created a set of reference correspondences between two ontologies on which their approach was evaluated. On the nine reference correspondences, only two can not be expressed with simple correspondences. The closer approach to ours is from [13] who extended the conference dataset with complex alignments to evaluate their knowledge-rule based approach. However, the methodology used for the construction of the dataset is not specified and the dataset is not available online.

In order to evaluate and compare alignment approaches, we need evaluation alignment sets. As discussed above, complex matchers have been evaluated on custom evaluation alignment sets. When the evaluation used a reference alignment, manually or automatically created, it usually contained correspondences which match only one pattern (Class by attribute-value for [36], attribute-value = attribute-value for [21]).

Approaches using complex correspondences for a given purpose (query rewriting for example), also propose alignment sets created for their needs, even though they have not been used for matcher evaluation. For instance, the authors of [16] present a set of complex correspondences used for query rewriting³. However, they are not in a reusable format and only concern a pair of ontologies. In [32], complex correspondences between agronomic ontologies were manually created for query rewriting on the LOD.

Regarding task-oriented evaluation, the authors of [12] propose ontology alignment evaluation methods for different task purposes: thesaurus merging, and data translation. The OA4QA track⁴ of the OAEI [28] evaluate the suitability of an alignment for the task of query answering. This evaluation dataset consists in the conference track ontologies populated with DBLP, 18 queries over these ontologies and simple reference alignments. The evaluation approach for query rewriting proposed by [10] is very similar. The evaluation data set they propose is also composed of queries, populated instances and simple reference alignments.

Summing up, there is no complex alignment set for systematic evaluation. Moreover, complex alignments are not considered in task-oriented alignment evaluation.

4 Methodology

In this section, we introduce the methodology that we have followed to create the complex alignment sets. As we focus on the purpose of an alignment to create it, we describe a general methodology followed by the variants for the generation of complex alignments dedicated to the ontology merging and query rewriting tasks. As this methodology has been manually applied, it is not suitable for large scale ontologies. Its purpose is to translate each entity of the source ontology $o_1$ using entities of the target ontology $o_2$ when possible for a given task.

The methodology focuses on finding as many complex correspondences as possible with an equivalence relation according to the task purpose of the alignment.

The methodology is articulated in the following steps:

• 1. Find simple equivalence correspondences between $o_1$ and $o_2$. If such an alignment is not available, state-of-the-art approaches [2] may provide a good base which can be manually enriched.

• 2. Create the complex correspondences based on the simple correspondences so that the complex correspondences fit the purpose of the alignment.

• 3. Express the correspondences in a reusable format (e.g., EDOAL).

Methodology to Create an Alignment for Ontology Merging. The first requirement for ontology merging is that the resulting ontology must be coherent; in other words, the reasoning on the resulting ontology must be decidable. Therefore, the alignment should follow the $\mathcal {SROIQ}$ expressiveness and should not bring any incoherence. In order to create the ontology merging alignment, we have followed this methodology. It relies on a reasoner to verify the coherence of the merged ontology.

• 1. Create a new ontology importing $o_1$ and $o_2$.

• 2. Express the simple correspondences obtained at the first step of the global methodology in OWL. Check coherence of the merged ontology (e.g., run a reasoner).

• 3. For each entity of $o_1$ not in a simple equivalence correspondence, find an equivalent construction with entities from $o_2$. This step is done by descending the ontology hierarchy (start by the most general to the most specific).

  • if a construction is found, add the new axiom to the merged ontology and verify the coherence of the merged ontology (e.g., run a reasoner).

  • if no equivalent construction if found, look for the closest super entity or construction from $o_2$ entities. If this axiom is not already entailed by the reasoner, add it to the merged ontology.

• 4. Repeat previous step but for each entity of $o_2$.

We chose this top-down approach because if an axiom is defined on an entity $e_1$, the reasoner will be able to make inferences on the entities subsumed by $e_1$ [14].

Methodology to Create an Alignment for Query Rewriting. For query rewriting, the expressiveness of the correspondences is not limited. Transformation functions can be used as well as “complex roles” (which are limited in $\mathcal {SROIQ}$). Therefore, the coherence of an alignment can not be verified because a reasoning task is not decidable given its expressiveness.

• 1. For each entity $e_1$ of $o_1$ not in a simple equivalence correspondence, find a semantically equivalent construction from $o_2$ entities.

  • if no equivalence can be found, look for the closest entity or construction from $o_2$ subsumed by $e_1$.

• 2. Repeat previous step for each entity of $o_2$ (constructions from $o_1$ entities).

We chose this subsumption entity substitute as for each entity, we wish to get the closest interpretation possible without errors: therefore the biggest subset of the interpretation of $e_1$.

5 Complex Alignment Set

The alignment sets are available at https://doi.org/10.6084/m9.figshare.4986368.v7 under CC-BY license. They are expressed in first-order logic (FOL), EDOAL [5], and OWL for the ontology merging alignment set. EDOAL can express transformations as well as logical relations between entities. We have considered this language instead of others (SWRL, etc.) as it is integrated in the Alignment API and extends the Alignment Format (standard de facto in OAEI campaigns). Before describing the proposed alignment sets, we introduce the Conference dataset from which our dataset have been built.

5.1 The Conference Dataset

The conference dataset⁵ was proposed in [34]. It has been widely used [37], especially in the OAEI where it is a reference evaluation track. This dataset is composed of 16 ontologies on the conference organisation domain and simple reference alignments between 7 of these ontologies. These ontologies were developed individually. The motivation for the extension of this dataset is that the ontologies are real ontologies (as opposed to synthetic ones), they are expressive and largely used for evaluation in the field. Moreover, the reference alignments of simple correspondences between these ontologies are available.

We chose five ontologies among the ones in the reference simple alignment for their different number of classes (c.f. Table 1): cmt, conference (Sofsem), confOf (confTool), edas and ekaw.

The reference simple alignment set was modified during the first step of the methodology. The modifications made to the reference simple alignment set are specified in the FOL alignments on the repository.

Table 1. Number of entities by type of each ontology

5.2 Conference Complex Alignment Sets

We detail in the following the two created alignment sets. The methodology was manually applied by one expert to all ten pairs of ontologies involving the five ontologies.The number of entities of these ontologies is detailed in Table 1. The merged ontologies were checked for coherence with the HermiT reasoner [9].

The ontology merging set is composed of 313 correspondences with 54 complex correspondences from 9 different patterns (some patterns are composite). The query rewriting set is composed of 431 correspondences with 191 complex correspondences from 17 different patterns (some patterns are composite). The patterns are used a posteriori for analysing the alignments, not as a basis for the correspondence creation. An extensive list of the patterns can be found in [25]. The meaning of the abbreviations used in the following tables is: CAT: $A \equiv \exists b.C$, CAE: $A \equiv \exists b.\top$, CIAE: $A \equiv \exists b^{-}.\top$, CAV: $A \equiv \exists b.\{v\}$, neg: not exists, dom: domain restriction, range: range restriction, dom/range: domain and range restriction, transfo: transformation function on data properties, c: class, rel: object property, prop: data property, chain: a chain of properties (object properties and/or data properties), IP: inverse of an object property, composite or compo: different patterns in same correspondence. The domain restriction and range restriction patterns are correspondence patterns from [25] and not OWL axiom primitives.

Fig. 2.

Number of correspondences per pattern per alignment set.

Figure 2 details the number of correspondences per pattern per alignment set. Table 2 presents examples of correspondences from the alignment sets and their type. The ontology merging alignment set has no correspondences implementing domain or range restrictions, transformation functions, inverse properties, union of object or data properties, or negation. Indeed, these correspondences are either not in $\mathcal {SROIQ}$ (domain restriction, range restriction, union of properties) or were already entailed by previous correspondences (inverse property, negation). The number of subsumptions also differs in both alignment sets because of the adopted methodology (top-down subsumption in ontology merging and bottom-up subsumption in query rewriting). Nevertheless, the subsumption correspondences are frequent in both sets. As above, we argue that complex correspondences come as a complement to simple correspondences. Their need may be different depending on the task purpose of the alignment. For query rewriting for instance, complex correspondences represent 44% of all correspondences whereas they only represent 17% of all correspondences for ontology merging.

6 Evaluation of Complex Matchers

As populating the ontologies to match with common instances would add new considerations for the evaluation dataset (e.g., choice and quantity of the instances), we chose to evaluate the available approaches that do not need common instances, as those described in [13, 23, 24].

We evaluated the matchers on the correspondences they output. Here we only evaluate the complex correspondences output as simple correspondences are taken as input by the approaches. For ontology merging, we only consider the $\mathcal {SROIQ}$ compliant correspondences output by the approaches. The correspondences output by the matchers were classified into true positive or false positive by comparison with each reference alignment set. A true positive is semantically equivalent to a correspondence in the reference alignment. The number of true and false positive are presented in Table 3. The knowledge rules needed for [13] were the one used in the evaluation section of the paper.

Table 2. Example of correspondences of the query rewriting alignment set and their type (correspondence pattern)

Fig. 3.

Precision, Recall and F-measure of the three evaluated approaches

Precision, recall and F-measure have been computed for both alignment sets as shown in Fig. 3. For both purposes, Ritze2010 [24] has the best precision but its recall is the lowest. For the purpose of ontology merging, Ritze2009 [23] has a slightly better F-measure than the others. For query rewriting, Jiang2016 (KAOM) [13] is better than the other approaches. The precision of KAOM is better on the query rewriting alignment set than on the ontology merging set because most of its output correspondences are of the form $o_1$:role $\equiv$ $o_2$:otherRole.$o_2$:Domain.$o_2$:Range. Such correspondences are not expressible in $\mathcal {SROIQ}$ therefore we did not consider them during the evaluation on the ontology merging alignment set.

Table 3. True positive (TP) and false positive (FP) complex correspondences of the three evaluated approaches. $\mathcal {SROIQ}$ and All correspondences compared to the number of complex correspondences in the reference alignment sets

We also note that some correspondences in both alignment sets whose pattern detecting conditions were described in Ritze2009 [23] and Ritze2010 [24] were not retrieved by these two approaches because of the too restrictive conditions.

7 Discussion

In this section, we discuss the limitations and ways to improve the alignment sets, the evaluation and the potential reusability of these sets.

First of all, some difficulties were met with respect to the creation of the complex correspondences. Even though a real effort was made to grasp the semantics of every ontology entity based on its context (axioms, annotations, pseudo-labelling, neighbour entities and entity usage), one of the main difficulties was to fully understand the nuances between similar entities definitions which can lead or not to an equivalence correspondence. For example, the concept reviewer of a paper can either mean “a person who reviews a paper” or “a person who is assigned to a paper” which is slightly different.

With respect to the ontologies, besides the fact that the ontologies are real-world ones and relatively expressive, they are relatively small. However, we can argue that the target specificity of these alignments was not size but expressiveness (although they are limited to one entity to a construction). Moreover, as the ontologies are not populated, this impacts the evaluation of complex matchers which is limited to approaches not relying on instances. Furthermore, as the set of ontologies considered here model a same particular domain, this may bring a bias in the evaluation of complex matchers. This could be overcome by considering other ontology sets on different domains.

Regarding the (reference) generated alignments, they have been manually created based on one domain expert’s interpretation of each ontology given the specific task scenario. Thus, they are not absolute. We have also made the assumption that the task impacts the alignment’s expressiveness. However, we do not consider the final application for which the alignment is used (e.g., conference paper management, conference attendees management, etc.). Taking into account the specific application purpose for an alignment would may impact not only the expressiveness of the alignment but also its content.

With respect the evaluation, the metrics used here are the classical precision, recall and f-measure. Applied to complex correspondences, they present some limits. First, the relation of the correspondence is not taken into account. Second, the same correspondence can be expressed in different ways: in this evaluation, we manually compared two expressions. Third, we could consider the confidence of correspondences (here we assume that all generated correspondences by matchers are 1.0). Finally, the evaluation is not task-centered in the sense that the alignments generated by the approaches were not applied to query rewriting or ontology merging.

Nevertheless, the evaluation of the matchers shows that there is room for improvements in complex alignment generation. In our evaluation, we could observe that a good precision is often achieved in detriment of recall. The approaches [23, 24] globally perform better for the task of ontology merging due to the set of correspondence patterns guiding their detection. The approach of [13] is the only one from the three approaches that considers object property restrictions, needed for query rewriting. In case the ontologies were populated with linked instances, the Class-by-attribute-value (CAV) correspondences of the alignment set could be detected by the approaches of [20, 21, 36], the correspondences with transformation functions such as string concatenation could be detected by the approaches of [18], and property chains could be detected by the approach of [22].

Summing up, as future directions in the field, some aspects have to be better addressed. Regarding the use of these alignment sets in complex ontology matching evaluation, population of the ontologies and consensus version (currently in work) should be taken into account. Regarding the evaluation process, automatising the process and finding better metrics seem compulsory. For example, semantic precision and recall [7] could be applied on the deductive closure set of axioms for ontology merging. An other metric could also take into account the conservativity [27], coherence and decidability of the merged ontology. Gold standard queries, as for the OA4QA campaign [28] could be a solution for query rewriting.

8 Conclusion and Perspectives

This paper has presented two task-oriented complex ontology alignment sets. Our work outlines two main points: the first one is that complex alignments are necessary to tightly align two ontologies. The second one is that two alignments can differ according to their task purpose. As the evaluation has shown, these alignment sets are rather challenging.

As discussed in the previous section, the proposed alignment sets can be improved in different directions. Therefore, we plan to address the points mentioned in the discussion and to extend the alignments with construction to construction correspondences. The evaluation of complex matchers is a problem that has not yet been addressed. We hope that this first rudimentary evaluation will pave the way towards a more complete benchmark for complex alignment evaluation.