=Paper=
{{Paper
|id=Vol-1265/paper2
|storemode=property
|title=A Multi-strategy Approach for Detecting and Correcting Conservativity Principle Violations in Ontology Alignments
|pdfUrl=https://ceur-ws.org/Vol-1265/owled2014_submission_2.pdf
|volume=Vol-1265
|dblpUrl=https://dblp.org/rec/conf/owled/SolimandoJG14
}}
==A Multi-strategy Approach for Detecting and Correcting Conservativity Principle Violations in Ontology Alignments==
https://ceur-ws.org/Vol-1265/owled2014_submission_2.pdf
A Multi-strategy Approach for Detecting and
Correcting Conservativity Principle Violations in
Ontology Alignments?
Alessandro Solimando1 , Ernesto Jiménez-Ruiz2 , and Giovanna Guerrini1
1
DIBRIS, Università di Genova, Italy
2
Department of Computer Science, University of Oxford, UK
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).
1 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 num-
ber 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 un-
desired 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) con-
servativity 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 align-
ments, 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 prin-
ciples 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 con-
servativity 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 com-
bined 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 prelim-
inaries. Section 3 introduces our motivating scenario. Section 4 describes our method.
Section 5 presents the conducted evaluation. Section 6 provides a comparison with rel-
evant 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 seman-
tic 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 ∈ Sig(O1 ) and e2 ∈ 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 EL, 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 Σ ∪ {>, ⊥}, 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
diff ≈ 0
Σ (O, O ) as the set of axioms of the form A v B satisfying: (i) O 6|= A v B, and
(ii) O0 |= 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 diff ≈Σ1 (O1 , OU ) and
diff ≈
Σ2 (O 2 , OU ) must be empty for signatures Σ 1 = Sig(O 1 ) and Σ 2 = Sig(O2 ), re-
spectively. 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 subsump-
tion relationship (i.e., resulting in an equivalence between them), denoted as equiva-
lence 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., diff ≈ Σ (O1 ∪O2 , OU )
does not contain any axiom A v ⊥, for any A ∈ Σ = Sig(O1 ∪ O2 )).
Definition 2 (Conservativity Principle Violations). Let O be one of the input ontolo-
gies and Sig(O) be its signature, let OU be the integrated ontology, and let A, B be
atomic concepts in Sig(O) ∪ {>, ⊥}. 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 ∈ diff ≈ Sig(O) (O, OU ), (ii) O 6|= B v A, and (iii) there is no C in
Sig(O) ∪ {>, ⊥} s.t. O |= C v A, and O |= C v B.
– equivalence violations, denoted eqViol(O, OU ), as the set of A ≡ B axioms sat-
isfying: (i) OU |= A ≡ B, (ii) A v B ∈ diff ≈ Sig(O) (O, OU ) and/or B v A ∈
diff ≈
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 con-
sistency 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 ex-
press complex search problems up to Σ2P complexity class (and its complement Π2P [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 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 minimiz-
ing numeric variables or the cardinality of a predicate. These rules are called soft con-
straints, in opposition to hard constraints, which are rules with an empty Head. 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.
Table 1. Fragments of the ontologies used in Optique project [25].
Ontology O 1 Ontology O 2
α1 WellBore v ∃belongsTo.Well β1 Exploration well v Well
α2 WellBore v ∃hasOperator.Operator β2 Explor borehole v Borehole
α3 WellBore v ∃locatedIn.Field β3 Appraisal exp borehole v Explor borehole
α4 AppraisalWellBore v WellBore β4 Appraisal well v Well
α5 ExplorationWellBore v WellBore β5 Field v ∃hasFieldOperator.Field operator
α6 Operator v Owner β6 Field operator u Owner v Field owner
α7 Operator v Company β7 Company v Field operator
α8 Field v ∃hasOperator.Company β8 Field owner v Owner
α9 Field v ∃hasOwner.Owner β9 Borehole v Continuant t Occurrent
Table 2. Ontology mappings for the vocabulary in O1 and O2 .
Mappings M
id e1 e2 n ρ
m1 O1 :Well O2 :Well 0.9 ≡
m2 O1 :WellBore O2 :Borehole 0.7 ≡
m3 O1 :ExplorationWellBore O2 :Exploration well 0.6 v
m4 O1 :ExplorationWellBore O2 :Explor borehole 0.8 ≡
m5 O1 :AppraisalWellBore O2 :Appraisal exp borehole 0.7 ≡
m6 O1 :Field O2 :Field 0.9 ≡
m7 O1 :Operator O2 :Field operator 0.7 w
m8 O1 :Company O2 :Company 0.9 ≡
m9 O1 :hasOperator O2 :hasFieldOperator 0.6 ≡
m10 O1 :Owner O2 :Owner 0.9 ≡
Table 3. Example of conservativity principle violations.
σ Entailment: follows from: basicViol(O i , O U )?eqViol(O i , O U )?
σ1 O2 :Explor borehole v O2 :Exploration well m3 , m4 YES NO
σ2 O1 :AppraisalWellBore v O1 :ExplorationWellBore β3 , m4 , m5 YES NO
σ3 O2 :Field operator v O2 :Field owner α6 , β6 , m7 , m10 YES NO
σ4 O1 :Company ≡ O1 :Operator
α7 , β7 , m7 , m8 NO YES
σ5 O2 :Field operator ≡ O2 :Company
σ6 O1 :Company v O1 :Owner σ4 , α 6 YES NO
σ7 O2 :Company v O2 :Field owner σ3 , σ 5 YES NO
0.9
1
Company1 Company2 F ield operator2
0.9
1
0.7
Operator1 F ield owner2
1
1
Owner1 Owner2
0.9
0.9
Fig. 1. Graph representation of the fragment of the aligned ontology of Tables 1 involved in
conservativity violations. Dashed arcs represent inferred axioms, while red arcs are those involved
in equivalence violations. Each non-inferred arc is labeled with its confidence value.
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 relation-
ship between the entities O1 :WellBore and O2 :Borehole, with confidence 0.7.
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
1: hO10 , O20 i := ModuleExtractor(O1 , O2 , M)
2: hP1 , P2 i := PropositionalEncoding(O10 , O20 )
3: SI1 := StructuralIndex(O10 ), SI2 := StructuralIndex(O20 )
4: SIU := StructuralIndex(O10 ∪ O20 ∪ M)
5: hP1d , disj1 i := DisjointAxiomsExtension(P1 , SI1 , SIU ) . See Algorithm 2
6: hP2d , disj2 i := DisjointAxiomsExtension(P2 , SI2 , SIU )
7: hM0 , R≈ i := MappingRepair(P1d , P2d , M) . See Algorithm 2 in [13]
8: return hM0 , R≈ , disj1 + disj2 i
The integrated ontology OU = O1 ∪ O2 ∪ M, however, violates the conservativity
principle, according to Definition 2, and introduces unwanted subsumption relation-
ships (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 ASP-
based 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 ad-
dressig 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 ac-
cepts 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 locality-
based 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 \ 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.
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 en-
coded as rule Field operator ∧ Owner → Field owner, while the mapping m2 is trans-
lated 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 in-
dexed 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 dis-
jointness, we need to automatically add sufficient disjointness axioms into each mod-
ule Oi0 . However, additional disjointness axioms δ may lead to unsatisfiable classes in
Oi0 ∪ δ.
Example 2. Consider the axiom β9 from Table 1. Following the assumption of dis-
jointness 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 propo-
sitional 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 ∈ {1, 2}), the theory Pid ∪ {true → A}
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 rela-
tionship (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 ∈ {1, 2}); i.e., adding a disjointness
axiom between each pair of classes A, B ∈ Oi0 s.t. A v B ∈ 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: P d : extended propositional theory;disj: number of disjointness rules
1: disj := 0, P d := P
2: for A → B ∈ BasicConservativityViolations(SI, SIU ) do
3: if not (areDisj(SI, A, B)) then
4: P d := P d ∪ {A ∧ B → f alse}
5: SI := updateIndex(SI, A u B → ⊥)
6: disj := disj + 1
7: end if
8: end for
9: return hP d , disji
Mapping Repair. Line 7 of Algorithm 1 uses the mapping (incoherence) repair algo-
rithm 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 ∈
P1d ∪P2d , the satisfiability of the propositional theory PA = P1d ∪P2d ∪M∪{true → A}.
Satisfiability of PA is checked in worst-case linear time in the size of PA , and the num-
ber of Dowling-Gallier calls is also linear in the number of propositional variables in
P1d ∪ P2d . The algorithm records the conflicting mappings involved in the unsatisfia-
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 map-
ping repair algorithm identifies the propositional theory P1d ∪ P2d ∪ M ∪ {true →
O1 :ExplorationWellbore} as unsatisfiable. This is due to the combination of the map-
pings 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 \ 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: O M = alignOnto(O1 , O2 , M)
2: G = createDigraph(O M )
3: SCCSi = tarjan(G, Oi ),V globalSCCs = tarjan(G)
4: for S ∈ globalSCCs s.t. ¬ 2i=1 ΠOi (S) ∈ 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 con-
cepts 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 on-
tologies 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.
r 0 : # domain v t x (X, O ) . # domain v t x (Y, P ) . # domain v t x ( Z , Q ) .
r 1 : r e a c h e s S a f e (X, Y) :− e d g e (X, Y, C , 0 ) , O=P , X! =Y .
r 2 : 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) , e d g e (Y, Z , C , 0 ) , O=P , P=Q, X! =Y, Y! =Z , X! =Z .
r 3 : r e a c h e s (X, Y) :− e d g e (X, Y, C ,M) , unremoved ( e d g e (X, Y, C ,M) ) , X! =Y .
r 4 : r e a c h e s (X, Z ) :− r e a c h e s (X, Y) , e d g e (Y, Z , C ,M) , unremoved ( e d g e (Y, Z , C ,M) ) , X! =Y,
Y! =Z , X! =Z .
r 5 : unremoved ( e d g e (X, Y, C ,M) ) | removed ( e d g e (X, Y, C ,M) ) :− e d g e (X, Y, C ,M) , X! =Y .
r 6 : unremoved ( e d g e (X, Y, C , 0 ) ) :− e d g e (X, Y, C , 0 ) , X! =Y, O=P .
r 7 : u n s a f e C y c l e (Y) :− n o t 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 .
r 8 : :− u n s a f e C y c l e (Y ) .
r 9 : # m i n i m i z e [ removed ( e d g e (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 tran-
sitive 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 con-
straint 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 fol-
lowing 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)
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 := |basicViol(O1 , OU )| + |basicViol(O2 , OU )| (IV) . basic violations, as in Definition 2
4: diff ≈ := |diff ≈ ≈
Sig(O1 ) (O1 , OU )| + |diff Sig(O2 ) (O2 , OU )| (V) . general notion as in Section 2
5: eqViol := |eqViol(O1 , OU )| + |eqViol(O2 , OU )| (VI) . equivalence violations, as in Definition 2
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 \ R≈
9: Store size global time to compute the combined mapping repair tr (IX) and size of repair |RSCC | (X)
10: OU := O1 ∪ O2 ∪ M \ RSCC
Compute number of remaining conservativity principle violations:
11: basicViol := |basicViol(O1 , OU )| + |basicViol(O2 , OU )| (XI) . basic violations
12: diff ≈ := |diff ≈ ≈
Sig(O1 ) (O1 , OU )| + |diff Sig(O2 ) (O2 , OU )| (XII) . general notion
13: eqViol := |eqViol(O1 , OU )| + |eqViol(O2 , OU )| (XIII) . 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 follow-
ing facts, encoding the problematic SCC of Figure 1, is equal to mapping m7 of Table 2:
v t x ( Company1 , 1 ) . v t x ( O p e r a t o r 1 , 1 ) . v t x ( Company2 , 2 ) . v t x ( F i e l d o p e r a t o r 2 , 2 ) .
e d g e ( Company1 , Company2 , 9 0 , 1 ) . e d g e ( Company2 , Company1 , 9 0 , 1 ) .
e d g e ( Company2 , F i e l d o p e r a t o r 2 , 1 0 0 , 0 ) . e d g e ( F i e l d o p e r a t o r 2 , O p e r a t o r 1 , 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 refer-
ence 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 ex-
pecially 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.
Table 4. Test cases and violations with original reference mappings.
Problem size Original Violations
Dataset O1 ∼ O2 I II III IV V VI
|Sig(O1 )| |Sig(O2 )| |M| basicViol diff ≈ eqViol
Optique NPD∼BootsOnto 757 40,671 102 214 220 25
SNOMED∼NCI 51,179 24,040 36,405 >525,515 >546,181 >6,090
LargeBio FMA∼SNOMED 10,181 13,430 17,212 125,232 127,668 1,091
FMA∼NCI 3,720 6,551 5,821 19,740 19,799 427
Anatomy MO∼NCIAnat 2,747 3,306 3,032 1,321 1,335 26
Library STW∼TheSoz 6,575 8,376 6,322 42,045 42,872 895
cmt∼confof 89 75 32 11 11 0
conference∼edas 124 154 34 8 8 0
Conference conference∼iasted 124 182 28 9 9 0
confof∼ekaw 75 107 40 6 6 1
edas∼iasted 154 182 38 7 7 0
Table 5. Results of our method to detect and solve conservativity principle violations.
Solution size Times Remaining Violations
Dataset O1 ∼ O2 VII X VIII IX XI XII XIII
#disj |RSCC | td (s) tr (s) basicViol diff ≈ eqViol
Optique NPD∼BootsOnto 214 44 2.22 1.94 0 0 0
SNOMED∼NCI 525,515 16,180 80 3,721 >51 >402 >2
LargeBio FMA∼SNOMED 125,232 8,369 30 269 0 33 0
FMA∼NCI 19,740 2,179 36 36 103 104 0
Anatomy MO∼NCIAnat 1,321 493 1.46 1.34 0 2 0
Library STW∼TheSoz 42,045 3,068 4.96 44 0 15 0
cmt∼confof 11 6 0.04 0.04 0 0 0
conference∼edas 8 6 0.07 0.07 0 0 0
Conference conference∼iasted 9 3 0.21 0.14 0 0 0
confof∼ekaw 6 5 0.04 0.03 0 0 0
edas∼iasted 7 4 0.21 0.16 1 1 0
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 gen-
eral 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.
6 Related Work
The conservativity principle, although indirectly, has been actively studied in the litera-
ture. For example, the assumption of disjointness was originally introduced by Schlobach
[22] to enhance the repair of ontologies that were underspecified in terms of disjoint-
ness 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 or-
der 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 particu-
lar, 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 incom-
pleteness 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 pro-
gramming, 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 modifi-
able (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: The-
ory 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 Propo-
sitional 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. Ferré, S., Rudolph, S.: Advocatus Diaboli - Exploratory Enrichment of Ontologies with Neg-
ative 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 Tax-
onomies 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 Ver-
ification. J. Web Sem. 7(3), 235–251 (2009)
10. Jimé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. Jimé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. Jimé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. Jimé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., Krö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., Vö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 correct-
ness and coherence in ontology reference alignments. In: Ontology Matching (OM) (2013)
21. Santos, E., Faria, D., Pesquita, C., Couto, F.: Ontology Alignment Repair Through Modular-
ization 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., Jimé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. Vö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 In-
formatics 27(1), 21–36 (2012)