CANARD: An approach for generating expressive correspondences based on competency questions for alignment

2.1.Complex ontology alignment

Ontology matching (as in [7]) is defined as the process of generating an alignment A between two ontologies: a source ontology o and a target ontology o′. A is a set of correspondences ⟨e1,e2,r,n⟩. Each correspondence expresses a relation r (e.g., equivalence (≡), subsumption (⊒, ⊑)) between two members e1 and e2, and n expresses its level of confidence [0..1]. A member can be a single ontology entity (class, object property, data property, individual) of respectively o and o′ or a complex construction which is composed of entities using constructors. Two kinds of correspondences are considered depending on the type of their members:

A simple correspondence is noted (s:s), and a complex correspondence (s:c) if its source member is a single entity, (c:s) if its target member is a single entity, or (c:c) if both members are complex entities. An approach that generates complex correspondences is referred to as a “complex approach” or “complex matcher” below.

2.2.Competency questions for alignment (CQAs)

In ontology authoring, to formalize the knowledge needs of an ontology, competency questions (CQs) have been introduced as ontology’s requirements in the form of questions the ontology must be able to answer [11]. A competency question for alignment (CQA) is a competency question which should (in the best case) be covered by two ontologies, i.e., it expresses the knowledge that an alignment should cover if both ontologies’ scopes can answer the CQA. The first difference between a CQA and a CQ is that the scope of the CQA is limited by the intersection of its source and target ontologies’ scopes. The second difference is that this maximal and ideal alignment’s scope is not known a priori. As CQs [21], a CQA can be expressed in natural language or as SPARQL queries. Inspired from the predicate arity in [21], the notion of question arity, which represents the arity of the expected answers to a CQA is adapted, as introduced in [28]:

In CANARD, CQAs are limited to unary and binary, of select type, and no modifier. This is a limitation in the sense that it does not deal with specific kinds of SPARQL queries, such as the ones involving CONSTRUCT and ASK. The approach does not deal with transformation functions or filters inside the SPARQL queries and only accepts queries with one or two variables. However, as classes and properties are unary and binary predicates, these limitations still allow the approach to cover ontology expressiveness. Questions with a binary or counting type have a corresponding selection question. For example, the question Is this paper accepted? has a binary type: its answers can only be True or False. The question How many papers are accepted? is a counting question. These two questions have the same selection question: What are the accepted papers?. We also restrain the question polarity to positive because a negative question implies that positive information is being negated. For example, the question Which people are not reviewers? is a negation of the question Who are the reviewers?. The CQA we consider has no modifier. The question arity of the CQA is limited to unary and binary because ontologies are mostly constructed using unary predicates (classes or class expressions) and binary predicates (object or data properties).

3.1.Approach over a unary CQA

In the following, Figure 1 is instantiated for a unary CQA. The SPARQL CQA is that of Figure 3(a):

3.2.Approach over a binary CQA

The main difference with the case of unary CQAs is in Step because the two instances of the pair answer are matched instead of one, Step and Step which deal with the subgraph extraction and pruning.

4.1.Translating SPARQL CQAs into DL formulae

In Step , to translate a SPARQL query into a DL formula, the first step is to translate it into a FOL formula and then transform it into a DL formula. A SPARQL SELECT query (in the scope of our approach) is composed of a SELECT clause containing variable names and a basic graph pattern, i.e., a set of triples with variables sometimes with constructors (such as UNION or MINUS). First, the variables in the SELECT clause become the quantified variables of the formula. In unary CQA, the SELECT clause contains one variable. In binary CQA, the SELECT clause contains two variables. The SPARQL query of Figure 4, ?x becomes the quantified variable of our formula: ∀x. Then, the basic graph pattern is parsed to find what predicates apply to the quantified variables and add them to the formula. Each triple of the basic graph pattern is either a unary or a binary predicate. If new variables are added, an existential quantifier is used for them. In the example, we find the triple ⟨?x, o′:hasDecision, ?y ⟩. The FOL formula becomes ∀x, ∃y, o′:hasDecision(x,y). We then recursively keep on exploring the basic graph pattern for each new variable introduced. After exploring the basic graph pattern for the variable ?y, the FOL formula becomes ∀x, ∃y, o′:hasDecision(x,y) ∧o′:Acceptance(y). At the end of the process, we transform the basic graph pattern into a DL formula, which can also be translated into an EDOAL formula as shown below. ∀x, ∃y, o′:hasDecision(x,y) ∧o′:Acceptance(y) becomes in DL: ∃o′:hasDecision.o′:Acceptance. The FOL to DL equivalence is done as in [4].

Fig. 4.

SPARQL SELECT query with one variable in SELECT clause.

4.2.Instance matching

In Step , the answers of the CQA over the source knowledge base that have been retrieved are matched with the instances of the target knowledge base. This instance matching phase relies on existing links (owl:sameAs, skos:exactMatch, skos:closeMatch, etc.) if they exist. If no such link exists, an exact label match is performed. When dealing with binary CQA whose results are an instance-literal value pair, the instance is matched as before (existing links or exact labels), and the literal value will be matched with an exactly identical value (the datatype is not considered) in the pathfinding step, detailed in Section 4.3.

4.3.Retrieving and pruning subgraphs

The approach relies on subgraphs, which are sets of triples from a knowledge base. These subgraphs are found (Step ), pruned, and transformed into DL formulae (Step ). The type of subgraphs for unary or binary CQAs is inspired by [39], which proposes an approach to find equivalent subgraphs within the same knowledge base.

A unary CQA expects a set of single instances as an answer. The subgraph of a single instance is composed of a triple in which the instance is either the subject or the object, and the types (classes) of the object or subject of this triple. For example, o′:paper1 is the subject of the triple o′:paper1 o′:hasDecision o′:decision1 and o′:decision1 has types (classes) o′:Acceptance and o′:Decision. A subgraph of o′:paper1 is therefore composed of the three following triples: (i) ⟨ o′:paper1 , o′:hasDecision , o′:decision1 ⟩, (ii) ⟨ o′:decision1 , rdf:type , o′:Acceptance ⟩, (iii) ⟨ o′:decision1 , rdf:type , o′:Decision ⟩.

When comparing the subgraph with the CQA labels, if the most similar object (resp. subject) type is more similar than the object (resp. subject) itself, the type is kept. Let us consider the accepted paper CQA. The most similar type of the triple of the object is o′:Acceptance. Therefore, triple 3 is pruned. The object of triple 1 is o′:decision1 and the most similar object type to the CQA is o′:Acceptance. o′:Acceptance is more similar to the CQA than o′:decision1. Therefore, o′:decision1 becomes a variable and triple 2 stays in the subgraph. In order to translate a subgraph into a DL formula, we first translate this subgraph into a SPARQL query:

A binary CQA expects a set of pairs of instances (or pairs of instance-literal value) as an answer. Finding a subgraph for a pair of instances consists in finding a path between the two instances. The shortest paths are considered more accurate. Because finding the shortest path between two entities is a complex problem, paths of length below a threshold are sought. First, paths of length 1 are sought, then if no path of length 1 is found, paths of length 2 are sought, etc. If more than one path of the same length is found, all of them go through the following process. When a path is found, the types of instances forming the path are retrieved. If the similarity of the most similar type to the CQA is above a threshold, this type is kept in the final subgraph. For example, for a “paper written by” CQA with the answer (o′:paper1,o′:person1) in the target knowledge, a subgraph containing the following triples is found: ⟨ o′:person1 , o′:writes , o′:paper1 ⟩, ⟨ o′:paper1 , rdf:type , o′:Paper ⟩, ⟨ o′:paper1 , rdf:type , o′:Document ⟩, ⟨ o′:person1 , rdf:type , o′:Person ⟩. The most similar type of o′:person1 is o′:Person, which is below the similarity threshold. Triple 4 is then removed from the subgraph. The most similar type of o′:paper1 is o′:Paper. Triple 3 is therefore removed from the subgraph. o′:Paper’s similarity is above the similarity threshold: triple 2 stays in the subgraph. The translation of a subgraph into a SPARQL query is the same for binary and unary CQAs. Therefore, the subgraph will be transformed into a SPARQL query and saved as a DL formula: dom(o′:Paper) ⊓ o′:writes−.

4.4.Label similarity

In step , a label similarity metric is needed to compare two sets of labels Ls and Lt. A Levenshtein [14] distance-based similarity metric was chosen. It measures the minimum number of single-character edits (insertions, deletions, or substitutions) between two strings. The similarity between two sets of labels is the Cartesian product of the string similarities between the labels of Ls and Lt (1). strSim is the string similarity of two labels ls and lt (2).

4.5.DL formula aggregation

In Step of the approach, when dealing with unary CQA, the DL formulae can be aggregated. It consists in transforming one or more formulae with a common predicate into a more generic formula. This aggregation only applies to formulae that contain an instance or a literal value and which were kept in the subgraph selection step. For example, this step would apply to a formula such as ∃ o′:hasDecision.{o′:accept}. There are three steps to the aggregation. First, we create a first aggregated formula which we call the extension formula. It consists in merging the instances or literal values of the formulae with the same predicate into one set of values. Let us consider that through various answers to a CQA (e.g., o′:paper1, o′:paper2, etc.), we encountered the following formulae: ∃o′:hasDecision.{o′:accept}, ∃o′:hasDecision.{o′:strongAccept}, ∃o′:hasDecision.{o′:weakAccept}. The extension formula of these formulae is: ∃o′:hasDecision.{o′:accept, o′:strongAccept, o′:weakAccept}. The extension formula of a formula that does not share its predicate with any other is the formula itself. Then, an intension formula can be computed by replacing the set of values by the top class ⊤. The intension formula of the example formulae is: ∃o′:hasDecision.⊤. Finally, a choice is made between the extension or intension formulae based on the predicate similarity to the CQA. If the predicate is more similar than the values, the intension formula is kept. Otherwise, the extension formula is kept. In our example, the extension formula ∃o′:hasDecision.{o′:accept, o′:strongAccept, o′:weakAccept} is kept.

We present two examples of initial formulae, with their respective intension and extension formulae in Table 1. These were obtained with the competency question “accepted paper”. In Table 1, the final formulae are in bold. Applied to the examples of Table 1:

4.6.Calculating the percentage of counter-examples

In Step , the approach refines the DL formula similarity score by looking for counter-examples (details about the similarity score are given in Section 4.7). A counter-example is a common instance of the source and target ontologies which is described by the DL formula found by the approach in the target ontology but which is not described by the CQA in the source ontology. For example, let us assume that the target formula et is o′:Paper for the “accepted paper” CQA. From the target ontology, the answers o′:paper1, o′:paper2, o′:paper3 and o′:paper4 are retrieved from et and matched to the source instances respectively o:paper1, o:paper2, o:paper3 and o:paper4. However, only o:paper1 and o:paper2 are accepted papers (and are described by the CQA) in the source ontology. Therefore o:paper3 and o:paper4 are counter-examples. The percentage of counter-examples is computed as follows. The answers anstet described by the target subgraph (et) are retrieved from the target knowledge. These answers are matched to source instances: ansset. The percentage of counter-examples is the proportion of common instances ansset which are not answers to the CQA (¬(ansscqa)). The equation for the percentage of counter-examples (percCounterExamples) is therefore:

4.7.DL formula similarity

In Step , the formulae are filtered based on their similarity score with the CQA. The similarity score is a combination of:

The similarity score is calculated with the following equation:

For instance, consider the similarity of ∃o′:hasDecision.o′:Acceptance with the unary CQA “accepted paper”.

4.8.DL formula filtering

In Step , the formulae are filtered. Only the DL formulae with a similarity higher than a threshold are put in correspondence with the CQA DL formula. If for a given CQA, there is no DL formula with a similarity higher than the threshold, only the best DL formulae with a non-zero similarity are put in the correspondence. The best DL formulae are the formulae with the highest similarity score. When putting the DL formula in a correspondence, if its similarity score is greater than 1, the correspondence confidence value is set to 1.

The definition of similarity can be seen as unusual, as it ranges from 0 to 1.5, while values of similarity are usually in [0,1]. We chose to have a structural similarity strong enough to exceed the sorting threshold for properties. In order to consider a non-structural similarity, a lexical measure has been considered. The structural similarity is only applied in the case of properties. In all cases, similarity/confidence is only used to filter out correspondences.

5.1.Matching approach set-up

Label similarity A threshold is applied to the similarity measure obtained: if the similarity between two labels is below a threshold τ, this similarity is considered noisy and is set to zero.

Path length threshold The maximum path length sought is 3. Paths longer than that may bring noise in the correspondences, as the path-finding algorithm searches for all combinations of properties.

Structural similarity The structural similarity is 0 for a triple (in the case of a unary CQA) and 0.5 for a path found between two matched entities (in the case of a binary CQA). Finding a path between two instances (the matched answers of a binary CQA) is a hint that this subgraph can be correct. In opposition, the structure subgraphs for unary CQA are not that informative.

DL formula threshold The DL formulae with a similarity higher than 0.6 are kept. If a CQA has no DL formula with a similarity higher than 0.6, the best formulae are put in correspondence (the formulae having the best similarity, if this similarity is above 0.01). This threshold was chosen to be above the structural similarity threshold (0.5) for a path subgraph. Indeed, if two paths are found but only one has a label similarity above 0, then its associated DL formula will be the only one output. These thresholds were empirically chosen.

Approach variants The other parameters have been varied to create a set of variants. These variants are listed in Table 2. For each variant (lines in the table), the different parameters (number of support answers, Levenshtein threshold, type of instance matching strategy, and computation of counter-examples) have been varied. The values of the baseline approach were empirically chosen: a Levenshtein distance threshold of 0.4, 10 support answers, and no similarity value reassessment based on counter-examples. Note that the support answers correspond to the CQA answers with a match in the target knowledge base which are used to find subgraphs.

5.2.Evaluation settings

Evaluation datasets An automatic evaluation was performed on the populated version of the OAEI Conference benchmark [32]. This dataset is composed of 5 ontologies, with 100 manually generated CQAs. This evaluation measured the impact of various parameters on the approach. Second, a manual evaluation was carried out on the Taxon dataset about plant taxonomy, composed of 4 large populated ontologies: AgronomicTaxon [25], AgroVoc [5], DBpedia [3] and TaxRef-LD [16]. 6 CQAs from AgronomicTaxon have been manually generated. The CQA used in this evaluation are the one presented in [31] which were manually written from AgronomicTaxon CQs [25].

Evaluation metrics The evaluation metrics are based on the comparison of instance sets, as described in [30]. The generated alignment is used to rewrite a set of reference source CQAs whose results (set of instances) are compared to the ones returned by the corresponding target reference CQA. This metric shows the overall coverage of the alignment with respect to the knowledge needs and the best-rewritten query.33 A balancing strategy consists of calculating the intrinsic alignment precision based on common instances.

Given an alignment Aeval to be evaluated, a set of CQA reference pairs cqapairs (composed of source cqas and target cqat), kbs the source knowledge base, kbt a target knowledge base, and f an instance set (I) comparison function:

coverage is based on the queryFmeasure (also used for selecting the best-rewritten query). This is motivated by the fact that it better balances precision and recall. Given a reference instance set Iref and an evaluated instance set Ieval:

A best-match (query f-measure) aggregation over the reference CQA is performed. An average of the best-match scores gives the CQA Coverage.

Balancing coverage, precision is based on classical (i.e., scoring 1 for same instance sets or 0 otherwise) or non-disjoint functions f (as in the following):

The CQA Coverage and Precision with the same scoring metric are finally aggregated in a Harmonic Mean.

For both coverage and precision, different functions f can be used for comparing instance sets (overlap, precision-oriented, recall-oriented etc.). These different functions are complementary. The classical (Equation (10)), recall-oriented (Equation (11)) and precision-oriented (Equation (12)) scoring functions are used in state-of-the-art works to emphasise whether the alignment favours precision or recall [6]. We have introduced the overlap metric to represent whether two queries have at least one common answer (Equation (13)). The not disjoint metric gives a 1 score to all the overlapping queries and the queries where Iev and Iref are empty sets.

Such metrics have been used in the automatic evaluation of the controlled populated version of the Conference dataset. Given the uneven population of Taxon (i.e., a same piece of knowledge can be represented in various ways within the same ontology and that all instances are not described identically), a manual evaluation has been carried out instead to avoid entailing noise in the instance-based comparison.

Environment The approach and evaluation system has been executed on an Ubuntu 16.04 machine configured with 16 GB of RAM running under an i7-4790 K CPU 4.00 GHz × 8 processors. The runtimes are given for a single run. The local SPARQL endpoints were run on the same machine with Fuseki 2.44

5.3.Results on populated conference

The approach has been run and evaluated on the populated conference 100% dataset on a local Fuseki 2 server. This choice is motivated by the fact that the search for a common instance is faster when the proportion of common instances in the source answers is higher. The implementation in Java of the evaluation system, as well as the Populated Conference dataset, is available.55

The variants of the approach have been compared to its baseline (Table 2). The parameters that are not described in this table such as path length threshold (3), DL formula filtering threshold (0.6), and structural similarity constants (0.5 for a path, 0 for a class expression) as presented in Section 5.1. This evaluation strategy allows for isolating the parameters and measuring their impact, as discussed in the following.

5.3.1.Impact of the threshold in the string similarity metric

An evaluation was performed with a Levensthein threshold set between 0.0 and 1.0. Figure 5 shows the number of found correspondence per type, with the detailed results in Figure 6. The number of correspondences decreases when the Levenshtein threshold increases. Numerous correspondences obtained with a low Levenshtein threshold cover a lot of CQAs (high CQA Coverage) but contain a lot of errors (low Precision). The lower the threshold, the better the CQA Coverage and the lowest the Precision. The Harmonic Mean is the highest for a threshold of 0.4 in the similarity metric. The baseline approach Levenshtein threshold (0.4) was chosen based on this experiment.

Fig. 5.

Number of correspondences per type for each variant with a different Levenshtein threshold.

Fig. 6.

Results of the evaluation with 10 support answers and variable Levenshtein threshold in the string similarity measure. The baseline results are highlighted by a vertical dashed line.

5.3.2.Impact of the number of support answers

The approach has been evaluated with a number of support answers between 1 and 100. The runtime of the approach over the 20 oriented pairs of ontologies is displayed in Figure 7 and Figure 8 shows the number of correspondences per type. The evaluation results are shown in Figure 9. It could be observed that even with 1 answer as support, the CQA Coverage and Precision scores are high, which shows that the approach can make a generalization from a few examples. As expected, the bigger the number of support answers, the longer the process is to run. Some CQA has only 5 answers (only 5 conference instances in the population of the ontologies), which explains why the time rises linearly between 1 support answer and 5 support answers and has a lower linear coefficient for support instances over 5. The Precision scores get lower with more support answers. The main reason is that particular answer cases that are lexically similar to the CQA labels can be discovered when a lot of instances are considered. For example, the correspondence ⟨ cmt:Person , ∃ conference:has_the_last_name.{“Benson”} , ≡⟩ was discovered by the variant with 100 support answers. Indeed, “Benson” is lexically similar to “Person”. The increase in the number of correspondences with the number of support answers shows that incorrect correspondences have been introduced.

The same problem occurs in the CQA Coverage: with 100 support answers, special cases having a higher similarity to the CQA than the expected formula can be found. As in the approach, the formulae are filtered, and when the similarity of the best formula is below a threshold (0.6), only the best one is kept. For example, with 10 support answers, the correspondence ⟨ conference:Rejected_contribution, ∃cmt:hasDecision.cmt:Rejection, ≡⟩ was found for the “rejected paper” CQA, the similarity of the target DL formula (0.43) was below the threshold (0.6) but it was the best formula so it was kept. For the 100 support answers, the correspondence ⟨conference:Rejected_contribution, ∃cmt:hasSubjectArea.{“entity consolidation”, “distribution”, “categorization”}, ≡⟩ and had a DL formula similarity (0.44) higher than the expected formula, so only this correspondence was output. Therefore the conference:Rejected_contribution CQA could not be covered with this alignment. However, the overlap CQA Coverage gets slightly higher for a high number of support answers because accidental correspondences have been introduced. For example, the correspondence ⟨conference:Topic, ∃rdfs:label.{“compliance”}, ≡⟩ was found with 100 support answers because “topic” and “compliance” have a 0.4 label similarity score. The Topic CQA over the conference-cmt pair was not covered by the variants of the approach with less than 100 support answers because no DL formula with a similarity above 0 was found.

Fig. 7.

Time taken by the approach to run for the 20 oriented pairs of ontologies with a different number of support answers.

Fig. 8.

Number of correspondence per type for each variant with a different number of support answers.

Fig. 9.

Results of the evaluation with a 0.4 Levenshtein similarity threshold and a variable number of support answers. The baseline results are highlighted by a vertical dashed line.

5.3.3.Similar instances based on exact label match or existing links

A variant of the approach does not use existing links between instances, instead, it performs an exact label match between instances. Figure 10 shows the number of correspondences per type of the baseline and its variant. Figure 11 shows the results of the baseline and its exact label match variant. The use of an exact label match for the instance matching phase brings noise to the correspondences and lowers the Precision. The overlap Precision also decreases because the correspondences are not ensured to share a common instance. In the baseline approach, which uses owl:sameAs links, the support answers were by definition common instances, and outputting correspondences with no overlap was not possible (except when dealing CQA with literal values). For example, the paper submissions and their abstracts share the same title. Therefore, a rejected paper instance can be matched with its abstract in the target knowledge base. The following correspondence results from this wrong instance match: ⟨ekaw:RejectedPaper, ∃conference:is_the_first_part_of.conference:Rejected_contribution, ≡⟩. This impacts the number of (c:c) correspondences which increases significantly when using the exact label match. Some ontologies use two data properties to link a person to their first and last name. The first and last names are then considered independent labels of the person instance. This induces confusion between two people sharing a first or a last name. The following correspondence was obtained by matching a person to another sharing the same first name: ⟨conference:has_the_first_name, edas:isReviewedBy⁻ ∘ edas:isWrittenBy ∘ edas:hasFirstName, ≡⟩.

The baseline approach (existing owl:sameAs links) takes 2.0 hours to run over the 20 pairs of ontologies whereas the exact label match approach takes 59.2 hours. The long runtime for the exact label match approach can be explained by the necessary steps to find the exact label match answers. First, the labels of each source answer to the CQA must be retrieved. This query takes about 64 ms. Then, for each label of the source answer, a match is sought. The runtime of the query to retrieve all instances annotated by a given label is about 2 s. The reason is that this query contains a tautology. The choice of this query was made because some ontologies define their labeling properties instead of using rdfs:label or other widely used properties.

When using direct links, these steps are replaced by directly retrieving owl:sameAs links, which takes about 20 ms per source instance. If the number of common support answers between the source and target ontology is reached (in the baseline, when 10 support answers are found), the approach stops looking for new matches. However, when no common instance can be found, the approach looks for a match for every answer of the CQA. This fact coupled with the slow label queries results in a long time. When common instances exist but do not share the same exact labels, the approach also looks for matches for every source answer, without success. For example, cmt represents the full name of a person, and conference represents its first name and its last name in two different labels. For the CQA retrieving all the Person instances, the approach goes through the 4351 instances without finding any match.

Fig. 10.

Number of correspondence per type for the baseline and the variant based on exact label match.

Fig. 11.

Comparison of the approach results when relying on existing owl:sameAs links or on an exact label-based instance matching. The baseline results are highlighted by a vertical dashed line.

5.3.4.CQAs or generated queries

In order to measure how the CQA impacts the results of the approach, the baseline approach is compared to a variant that does not rely on input CQA but automatically generates queries. Three types of SPARQL queries are generated for a given source ontology: Classes, Properties, and Property-Value pairs.

Classes For each owl:Class populated with at least one instance, a SPARQL query is created to retrieve all the instances of this class.

Properties For each owl:ObjetProperty or owl:DatatypeProperty with at least one instantiation, a SPARQL query is created to retrieve all the pairs of instances of this class.

Property-value pairs Inspired by the approaches of [17,18,35], SPARQL queries of the following form are created:

• – SELECT DISTINCT ?x WHERE {?x o1:property1 o1:Entity1.}

• – SELECT DISTINCT ?x WHERE {o1:Entity1 o1:property1 ?x.}

• – SELECT DISTINCT ?x WHERE {?x o1:property1 "Value".}

Table 3 shows the number of generated queries per source ontology of the evaluation set.

The approach based on generated queries will not output a correspondence for each CQA in the evaluation. Therefore, the rewriting systems in the evaluation process will bring noise. The CQA Coverage scores are comparable as only the best result is kept. The Precision of the alignment output is computed by comparing the instances of the source and target members in their respective ontologies. These Precision scores give an indicator of the actual precision of these approaches.

The results of the evaluation of the baseline (based on CQAs) and the query variant are presented in Figure 12. Figure 13 shows the number of correspondences per type. The CQA Coverage scores when the approach is based on generated queries are between 10% and 20% lower than those obtained with CQA. Indeed, the (c:c) correspondences it retrieves are limited to the Class-by-Attribute-Value pattern on their source member. The Precision scores are not comparable because the ontologies were populated based on CQA and not on entities: a Document class may be populated with more or fewer instances given its subclasses. As the approach relies on common instances, the overlap Precision (percentage of correspondences whose member’s instances overlap) is around 1.0. The classical Precision (percentage of correspondences whose members are strictly equivalent) is, however, rather low overall.

The baseline and the query variant both take 2.0 hours to run on the 20 pairs of ontologies. Even if there are more queries to cover than CQA, the runtime of the query variant is compensated by the “difficulty” of the CQA: some CQAs contain unions or property paths and therefore take more time to be answered by the Fuseki server than the generated queries.

The number of (s:s) and (s:c) correspondences is much higher for the query variant. This approach generates 380 queries that express simple expressions (lines classes and properties of Table 3) and therefore, will give (s:s) or (s:c) correspondences if a match is found. In comparison, the baseline approach relies on 133 SPARQL CQAs which represent a simple expression, and 145 which represent a complex expression.

Table 3

Number of generated queries and CQAs per source ontology

Nb of queries	cmt	Conference	confOf	edas	ekaw
classes	26	51	29	43	57
properties	50	50	20	28	26
properties-value	30	20	0	5	15
TOTAL	106	121	49	76	98
CQAs	34	73	54	52	65

Fig. 12.

Results for the baseline and the variant which generates queries (query).

Fig. 13.

Number of correspondence per type for the baseline and the variant which generates queries.

5.3.5.Similarity reassessment with counter-examples

The baseline, the query variant and their equivalent were run with a similarity reassessment phase. The runtime of the variants is presented in Figure 14. Figure 15 shows the number of correspondences per type output by the baseline and its variants. The results of this evaluation are presented in Figure 16.

Fig. 14.

Runtime of the baseline and its variants over the 20 oriented pairs of ontologies.

Fig. 15.

Number of correspondence per type for the baseline, the variant which generates queries (query) and their equivalent variants with similarity reassessment based on counter-examples.

The reassessment phase (finding counter-examples) increases the runtime by far, especially when running queries. It took 46.4 hours to run the cqa+reassess approach and 99.9 hours to run the query+reassess over the 20 pairs of ontologies when it only took 2.0 hours for the baseline or query versions. The baseline approach and the generated query variants have approximately the same runtime over the 20 pairs of ontologies. However, for a similar runtime, the results of the approach with the CQA are better than those with the generated queries.

As expected, the reassessment phase decreases the number of correspondences as they are filtered. It entails an increase in Precision. The Precision of cqa+reassess is between 8% and 15% higher than that of the baseline. The Precision of query+reassess is between 6% and 17% higher than that of the query variant.

The CQA Coverage remains the same for the baseline and cqa+reassess. The CQA Coverage score of query+reassess is about 3% lower than that of query. As more specific correspondences are preferred over more general ones during the similarity reassessment phase, it leaves fewer possibilities during the rewriting phase.

Fig. 16.

Results for the baseline, the variant which generates queries (query) and their equivalent with a counter-example-based similarity reassessment.

5.4.Comparison with existing approaches

The generated alignments for the Conference were compared with three reference alignments (two task-oriented alignments which vary in the types of correspondences and expressiveness – query rewriting alignment set and ontology merging alignment set – and the simple reference alignment from the OAEI Conference dataset) and two complex alignments generated from existing approaches (Ritze 2010 and AMLC):

The two approaches have been chosen because their implementations are available online and they output alignments in EDOAL. Ritze 2010 [23] and AMLC [9] both require simple alignments as input. They were run with ra1 as input. ra1 has then been added to Ritze 2010 and AMLC for the CQA Coverage evaluation. The Precision evaluation was made only on their output (ra1 correspondences excluded). Ritze 2010 took 58 minutes while AMLC took about 3 minutes to run over the 20 pairs of ontologies. Even though these two approaches are similar, this difference of runtime can be explained by the fact that Ritze 2010 loads the ontologies and parses their labels for each pattern while AMLC only loads the ontologies once. Moreover, Ritze 2010 covers 5 patterns while AMLC only covers 2. Some refactoring was necessary so that the alignments could be automatically processed by the evaluation system. The ra1 dataset had to be transformed into EDOAL, instead of the basic alignment format. The Alignment API could not be used to perform this transformation as the type of entity (class, object property, data property) must be specified in EDOAL. The Ritze 2010 alignments used the wrong EDOAL syntax to describe some constructions (AttributeTypeRestriction was used instead of AttributeDomainRestriction). The AMLC alignments were not parsable because of RDF/XML syntax errors. The entities in the correspondences were referred to by their URI suffix instead of their full URI (e.g., Accepted_Paper instead of http://ekaw#Accepted_Paper). Some correspondences were written in the wrong way: the source member was made out of entities from the target ontology and the target member was made out of entities from the source ontology. As the evaluation of these alignments was manual so far in the OAEI complex track, these errors had not been detected. The alignments’ syntax has been manually fixed so that they can be automatically evaluated.

Figure 17 shows the number of correspondences per type over the 20 pairs of ontologies. These alignments were not directional so their number of (s:c) and (c:s) correspondences are identical.

Fig. 17.

Number of correspondence per type for the proposed approach, reference alignments and complex alignment generation approaches. The alignments of Ritze 2010 and AMLC include ra1.

Fig. 18.

Results of the proposed approach, reference alignments and complex alignment generation approaches.

Figure 18 shows the results of the baseline approach (baseline), the baseline approach with counter-example-based similarity reassessment (cqa+reassess), and the compared alignments. The Precision results should be considered carefully. First of all, the relation of the correspondence is not considered in this score: all correspondences are compared as if they were equivalences. The Ontology merging and Query rewriting alignments contain a lot of correspondences with subsumption relations so their classical Precision score is lower than the percentage of correct correspondences it contains. Second, the precision of the alignments is considered to be between the classical Precision and the percentage of correspondences whose members are either overlapping or both empty (not disjoint) due to the way the ontologies were populated.

Another limitation of the Precision score is related to the correspondences whose members are not populated in the dataset. For instance, ⟨cmt:Preference, conference:Review_preference, ≡⟩ is a correct correspondence that was not detected as such in the Precision evaluation. The review preference of a reviewer for a paper was not part of the CQA for the population process. There is therefore no instance for either member of the correspondence.

To compensate for these errors, we use the not disjoint scoring metric in the Precision evaluation. The score for a correspondence is 1 when the members are overlapping or both empty and 0 otherwise. This metric gives the upper bound of the precision of an alignment. When calculating the Harmonic Mean of CQA Coverage and Precision, the overlap CQA Coverage was used with the not disjoint Precision score to give an upper bound. Indeed, in the CQA Coverage, the source query will never return empty results.

The CQA Coverage of Ritze 2010 and AMLC is higher than that of ra1 which they include. Overall, the CQA Coverage of the other alignments (Ontology Merging, Query Rewriting, ra1, Ritze 2010, and AMLC) is lower than the score of our approach. Indeed, ra1 only contains simple equivalence correspondences, Ritze 2010 and AMLC are mostly restrained to finding (s:c) class expressions correspondences (and therefore do not cover binary CQA). The Ontology merging and query rewriting alignments are limited to (s:c), (c:s) correspondences.

Globally, the Query rewriting alignment outperforms the Ontology merging in terms of CQA Coverage except for the edas-confOf pair. In the Ontology merging alignments, unions of properties were separated into individual subsumptions which were usable by the rewriting system. In the Query rewriting alignment, the subsumptions are unions.

CANARD obtains the best CQA Coverage scores except for the classical CQA Coverage where the Query rewriting alignment is slightly better (0.62 vs. 0.60). It can generate (c:c) correspondences which cover more CQA than the other alignments limited to (s:s), (s:c) and (c:s).

The Precision of our approach is overall lower than the Precision of reference alignments (considering that their Precision score is between the classical and not disjoint score). Ritze 2010 only outputs equivalent or disjoint correspondences. Its Precision score is therefore the same (0.75) for all metrics. AMLC achieves a better classical Precision than our baseline approach but contains a high number of disjoint correspondences (37% of all the output correspondences had members whose instance sets were disjoint).

Overall, as expected, the Precision scores of the reference alignments are higher than those output by the matches. Our approach relies on CQAs and for this reason, it gets higher CQA Coverage scores than Ritze 2010 and AMLC. Moreover, these two matches both rely on correspondence patterns which limit the types of correspondences they can generate.

5.5.Evaluation on taxon

The Taxon dataset is composed of 4 ontologies that describe the classification of species: AgronomicTaxon [25], AgroVoc [5], DBpedia [3] and TaxRef-LD [16]. The CQA used in this evaluation are the one presented in [31] which were manually written from AgronomicTaxon CQs [25]. The ontologies are populated and their common scope is plant taxonomy. Their particularity, however, is that within the same dataset, the same information can be represented in various ways but irregularly across instances. For this reason, creating a set of references and exhaustive CQA is not easily feasible.

The knowledge bases described by these ontologies are large. The English version of DBpedia describes more than 6.6 million entities alone and over 18 million entities.1010 The TaxRef-LD endpoint contains 2,117,434 instances1111 and the AgroVoc endpoint 754,87411. AgronomicTaxon has only been populated with the wheat taxonomy and only describes 32 instances. The approach has been run on the distant SPARQL endpoints but server exceptions have been encountered, probably due to an unstable network connection or an overload of the servers. A reduced version of the datasets was then stored on a local machine to avoid these problems. The reduced datasets contain all the plant taxa and their information (surrounding triples, annotations, etc.) from the SPARQL endpoint of the knowledge bases. Table 4 shows the number of plant taxa in each knowledge base. Even though the number of instances was reduced, the knowledge bases are still large-scale.

The approach is run with the following settings: Levenshtein threshold: 0.4; Number of support answers: 1 and 10 (two runs); Instance matching: look for existing links (owl:sameAs, skos:closeMatch, skos:exactMatch) and if no target answer is found like that, perform an exact label match; No counter-example reassessment (computing the percentage of counter-examples would last too long on this dataset). The generated correspondences have been manually classified as equivalent, more general, more specific, or overlapping. The classical, recall-oriented, precision-oriented, and overlap scores have been calculated based on this classification.

5.5.1.Evaluation results

The number of correspondences per type is shown in Figure 19. The correspondences have been manually classified as equivalent, more general, more specific, or overlapping. The classical, recall-oriented, precision-oriented, and overlap scores have been calculated based on this classification. The results are shown in Figure 20.

Fig. 19.

Number of correspondence per type for the approach with 1 and 10 support answers on the taxon dataset.

Overall, the classical Precision and CQA Coverage scores are rather low. The Precision of the approach with 1 or 10 support answers is approximately the same. However, the CQA Coverage is higher with 10 instances. In comparison with the Conference dataset, this can be explained by the differences in population between the knowledge bases and the uneven population of a knowledge base in itself. We guess that the more support answers the approach takes, the better its CQA Coverage will be when dealing with unevenly populated ontologies.

The uneven population of some knowledge bases leads to missing correspondences. For example, the entity agronto:hasTaxonomicRank is not represented for every instance of Agrovoc. agrovoc:c_35661 which is the Asplenium genus taxon has no agronto:hasTaxonomicRank property. When this instance was used as a support instance, it could not lead to the detection of a correspondence involving its rank. When running our matching approach with only 1 support instance, using this instance would result in an empty set of correspondences for some CQAs. Consequently, the CQA Coverage is globally higher for the approach with 10 support answers.

The particularity of a dataset about species taxonomy is that two taxa are likely to share the same scientific name. Our exact label match strategy is therefore rather suited for such a dataset. In some cases, however, it introduced noise. For example, confusion was made between wheat the plant taxon, and wheat the consumable good, or between a division, part of an administrative structure, and the taxonomic rank division.

The Levenshtein-based string similarity brings the noise. For example, the correspondence ⟨agrotaxon:GenusRank, ∃agronto:produces.{agrovoc:c_8373}, ≡⟩ whose target member represents all the agronomic taxa which produce wheat has been output. This is due to the string similarity between the Malay label of wheat “Gandum” and the English label “Genus” of the agrotaxon:GenusRank class. We could have chosen to compare labels in the same language together but sometimes, the language of a label was missing, and sometimes the scientific name was either tagged as English or Latin.

Fig. 20.

Results of the approach with 1 and 10 support answers on the taxon dataset.

The total runtime over the 12 pairs of ontologies was 99,297 s (27.6 h) for the approach with 1 support instance and 113,474 s (31.5 h) for the approach with 10 support answers. The runtime per pair of ontologies is detailed in Table 5. Three factors explain the different runtime over the pairs of ontologies in Table 5.

Query difficulty	Some CQA was long to run on large knowledge bases, in particular those involving the union of properties.
Percentage of source common instances	The number of taxa instances can be different between knowledge bases. AgronomicTaxon and DBpedia share 22 instances. When AgronomicTaxon, which has only 32 instances is matched to DBpedia, finding a common instance between the two is rather easy because about 68% of its instances have an equivalent in DBpedia. The other way around is way harder because only 0.04% of DBpedia taxa instances have an equivalent in AgronomicTaxon.
Existence of instance links	When no explicit instance links exist between two knowledge bases, all the source instances are explored and the exact label match is performed. This can take a lot of time according to the size of the target knowledge base.

5.6.Comparison on OAEI systems

Section 5.4 has presented a comparison of CANARD with existing systems in the OAEI Conference ontologies. This section provides a comparison of the complex systems participating in the OAEI Complex Track since its creation in 2018. These results are presented in Table 6. Results involving simple alignments are not reported here. With respect to the systems (some already introduced above), AROA [41] is based on association rule mining and implements the algorithm FP-growth to generate complex alignments. MatchaC [8] is the successor of AMLC and has introduced machine learning strategies.

Overall, results and participation are still modest (only 3 participants in all campaigns) and as explained in this paper, CANARD can only deal with populated datasets.

For the (non-populated) Conference dataset (manual evaluation on a subset of the original Conference dataset), only AMLC (and its successor MatchaC) was able to deal with the task, with results that have been similar over the years. Still, the performance is far from those obtained with simple alignments. AMLC maintained its F-measure over the campaigns. For the Populated Conference, introduced in 2019, CANARD achieved close results to AMLC in terms of Coverage and it maintains its performance over the campaigns (the detailed results are described in Section 5.3.

With respect to the Hydrography sub-track case, only AMLC can generate (few) correct complex correspondences, with fair results in terms of precision, to the detriment of recall. In GeoLink, AMLC, AROA, and CANARD were able to output correspondences, for the version of the dataset having instances, with a higher number of complex correspondences being found by AROA and CANARD (which report close results). In 2020, a fully populated version has been introduced (Populated GeoLink), reporting as expected the same results as the previous version of GeoLink in 2019. In the Populated Enslaved sub-track, CANARD is outperformed by AMLC and AROA. AROA found the largest number of complex correspondences among the three systems, while the AMLC outputs the largest number of simple correspondences. For Taxon, CANARD is the only system that can deal with the high heterogeneity of the task and can retrieve correct complex correspondences (with a high performance considering at least one common instance in the coverage results). Overall systems still privilege precision and detriment of recall (except AMLC in 2018), leaving room for several improvements in the field.

Concerning OAEI 2023, MatchaC, LogMap, and LogMapLite have registered to participate. While LogMapLite and LogMap are dedicated to generating simple correspondences, only LogMap was able to generate nonempty (simple) alignments. MatchaC, the only system specifically designed to generate expressive correspondences in OAEI 2023, had some issues dealing with the datasets and was not able to generate valid alignments. Unfortunately, in 2023, several datasets have also been discontinued (Hydrography, GeoLink, Populated GeoLink, Populated Enslaved, and Taxon). While the last participation of CANARD in OAEI campaigns was in 2020, improvements so far have addressed runtime, as reported in this paper. We plan to come back to the campaigns with new improvements in the way expressive correspondences are generated.

5.7.Qualitative evaluation

In order to provide a more qualitative analysis of the generated alignments, we analyzed the correct correspondences uniquely identified by CANARD whereas missed by other systems. The alignments come from the outputs of the systems in the 2020 OAEI corresponding to Table 6, on the Populated Conference dataset. The choice of this dataset is motivated by the fact that we have reference competency questions and access to the evaluation system for providing such an analysis. The analysis involves 8 pairs of alignments: conference-confOf, conference-ekaw, confOf-conference, confOf-ekaw, edas-ekaw, ekaw-conference, ekaw-confOf, ekaw-edas. The number of correct correspondences in each pair found only by CANARD is presented in Table 7.

The majority of correspondences that CANARD can generate, and that AMLC is not able to, are related to properties in the target entity. They are correspondences between properties or correspondences between class constructors and restrictions that apply to properties. Such a correspondence is the correspondence between the property reviewerOfPaper and a property restriction of contributes with the domain of Review. Another similar correspondence is between the property hasReview and the inverse of reviews with range restriction to Review. The correct correspondences that CANARD can find and AMLC is not able to identify for the pair confOf-ekaw are listed in Table 8. It shows that all types of target entities (ent2_type) are related to properties since edoal:Relation relates to properties and edoal:AttributeDomainRestriction are restrictions applied to property domains.

5.8.Improvements in performance

As reported above, CANARD has a higher runtime in specific settings. To address this weakness, improvements in its implementation have been carried out.1212 The most expensive steps in the current implementation concern steps 4 to 7. The first issue is the text search done in Jena without a text index, which has to be mitigated with a text index configuration. The second issue relates to the many requests to the server and since the main line of communication is done through HTTP, some steps like the socket communication and HTTP request parsing slow the system. One example of such a case is in step 4 where the system looks for shared instances between the ontologies. When no instances are found, similar instances are queried using the SPARQL filter with a regex search that is slow without a full-text search index. As an exact string comparison is made in this step, the first improvement is the use of a map structure to store the triples in memory, and with this structure is possible to query similar instances by text in constant time without the HTTP overhead. With this structure, the majority of queries executed in Apache Jena can be replaced by the map lookup. This structure improves performance on steps 5, 6, and 7 as they depend on these functions to operate. The improvements come at the cost of increased memory usage as indexes need to be stored for subjects, predicates, and objects.

Another step with high running time is the subgraph query for binary CQs. This step needs to find similar paths in the ontology structure using an iterative path-finding algorithm. However, the populated ontologies can have imbalanced structures. For example, a Paper class can have thousands of instances that need to be verified in each step even for small paths (size 5 for example). This issue is still not addressed in terms of the number of comparisons done in path-finding. Still, since the similarity calculation performed in each step uses the indexed map it is faster than the original implementation.

To evaluate the impact of these modifications, the base and improved version performances were compared in the populated Conference dataset with an exact label match approach. The base version was run in one alignment pair between CMT and Conference with 34 CQAs and takes approximately 6:18 hours to run with one threshold value. The improved version was run in 4 alignment pairs between CMT and Conference, Conference and ConfOf, ConfOf and Edas, and Edas and ekaw with 213 CQAs in total with 9 thresholds in the range from 0.1 to 0.9. The improved system runs the 4 pairs in 25 minutes and runs the CMT and conference pair in 52 seconds approximately.