A Multi-strategy Approach for Detecting and Correcting Conservativity Principle Violations in Ontology Alignments?

Abstract

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).

Introduction

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 Initiative3 (OAEI). Also manually curated alignments, such as UMLS-Metathesaurus [ 1 ] (UMLS), a comprehensive effort for integrat? This work was supported by the EU FP7 IP project Optique (no. 318338) and by the Italian

PRIN 2010LHT4KM CINA. 3 http://oaei.ontologymatching.org/ 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. 2

Preliminaries

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 hid; e1; e2; n; i, with id a unique identifier, e1; e2 entities in the vocabulary or signature of the relevant input ontologies (i.e., e1 2 Sig(O1) and e2 2 Sig(O2)), n a confidence measure between 0 and 1, and a relation between e1 and e2, 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 inte

gration of two ontologies O1 and O2 via a set of mappings M may entail axioms that do not follow from O1, O2, or M alone. These new semantic consequences can be captured by the notion of deductive difference [ 15 ].

Intuitively, the deductive difference between O and O0 w.r.t. a signature is the set of entailments constructed over that do not hold in O, but do hold in O0. However, no algorithm is available for computing it for DLs more expressive than E L, for which the existence of tractable algorithms is still open [ 15 ]

Definition 1 (Approximation of the Deductive Difference). Let A; B be atomic con

cepts from [ f>; ?g, O and O0 be two OWL 2 ontologies, with is a signature. We define the approximation of the -deductive difference between O and O0 (denoted di (O; O0) as the set of axioms of the form A v B satisfying: (i) O 6j= A v B, and (ii) O j

0 = A v B.

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 O0 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 OU = O1 [ O2 [ M should not induce any change in the concept hierarchies of the input ontologies. That is, the sets di 1 (O1; OU ) and di 2 (O2; OU ) must be empty for signatures 1 = Sig(O1) and 2 = Sig(O2), respectively. In [ 25 ] we proposed a basic variant of the conservativity principle where OU 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.t. O1 and O2 (i.e., di (O1[O2; OU ) does not contain any axiom A v ?, for any A 2 = Sig(O1 [ O2)). Definition 2 (Conservativity Principle Violations). Let O be one of the input ontologies and Sig(O) be its signature, let OU be the integrated ontology, and let A; B be atomic concepts in Sig(O) [ f>; ?g. We define two sets of violations of OU w.r.t. O: – basic violations, denoted basicViol(O; OU ), as the set of A v B axioms satisfying: (i) A v B 2 di Sig(O)(O; OU ), (ii) O 6j= B v A, and (iii) there is no C in Sig(O) [ f>; ?g s.t. O j= C v A, and O j= C v B. – equivalence violations, denoted eqViol(O; OU ), as the set of A B axioms satisfying: (i) OU j= A B, (ii) A v B 2 di Sig(O)(O; OU ) and/or B v A 2 di Sig(O)(O; OU ).

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 2P complexity class (and its complement 2P [ 6 ]). Each ASP program is a set of rules of the form H ead Body, where H ead can be a disjunction of atoms. More formally, a disjunctive rule has the form a1 _ : : : _ an b1; : : : ; bk; not bk+1; : : : ; not bm: 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 H ead. In ASP, solutions are called stable models [ 6 ]. 3

Running Example

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 O1 and O2, 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 m2 suggests an equivalence relationship between the entities O1:WellBore and O2:Borehole, with confidence 0:7. n YES YES YES NO YES

YES Owner2

F ield owner2 1 Algorithm 1 Algorithm to detect and solve basic violations Input: O1, O2: input ontologies; M: (coherent) input mappings; Output: M0: output mappings; R : approximate repair; disj: number of disjointness rules 12:: hhPO110;;PO220ii ::== PMroopdousleitEioxntraalEctnocro(dOin1g;(OO21; M0))

0 ; O2 3: SI1 := StructuralIndex(O10), SI2 := StructuralIndex(O20) 4: SIU := StructuralIndex(O10 [ O20 [ M) 5: hP1d; disj1i := DisjointAxiomsExtension(P1; SI1; SIU ) 6: hP2d; disj2i := DisjointAxiomsExtension(P2; SI2; SIU ) 7: hM0; R i := MappingRepair(P1d; P2d; M) 8: return hM0; R ; disj1 + disj2i . See Algorithm 2 in [ 13 ]

The integrated ontology OU = O1 [ O2 [ 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 O1:Company and O1:Operator (resp. O2:Field operator and O2:Company) are involved in a subsumption relationship in O1 (resp. O2). 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. 4

Methods

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). 4.1

Approximate Repair of Basic Conservativity Principle Violations

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, O1 and O2, and a set of mappings M which are coherent4 w.r.t. O1 and O2. The problem size is reduced by extracting two localitybased modules [ 3 ] (O10 and O20) 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 M0, and an approximate repair R s.t. M0 = M n R . The repair R aims at solving most of the basic violations of M w.r.t. O1 and O2. We next describe the techniques used in each step.

Propositional Horn Encoding. The modules O10 and O20 are encoded as the Horn propositional theories, P1 and P2 (line 2 in Algorithm 1). The encoding includes rules of the form A1 ^ : : : ^ An ! B, with Ai; B atomic concepts. For example, the concept 4 Note that M may be the result of a prior mapping (incoherence) repair process. Oi0 [ . 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 Ai ^ Aj ! 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 m2 is translated into rules O1:WellBore ! O2:Borehole, and O2:Borehole ! O1:WellBore. Structural Index. The concept hierarchies provided by an OWL 2 reasoner (excluding ?) and the explicit disjointness axioms of the modules O10 and O20 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 Oi0 . However, additional disjointness axioms may lead to unsatisfiable classes in 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 Oi0 [ is restricted to the Horn propositional case. We have implemented an algorithm to extend the propositional theories P1 and P2 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 Pid (with i 2 f1; 2g), the theory Pid [ ftrue ! Ag is satisfiable. Note that this does not necessarily hold when considering the OWL 2 ontology modules, O10 and O20, 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 OU = O10 [ O20 [ M, w.r.t. one of the ontology modules Oi0 (with i 2 f1; 2g); i.e., adding a disjointness axiom between each pair of classes A; B 2 Oi0 s.t. A v B 2 basicViol(Oi0 ; OU ), 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).

Algorithm 2 Disjointness axioms extension Input: P: propositional theory; SI: structural index SIU : structural index of the union ontology Output: Pd: extended propositional theory;disj: number of disjointness rules 1: disj := 0, Pd := P 2: for A ! B 2 BasicConservativityViolations(SI; SIU ) do 3: if not (areDisj(SI; A; B)) then 4: Pd := Pd [ fA ^ B ! falseg 5: SI := updateIndex(SI; A u B ! ?) 6: disj := disj + 1 7: end if 8: end for

9: return hPd; disji

Mapping Repair. Line 7 of Algorithm 1 uses the mapping (incoherence) repair algorithm presented in [ 13 ]for the extended Horn propositional theories P1d and P2d, 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 2 P1 [P2d, the satisfiability of the propositional theory PA = P1 [P2 [M[ftrue ! Ag.

d d d Satisfiability of PA is checked in worst-case linear time in the size of PA, and the number of Dowling-Gallier calls is also linear in the number of propositional variables in P1 [ P2d. The algorithm records the conflicting mappings involved in the unsatisfiad bility, 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.5 Example 3. Consider the propositional encoding P1 and P2 of the axioms of Table 1 and the mappings M in Table 2, seen as propositional rules. P1d and P2d have been created by adding disjointness rules to P1 and P2, according to Algorithm 2. For example, P2d includes the rule = O2:Well ^ O2:Borehole ! f alse. The mapd d ping repair algorithm identifies the propositional theory P1 [ P2 [ M [ ftrue ! O1:ExplorationWellboreg as unsatisfiable. This is due to the combination of the mappings m3 and m4, the propositional projection of axioms 1 and 2, and the rule . The mapping repair algorithm also identifies m3 and m4 as the cause of the unsatisfiability, and discards m3 since its confidence is smaller than that of m4 (see Table 2).

Algorithm 1 gives as output the number of added disjointness rules disj, a set of mappings M0, and an (approximate) repair R such that M0 = M n R . M0 is coherent w.r.t. P1d and P2d. Furthermore, the propositional theory P1 [ P2 [ M0 does not contain any basic violation w.r.t. P1 and P2 (according to the propositional case of Definition 2). However, our incomplete encoding cannot guarantee that O10 [ O20 [ M0 does not contain basic violations w.r.t. O10 and O20. Nonetheless, our evaluation suggests that the number of remaining violations after repair is typically small (see Section 5). 4.2

Repair of Equivalence Conservativity Principle Violations

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. 5 Note that the locality principle can be used to compute fresh confidence values, if needed [ 12 ]. 6 Formal definitions and proofs are provided in an accompanying technical report [ 24 ]. Algorithm 3 CycleBreaker Algorithm Input: Ontology O1, Ontology O2, Alignment M Output: Repair 1: OM = alignOnto(O1; O2; M) 2: G = createDigraph(OM) 3: SCCSi = tarjan(G; Oi), globalSCCs = tarjan(G) 4: for S 2 globalSCCs s.t. : Vi2=1 Oi (S) 2 SCCsi do 5: [ ASP(S) 6: end for 7: return Algorithm Description. Algorithm 3 takes as input two ontologies O1,O2, and an alignment M between them. The aligned ontology OM 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 G0 can be reduced to computing SCC(G0), 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).

Listing 1.1. ASP program computing a minimal repair for a problematic SCC. r0 : # domain v t x (X,O ) . # domain v t x (Y, P ) . # domain v t x ( Z ,Q ) . r1 : r e a c h e s S a f e (X,Y) : edge (X, Y, C , 0 ) , O=P , X!=Y. r2 : r e a c h e s S a f e (X, Z ) : r e a c h e s S a f e (X,Y) , edge (Y, Z , C , 0 ) , O=P , P=Q, X!=Y, Y!=Z , X!=Z . r3 : r e a c h e s (X,Y) : edge (X, Y, C ,M) , unremoved ( edge (X, Y, C ,M) ) , X!=Y. r4 : r e a c h e s (X, Z ) : r e a c h e s (X,Y) , edge (Y, Z , C ,M) , unremoved ( edge (Y, Z , C ,M) ) , X!=Y,

Y!=Z , X!=Z . r5 : unremoved ( edge (X, Y, C ,M) ) j removed ( edge (X, Y, C ,M) ) : edge (X, Y, C ,M) , X!=Y. r6 : unremoved ( edge (X, Y, C , 0 ) ) : edge (X, Y, C , 0 ) , X!=Y, O=P . r7 : u n s a f e C y c l e (Y) : not r e a c h e s S a f e (Y,X) , r e a c h e s (Y,X) , r e a c h e s (X,Y) , O=P , X!=Y. r8 : : u n s a f e C y c l e (Y ) . r9 : # minimize [ removed ( edge (X, Y, C , 1 ) ) = C ] . (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 2 f1; 2g is the index of the input ontology of the concept, (ii) Algorithm 4 Conducted evaluation over the Optique and OAEI data sets Input: O1, O2: input ontologies M: reference mappings for O1 and O2 1: OU := O1 [ O2 [ M 2: Store size of Sig(O1) (I), Sig(O2) (II) and M (III)

Compute number of conservativity principle violations: 3: basicViol := jbasicViol(O1; OU )j + jbasicViol(O2; OU )j (IV) 4: di := jdi Sig(O1)(O1; OU )j + jdi Sig(O2)(O2; OU )j (V) 5: eqViol := jeqViol(O1; OU )j + jeqViol(O2; OU )j (VI) 6: Compute a repair R using Algorithm 1 for O1, O2, M 7: Store number of added disjointness disj (VII), time to compute disjointness rules td (VIII) 8: Compute a repair RSCC using Algorithm 3 for O1, O2, M n R 9: Store size global time to compute the combined mapping repair tr (IX) and size of repair jRSCCj (X) 10: OU := O1 [ O2 [ M n RSCC

Compute number of remaining conservativity principle violations: 11: basicViol := jbasicViol(O1; OU )j + jbasicViol(O2; OU )j (XI) 12: di := jdi Sig(O1)(O1; OU )j + jdi Sig(O2)(O2; OU )j (XII) 13: eqViol := jeqViol(O1; OU )j + jeqViol(O2; OU )j (XIII) . basic violations, as in Definition 2

. general notion as in Section 2 . equivalence violations, as in Definition 2 . basic violations . general notion . equivalence violations predicate edge(X; Y; C; M ) encodes arcs, where X and Y are vertices, C is an integer encoding for arc weight in [0 : : : 100], M is a boolean flag for mappings. Example 4. The model (i.e., the computed repair) for the logic program on the following facts, encoding the problematic SCC of Figure 1, is equal to mapping m7 of Table 2: v t x ( Company1 , 1 ) . v t x ( Op er ato r1 , 1 ) . v t x ( Company2 , 2 ) . v t x ( F i e l d o p e r a t o r 2 , 2 ) . edge ( Company1 , Company2 , 9 0 , 1 ) . edge ( Company2 , Company1 , 9 0 , 1 ) . edge ( Company2 , F i e l d o p e r a t o r 2 , 1 0 0 , 0 ) . edge ( F i e l d o p e r a t o r 2 , O per at or1 , 7 0 , 1 ) .

5 Evaluation

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.7

Table 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.59 ASP solver. The obtained results10 can be summarised as follows: 7 More information can be found in http://oaei.ontologymatching.org/2013/ 8 No OWL 2 reasoner could classify the integrated SNOMED-NCI ontology. The OWL 2 EL reasoner ELK [ 14 ] computed a lower bound on the number of conservativity violations. 9 http://potassco.sourceforge.net/ 10 The computation times of lines 1-3 in Algorithm 1 were negligible with respect to the repair and disjointness addition times (tr and td) and thus they were not included in the result tables. Dataset Optique NPDsBootsOnto

SNOMEDsNCI LargeBio FMAsSNOMED

FMAsNCI Anatomy MOsNCIAnat Library STWsTheSoz cmtsconfof conferencesedas Conference conferencesiasted confofsekaw edassiasted 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 RSCC (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 tr (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.

Related Work

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. 7

Conclusions and Future Work

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.

References

1. Bodenreider , O. : The Unified Medical Language System (UMLS): integrating biomedical terminology . Nucleic Acids Research 32 , 267 - 270 ( 2004 )

2. Borgida , A. , Serafini , L. : Distributed Description Logics: Assimilating Information from Peer Sources . J. Data Sem . 1 , 153 - 184 ( 2003 )

3. Cuenca Grau , B. , Horrocks , I. , Kazakov , Y. , Sattler , U. : Modular Reuse of Ontologies: Theory and Practice . J. Artif. Intell. Res . 31 , 273 - 318 ( 2008 )

4. Dowling , W.F. , Gallier , J.H. : Linear-Time Algorithms for Testing the Satisfiability of Propositional Horn Formulae . J. Log. Prog . 1 ( 3 ), 267 - 284 ( 1984 )

5. Euzenat , J. , Meilicke , C. , Stuckenschmidt , H. , Shvaiko , P. , Trojahn , C. : Ontology Alignment Evaluation Initiative: Six Years of Experience . J. Data Sem . 15 , 158 - 192 ( 2011 )

6. Faber , W.: Answer Set Programming . In: Reasoning Web . pp. 162 - 193 ( 2013 )

7. Ferre´, S. , Rudolph , S. : Advocatus Diaboli - Exploratory Enrichment of Ontologies with Negative Constraints . In: Int'l Conf. on Knowl. Eng. (EKAW) . pp. 42 - 56 ( 2012 )

8. Ivanova , V. , Lambrix , P. : A Unified Approach for Aligning Taxonomies and Debugging Taxonomies and their Alignments . In: Eur. Sem. Web Conf. (ESWC) , pp. 1 - 15 . Springer ( 2013 )

9. Jean-Mary , Y.R. , Shironoshita , E.P. , Kabuka , M.R. : Ontology Matching With Semantic Verification . J. Web Sem . 7 ( 3 ), 235 - 251 ( 2009 )

10. Jime ´nez- Ruiz , E. , Cuenca Grau , B. : LogMap: Logic-based and Scalable Ontology Matching . In: Int'l Sem . Web Conf. (ISWC) . pp. 273 - 288 ( 2011 )

11. Jime ´nez- Ruiz , E. , Cuenca Grau , B. , Horrocks , I. , Berlanga , R.: Ontology integration using mappings: Towards getting the right logical consequences . In: Eur. Sem. Web Conf . ( 2009 )

12. Jime ´nez- Ruiz , E. , Cuenca Grau , B. , Horrocks , I. , Berlanga , R. : Logic-based Assessment of the Compatibility of UMLS Ontology Sources . J. Biomed. Semant . 2 ( Suppl 1 ), S2 ( 2011 )

13. Jime ´nez- Ruiz , E. , Meilicke , C. , Cuenca Grau , B. , Horrocks , I. : Evaluating Mapping Repair Systems with Large Biomedical Ontologies . In: Description Logics. pp. 246 - 257 ( 2013 )

14. Kazakov , Y. , Kro¨tzsch, M. , Simancik , F. : Concurrent Classification of EL Ontologies . In: Int'l Sem . Web Conf. (ISWC) . pp. 305 - 320 ( 2011 )

15. Konev , B. , Walther , D. , Wolter , F. : The Logical Difference Problem for Description Logic Terminologies . In: Int'l Joint Conf. on Automated Reasoning (IJCAR) . pp. 259 - 274 ( 2008 )

16. Meilicke , C. : Alignments Incoherency in Ontology Matching . Ph.D. thesis ( 2011 )

17. Meilicke , C. , Vo¨lker, J., Stuckenschmidt , H.: Learning Disjointness for Debugging Mappings between Lightweight Ontologies . In: Int'l Conf. on Knowl. Eng. (EKAW) . pp. 93 - 108 ( 2008 )

18. Motik , B. , Shearer , R. , Horrocks , I. : Hypertableau Reasoning for Description Logics . J. Artif. Intell. Res. (JAIR) 36 , 165 - 228 ( 2009 )

19. Ngo , D. , Bellahsene , Z. : YAM++ : A Multi-strategy Based Approach for Ontology Matching Task . In: Int'l Conf. on Knowl. Eng. (EKAW) . pp. 421 - 425 ( 2012 )

20. Pesquita , C. , Faria , D. , Santos , E. , Couto , F.M.: To repair or not to repair: reconciling correctness and coherence in ontology reference alignments . In: Ontology Matching (OM) ( 2013 )

21. Santos , E. , Faria , D. , Pesquita , C. , Couto , F. : Ontology Alignment Repair Through Modularization and Confidence-based Heuristics . arXiv:1307 .5322 preprint ( 2013 )

22. Schlobach , S. : Debugging and Semantic Clarification by Pinpointing . In: Eur. Sem. Web Conf. (ESWC) , pp. 226 - 240 . Springer ( 2005 )

23. Shvaiko , P. , Euzenat , J.: Ontology Matching: State of the Art and Future Challenges . IEEE Transactions on Knowl. and Data Eng. (TKDE) ( 2012 )

24. Solimando , A. , Guerrini , G.: Coping with Conservativity Principle Violations in Ontology Mappings . Tech. Rep. DIBRIS-TR-14-01 , University of Genova (Jan 2014 ), ftp://ftp. disi.unige.it/person/SolimandoA/cycleMappingDbgExt.pdf

25. Solimando , A. , Jime´nez- Ruiz , E. , Guerrini , G.: Detecting and Correcting Conservativity Principle Violations in Ontology-to-Ontology Mappings . In: Int'l Sem . Web Conf . ( 2014 ), ftp://ftp.disi.unige.it/person/SolimandoA/conservLogMap.pdf

26. Tarjan , R.: Depth-first Search and Linear Graph Algorithms . SIAM J. Comp . 1 ( 2 ) ( 1972 )

27. Vo¨lker, J., Vrandecic , D. , Sure , Y. , Hotho , A. : Learning Disjointness . In: Eur. Sem. Web Conf. (ESWC) . pp. 175 - 189 ( 2007 )

28. Wang , P. , Xu , B. : Debugging Ontology Mappings: A Static Approach . Computing and Informatics 27 ( 1 ), 21 - 36 ( 2012 )