11institutetext: Linköping University, Linköping, Sweden 22institutetext: The
Swedish e-Science Research Centre, Linköping, Sweden

# Repairing Networks of $\mathcal{EL_{\perp}}$ Ontologies using Weakening and
Completing
\-
Extended version

Ying Li 1122 0000-0002-1367-9679 Patrick Lambrix 1122 0000-0002-9084-0470

###### Abstract

The quality of ontologies and their alignments is crucial for developing high-
quality semantics-based applications. Traditional debugging techniques repair
ontology networks by removing unwanted axioms and mappings, but may thereby
remove consequences that are correct in the domain of the ontology network. In
this paper we propose a framework for repairing ontology networks that deals
with this issue. It defines basic operations such as debugging, weakening and
completing. Further, it defines combination operators that reflect choices in
how and when to use the basic operators, as well as choices regarding the
autonomy level of the ontologies and alignments in the ontology network. We
show the influence of the combination operators on the quality of the repaired
network and present an implemented tool. By using our framework together with
existing algorithms for debugging, weakening and completing, we essentially
provide a blueprint for extending previous work and systems. 111This is a
slightly revised and extended version of [26].

##  1 Introduction

Ontologies and ontology networks, i.e., a set of ontologies connected through
alignments, are core components in application scenarios that involve
searching, integrating, managing and extracting value from diverse sources of
data at large scale. In the latter case they are the input for machine
learning and data mining applications in diverse fields such as business
analytics, health, crime analysis, and materials design. They are also the
structural part of knowledge graphs which are used by, e.g., major data and
database providers such as Google, Amazon, Meta, and Neo4j. The quality of
ontologies, ontology networks and knowledge graphs is crucial for developing
high-quality semantics-based applications. However, ensuring their quality, in
particular regarding completeness (or coverage, all relevant information is
modeled) and correctness (no wrong information is modeled), is a major
challenge [33, 32, 9, 4, 18].

Repairing ontology networks is a natural requirement for any application that
would need to use several ontologies. We have, for instance, experience in a
number of settings where an ontology network is repaired. A first example is
the case of ontologies in the Ontology Alignment Evaluation Initiative (OAEI)
where the ontologies to be aligned and a partial alignment were used to detect
and repair defects [21] (and the results were sent to the ontology owners).
Another example is the development of modular ontologies where the modules and
connections between the modules have been repaired (e.g., [19]). Further, we
have worked with companies that used publicly available ontologies as well as
concern-wide ontologies and where the network of these were repaired (e.g.,
[10]).

The workflow for dealing with unwanted axioms in ontologies or networks
consists of several steps including the detection and localization of the
defects and the repairing. In this paper we assume we have detected defects
and we now need to repair the ontologies and networks. In the classical
approaches the end result is a set of axioms to remove from the ontology or
network that is obtained after detection and localization, and the repairing
consists solely of removing the suggested axioms. However, more knowledge than
needed may be removed and approaches that alleviate the effect of removing
unwanted axioms using weakening and completing have been proposed. In [24] a
framework for repairing ${\cal{EL}}$ ontologies, based on the basic operations
removing, weakening and completing, was proposed. Further, different
combination operators were introduced that relate to choices that can be made
when combining the basic operations (e.g., in which order to perform the
operations, and when to update the ontologies). It was shown that the choice
of combination has an influence on the amount of validation work by a domain
expert and the completeness of the final ontology. It was also shown that
earlier work on weakening (without completing) only considered one of the
possible combinations. Similarly, earlier work on completing (without
weakening) also considered only one of the possible combinations. The
framework was extended with the basic operation debugging in [25].

Our contributions in this paper relate to different ways in which we extend
the framework in [24, 25] to deal with ontology networks. (i) We formalize the
problem, and show that new choices appear in addition to the choices for
ontologies, when ontologies are connected with alignments (Sect. 3) (ii) We
introduce different levels of autonomy for the ontologies and the alignments
in the ontology network, reflecting the policies of the ontology and alignment
owners regarding updating and computing for their ontologies and alignments
(Sect. 3). We define combination operators based on these autonomy levels and
show the influences on the quality of the repair and the validation work
(Sect. 4). In general, there is a trade-off between the quality of the
repaired ontologies on the one hand, and the amount of validation work for the
oracle (e.g., domain experts) and the autonomy level for the ontologies and
alignments on the other hand. We also give recommendations about which
combinations to use in different cases, and we show that current systems for
alignment repair (a special case of ontology network repair) use one
particular combination of choices. In Sect. 5 we give examples of repairing
existing ontology networks and (iii) in Sect. 6 we briefly describe an
implemented tool that allows users to make different choices for the
combination operators.

The only other work that discusses the combination of basic operations for
repairing is [24, 25] where the focus is on ontologies and the basic
operations are removing, weakening and completing in [24], and additionally
debugging in [25]. For the basic operations different approaches can be used.
As this paper is not about possible approaches for the basic operations, but
rather about their combinations, we mention these approaches in Sect. 2.3 and
refer for an overview that compares these approaches to [18]. This paper
essentially treats the basic operations of debugging, weakening and completing
as black boxes and does not put requirements on the actual implementation of
these operations. Therefore, by using our framework and the combination
operators together with existing algorithms for debugging, weakening and
completing, we essentially provide a blueprint for extending previous work and
systems.

Table 1: ${\mathcal{EL_{\perp}}}$ syntax and semantics.  Name | Syntax | Semantics
---|---|---
top | $\top$ | $\Delta^{\mathcal{I}}$
bottom | $\perp$ | $\emptyset$
conjunction | $P\sqcap Q$ | $P^{\mathcal{I}}\cap Q^{\mathcal{I}}$
existential restriction | $\exists r.P$ |  $\\{x\in\Delta^{\mathcal{I}}$ $\mid$ $\exists y\in\Delta^{\mathcal{I}}:$
|  | $(x,y)\in r^{\mathcal{I}}\wedge y\in P^{\mathcal{I}}\\}$
GCI | $P\sqsubseteq Q$ | $P^{\mathcal{I}}\subseteq Q^{\mathcal{I}}$

##  2 Preliminaries

###  2.1 Description logics

Description logics (DL) [2] are knowledge representation languages where
concept descriptions are constructed inductively from a set $N_{C}$ of atomic
concepts and a set $N_{R}$ of atomic roles and (possibly) a set $N_{I}$ of
individual names. Different DLs allow for different constructors for defining
complex concepts and roles. An interpretation $\mathcal{I}$ consists of a non-
empty set $\Delta^{\mathcal{I}}$ and an interpretation function
$\cdot^{\mathcal{I}}$ which assigns to each atomic concept $P\in N_{C}$ a
subset $P^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}$, to each atomic role
$r\in N_{R}$ a relation
$r^{\mathcal{I}}\subseteq\Delta^{\mathcal{I}}\times\Delta^{\mathcal{I}}$, and
to each individual name222As we do not deal with individuals in this paper, we
do not use individuals in the later sections. $i\in N_{I}$ an element
$i^{\mathcal{I}}\in\Delta^{\mathcal{I}}$. The interpretation function is
straightforwardly extended to complex concepts. A TBox is a finite set of
axioms which in ${\mathcal{EL_{\perp}}}$ are _general concept inclusions_
(GCIs). The syntax and semantics for ${\mathcal{EL_{\perp}}}$ are shown in
Table 1.

An interpretation ${\mathcal{I}}$ is a _model_ of a TBox ${\mathcal{T}}$ if
for each GCI in ${\mathcal{T}}$, the semantic conditions are satisfied. We say
that a TBox ${\mathcal{T}}$ is _inconsistent_ if there is no model for
${\mathcal{T}}$. Further, a concept $P$ in a TBox ${\mathcal{T}}$ is
_unsatisfiable_ if for all models ${\mathcal{I}}$ of ${\mathcal{T}}$ :
$P^{\mathcal{I}}$ = $\emptyset$. We say that a TBox is _incoherent_ if it
contains an unsatisfiable concept. One of the main reasoning tasks for DLs is
subsumption checking333Note that unsatisfiability checking in
${\mathcal{EL_{\perp}}}$ can be be performed using subsumption checking. A
concept $P$ is unsatisfiable if $P$ $\sqsubseteq$ $\perp$. Further, we can
express that two concepts $P$ and $Q$ are disjoint by requiring that $P\sqcap
Q\sqsubseteq\perp$. in which the problem is to decide for a TBox
${\mathcal{T}}$ and concepts $P$ and $Q$ whether ${\mathcal{T}}$ $\models
P\sqsubseteq Q$, i.e., whether $P^{\mathcal{I}}\subseteq Q^{\mathcal{I}}$ for
every model $\mathcal{I}$ of TBox ${\mathcal{T}}$. In this paper we update the
TBox during the repairing and we always use subsumption with respect to the
current TBox.

###  2.2 Ontology networks

In this paper we assume that ontologies are represented using DL TBoxes. An
alignment between two ontologies is a set of mappings between the ontologies.
A mapping between two ontologies is represented by $P$ $\sqsubseteq$ $Q$ where
$P$ is a concept in the first ontology and $Q$ is a concept in the second
ontology. Note that equivalence mappings (e.g., $P$ is equivalent to $Q$) are
represented by two subsumption mappings ($P$ $\sqsubseteq$ $Q$ and $Q$
$\sqsubseteq$ $P$). Although we base our work and examples on
${\mathcal{EL_{\perp}}}$, the discussions hold for ontologies represented by
DLs in general. An ontology network is a collection of ontologies together
with their alignments and can be represented by a TBox (Def. 1).444We do not
require that the ontologies in the network have the same signature. In the
remainder we use the term axiom for the axioms in the ontologies and the
mappings. When we mean axioms in the ontologies, we will explicitly state
this.

######  Definition 1.

Let ${\mathcal{T}}_{1}$, …,${\mathcal{T}_{n}}$ be TBoxes representing
ontologies ${\mathcal{O}_{1}}$, …, ${\mathcal{O}_{n}}$, respectively. For
$i,j\in[1..n]$ with $i<j$, let ${\mathcal{A}_{ij}}$ be an alignment between
ontology ${\mathcal{O}_{i}}$ and ${\mathcal{O}_{j}}$. The network of the
ontologies and their alignments is then represented by TBox ${\mathcal{T}}$ =
($\bigcup_{i=1..n}$ ${\mathcal{T}}_{i}$) $\cup$ ($\bigcup_{i,j=1..n,i<j}$
${\mathcal{A}_{ij}}$).

Our aim is to find repairs that remove as much wrong knowledge and add as much
correct knowledge (back) to our ontology network as possible. Therefore, we
use the preference relations more complete and less incorrect between TBoxes
(Defs. 2 and 3) that formalize these intuitions [18]. Further, if a TBox
representing an ontology (network) is more complete/less incorrect than the
Tbox of an other ontology (network), then we say that the first ontology
(network) is more complete/less incorrect than the second ontology (network).
The definitions assume the existence of an oracle (representing a domain
expert) that, when given an axiom, can answer whether this axiom is correct or
wrong in the domain of interest of the ontology network.

######  Definition 2.

(more complete) TBox ${\mathcal{T}}_{1}$ is _more complete_ than TBox
${\mathcal{T}}_{2}$ (or ${\mathcal{T}}_{2}$ is _less complete_ than
${\mathcal{T}}_{1}$) according to oracle $Or$ iff
$(\forall\psi:({\mathcal{T}}_{2}\models\psi\wedge\leavevmode\nobreak\
Or(\psi)=true)\rightarrow{\mathcal{T}}_{1}\models\psi))\wedge(\exists\psi:Or(\psi)=true\leavevmode\nobreak\
\wedge{\mathcal{T}}_{1}\models\psi\wedge{\mathcal{T}}_{2}\not\models\psi)$.
They are _equally complete_ iff
$\forall\psi:Or(\psi)=true\rightarrow({\mathcal{T}}_{1}\models\psi\leftrightarrow{\mathcal{T}}_{2}\models\psi)$

######  Definition 3.

(less incorrect) TBox ${\mathcal{T}}_{1}$ is _less incorrect_ than TBox
${\mathcal{T}}_{2}$ (${\mathcal{T}}_{2}$ is _more incorrect_ than
${\mathcal{T}}_{1}$) according to oracle $Or$ iff
$(\forall\psi:({\mathcal{T}}_{1}\models\psi\wedge
Or(\psi)=false)\rightarrow{\mathcal{T}}_{2}\models\psi))\wedge(\exists\psi:Or(\psi)=false\leavevmode\nobreak\
\wedge{\mathcal{T}}_{1}\not\models\psi\wedge{\mathcal{T}}_{2}\models\psi)$.
${\mathcal{T}}_{1}$ and ${\mathcal{T}}_{2}$ are _equally incorrect_ iff
$\forall\psi:Or(\psi)=false\rightarrow({\mathcal{T}}_{1}\models\psi\leftrightarrow{\mathcal{T}}_{2}\models\psi)$.

###  2.3 Basic operations

To repair ontologies, algorithms can be developed using a number of basic
operations such as debugging, removing, weakening and completing, and
combining these in different ways [24, 25]. In this paper we use variants of
these operations to repair ontology networks.

Given a set of wrong axioms $W$, debugging aims to find a set of wrong
asserted axioms $D$ that when all axioms in $D$ are removed from the network,
the axioms in $W$ cannot be derived anymore. Many debugging approaches have
been proposed (e.g., [40, 39, 16, 28, 41, 15, 23, 11, 29, 31, 42, 7, 1, 17,
36, 38, 30], overview in [18])555Many of these approaches use axiom
pinpointing [34]. Further, there are other approaches that take ABoxes into
account.. A basic approach is based on the computation of justifications for
the wrong axioms and then computing a Hitting set over the set of
justifications. As an example, in Fig. 1 derived wrong axiom A $\sqsubseteq$ C
needs to be removed. This can be done by removing asserted axiom A
$\sqsubseteq$ B or asserted axiom B $\sqsubseteq$ C. Removing deletes all the
wrong asserted axioms in a given set $D$ from the ontology network. Removing
makes a network less or equally incorrect than it was before the operation.
Given an axiom, weakening aims to find other axioms that are weaker than the
given axiom, i.e., the given axiom logically implies the other axioms within
the network. For the repairing this means that a wrong axiom $\alpha$
$\sqsubseteq$ $\beta$ can be replaced by a correct weaker axiom $sb$
$\sqsubseteq$ $sp$ such that $sb$ is a sub-concept of $\alpha$ and $sp$ is a
super-concept of $\beta$, thereby mitigating the effect of removing the wrong
axiom (Fig. 1). Algorithms for weakening have been provided in e.g., [43, 3,
5, 24]. Completing aims to find correct axioms that are not derivable from the
ontology yet and that would make a given axiom derivable. For a given axiom
$\alpha$ $\sqsubseteq$ $\beta$, it finds correct axioms $sp$ $\sqsubseteq$
$sb$ such that $sp$ is a super-concept of $\alpha$ and $sb$ is a sub-concept
of $\beta$ (Fig. 1). This means that if $sp$ $\sqsubseteq$ $sb$ is added to
${\mathcal{T}}$, then $\alpha$ $\sqsubseteq$ $\beta$ would be derivable.
Completing is performed on correct axioms, and in repairing, it is applied to
weakened axioms. Completing algorithms are proposed in, e.g., [20, 44, 6, 8,
24]. Note that weakening and completing are dual operations where the former
finds weaker axioms and the latter stronger axioms. Both these operations make
an ontology network more or equally complete.

Figure 1: Debugging, weakening and completing.

(a) Debugging

(b) Removing

(c) Weakening

(d) Completing

Figure 2:  Hasse diagrams (a from [26, 25] and b-d from [24]). (a) selecting
and debugging; (b) removing and adding back wrong axioms; (c) weakening and
updating; (d) completing and updating.

These basic operations can be combined in different ways and there are choices
to be made in terms of, e.g., the order in which the operations are performed,
the order in which the axioms are processed, whether one axiom is dealt with
at a time or all at once, and when the TBox is updated. For removing,
weakening and completing, the different combinations were classified in Hasse
diagrams in [24], and for debugging in [25] (Fig. 2). Explanations for
removing, weakening and completing, and for debugging are from [24] and [25],
respectively and are given in the appendix. The proofs of the Hasse diagrams
are given in the appendix. Note that the discussions and proofs for all Hasse
diagrams in this paper hold for ontologies and ontology networks represented
by DL TBoxes in general, and thus the results regarding the combination
operators are language agnostic.666When the framework is instantiated to
create actual systems, then choices need to be made regarding which algorithms
to use for the different basic operations, and the choice of these algorithms
will, of course, also influence the completeness and correctness of an
ontology or ontology network (but this is not the topic of this paper).

In general, operations higher up in the diagrams use more (but also more
possibly wrong) information during the computations and lead to more (or
equally) complete ontologies, more (or equally) incorrect ontologies as well
as more validation work for the domain expert. Algorithms for repairing can be
defined by which of the operators are used and in which order. These
algorithms can then be compared using the Hasse diagrams. In general, if the
sequence of operators for one algorithm can be transformed into the sequence
of operators of a second algorithm, by replacing some operators of the first
algorithm using operators higher up in the Hasse diagrams in Fig. 2, then the
ontologies repaired using the second algorithm are more or equally complete
and incorrect than the ontologies repaired using the first algorithm. The work
in [24] was the first to identify these different combinations. It also showed
that previous work on combining removing with weakening used the combination
(R-one, AB-none) with (W-one, U-now). Previous work on completing used (C-one,
U-end-all). There was no work that used other combinations and no work that
combined all basic operations.

For the examples in this paper we have used Algorithm 1 as a basis for
discussing repairing of ontology networks. It uses a particular combination of
debugging, removing, weakening and completing with specific algorithms for the
basic operations. Our discussion regarding the choices for ontology networks
(Sect. 3) would still hold if we used other algorithms for the basic
operations, or different combination operators for the basic operators.

Algorithm 1 Generate the justifications of each wrong axiom and validate all
wrong asserted axioms from the generated justifications, weaken all wrong
asserted axioms, complete all weakened axioms, add all completed axioms and
remove all wrong asserted axioms at the end (S-one,D-v-all/R-none,AB-
none/W-all,U-end_all/C-all,U-end_all).

Input: TBox ${\cal T}$, Oracle Or, set of unwanted axioms $W$
Output: A repaired TBox

1:$D\leftarrow$ $\emptyset$

2:for each $\alpha$ $\sqsubseteq$ $\beta$ $\in$ $W$ do

3: for each $J\in$ Justifications$({\alpha\sqsubseteq\beta})$ do

4: for each $axiom\in$ $J$ do

5: if $Validate\\_axiom(axiom,Or)=false$ then

6: $D\leftarrow$ $D$ $\cup$ {$axiom$}

7: end if

8: end for

9: end for

10:end for

11:for each $\alpha$ $\sqsubseteq$ $\beta$ $\in$ $D$ do

12: $w_{\alpha\sqsubseteq\beta}\leftarrow$ weakened-axiom-
set($\alpha\sqsubseteq\beta$, ${\cal T},Or)$

13:end for

14:$c_{\alpha\sqsubseteq\beta}\leftarrow$ $\emptyset$

15:for each $\alpha$ $\sqsubseteq$ $\beta$ $\in$ $D$ do

16: for each $sb$ $\sqsubseteq$ $sp$ $\in$ $w_{\alpha\sqsubseteq\beta}$ do

17: $c_{sb\sqsubseteq sp}\leftarrow$ completed-axiom-set($sb\sqsubseteq
sp$,${\cal T},Or)$

18: $c_{\alpha\sqsubseteq\beta}\leftarrow$ $c_{\alpha\sqsubseteq\beta}$ $\cup$
$c_{sb\sqsubseteq sp}$

19: end for

20:end for

21:${\cal T}_{r}$ $\leftarrow$ Add-axioms(${\cal
T}$,$\bigcup_{\alpha\sqsubseteq\beta}$ $c_{\alpha\sqsubseteq\beta}$)

22:${\cal T}_{r}$ $\leftarrow$ Remove-axioms(${\cal T}_{r}$,$D$)

23:return ${\cal T}_{r}$

##  3 Repairing ontology networks - problem definition

In this section we define the repairing problem for ontology networks. Def. 4
is an extension of the definition of repair for single ontologies as defined
in [24]. We are given a set of wrong axioms $W$ that we want to remove from
the ontology network, and when they are removed, they cannot be derived from
the TBox representing the ontology network anymore. These axioms in $W$ can be
axioms in the ontologies or mappings. Further, to guarantee a high level of
quality of the ontology (i.e., so that no correct information is removed or no
incorrect information is added), domain expert validation is a necessity
(e.g., [35, 24]). Therefore, we assume an oracle (representing a domain
expert) that, when given an axiom, can answer whether this axiom is correct or
wrong in the domain of interest of the ontology network. A repair ($A$, $D$)
for the ontology network given the TBox ${\mathcal{T}}$, oracle $Or$, and a
set of wrong axioms $W$, is a tuple containing two sets: a set $A$ of axioms
that are correct according to the oracle and should be added to the TBox, and
a set $D$ of asserted axioms that are not correct according to the oracle and
should be removed from the TBox. We require that when the axioms in $D$ are
removed and the axioms in $A$ are added, the wrong axioms in $W$ cannot be
derived anymore.

######  Definition 4.

(Repair) Let TBox ${\mathcal{T}}$ = ($\bigcup_{i=1..n}$ ${\mathcal{T}}_{i}$)
$\cup$ ($\bigcup_{i,j=1..n,i<j}$ ${\mathcal{A}_{ij}}$) represent a network of
ontologies ${\mathcal{O}_{i}}$ represented by TBoxes ${\mathcal{T}_{i}}$, and
their alignments ${\mathcal{A}_{ij}}$. Let $Or$ be an oracle that given a TBox
axiom returns true or false. Let $W$ be a finite set of TBox axioms in
${\mathcal{T}}$ such that $\forall$ $\psi$ $\in$ $W$: $Or$($\psi$) = false.
Then, a repair for Debug-Problem DP$({\mathcal{T}},Or,W)$ is a tuple ($A$,
$D$) where $A$ and $D$ are finite sets of TBox axioms such that
(i) $\forall$ $\psi$ $\in$ $A$: $Or$($\psi$) = true;
(ii) $D$ is a finite set of asserted axioms in ${\mathcal{T}}$;
(iii) $\forall$ $\psi$ $\in$ $D$: $Or$($\psi$) = false;
(iv) $\forall$ $\psi$ $\in$ $W$: $({\mathcal{T}}\cup A)\setminus D$
$\not\models$ $\psi$.

From a theoretical point of view, as we have represented the ontology network
as a TBox, and previous work has represented ontologies as TBoxes, we could
reuse the algorithms and approaches in, e.g., [24, 25]. However, from a
practical point of view, the situation is more complex. When working with
single ontologies, it is in the interest and mandate of the ontology owners to
repair their ontologies. However, when ontologies are connected in a network,
the ontology and alignment owners may want to retain different levels of
autonomy and not necessarily allow others to change or propose changes to
their ontologies and alignments. Also, computation time and validation work
for repairing may be issues. In this case, computation time and validation
work may be lower within an ontology or alignment than for the whole network.
In this paper we discuss three levels of autonomy and show the influence of
these different choices.

The first level consists of the cases ’O’ (ontology) and ’M’ (mappings). ’O’
represents the choice where ontologies are completely autonomous. Essentially,
this means that ontologies act on their own regarding detection and repairing
of defects. $W$ in Def. 4 contains only axioms in the ontology, only the
axioms within the ontology itself can be used for the computation of repairs,
and solutions can only include axioms in the ontology itself. A dual case is
’M’ where the owners of an alignment are autonomous. In this case $W$ contains
only mappings, and the alignment is repaired using only the mappings in the
alignment. The second level consists of the cases ’MO’ (materialized ontology)
and ’MM’ (materialized mappings). ’MO’ uses the network to derive new axioms
within the ontology and materializes these axioms.777We note that a choice may
be made regarding which axioms to materialize. For taxonomies it may be
feasible to materialize all. However, for ${\mathcal{EL_{\perp}}}$ there is an
infinite number of derivable axioms. In our experiments we restrict the space
to axioms with concepts at the left- and right-hand side with non-nested
operators (SCC in [24]). $W$ contains only axioms in the ontology. For the
computation of repairs the materialized ontology is used, and solutions
contain only axioms within the ontology. This level accepts the fact that the
network provides more knowledge about the own ontology than is represented by
the ontology itself, and accepts this knowledge, but it does not use the
network in repairing. ’MM’, the dual case for mappings, computes derived
mappings for the alignment, but then acts autonomously. $W$ contains only
mappings. The third level ’ON’ (ontology network) considers the ontologies and
alignments as integral parts of the network, uses the full network for the
computation of repairs, and repairs defects using axioms within all ontologies
and alignments. $W$ can contain ontology axioms and mappings. We note that
different ontology and alignment owners may make different choices regarding
their level of autonomy.

These choices have an influence on the detection and repairing of effects. We
give an example for the detection here, and focus on the repairing in further
sections. For the network in Fig. 3 we have the following situation. Using the
full network (level ’ON’), we can derive that concepts E, F, e, and f are
unsatisfiable.888E unsatisfiable because D $\sqcap$ E $\sqsubseteq$ $\perp$, E
$\sqsubseteq$ e, e $\sqsubseteq$ b, b $\sqsubseteq$ D. e unsatisfiable because
E unsatisfiable and e $\sqsubseteq$ E. f unsatisfiable because e unsatisfiable
and f $\sqsubseteq$ e. F unsatisfiable because f unsatisfiable and F
$\sqsubseteq$ f. Using level ’MO’ for both ontologies, we materialize E
$\sqsubseteq$ D and F $\sqsubseteq$ E in the first ontology, and e $\sqcap$ b
$\sqsubseteq$ $\perp$ in the second ontology. This allows us to obtain the
same unsatisfiable concepts as in the ’ON’ level (although the repairing will
be different). When using level ’O’ for both ontologies, we cannot detect any
unsatisfiable concepts.

In general, there is a trade-off between the quality of the repaired
ontologies on the one hand, and the amount of validation work for the oracle
and the autonomy level for the ontologies and alignments on the other hand. In
the next sections we define and exemplify these notions.

Figure 3: The network contains unsatisfiable concepts E, F, e, and f. Asserted
axiom e $\sqsubseteq$ b in $O_{2}$, and mapping b $\sqsubseteq$ D between
$O_{2}$ and $O_{1}$ lead to network incoherence.

##  4 Repairing ontology networks - Combination operators

During the repairing process different levels of autonomy can be used at
different stages. The choice has an influence on the quality of the repair.
Here we show this influence for different stages.

Figure 4: Hasse diagrams regarding (a) the use of different knowledge bases during repairing (KB); (b) different restrictions on the add set (AS);  Table 2: Choices for background knowledge (KB) and add sets (AS). Choices | Description
---|---
KBON | Use the whole ontology network as the background knowledge base to compute
| the sub/sup-concepts when weakening and completing an axiom.
KBMO | Materialize each ontology in the network. Disconnect each ontology from the
| ontology network. Use only the axioms within the materialized ontologies to
| compute the sub/sup-concepts when weakening and completing an axiom.
KBO | Disconnect each ontology from the ontology network. Use the axioms within the
| respective ontologies to compute the sub/sup-concepts when weakening and
| completing an axiom.
KBMM | Materialize each alignment in the network. Disconnect each alignment from the
| ontology network. Use only the mappings within the materialized alignments
to
| compute the sub/sup-concepts when weakening and completing an axiom.
KBM | Disconnect each alignment from the ontology network. Use the mappings within
| the respective alignments to compute the sub/sup-concepts when weakening and
| completing an axiom.
ASON | Add all axioms.
ASO | Add only axioms within the respective ontologies.
ASM | Add only mappings between the ontologies.

###  4.1 Use of background

As discussed earlier, we can use different autonomy levels during the
computation of repairs. In our algorithms, this is reflected by which TBox is
used. We can combine particular choices for debugging, removing, weakening and
completing algorithms with different autonomy levels. As an example, assume we
have made the choices for the basic operations as in Algorithm 1. Then, for
autonomy level ’ON’ we can use Algorithm 1 with as input the TBox representing
the whole network. For levels ’O’ and ’MO’ we can use Algorithm 1 repeatedly
using each of the TBoxes of the ontologies or materialized ontologies,
respectively. (Another possibility is to use as input the union of these
TBoxes, i.e., there will be no axioms representing mappings in the network.)
For ’M’ and ’MM’ we use the alignments or materialized alignments as TBoxes.
The choices are explained in Table 2 where KB stands for ’knowledge base’.
Note that the choices can be performed on each of the basic operations. For
instance, it is possible to debug using ’ON’ and then weaken and complete
using ’MO’. We can organize the choices in a Hasse diagram as in Fig. 4(a).
The proofs for the Hasse diagram are given in the appendix. In general, using
more background knowledge leads to more (or equally) complete and more (or
equally) incorrect networks, and more validation work by the oracle.

As an example, assume we have used ’ON in the debugging step where we validate
all axioms in the justifications, for the network in Fig. 3. This results in
wrong axioms e $\sqsubseteq$ b and b $\sqsubseteq$ D. We now look at the
weakening step for the different autonomy levels. When weakening e
$\sqsubseteq$ b in the second ontology, we use sub-concepts of e and super-
concepts of b to find weakened axioms. These sets are different for different
autonomy levels. We have Sub(e,KBO)={e, f}, Sub(e,KBMO)={e, f},
Sub(e,KBON)={e, f, E, F}, and Sup(b,KBO)={b}, Sup(b,KBMO)={b, a},
Sup(b,KBON)={b, a, D, B, A}. Therefore, there are 2, 4 and 20 candidates for
the weakened axioms for ’O’, ’MO’ and ’ON’, respectively. After validation we
have as weakened axioms f $\sqsubseteq$ b for ’O’, f $\sqsubseteq$ b and e
$\sqsubseteq$ a for ’MO’, and f $\sqsubseteq$ b, e $\sqsubseteq$ a, and E
$\sqsubseteq$ A for ’ON’ (Table 3). As expected from the Hasse diagram, ’ON’
leads to the most complete network, followed by ’MO’ and then ’O’. When
weakening the wrong mapping b $\sqsubseteq$ D, we can choose between ’M’, ’MM’
and ’ON’. We have Sub(b,KBM)={b, D}, Sub(b,KBMM)=Sub(b,KBON)={e, f, b, D, E,
F}, Sup(D,KBM)={D, b}, and Sup(D,KBMM)=Sup(D,KBON)={D, A, B, b, a}.999All
algorithms for debugging, weakening and completing use heuristics when
computing the sub-concepts and super-concepts to prune the search space of
solutions [18, 24]. Also for the networks different heuristics can be used.
For instance, when computing the sub- and super-concepts for the concepts in
mappings, one heuristic is to only allow sub- and super-concepts in the same
ontology. In the example we have allowed sub- and super-concepts to belong to
other ontologies as long as they are involved in mappings. For ’M’ there are
no weakened axioms. For ’MM’ we find b $\sqsubseteq$ B. For ’ON’ we find b
$\sqsubseteq$ B and e $\sqsubseteq$ a. The latter includes both mappings and
ontology axioms. Table 3 also shows the results after completing the weakened
axioms using the same autonomy level as for weakening. The network is repaired
by removing the wrong axioms and adding the completed axioms.

Table 3: Weakening and completing the wrong axioms e $\sqsubseteq$ b and b $\sqsubseteq$ D. Background |  KBO |  KBMO |  KBON |  |  KBM |  KBMM |  KBON
---|---|---|---|---|---|---|---
knowledge base |  e $\sqsubseteq$ b |  e $\sqsubseteq$ b |  e $\sqsubseteq$ b |  |  b $\sqsubseteq$ D |  b $\sqsubseteq$ D |  b $\sqsubseteq$ D
$\mid$Sub($\alpha$,${\mathcal{T}}$)$\mid$ |  2 |  2 |  4 |  |  2 |  6 |  6
$\mid$Sup($\beta$,${\mathcal{T}}$)$\mid$ |  1 |  2 |  5 |  |  2 |  5 |  5
Weakened |  f $\sqsubseteq$ b |  f $\sqsubseteq$ b, e $\sqsubseteq$ a |  f $\sqsubseteq$ b, e $\sqsubseteq$ a, E $\sqsubseteq$ A |  |  |  b $\sqsubseteq$ B |  b $\sqsubseteq$ B, e $\sqsubseteq$ a
$\mid$Sup($\alpha$,${\mathcal{T}}$)$\mid$ |  2 |  4 3 |  10 7 7 |  |  |  5 |  5 7
$\mid$Sub($\beta$,${\mathcal{T}}$)$\mid$ |  1 |  3 5 |  6 11 11 |  |  |  7 |  7 11
Completed |  f $\sqsubseteq$ b |  f $\sqsubseteq$ b, e $\sqsubseteq$ d |  f $\sqsubseteq$ b, e $\sqsubseteq$ d, E $\sqsubseteq$ C |  |  |  b $\sqsubseteq$ B, B $\sqsubseteq$ b |  b $\sqsubseteq$ B, B $\sqsubseteq$ b

###  4.2 Add sets

Another stage where the choice of autonomy level influences the quality of the
repair is when deciding what repairing solutions to retain for the final
repair, i.e. $A$ in Def. 4. The choices are summarized in Table 2 under ’AS’
(Add Set). Choice ASON is the most general case and allows all kinds of axioms
to be added to the network. This means that regardless which choice was used
during the computation of the repairs, these repairs can be used without any
adaptions. Choice ASO only allows to add axioms within ontologies. This
represents the case where ontology owners only focus on repairing their own
ontologies. Similarly, choice ASM only allows to add mappings and represents
the case where alignment owners only focus on repairing their own mappings. In
ASO and ASM, not all repairing suggestions may be retained for the final
solution. Therefore, when ’ON’ was used during the computation of repairs and
’O’ or ’M’ is used during this stage, this may lead to a lower level of
completeness for the network than if ’ON’ is used for this stage. The Hasse
diagram for these choices is given in Fig. 4(b) and the proofs are given in
the appendix.

###  4.3 Finalizing

In the case of ’ON’ the repairing solutions may contain axioms in different
ontologies as well as mappings. In this case the ontology and alignment owners
may decide to materialize the knowledge derived from the network which regards
their ontology or alignment. From the network point of view the network does
not change logically as the same axioms can be derived. From the ontology or
alignment point of view, the difference appears when they are disconnected
from the network. The materialized versions are more (or equally) complete.

###  4.4 Discussion

When the network is owned by one entity (e.g., in the case of modular
ontologies with mappings) or there is a tight cooperation between the owners
of the individual parts of the network (e.g., in a consortium such as EMMO
(https://github.com/emmo-repo/EMMO) or OBO (https://obofoundry.org/)), and
computation time and domain expert staff is not an issue, the recommended
combination is to use (KBON, ASON, final materialization). This ensures the
highest level of completeness for the network as well as for the ontologies
and alignments when they are disconnected from the network.

The least complete networks come from the combinations (KBO, ASO) and (KBM,
ASM). Essentially, this means that mappings between the ontologies exist, but
the network is not taken into account at all during repairing. The repairs are
the same as when repairing is done without the network, and this seems to be a
common case in practice.

When ontology or alignment owners require full control over the computation
resources, while still taking into account the knowledge in the network, then
the combinations with KBMO and KBMM may be a good choice. Maintaining full
control about what is added leads to choices with ASO and ASM.

In the ontology alignment field there are alignment systems that also repair
the alignment. The current systems require that the repair only contains
mappings and thus use ASM. Examples of such systems are ALCOMO [27], LogMap
[13, 14], AgreementMakerLight [37]. Regarding the background knowledge, they
all use the choice KBON. RaDON [12] is a system focusing on network repair,
but makes the same choices as the alignment systems with repair functionality.

##  5 Experiments

As examples of the use of different choices for the combination operators, we
performed experiments on 5 ontology networks. The ontologies (ekaw, sigkdd,
iasted, cmt) used in these networks are from the conference track of the
OAEI101010http://oaei.ontologymatching.org/2023/conference/index.html. We have
used the parts of these ontologies that are expressible in
${\mathcal{EL_{\perp}}}$ in the sense that we removed the parts of axioms that
used constructors not in ${\mathcal{EL_{\perp}}}$. We introduced wrong axioms
in the ontologies and mappings between ontologies by replacing existing axioms
with axioms where the left-hand or right-hand side concepts of the existing
axioms were changed. Further, we also flagged some existing axioms as wrong in
our full experiment set. All axioms were validated manually. The
characteristics of the ontologies and the wrong axioms are shown in the
supplemental material.

We repaired the networks using all choices regarding the use of background
knowledge together with Algorithm 1. To repair ontology axioms we used KBO,
KBMO and KBON. To repair mappings we used KBM, KBMM and KBON. We computed the
sizes of the sets of sub-concepts and super-concepts used in weakeing and
completing. The sizes of these sets reflect the number of axioms that need to
be validated by the oracle. We note, however, that using the visualization in
our system (see below) these sets are shown together and thus the validation
of many axioms can be done at the same time.

The full results for the experiments are shown in the appendix. In the
experiments, the number of axioms to be validated for KBON is between 3 and 5
times higher than for KBO/KBM. The validation work for the materialized
versions KBMO/KBMM is between 6% and 40% higher than for KBO/KBM. For all
networks there were axioms for which the repairing with an operator higher up
in the Hasse diagram led to a strictly more complete ontology network.

##  6 Implemented system

We implemented a Java-based system which extends the ${\cal{EL}}$ version of
the RepOSE system ([44, 22, 24]) with full debugging, weakening and completing
for ${\mathcal{EL_{\perp}}}$ ontology network repairing. The system allows the
user to choose different combinations, thereby giving a choice in the trade-
off between validation work, incorrectness and completeness.

The system uses an interactive way to repair the ontology network. It takes as
input the ontologies and alignments in the network as well as a set of wrong
axioms. It is also possible to not give a set of wrong axioms but let the
system deduce unsatisfiable concepts in the network. As basic algorithms, we
have used the black-box algorithm in [15] for debugging, and the weakening and
completing algorithms in [24]. With respect to the combination operators in
the Hasse diagrams, the system supports (S-one, D-v-all) and (S-one, D-one-v)
thereby providing the choice to validate all axioms in the justifications or
to validate Hitting sets. Regarding weakening the combinations are (R-none,AB-
none/W-all,U-end_all), (R-all,AB-none/W-all,U-end_all) and (R-one,AB-
one/W-one,U-end_all). The first combination does not remove wrong axioms
during the computation, weakens all axioms at once and updates at the end. The
second removes all wrong axioms before the computation, weakens all axioms at
once and updates at the end. The third removes wrong axioms one at a time
during the computation and puts them back before dealing with the next wrong
axiom. It weakens axioms one at a time and updates at the end. For completing,
the choices are (C-all,U-end_all) and (C-one,U-end_one). The first combination
completes all weakened axioms at once and updates at the end. The second
completes the weakened axioms one at a time and updates the ontology after the
weakened axiom set is handled for each wrong axiom. Regarding the choices for
the combinations for the network, all choices for KB are implemented. The AS
choices are supported using visual clues. The concepts in the axioms to be
validated are labeled with the ontology source, such that the user can
distinguish mappings from axioms within the ontologies. We also use different
colors to represent the concepts which belong to different ontologies. At the
appropriate times the system shows the different combinations that can be
chosen and the user can select the desired choice.

For the basic operations the user interactions are adapted to the task at hand
and different panels are used. For debugging the user requests the generation
of the justifications. Then, the user can validate the axioms in the
justifications or ask the system to compute Hitting sets and validate the
axioms in those. The axioms to be validated are shown in a list. During
weakening, after choosing the preferred combination strategy, the user
requests the system to generate the candidate weakened axioms for each axiom
$\alpha$ $\sqsubseteq$ $\beta$ in the wrong asserted axioms set. The system
computes the set of sub-concepts of $\alpha$ (sub) and the set of super-
concepts of $\beta$ (sup), thereby representing the possible choices for
weaker axioms. These weaker axioms can be visualized in two ways: (i) as a
list of axioms and (ii) by two panes representing the sub and sup sets with
their subsumption relations (Fig. 5), respectively. In the latter case the
user can choose weakened axioms by clicking on a concept in the sub set and a
concept in the sup set and select the axiom as a weakened axiom. The advantage
of this case is that these axioms are validated with the context in the domain
of the ontology (showing the partial ontology through visualization). The set-
up for completing is similar as for the weakening. For an axiom $\alpha$
$\sqsubseteq$ $\beta$ to be completed, the set of super-concepts of $\alpha$
and the set of sub-concepts of $\beta$ are computed and visualized as lists or
using two panes (Fig. 6). Validation is performed in a similar way as for
weakening.

Figure 5: Sub and sup when weakening wrong axiom Organizator $\sqsubseteq$
Organizing_Committee_Member in ontology network ekaw-sigkdd using (a) KBO; (b)
KBON. Concepts in wrong axiom in red, concepts in ekaw in blue, concepts in
sigkdd in black.

Figure 6: Sub and sup when completing weakened axiom Organizator $\sqsubseteq$
Person in ontology network ekaw-sigkdd using (a) KBO; (b) KBON. Concepts in
weakened axiom in red, concepts in ekaw in blue, concepts in sigkdd in black.

##  7 Conclusion

In this paper we presented a framework for repairing ontology networks that
alleviates the problem of removing correct knowledge when removing unwanted
axioms from the network. It uses the basic operators of debugging, removing,
weakening and completing for which there exist different approaches. We
defined combination operators that represent choices to be made when combining
the basic operations. We introduced different levels of autonomy for the
ontologies and alignments in the networks and defined combination operators
based on these levels and the use of background knowledge during the
computation of repairs and the selection of the final solution. We have shown
the influence of the combination operators on the quality of the repaired
network. The framework gives flexibility to the ontology and alignment owners
regarding their use and update policies. The framework also provides a
blueprint to extend existing systems to more general systems for repairing
ontologies and ontology networks.

##### Supplemental Material Statement:

The supplemental material is available at
https://figshare.com/s/e652a8e100579316f876. It includes the ontology versions
used in the experiments and implemented system.

## Acknowledgements

This work is financially supported by the Swedish e-Science Research Centre
(SeRC) and the EU Horizon Europe project Onto-DESIDE under Grant Agreement
101058682.

## References

  * [1] Arif, M.F., Mencía, C., Ignatiev, A., Manthey, N., Peñaloza, R., Marques-Silva, J.: BEACON: An Efficient SAT-Based Tool for Debugging $\mathcal{EL}$\+ Ontologies. In: SAT. LNCS, vol. 9710, pp. 521–530 (2016). https://doi.org/10.1007/978-3-319-40970-2_32
  * [2] Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press (2003)
  * [3] Baader, F., Kriegel, F., Nuradiansyah, A., Peñaloza, R.: Making repairs in description logics more gentle. In: KR. pp. 319–328 (2018)
  * [4] Chen, J., Dong, H., Hastings, J., Jiménez-Ruiz, E., López, V., Monnin, P., Pesquita, C., Škoda, P., Tamma, V.: Knowledge Graphs for the Life Sciences: Recent Developments, Challenges and Opportunities. Trans Graph Data and Knowledge 1(1), 5:1–33 (2023). https://doi.org/10.4230/TGDK.1.1.5
  * [5] Confalonieri, R., Galliani, P., Kutz, O., Porello, D., Righetti, G., Troquard, N.: Towards even more irresistible axiom weakening. In: DL (2020)
  * [6] Du, J., Wan, H., Ma, H.: Practical TBox abduction based on justification patterns. In: AAAI. pp. 1100–1106 (2017)
  * [7] Fleischhacker, D., Meilicke, C., Völker, J., Niepert, M.: Computing incoherence explanations for learned ontologies. In: RR. LNCS, vol. 7994, pp. 80–94 (2013). https://doi.org/10.1007/978-3-642-39666-3_7
  * [8] Haifani, F., Koopmann, P., Tourret, S., Weidenbach, C.: Connection-minimal abduction in $\mathcal{EL}$ via translation to fol. In: IJCAR. LNCS, vol. 13385, pp. 188–207 (2022). https://doi.org/10.1007/978-3-031-10769-6_12
  * [9] Hogan, A., Blomqvist, E., Cochez, M., D’amato, C., Melo, G.D., Gutierrez, C., Kirrane, S., Gayo, J.E.L., Navigli, R., Neumaier, S., Ngomo, A.C.N., Polleres, A., Rashid, S.M., Rula, A., Schmelzeisen, L., Sequeda, J., Staab, S., Zimmermann, A.: Knowledge graphs. ACM Comput. Surv. 54(4), 71:1–37 (2022). https://doi.org/10.1145/3447772
  * [10] Ivanova, V., Laurila Bergman, J., Hammerling, U., Lambrix, P.: Debugging Taxonomies and their Alignments: the ToxOntology - MeSH Use Case. In: WoDOOM. LECP, vol. 79, pp. 25–36 (2012)
  * [11] Ji, Q., Gao, Z., Huang, Z., Zhu, M.: An efficient approach to debugging ontologies based on patterns. In: JIST. LNCS, vol. 7185, pp. 425–433 (2011). https://doi.org/10.1007/978-3-642-29923-0_33
  * [12] Ji, Q., Haase, P., Qi, G., Hitzler, P., Stadtmüller, S.: Radon - repair and diagnosis in ontology networks. In: ESWC. LNCS, vol. 5554, pp. 863–867 (2009). https://doi.org/10.1007/978-3-642-02121-3_71
  * [13] Jiménez-Ruiz, E., Grau, B.C.: Logmap: Logic-based and scalable ontology matching. In: ISWC. LNCS, vol. 7031, pp. 273–288 (2011). https://doi.org/10.1007/978-3-642-25073-6_18
  * [14] Jiménez-Ruiz, E., Grau, B.C., Zhou, Y., Horrocks, I.: Large-scale interactive ontology matching: Algorithms and implementation. In: ECAI. pp. 444–449 (2012). https://doi.org/10.3233/978-1-61499-098-7-444
  * [15] Kalyanpur, A., Parsia, B., Horridge, M., Sirin, E.: Finding All Justifications of OWL DL Entailments. In: ISWC. LNCS, vol. 4825, pp. 267–280 (2007). https://doi.org/10.1007/978-3-540-76298-0_20
  * [16] Kalyanpur, A., Parsia, B., Sirin, E., Cuenca-Grau, B.: Repairing Unsatisfiable Concepts in OWL Ontologies. In: ESWC. LNCS, vol. 4011, pp. 170–184 (2006). https://doi.org/10.1007/11762256_15
  * [17] Kazakov, Y., Skocovský, P.: Enumerating justifications using resolution. In: IJCAR. LNCS, vol. 10900, pp. 609–626 (2018). https://doi.org/10.1007/978-3-319-94205-6_40
  * [18] Lambrix, P.: Completing and debugging ontologies: State of the art and challenges in repairing ontologies. ACM J Data and Information Quality 15(4), 41:1–38 (2023). https://doi.org/10.1145/3597304
  * [19] Lambrix, P., Armiento, R., Li, H., Hartig, O., Pour, M.A.N., Li, Y.: The materials design ontology. Semantic Web 15(2), 481–515 (2024). https://doi.org/10.3233/SW-233340
  * [20] Lambrix, P., Dragisic, Z., Ivanova, V.: Get my pizza right: Repairing missing is-a relations in $\mathcal{ALC}$ ontologies. In: JIST. LNCS, vol. 7774, pp. 17–32 (2012). https://doi.org/10.1007/978-3-642-37996-3_2
  * [21] Lambrix, P., Ivanova, V.: A unified approach for debugging is-a structure and mappings in networked taxonomies. J Biomed Semant 4, 10 (2013). https://doi.org/10.1186/2041-1480-4-10
  * [22] Lambrix, P., Wei-Kleiner, F., Dragisic, Z.: Completing the is-a structure in light-weight ontologies. J Biomedical Semantics 6, 12:1–26 (2015). https://doi.org/10.1186/s13326-015-0002-8
  * [23] Lehmann, J., Bühmann, L.: ORE - A tool for repairing and enriching knowledge bases. In: ISWC. LNCS, vol. 6497, pp. 177–193 (2010). https://doi.org/10.1007/978-3-642-17749-1_12
  * [24] Li, Y., Lambrix, P.: Repairing $\mathcal{EL}$ ontologies using weakening and completing. In: ESWC. LNCS, vol. 13870, pp. 298–315 (2023). https://doi.org/10.1007/978-3-031-33455-9_18
  * [25] Li, Y., Lambrix, P.: Repairing $\mathcal{EL\perp}$ ontologies using debugging, weakening and completing (2024), submitted
  * [26] Li, Y., Lambrix, P.: Repairing networks of $\mathcal{EL_{\perp}}$ ontologies using weakening and completing. In: ISWC (2024)
  * [27] Meilicke, C.: Alignment Incoherence in Ontology Matching. Ph.D. thesis, University of Mannheim (2011)
  * [28] Meyer, T., Lee, K., Booth, R., Pan, J.: Finding maximally satisfiable terminologies for the description logic $\mathcal{ALC}$. In: AAAI. pp. 269–274 (2006)
  * [29] Moodley, K., Meyer, T., Varzinczak, I.J.: Root justifications for ontology repair. In: RR. LNCS, vol. 6902, pp. 275–280 (2011). https://doi.org/10.1007/978-3-642-23580-1_24
  * [30] Méndez, J., Alrabbaa, C., Koopmann, P., Langner, R., Baader, F., Dachselt, R.: Evonne: A visual tool for explaining reasoning with OWL ontologies and supporting interactive debugging. Computer Graphics forum 42(6), e14730:1–15 (2023). https://doi.org/10.1111/cgf.14730
  * [31] Nikitina, N., Rudolph, S., Glimm, B.: Interactive ontology revision. J Web Semantics 12, 118–130 (2012). https://doi.org/10.1016/j.websem.2011.12.002
  * [32] Noy, N., Gao, Y., Jain, A., Narayanan, A., Patterson, A., Taylor, J.: Industry-scale knowledge graphs: Lessons and challenges. Comm ACM 62(8), 36–43 (2019). https://doi.org/10.1145/3331166
  * [33] Paulheim, H.: Knowledge graph refinement: A survey of approaches and evaluation methods. Semantic Web J 8(3), 489–508 (2017). https://doi.org/10.3233/SW-160218
  * [34] Peñaloza, R.: Axiom pinpointing. In: Cota, G., Daquino, M., Pozzato, G.L. (eds.) Applications and Practices in Ontology Design, Extraction, and Reasoning, Studies on the Semantic Web, vol. 49, pp. 162–177. IOS Press (2020). https://doi.org/10.3233/SSW200042
  * [35] Pesquita, C., Faria, D., Santos, E., Couto, F.M.: To repair or not to repair: reconciling correctness and coherence in ontology reference alignments. In: OM. pp. 13–24 (2013)
  * [36] Rodler, P., Schmid, W.: On the impact and proper use of heuristics in test-driven ontology debugging. In: RuleML+RR. LNCS, vol. 11092, pp. 164–184 (2018). https://doi.org/10.1007/978-3-319-99906-7_11
  * [37] Santos, E., Faria, D., Pesquita, C., Couto, F.M.: Ontology alignment repair through modularization and confidence-based heuristics. PLoS ONE 10(12):e0144807), 1–19 (2015). https://doi.org/10.1371/journal.pone.0144807
  * [38] Schekotihin, K., Rodler, P., Schmid, W.: OntoDebug: Interactive Ontology Debugging Plug-in for Protégé. In: FoIKS. LNCS, vol. 10833, pp. 340–359 (2018). https://doi.org/10.1007/978-3-319-90050-6_19
  * [39] Schlobach, S.: Debugging and Semantic Clarification by Pinpointing. In: ESWC. LNCS, vol. 3532, pp. 226–240 (2005). https://doi.org/10.1007/11431053_16
  * [40] Schlobach, S., Cornet, R.: Non-Standard Reasoning Services for the Debugging of Description Logic Terminologies. In: IJCAI. pp. 355–360 (2003)
  * [41] Schlobach, S., Huang, Z., Cornet, R., van Harmelen, F.: Debugging Incoherent Terminologies. J Automated Reasoning 39(3), 317–349 (2007). https://doi.org/10.1007/s10817-007-9076-z
  * [42] Shchekotykhin, K.M., Friedrich, G., Fleiss, P., Rodler, P.: Interactive ontology debugging: Two query strategies for efficient fault localization. J Web Semantics 12, 88–103 (2012). https://doi.org/10.1016/j.websem.2011.12.006
  * [43] Troquard, N., Confalonieri, R., Galliani, P., Peñaloza, R., Porello, D., Kutz, O.: Repairing ontologies via axiom weakening. In: AAAI. pp. 1981–1988 (2018)
  * [44] Wei-Kleiner, F., Dragisic, Z., Lambrix, P.: Abduction framework for repairing incomplete $\mathcal{EL}$ ontologies: Complexity results and algorithms. In: AAAI. pp. 1120–1127 (2014)

Appendix

##  Appendix 0.A Combinations of basic operations

###  0.A.1 Combination operators

Table 4 shows combination operators that can be used as building blocks in the
design of algorithms. For each of the basic operations (debugging, removing,
weakening and completing) we show choices. The operations for removing,
weakening and completing are taken from [24]. The operations for debugging are
from [26, 25].

Table 4: Debugging, removing, weakening and completing - operations. Operations | Description
---|---
S-one | Compute the justifications for one wrong axiom at the time.
S-all | Compute the justifications for all wrong axioms at once.
D-one-v | Generate one Hitting set from the justifications, then validate
| the asserted axioms in the generated Hitting set.
D-v-one | Validate one valid Hitting set in the justifications.
D-all-v/D-v-all | Validate all asserted axioms from the justifications.
R-all | Remove all the wrong axioms at once.
R-one | Remove the wrong axioms one at a time.
R-none | Remove nothing.
W-all | Weaken all wrong axioms at once.
W-one | Weaken the wrong axioms one at a time
C-all | Complete all weakened axioms at once.
C-one | Complete the weakened axioms one at a time.
AB-one | Add one wrong axiom back.
AB-all | Add all wrong axioms back.
AB-none | Add nothing back.
U-now | Update the changes immediately.
U-end_one | Update the changes after the iteration of each wrong axiom.
U-end_all | Update the changes after iterations of all wrong axioms.

##  Appendix 0.B Derivation of Hasse diagrams

The proofs for the Hasse diagrams are based on the following observations. For
a given TBox $\mathcal{T}$, let Der($\mathcal{T}$) denote the set of derivable
axioms from $\mathcal{T}$. Then, for TBoxes $\mathcal{T}_{1}$ and
$\mathcal{T}_{2}$, if $\mathcal{T}_{1}$ $\subseteq$ $\mathcal{T}_{2}$, then we
know that Der($\mathcal{T}_{1}$) $\subseteq$ Der($\mathcal{T}_{2}$). This
means that if an axiom is derivable from TBox $\mathcal{T}_{1}$, it is also
derivable from TBox $\mathcal{T}_{2}$, but not necessarily the other way
around. Therefore, if $\mathcal{T}_{1}$ $\subseteq$ $\mathcal{T}_{2}$, all
correct axioms in $\mathcal{T}_{1}$ can also be derived from
$\mathcal{T}_{2}$, and thus $\mathcal{T}_{2}$ is more or equally complete than
$\mathcal{T}_{1}$. Similarly, all wrong axioms in $\mathcal{T}_{1}$ can also
be derived from $\mathcal{T}_{2}$, and thus $\mathcal{T}_{2}$ is more or
equally incorrect than $\mathcal{T}_{1}$.

###  0.B.1 Ontologies

The Hasse diagrams for removing, weakening and completing were derived in
[24]. The Hasse diagram for debugging was derived in [26, 25]. The proofs for
these are in [25] and are copied here for the sake of completeness.

####  0.B.1.1 Debugging

When choosing the operations which contain D-all-v or D-v-all, all wrong
asserted axioms in the justifications of the given wrong axioms are retained
after validation ($W_{S-all,D-all-v/D-v-all}$ = $W_{S-one,D-all-v/D-v-
all}$).111111We consider here the debugging phase separate from the weakening
and completing. In the case we would interleave the operations, it is not
clear how to compare the incorrectness of the original ontology and the
repaired ontology. For instance, if we use S-one, then when removing the
axioms in the justifications of a selected wrong axiom from the original
ontology (version 1) we obtain a less incorrect ontology (version 2). Then
during the weakening and completing steps, new axioms are added making the new
version of the ontology (version 3) more complete, but possibly also more
incorrect than version 2 (as new wrong axioms may be derivable using wrong
axioms still in the ontology in combination with the added axioms). These new
axioms may then influence the justifications for the next selected wrong axiom
to process, finding more wrong asserted axioms to remove and thus find a less
incorrect ontology (version 4) than version 3. Thus, when combining debugging
with weakening and completing for S-one, for each original wrong axiom we
would make the ontology less incorrect in one way and then more incorrect in
another way, but also producing opportunities for additional removal of
asserted wrong axioms that may not appear when using S-all. For the other
choices, not all axioms in the justifications are validated and used and thus
the set of asserted wrong axioms to remove for each of those choices is a
subset of $W_{S-all,D-all-v/D-v-all}$. Note that the Hitting sets computed by
the different choices may be different and thus they are siblings in the Hasse
diagram.

####  0.B.1.2 Removing

In general, when removing all axioms at once, the TBox is a subset of the TBox
with one axiom removed, which in turn is a subset of the TBox where no axioms
are removed. When adding no axioms back, the TBox is a subset of the TBox with
one axiom added back, which in turn is a subset of the TBox where all axioms
are added back. If no wrong axioms are removed, then nothing needs to be added
back and thus AB-one, AB-all and AB-none have the same result
($\mathcal{T}_{R-none,AB-all}$ = $\mathcal{T}_{R-none,AB-one}$ =
$\mathcal{T}_{R-none,AB-none}$). The TBox for these strategies is larger
during computation (of weakened or completed axiom sets) than the TBoxes where
one or all wrong axioms are removed. If one wrong axiom at the time is
removed, the adding back all (AB-all) or one (AB-one) give the same result
($\mathcal{T}_{R-one,AB-all}$ = $\mathcal{T}_{R-one,AB-one}$) as both
strategies add the same one axiom back. The TBox for these strategies is
larger than when no wrong axiom is added back ($\mathcal{T}_{R-one,AB-none}$
$\subseteq$ $\mathcal{T}_{R-one,AB-all}$ = $\mathcal{T}_{R-one,AB-one}$). When
all wrong axioms are removed at once, then they will be added back at the end
or not.121212After completing they should be removed, but after weakening they
could be added back for the completion step. However, this does not influence
the TBox during the computation. Therefore, the add back strategy does not
matter and the TBox during computation is smaller than when wrong axioms were
removed one at a time ($\mathcal{T}_{R-all,AB-all}$ = $\mathcal{T}_{R-all,AB-
one}$ = $\mathcal{T}_{R-all,AB-none}$ $\subseteq$ $\mathcal{T}_{R-one,AB-
none}$).

####  0.B.1.3 Weakening

First, we note that updating immediately or updating after each wrong axiom is
the same operation for weakening, as a complete weakened axiom set for a wrong
axiom is computed. Thus, the TBox for ($\mathcal{T}_{W-one,U-now}$) is the
same as for ($\mathcal{T}_{W-one,U-end\\_one}$), and the TBox for
($\mathcal{T}_{W-all,U-now}$) is the same as for
($\mathcal{T}_{W-all,U-end\\_one}$). Further, when weakening one axiom at a
time and updating the TBox (i.e., adding the axioms of the weakened axiom set
for a wrong axiom) immediately, results in a larger TBox for the next
computations of weakened axiom sets for wrong axioms, than if we would not
update immediately ($\mathcal{T}_{W-one,U-end\\_all}$ $\subseteq$
$\mathcal{T}_{W-one,U-now}$). When not immediately updating, the TBox for
generating the weakened axiom sets, stays the same for all wrong axioms and
thus gives the same result as weakening all wrong axioms at once. Thus,
$\mathcal{T}_{W-all,U-now}$ = $\mathcal{T}_{W-all,U-end\\_all}$ =
$\mathcal{T}_{W-one,U-end\\_all}$.

####  0.B.1.4 Completing

When completing one axiom at a time and updating the TBox (i.e., adding the
axioms of the completed axiom set for a weakened axiom) immediately, results
in a larger TBox for the next computations of completed axiom sets for
weakened axioms than not updating immediately
($\mathcal{T}_{C-one,U-end\\_one}$ $\subseteq$ $\mathcal{T}_{C-one,U-now}$,
$\mathcal{T}_{C-one,U-end\\_all}$ $\subseteq$ $\mathcal{T}_{C-one,U-now}$).
When not updating immediately, there is the choice between updating after all
weakened axioms for a particular wrong axiom have been processed or waiting
until all weakened axioms for all wrong axioms are processed. The TBox for the
former case is larger than the one for the latter case
($\mathcal{T}_{C-one,U-end\\_all}$ $\subseteq$
$\mathcal{T}_{C-one,U-end\\_one}$). Waiting to update the TBox until all
weakened axioms for all wrong axioms are processed, means the TBox stays the
same during the computation of the completed axioms sets and thus gives the
same result as completing all weakened axioms at once
($\mathcal{T}_{C-one,U-end\\_all}$ = $\mathcal{T}_{C-all,U-end\\_all}$ =
$\mathcal{T}_{C-all,U-end\\_one}$ = $\mathcal{T}_{C-all,U-now}$).

###  0.B.2 Ontology networks

####  0.B.2.1 Background knowledge

Let ${\mathcal{T}}_{1}$, …,${\mathcal{T}_{n}}$ be TBoxes representing
ontologies ${\mathcal{O}_{1}}$, …, ${\mathcal{O}_{n}}$, respectively. For
$i,j\in[1..n]$ with $i<j$, let ${\mathcal{A}_{ij}}$ be an alignment between
ontology ${\mathcal{O}_{i}}$ and ${\mathcal{O}_{j}}$. Let TBox
$\mathcal{T}_{ON}$ = ($\bigcup_{i=1..n}$ ${\mathcal{T}}_{i}$) $\cup$
($\bigcup_{i,j=1..n,i<j}$ ${\mathcal{A}_{ij}}$) represent the network.

Let Tbox $\mathcal{T}_{MON}$ be the materialized version of the network, i.e.,
all (chosen) derived axioms in the network represented by $\mathcal{T}_{ON}$
are asserted in $\mathcal{T}_{MON}$. Then $\mathcal{T}_{MON}$ =
($\bigcup_{i=1..n}$ ${\mathcal{T}}_{mi}$) $\cup$ ($\bigcup_{i,j=1..n,i<j}$
${\mathcal{A}_{mij}}$) where ${\mathcal{T}}_{mi}$ contains all axioms in
$\mathcal{T}_{MON}$ that relate concepts within ontology ${\mathcal{O}_{i}}$,
and ${\mathcal{A}_{mij}}$ contains all mappings in $\mathcal{T}_{MON}$ between
concepts in ${\mathcal{O}_{i}}$ and concepts in ${\mathcal{O}_{j}}$.

Then we have the following observations.
(i) Der($\mathcal{T}_{MON}$) = Der($\mathcal{T}_{ON}$).
(ii) As each axiom in ${\mathcal{T}}_{i}$ is derivable from the network, it is
contained in ${\mathcal{T}}_{mi}$. Thus, for each i: ${\mathcal{T}}_{i}$
$\subseteq$ ${\mathcal{T}}_{mi}$.
(iii) As each mapping in ${\mathcal{A}_{ij}}$ is derivable from the network,
it is contained in ${\mathcal{A}_{mij}}$. Thus, for each i,j:
${\mathcal{A}_{ij}}$ $\subseteq$ ${\mathcal{A}_{mij}}$.

We give now the proof of the Hasse diagrams considering that all ontologies
(or alignments) use the same autonomy level. (The framework allows to have
different autonomy levels for different ontologies and alignments. For this
case the proofs are similar.)

If we use KBO, then the algorithms for debugging, repairing and weakening use
TBox $\bigcup_{i}$ ${\mathcal{T}}_{i}$. (No connections between the
ontologies, so, in principle each ontology is dealt with separately.) When
using KBMO, then the algorithms use TBox $\bigcup_{i}$ ${\mathcal{T}m}_{i}$.
By observation (ii), more knowledge is used for KBMO than for KBO, and thus
the repaired ontology network for KBMO is more (or equally) complete and more
(or equally) incorrect than for KBO.

KBON uses TBox $\mathcal{T}_{ON}$ which is logically equivalent to using
$\mathcal{T}_{MON}$ (observation (i)). As $\bigcup_{i}$ ${\mathcal{T}m}_{i}$
$\subseteq$ ($\bigcup_{i=1..n}$ ${\mathcal{T}}_{mi}$) $\cup$
($\bigcup_{i,j=1..n,i<j}$ ${\mathcal{A}_{mij}}$) = $\mathcal{T}_{MON}$, we
know that the repaired ontology network for KBON is more (or equally) complete
and more (or equally) incorrect than for KBMO.

Similar reasoning (using observations (i) and (iii)) leads to the fact that
the repaired ontology network for KBON is more (or equally) complete and more
(or equally) incorrect than for KBMM, which in its turn is more (or equally)
complete and more (or equally) incorrect than for KBM.

####  0.B.2.2 Add sets

Axioms are added to the ontology network after weakening, completing or as the
final result. Assume the set of axioms AS is a result of one of these stages.
Then AS = OA $\cup$ M where OA is the set of axioms within ontologies in the
result and M is the set of mappings between ontologies in the result. We know
that OA $\cap$ M = $\emptyset$.

Assume the current ontology is represented by $\mathcal{T}$. When using ASON,
AS is added to the ontology network. When using ASO, OA is added to the
ontology network. Finally, when using ASM, M is added to the ontology network.
As $\mathcal{T}$ $\cup$ M $\subseteq$ $\mathcal{T}$ $\cup$ AS and
$\mathcal{T}$ $\cup$ OA $\subseteq$ $\mathcal{T}$ $\cup$ AS, using ASON leads
to a more complete network than using ASO or ASM.

##  Appendix 0.C Computing weakened and completed axioms

In this section we show the sub- and super-concept sets used for computing
weakened and completed axioms for the example in Sect. 4. (When there are
empty cells in the tables, it means that we did not need to compute the sub-
and super-concepts sets for these choices of combination operator.)

Table 5: The sub- and super-concepts computed during weakening e $\sqsubseteq$ b. | KBO | KBMO | KBON
---|---|---|---
Sub($e$,${\mathcal{T}}$) | {e, f} | {e, f} | {e, f, E, F}
Sup($b$,${\mathcal{T}}$) | {b} | {b, a} | {b, a, D, B, A}
Table 6: The sub- and super-concepts computed during weakening b $\sqsubseteq$ D. | KBM | KBMM | KBON
---|---|---|---
Sub($b$,${\mathcal{T}}$) | {b, D} | {e, f, b, D, E, F} | {e, f, b, D, E, F}
Sup($D$,${\mathcal{T}}$) | {D, b} | {D, b, A, a, B} | {D, A, B, b, a}
Table 7: The sub- and super-concepts computed during completing the weakened axioms for wrong axiom e $\sqsubseteq$ b. Background knowledge base |  KBO | KBMO | KBON
---|---|---|---
Sup($f$,${\mathcal{T}}$) |  {e, f} | {e, f, b, a} | {A, B, C, D, E, F, e, f, b, a}
Sub($b$,${\mathcal{T}}$) |  {b} | {e, f, b} | {D, E, F, e, f, b}
Sup($e$,${\mathcal{T}}$) |  | {e, b, a} | {e, E, b, D, A, B, a}
Sub($a$,${\mathcal{T}}$) |  | {d, e, f, b, a} | {b, C, f, d, e, E, F, D, A, B, a}
Sup($E$,${\mathcal{T}}$) |  |  | {e, E, b, D, A, B, a}
Sub($A$,${\mathcal{T}}$) |  |  | {b, C, f, d, e, E, F, D, A, B, a}
Table 8: The sub- and super-concepts computed during completing the weakened axioms for wrong mapping b $\sqsubseteq$ D. Background knowledge base | KBM | KBMM | KBON
---|---|---|---
Sup($b$,${\mathcal{T}}$) |  | {b, a, B, A, D} | {A, B, D b, a}
Sub($B$,${\mathcal{T}}$) |  | {B, D, E, F, e, f, b} | {B, D, E, F, e, f, b}
Sup($e$,${\mathcal{T}}$) |  |  | {e, E, b, D, A, B, a}
Sub($a$,${\mathcal{T}}$) |  |  | {b, C, f, d, e, E, F, D, A, B, a}

##  Appendix 0.D Experiments - results

In the experiments we use 5 ontology networks. Each network consists of two
ontologies and an alignment. The number of concepts, roles and axioms of the
ontologies are given in Table 9 and the number of mappings in the alignments
is given in Table 10. Tables 11 and 12 list the wrong axioms and mappings we
introduced in each ontology network. These wrong axioms were generated by
replacing existing axioms with axioms where their left/right-hand side
concepts were changed.

The results of the experiments are listed in Tables 13-17. These tables list
the sizes of the sub-concepts set of $\alpha$ and the super-concepts set of
$\beta$ for each wrong axiom $\alpha\sqsubseteq\beta$ and the correct weakened
axioms. Further, for each correct weakened axiom $\alpha\sqsubseteq\beta$, it
shows the sizes of the super-concepts set of $\alpha$ and the sub-concepts set
of $\beta$ as well as the correct completed axioms. The sizes of these sets
reflect the number of axioms that need to be validated by the oracle. We note,
however, that using the visualization in our system these sets are shown
together and thus the validation of many axioms can be done at the same time.

Table 9: Ontologies | ekaw | sigkdd | cmt | iasted
---|---|---|---|---
Concepts | 74 | 49 | 36 | 140
Roles | 33 | 17 | 49 | 38
Axioms | 340 | 193 | 319 | 539
Table 10: Ontology networks Ontology network | ekaw-sigkdd | cmt-sigkdd | cmt-ekaw | iasted-sigkdd | ekaw-iasted
---|---|---|---|---|---
Mappings | 11 | 9 | 11 | 14 | 10
Table 11: Wrong axioms in each ontology. Ontology |  Wrong axioms ($W$)
---|---
ekaw |  Tutorial $\sqsubseteq$ Conference
sigkdd |  Organizator $\sqsubseteq$ Organizing_Committee_Member
cmt |  Program _Committee $\sqsubseteq$ Person Program_ Committee_Chair $\sqsubseteq$ Program_ Committee
iasted |  Final_manuscript $\sqsubseteq$ Publication
Table 12: Wrong mappings in each ontology network. Ontology network |  Wrong mappings ($W$)
---|---
ekaw-sigkdd |  sigkdd:Organizator $\sqsubseteq$ ekaw:OC_Member
cmt-sigkdd |  cmt:Conference_Chair $\sqsubseteq$ sigkdd:Program_Chair
cmt-ekaw |  cmt:Conference Member $\sqsubseteq$ ekaw:OC_Member
ekaw-iasted |  ekaw:Workshop_ Chair $\sqsubseteq$ iasted:Session_Chair
iasted-sigkdd |  iasted:Registration_fee $\sqsubseteq$ sigkdd:NonMember_Registration
Table 13: ekaw-sigkdd Wrong |  sigkdd:Organizator$\sqsubseteq$ sigkdd:Organizing_Committee _Member |  ekaw:Tutorial$\sqsubseteq$ ekaw:Conference |  sigkdd:Organizator$\sqsubseteq$ekaw:OC_Member
---|---|---|---
KB |  KBO/KBMO |  KBON |  KBO/KBMO |  KBON |  KBM |  KBMM |  KBON
$\mid$Sub($\alpha$,${\mathcal{T}}$)$\mid$ |  5 |  8 |  1 |  1 |  2 |  4 |  8
$\mid$Sup($\beta$,${\mathcal{T}}$)$\mid$ |  3 |  4 |  3 |  4 |  2 |  4 |  7
Weakened |  sigkdd:Organizator $\sqsubseteq$sigkdd:Person |  ekaw:Tutorial $\sqsubseteq$ekaw:Scientific _Event |  |  sigkdd:Organ izator$\sqsubseteq$ ekaw:Person |  sigkdd:Organizator$\sqsubseteq$ ekaw:Conference _Participant
$\mid$Sup($\alpha$,${\mathcal{T}}$)$\mid$ |  4 |  7 |  4 |  5 |  |  4 |  7
$\mid$Sub($\beta$,${\mathcal{T}}$)$\mid$ |  13 |  32 |  15 |  16 |  |  10 |  18
completed |  sigkdd: Organizator$\sqsubseteq$ sigkdd:Person, sigkdd: Organizing _Committee _member$\sqsubseteq$ sigkdd: Organizator |  sigkdd: Organizator$\sqsubseteq$ sigkdd:Person, sigkdd: Organizing _Committee _member$\sqsubseteq$ sigkdd: Organizator, sigkdd: Organizing_ Committee _Member$\sqsubseteq$ ekaw:OC _Member |  ekaw:Tutorial$\sqsubseteq$ ekaw:Individual _Presentation |  |  sigkdd:Organ izator$\sqsubseteq$ ekaw:Person |  ekaw:OC_Member$\sqsubseteq$ sigkdd:Organizing _Committee_Member, sigkdd:Organizator$\sqsubseteq$ ekaw:Conference _Participant
Table 14: cmt-sigkdd Wrong |  sigkdd:Organizator $\sqsubseteq$ sigkdd:Organizing _Committee _Member |  cmt:Program _Committee$\sqsubseteq$ cmt:Person |  cmt:Conference_Chair$\sqsubseteq$ sigkdd:Program_Chair |  cmt:Program_Committee _Chair$\sqsubseteq$ cmt:Program_Committee
---|---|---|---|---
KB |  KBO |  KBMO |  KBON |  KBO/ KBMO |  KBON |  KBM |  KBMM |  KBON |  KBO/ KBMO |  KBON
$\mid$Sub($\alpha$,${\mathcal{T}}$)$\mid$ |  5 |  7 |  2 |  3 |  2 |  2 |  2 |  1 |  1
$\mid$Sup($\beta$,${\mathcal{T}}$)$\mid$ |  3 |  4 |  1 |  3 |  2 |  4 |  8 |  2 |  6
Weakened |  sigkdd:Organizator $\sqsubseteq$ sigkdd:Person |  |  |  cmt:Conferen ce_Chair$\sqsubseteq$ sigkdd:Person |  cmt:Conference _Chair$\sqsubseteq$ sigkdd:Organiza tor |  cmt:Program_Committee _Chair$\sqsubseteq$ cmt:Person
$\mid$Sup($\alpha$,${\mathcal{T}}$)$\mid$ |  4 |  4 |  5 |  |  |  4 |  8 |  3 |  7
$\mid$Sub($\beta$,${\mathcal{T}}$)$\mid$ |  13 |  14 |  30 |  |  |  10 |  7 |  16 |  30
completed |  sigkdd:Organizing_ Committee _Member$\sqsubseteq$ sigkdd:Organizator, sigkdd:Organizator $\sqsubseteq$ sigkdd:Person |  |  |  cmt:Conferen ce_Chair$\sqsubseteq$ sigkdd:Person |  cmt:Conference _Chair$\sqsubseteq$ sigkdd:General _Chair |  cmt:Program _Committee _Chair $\sqsubseteq$ cmt:Program _Committee _Member |  cmt:Program _Committee _Chair$\sqsubseteq$ cmt:Program _Committee _Member, cmt:Program _Committee _Chair$\sqsubseteq$ sigkdd: Program _Chair
Table 15: cmt-ekaw Wrong |  cmt:Program _Committee_Chair $\sqsubseteq$ cmt:Program _Committee |  cmt:Program_ Committee$\sqsubseteq$ cmt:Person |  cmt:Conference_Member$\sqsubseteq$ ekaw:OC_Member |  ekaw:Tutorial$\sqsubseteq$ ekaw:Conference
---|---|---|---|---
KB |  KBO/ KBMO |  KBON |  KBO/ KBMO |  KBON |  KBM |  KBMM |  KBON |  KBO/ KBMO |  KBON
$\mid$Sub($\alpha$,${\mathcal{T}}$)$\mid$ |  1 |  1 |  2 |  2 |  2 |  4 |  12 |  1 |  1
$\mid$Sup($\beta$,${\mathcal{T}}$)$\mid$ |  2 |  3 |  1 |  2 |  2 |  4 |  5 |  3 |  7
Weakened |  cmt:Program _Committee_Chair $\sqsubseteq$ cmt:Person |  |  |  cmt:Conference _Member$\sqsubseteq$ ekaw:Person |  cmt:Conference _Member$\sqsubseteq$ ekaw:Conference _Participant |  ekaw:Tutorial$\sqsubseteq$ ekaw:Scientific _Event
$\mid$Sup($\alpha$,${\mathcal{T}}$)$\mid$ |  3 |  4 |  |  |  4 |  5 |  4 |  8
$\mid$Sub($\beta$,${\mathcal{T}}$)$\mid$ |  16 |  35 |  |  |  6 |  22 |  15 |  16
completed |  cmt:Program _Committee_Chair $\sqsubseteq$ cmt:Program _Committee_Chair |  |  |  cmt:Conference _Member$\sqsubseteq$ ekaw:Person |  cmt:Conference _Member$\sqsubseteq$ ekaw:Conference _Participant, ekaw:Conference _Participant$\sqsubseteq$ cmt:Conference _Member |  ekaw:Tutorial$\sqsubseteq$ ekaw:Individual_ Presentation
Table 16: ekaw-iasted Wrong |  ekaw:Tutorial$\sqsubseteq$ ekaw:Conference |  ekaw:Workshop_Chair$\sqsubseteq$ iasted:Session_Chair |  iasted:Final_ manuscript$\sqsubseteq$ iasted: Publication |  iasted:Session_Chair$\sqsubseteq$ ekaw:Workshop_Chair
---|---|---|---|---
KB |  KBO/ KBMO |  KBON |  KBM |  KBMM |  KBON |  KBO/ KBMO |  KBON |  KBM |  KBMM |  KBON
$\mid$Sub($\alpha$,${\mathcal{T}}$)$\mid$ |  1 |  2 |  2 |  2 |  2 |  1 |  1 |  2 |  2 |  2
$\mid$Sup($\beta$,${\mathcal{T}}$)$\mid$ |  3 |  4 |  2 |  4 |  16 |  3 |  3 |  2 |  4 |  16
Weakened |  ekaw:Tutorial$\sqsubseteq$ ekaw:Scientific _Event |  |  ekaw:Work shop_Chair $\sqsubseteq$ iasted:Pers on |  ekaw:Workshop _Chair$\sqsubseteq$ iasted:Delegate |  iasted:Final_ manuscript$\sqsubseteq$ iasted:Item |  |  iasted: Session _Chair$\sqsubseteq$ ekaw:Person |  iasted: Session _Chair$\sqsubseteq$ ekaw: Conference _Participant
$\mid$Sup($\alpha$,${\mathcal{T}}$)$\mid$ |  4 |  12 |  |  4 |  16 |  5 |  6 |  |  4 |  16
$\mid$Sub($\beta$,${\mathcal{T}}$)$\mid$ |  15 |  18 |  |  6 |  24 |  34 |  61 |  |  6 |  13
completed |  ekaw:Tutorial$\sqsubseteq$ ekaw:Individual _Presentation |  |  ekaw:Work shop_Chair $\sqsubseteq$ iasted: Person |  ekaw:Workshop _Chair$\sqsubseteq$ iasted:Iasted_ member |  iasted:Final_ manuscript$\sqsubseteq$ iasted: Submission |  |  iasted: Session _Chair$\sqsubseteq$ ekaw:Person |  iasted: Session _Chair$\sqsubseteq$ ekaw:Session _Chair
Table 17: iasted-sigkdd Wrong |  iasted:Final _manuscript$\sqsubseteq$ iasted:Publication |  iasted:Registration_fee$\sqsubseteq$ sigkdd:Registration_NonMember |  sigkdd:Organizator$\sqsubseteq$ sigkdd:Organizing _Committee_Member
---|---|---|---
KB |  KBO/ KBMO |  KBON |  KBM |  KBMM |  KBON |  KBO/ KBMO |  KBON
$\mid$Sub($\alpha$,${\mathcal{T}}$)$\mid$ |  1 |  1 |  2 |  4 |  9 |  5 |  5
$\mid$Sup($\beta$,${\mathcal{T}}$)$\mid$ |  3 |  3 |  2 |  4 |  9 |  3 |  4
Weakened |  iasted:Final _manuscript$\sqsubseteq$ iasted:Item |  |  iasted:Regis tration_fee$\sqsubseteq$ sigkdd:fee |  iasted:Registra tion_fee$\sqsubseteq$ sigkdd:Registra tion_fee, iasted:Nonmem ber_Registration _fee$\sqsubseteq$ sigkdd:Registra tion_fee_Non _Member |  sigkdd:Organizator$\sqsubseteq$ sigkdd:Person
$\mid$Sup($\alpha$,${\mathcal{T}}$)$\mid$ |  5 |  5 |  |  4 |  12 9 |  4 |  5
$\mid$Sub($\beta$,${\mathcal{T}}$)$\mid$ |  34 |  35 |  |  6 |  9 12 |  13 |  44
completed |  iasted:Final _manuscript$\sqsubseteq$ iasted:Submission |  |  iasted:Regis tration_fee$\sqsubseteq$ sigkdd:fee |  iasted:Nonmember _Registration_fee $=$ sigkdd:Registration _fee_Non_Member, sigkdd:Registration _fee $=$ iasted:Registration _fee |  sigkdd:Organizator$\sqsubseteq$ sigkdd:Person, sigkdd:Organizing _Committee_member$\sqsubseteq$ sigkdd:Organizator