In order to enable interoperability between ontology-based systems, ontology matching techniques have been proposed. However, when the generated mappings suffer from logical flaws, their usefulness may be diminished. In this paper we present a multi-strategy approach to detect and correct violations of the so-called conservativity principle where novel subsumption entailments between named concepts in one of the input ontologies are considered as unwanted. The practical applicability of the proposed approach is experimentally demonstrated on the datasets from the Ontology Alignment Evaluation Initiative (OAEI).
Ontologies play a key role in the development of the Semantic Web and are being used in many diverse application domains, ranging from biomedicine to energy industry. An application domain can be modeled with different points of view and purposes. This situation usually leads to the development of different ontologies that intuitively overlap, but they use different naming and modeling conventions.
The problem of (semi-)automatically computing mappings between independently developed ontologies is usually referred to as the ontology matching problem. A number of sophisticated ontology matching systems have been developed in the last years [5,23]. Ontology matching systems, however, rely on lexical and structural heuristics and the integration of the input ontologies and the mappings may lead to many undesired logical consequences. In [12] three principles were proposed to minimize the number of potentially unintended consequences, namely: (i) consistency principle, the mappings should not lead to unsatisfiable classes in the integrated ontology, (ii) locality principle, the mappings should link entities that have similar neighbourhoods, (iii) conservativity principle, the mappings should not introduce new semantic relationships between concepts from one of the input ontologies.
The occurrence of these violations is frequent, even in the reference mapping sets of the Ontology Alignment Evaluation Initiative 3 (OAEI). Also manually curated alignments, such as UMLS-Metathesaurus [1] (UMLS), a comprehensive effort for integrat-ing biomedical knowledge bases, suffer from these violations. Violations of these principles may hinder the usefulness of ontology mappings [25]. These principles has been actively investigated in the last years (e.g., [17,9,12,10,16,21]).
In this paper we combine our previous approach [25] for detecting and solving conservativity principle violations, based on the assumption of disjointness [22] and the projection of the input ontologies to Horn propositional logic, with a new one based on Answer Set Programming [24], addressing violations between entities already involved in a subsumption relationship. Our evaluation supports the effectiveness of the combined approach in the detection and correction of an extended notion of conservativity violations, without harming efficiency, even on the largest test cases of OAEI.
The remainder of the paper is organised as follows. Section 2 presents the preliminaries. Section 3 introduces our motivating scenario. Section 4 describes our method. Section 5 presents the conducted evaluation. Section 6 provides a comparison with relevant related work. Finally, Section 7 gives some conclusions and future work lines.
This section introduces the representation of ontology mappings, the notions of semantic difference and conservativity principle, and the basics on Answer Set Programming.
Representation of Ontology Mappings. Mappings are 5-tuples of the form id, e 1 , e 2 , n, ρ , with id a unique identifier, e 1 , e 2 entities in the vocabulary or signature of the relevant input ontologies (i.e., e 1 ∈ Sig(O 1 ) and e 2 ∈ Sig(O 2 )), n a confidence measure between 0 and 1, and ρ a relation between e 1 and e 2 , typically subsumption, equivalence, or disjointness. Mappings are usually represented as OWL 2 axioms for reusing the currently available OWL 2 reasoning infrastructure, but alternative formal semantics have been proposed (e.g., [2]).
Semantic Consequences of the Integration. The ontology resulting from the integration of two ontologies O 1 and O 2 via a set of mappings M may entail axioms that do not follow from O 1 , O 2 , or M alone. These new semantic consequences can be captured by the notion of deductive difference [15]. Intuitively, the deductive difference between O and O w.r.t. a signature Σ is the set of entailments constructed over Σ that do not hold in O, but do hold in O . However, no algorithm is available for computing it for DLs more expressive than EL, for which the existence of tractable algorithms is still open [15] Definition 1 (Approximation of the Deductive Difference). Let A, B be atomic concepts from Σ ∪ { , ⊥}, O and O be two OWL 2 ontologies, with Σ is a signature. We define the approximation of the Σ-deductive difference between O and O (denoted In order to avoid the drawbacks of the deductive difference, in this paper we rely on the approximation given in Definition 1. This approximation only requires comparing the classification hierarchies of O and O provided by an OWL 2 reasoner, and it has successfully been used in the past in the context of ontology integration [11].
Conservativity Principle. The conservativity principle (as formulated in [12]) states that the integrated ontology
, respectively. In [25] we proposed a basic variant of the conservativity principle where O U is required not to introduce new subsumption relationships between concepts from one of the input ontologies, unless they were already involved in a subsumption relationship or they shared a common descendant. In this paper, in addition to these basic violations, we also aim at addressing violations between concepts already involved in a subsumption relationship (i.e., resulting in an equivalence between them), denoted as equivalence conservativity principle violations, or simply equivalence violations. As in [25], we assume that the mappings M are coherent w.r.
As discussed, for basic violations the assumption of disjointness can be applied, that is, if two atomic concepts A, B from one of the input ontologies are not involved in a subsumption relationship nor share a common subconcept (excluding ⊥) they can be considered as disjoint. Hence, the repair of these violations can be reduced to a consistency repair, if the input ontologies are extended with sufficient disjointness axioms. The same does not necessarily hold for equivalence violations, for which a suitable repair algorithm, based on ASP, is introduced (see Section 4.2).
Answer Set Programming. ASP is a declarative programming language able to express complex search problems up to Σ P 2 complexity class (and its complement Π P 2 [6]). Each ASP program is a set of rules of the form Head ← Body, where Head can be a disjunction of atoms. More formally, a disjunctive rule has the form a 1 ∨ . . . ∨ a n ← b 1 , . . . , b k , not b k+1 , . . . , not b m . Rules with an empty Body (i.e., k = m = 0) are called facts. ASP rules can also include optimization-oriented constructs for minimizing numeric variables or the cardinality of a predicate. These rules are called soft constraints, in opposition to hard constraints, which are rules with an empty Head. In ASP, solutions are called stable models [6].
In this section, we show an example involving the different kinds of conservativity principle violations arising in the integration of two ontologies modeling knowledge in oil and gas industry [25]. Table 1 shows the relevant fragments of the two ontologies. Assume that the set of mappings M in Table 2, between O 1 and O 2 , is generated by an off-the-shelf ontology alignment system. As described in Section 2, mappings are represented as 5-tuples; for example the mapping m 2 suggests an equivalence relationship between the entities O 1 :WellBore and O 2 :Borehole, with confidence 0.7.
Input: O1, O2: input ontologies; M: (coherent) input mappings; Output: M : output mappings; R ≈ : approximate repair; disj: number of disjointness rules 1:
The integrated ontology O U = O 1 ∪ O 2 ∪ M, however, violates the conservativity principle, according to Definition 2, and introduces unwanted subsumption relationships (see Table 3). Note that the entailments σ 4 and σ 5 are equivalence violations not belonging to the set of basic violations, since O 1 :Company and O 1 :Operator (resp. O 2 :Field operator and O 2 :Company) are involved in a subsumption relationship in O 1 (resp. O 2 ). As already discussed, these entailments cannot be repaired by the approach introduced in [25], and in addition they also lead to basic violations (σ 6 and σ 7 ), as shown in Figure 1. Note that equivalence violations σ 4 , σ 5 can be repaired by the ASPbased approach. As shown in [25], any of these conservativity violations may hinder the usefulness of the generated mappings, in a query answering scenario.
This section describes the algorithms composing our multi-strategy approach, one addressig basic violations (Section 4.1), the other the equivalence ones (Section 4.2).
We have reduced the problem of detecting and solving basic violations, to a mapping (incoherence) repair problem. Currently, our method uses the indexing and reasoning techniques of LogMap, an ontology matching and mapping repair system [10,13].
Algorithm 1 shows the pseudocode of the implemented method. The algorithm accepts as input two OWL 2 ontologies, O 1 and O 2 , and a set of mappings M which are coherent4 w.r.t. O 1 and O 2 . The problem size is reduced by extracting two localitybased modules [3] (O 1 and O 2 ) using the entities involved in the mappings M as seed signatures (line 1, Algorithm 1). The output is the number of added disjointness during the process disj, a set of mappings M , and an approximate repair R ≈ s.t. M = M \ R ≈ . The repair R ≈ aims at solving most of the basic violations of M w.r.t. O 1 and O 2 . We next describe the techniques used in each step.
Propositional Horn Encoding. The modules O 1 and O 2 are encoded as the Horn propositional theories, P 1 and P 2 (line 2 in Algorithm 1). The encoding includes rules of the form A 1 ∧ . . . ∧ A n → B, with A i , B atomic concepts. For example, the concept hierarchy provided by an OWL 2 reasoner (e.g., [18,14]) is encoded as A → B rules, while explicit disjointness axioms between atomic concepts are encoded as A i ∧ A j → false. Note that input mappings M can already be seen as propositional implications.
Example 1. Consider the ontologies and mappings in Tables 1 and 2. Axiom β 6 is encoded as rule Field operator ∧ Owner → Field owner, while the mapping m 2 is translated into rules O 1 :WellBore → O 2 :Borehole, and O 2 :Borehole → O 1 :WellBore.
Structural Index. The concept hierarchies provided by an OWL 2 reasoner (excluding ⊥) and the explicit disjointness axioms of the modules O 1 and O 2 are efficiently indexed using an interval labelling schema (line 3 in Algorithm 1). This structural index allows us to answer many entailment queries over the concept hierarchy as an index lookup operation (i.e., without the need of an OWL 2 reasoner).
Disjointness Axioms Extension. In order to reduce the (basic) conservativity problem to a mapping incoherence repair problem, following the notion of assumption of disjointness, we need to automatically add sufficient disjointness axioms into each module O i . However, additional disjointness axioms δ may lead to unsatisfiable classes in O i ∪ δ.
Example 2. Consider the axiom β 9 from Table 1. Following the assumption of disjointness a very naïve algorithm would add disjointness axioms between Borehole, Continuant and Occurrent, which would make Borehole unsatisfiable.
For avoiding an extensive use of a costly OWL 2 reasoner, our method exploits the propositional encoding and structural indexing of the input ontologies. Thus, checking for unsatisfiabilities introduced by candidate disjointness axioms in O i ∪ δ is restricted to the Horn propositional case. We have implemented an algorithm to extend the propositional theories P 1 and P 2 with disjointness rules of the form A ∧ B → ⊥ (see lines 5-6 in Algorithm 1). This algorithm guarantees that, for every propositional variable A in the extended propositional theory P d i (with i ∈ {1, 2}), the theory P d i ∪ {true → A} is satisfiable. Note that this does not necessarily hold when considering the OWL 2 ontology modules, O 1 and O 2 , as discussed above.
LogMap provides a structural index SI to check if two propositional variables (i.e., ontological classes) are disjoint (areDisj(SI, A, B)), they keep a sub/super-class relationship (inSubSupRel(SI, A, B)), or they share a descendant (shareDesc(SI, A, B)).
Nonetheless, the massive addition of disjointness rules is, in general, prohibitive for large ontologies [25]. Our key ingredient to achieve scalability is to focus only on the cases where a basic violation occurs in the integrated ontology
, as in Definition 2. Algorithm 2 implements this idea for the Horn propositional case and extensively exploits the structural indexing to identify the basic violations (line 2, Algorithm 2). Note that this algorithm also requires to compute the structural index of the integrated ontology and thus its classification with an OWL 2 reasoner (line 4, Algorithm 1). The classification cost of the integrated ontology is usually much higher than the classification of the input ontologies individually. However, this was not a bottleneck in our experiments (see Section 5).
Input: P: propositional theory; SI: structural index SI U : structural index of the union ontology Output: P d : extended propositional theory;disj: number of disjointness rules 1: disj := 0, P d := P 2: for A → B ∈ BasicConservativityViolations(SI, SI U ) do 3:
if not (areDisj(SI, A, B)) then 4:
end if 8: end for 9: return P d , disj Mapping Repair. Line 7 of Algorithm 1 uses the mapping (incoherence) repair algorithm presented in [13]for the extended Horn propositional theories P d 1 and P d 2 , and the input mappings M. The mapping repair process exploits the Dowling-Gallier algorithm for propositional Horn satisfiability [4] and checks, for every propositional variable A ∈ P d 1 ∪P d 2 , the satisfiability of the propositional theory P A = P d 1 ∪P d 2 ∪M∪{true → A}. Satisfiability of P A is checked in worst-case linear time in the size of P A , and the number of Dowling-Gallier calls is also linear in the number of propositional variables in
The algorithm records the conflicting mappings involved in the unsatisfiability, which will be considered for the subsequent repair process. The unsatisfiability will be fixed by removing some of the identified mappings. In case of multiple options, mapping confidence will be used as a differentiating factor. 5Example 3. Consider the propositional encoding P 1 and P 2 of the axioms of Table 1 and the mappings M in Table 2, seen as propositional rules. P d 1 and P d 2 have been created by adding disjointness rules to P 1 and P 2 , according to Algorithm 2. For example, P d 2 includes the rule ψ = O 2 :Well ∧ O 2 :Borehole → f alse. The mapping repair algorithm identifies the propositional theory P d 1 ∪ P d 2 ∪ M ∪ {true → O 1 :ExplorationWellbore} as unsatisfiable. This is due to the combination of the mappings m 3 and m 4 , the propositional projection of axioms β 1 and β 2 , and the rule ψ. The mapping repair algorithm also identifies m 3 and m 4 as the cause of the unsatisfiability, and discards m 3 since its confidence is smaller than that of m 4 (see Table 2). Algorithm 1 gives as output the number of added disjointness rules disj, a set of mappings M , and an (approximate) repair R ≈ such that M = M \ R ≈ . M is coherent w.r.t. P d 1 and P d 2 . Furthermore, the propositional theory P 1 ∪ P 2 ∪ M does not contain any basic violation w.r.t. P 1 and P 2 (according to the propositional case of Definition 2). However, our incomplete encoding cannot guarantee that O 1 ∪ O 2 ∪ M does not contain basic violations w.r.t. O 1 and O 2 . Nonetheless, our evaluation suggests that the number of remaining violations after repair is typically small (see Section 5).
In this section we describe CycleBreaker algorithm that detects equivalence violations at the taxonomical level, and computes a minimal repair by means of a logic program 6 . ∆ ← ∆ ∪ ASP(S) 6: end for 7: return ∆ Algorithm Description. Algorithm 3 takes as input two ontologies O 1 ,O 2 , and an alignment M between them. The aligned ontology O M is computed (line 1), and createDigraph function (line 2) builds its graph representation, having its named concepts as the set of vertices, and the subsumption axioms between them as (weighted) arcs. Given that the aligned ontology is equivalent, here, to the classification of the input ontologies plus the mappings, only inferred arcs between concepts of the same input ontology may exist. Given that at least one cycle containing all the elements of a strongly connected components (SCC) exists, cycle detection for a graph G can be reduced to computing SCC(G ), the set of its SCCs. Tarjan's algorithm [26] computes the SCCs of the graph representations of the input ontologies (named local SCCs) and of the aligned one (line 3). Note that not all the cycles leads to an equivalence violation. We therefore distinguish between unsafe and safe cycles as those producing or not a violation. For detecting all the unsafe cycles, it is sufficient to detect the problematic SCCs, identified by the fact that at least one of the two projections on the input ontologies is not a local SCC (line 4). The ASP program of Listing 1.1 then computes a minimal repair for each problematic SCC (line 5). (r0) states that X, Y, Z are always vertices, (r1,r2) define transitive predicate reachesSaf e expressing vertex reachability in the input ontologies (in isolation), (r3,r4) define transitive predicate reaches expressing vertex reachability in the aligned ontology (i.e., considering edges and unremoved mappings only), (r5) generates models, (r6) allows mapping removal only, (r7) computes unsafe cycles in the graph, (r8) is a hard constraint forbidding the existence of unsafe cycles (r9) is a soft constraint that selects one of the valid models having minimal total weight of removed mappings.
Repair Computation Using ASP. The input facts for the ASP program are the following kinds: (i) predicate vtx(X, O) encodes vertices, where X is a unique vertex id (e.g., vertex label) and O ∈ {1, 2} is the index of the input ontology of the concept, (ii)
In order to evaluate the practical feasibility of our approach, we have conducted the evaluation in Algorithm 4 (Roman numbers refer to stored measurements) over the Optique's use case [25] and the ontologies and reference mapping sets of OAEI 2013. 7Table 4 shows the size of the evaluated ontologies and mappings (I, II and III). For the Conference dataset we have selected only 5 pair of ontologies for which the reference mappings lead to more than five conservativity principle violations. Note that we count equivalence mappings as two subsumption mappings, and hence M represents subsumption mappings. Table 4 also shows the conservativity principle violations for the reference mappings (IV, V and VI). For LargeBio and Library the number is expecially large using both the basic variant and the general notion of the conservativity principle. 8 We have run the experiments shown in Table 5 on a desktop computer with an AMD Fusion A6-3670K CPU and allocating 12 GB of RAM. The prototype uses Clingo 3.0.5 9 ASP solver. The obtained results10 can be summarised as follows: i The number of added disjointness rules disj (VII), as expected, coincides with the number of basic violations, that is computed in a reasonable time also for large testcases (it requires only 80 seconds to compute them in the SNOMED-NCI case). ii The computed repair R SCC (X) is rather aggressive and it can remove from 16% (Anatomy) up to 48% (Optique) of the mappings. However, we follow a better safe than sorry approach, and we prefer to remove as many violations as possible, rather than preserving potentially conflicting mapping sets. iii Global repair time t r (IX) is small and it does not represent a bottleneck in spite of the large number of added disjointness rules and multiple applied techniques. iv The basic violations (XI) are fully removed in the Optique, Anatomy and Library cases, and almost fully removed in the Conference and LargeBio ones. v The number of missed violations is only slightly higher when considering the general notion of the conservativity principle (XII), which suggests that basic variant is suitable in practice. Furthermore, these violations are also almost always removed. vi Restricting to equivalence violations, they are almost completely removed by the combined approach (XIII). In order to evaluate the effectiveness of CycleBreaker, we also measured the number of unsolved equivalence violations after applying this repair algorithm, in isolation, on the input reference alignment. With the exception of SNOMED-NCI (failure rate of 0.9%), the violations are totally repaired.
The conservativity principle, although indirectly, has been actively studied in the literature. For example, the assumption of disjointness was originally introduced by Schlobach [22] to enhance the repair of ontologies that were underspecified in terms of disjointness axioms. As in our case, also [27,17,7], have focused on the addition of a small set of disjointness axioms, for supporting large ontologies. Ontology matching systems have also dealt with the conservativity principle in order to improve the precision (w.r.t. a reference alignment) of the computed mappings. For example, ASMOV [9], Lily [28] and YAM++ [19] implements different heuristics and patterns to minimise the violations of the conservativity principle. Lily, in particular, supports an incomplete detection of the equivalence violations, but lacks of a repair technique. Our basic method solves conservativity violations by reducing the problem to a consistency principle violation problem. Concretely, we have extended LogMap matcher [10] but other mapping repair systems could be considered (e.g., Alcomo [16] or AML [21]). Note that these systems only focused on the consistency principle.
The work presented in [8] follows an opposite approach with respect to ours, and considers conservativity violations as false positives, caused by the potential incompleteness of the input ontologies. Hence, the correction strategy, instead of removing mappings, aims at inserting subsumption axioms to the input ontologies, to enrich their concept hierarchies. Authors in [20] also suggest that fixing the input ontologies, in a mapping repair process, could be an alternative to mapping removal.
In this paper we have presented a fully-automatic multi-strategy method to detect and correct conservativity principle violations in practice. We have extended the detect and repair algorithm for basic violations [25] with a repair algorithm based on logic programming, tailored for equivalence violations. The conducted evaluation supports the practical effectivity of our incomplete method. We plan to extend the approach while keeping the current scalability properties. The proposed algorithms follow a "better safe than sorry" approach, suitable for scenarios where the input ontologies are not modifiable (e.g., fully automatic ontology matching systems). Nevertheless we do not discard to explore alternative methods to address the conservativity principle violations. We also plan to involve domain experts in the assessment of the additional disjointness [7], and to suggest extensions to the input ontologies [8] for violations recognised as false positives. We will also evaluate the mappings computed by systems participating at OAEI, and the integration of our techniques into LogMap matcher.