# Prioritized base Debugging in Description Logics

Julien Corman, Nathalie Aussenac-Gilles, Laure Vieu

► To cite this version:

Julien Corman, Nathalie Aussenac-Gilles, Laure Vieu. Prioritized base Debugging in Description Logics. 1st Workshop on Belief Change and Non-Monotonic Reasoning in Ontologies and Databases (ONTOCHANGE 2015) part of JOWO @ IJCAI 2015, Jul 2015, Buenos Aires, Argentina. pp.1-8.
hal-01343042

HAL Id: hal-01343042

https://hal.science/hal-01343042

Submitted on 7 Jul 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Open Archive TOULOUSE Archive Ouverte (OATAO)

OATAO is an open access repository that collects the work of Toulouse researchers and makes it freely available over the web where possible.

This is an author-deposited version published in : http://oatao.univ-toulouse.fr/
Eprints ID : 15368

The contribution was presented at ONTOCHANGE 2015:
http://iaoa.org/jowo/history/2015/workshops15/

**To cite this version** : Corman, Julien and Aussenac-Gilles, Nathalie and Vieu, Laure *Prioritized base Debugging in Description Logics*. (2015) In: 1st Workshop on Belief Change and Non-Monotonic Reasoning in Ontologies and Databases, part of JOWO – The Joint Ontology Workshops co-located with IJCAI 2015 (ONTOCHANGE 2015), 26 July 2015 (Buenos Aires, Argentina).
Prioritized base debugging in Description Logics

Julien Corman

IRIT, University of Toulouse

Nathalie Aussenac-Gilles

CNRS

IRIT, University of Toulouse

Laure Vieu

CNRS

IRIT, University of Toulouse

Abstract

The problem investigated is the identification within an input knowledge base of axioms which should be preferably discarded (or amended) in order to restore consistency, coherence, or get rid of undesired consequences. Most existing strategies for this task in Description Logics rely on conflicts, either computing all minimal conflicts beforehand, or generating conflicts on demand, using diagnosis. The article studies how prioritized base revision can be effectively applied in the former case. The first main contribution is the observation that for each axiom appearing in a minimal conflict, two bases can be obtained for a negligible cost, representing what part of the input knowledge must be preserved if this axiom is discarded or retained respectively, and which may serve as a basis to obtain a semantically motivated preference relation over these axioms. The second main contribution is an algorithm which, assuming this preference relation is known, selects some of the maximal consistent/coherent subsets of the input knowledge base accordingly, without the need to compute all of them.

# 1 Introduction

The focus of this work is the automated or semi-automated debugging of some knowledge base (KB) expressed in the Description Logic (DL) SROIQ (Horrocks et al. 2006), which underlies the OWL 2 W3C recommendation. More exactly, the task considered here consists in suggesting axioms of the input knowledge base which could be discarded in order to restore consistency, coherence, or get rid of some undesired consequence. This is of particular interest for OWL KBs within the Semantic Web framework, where aggregated knowledge issued from different sources with overlapping signatures may have unexpected consequences.

The problem has been studied in the field of knowledge base engineering, as well as belief base revision/contraction<fnref n="1" />, from a different perspective though. In order to account for both, it will be assumed that the user wants to preserve a (consistent) part Θ of the input knowledge, but that Θ may be empty.

As an example, consider the following inconsistent set of statements $K \cup \Theta$,<fnref n="2" /> and assume that $\Theta$ should be preserved :

Ex 1. $K = \{ $

(1) owningCompany(Smithsonian Networks, Smithsonian Institution),

(2) publisher(Birds of South Asia, Smithsonian Institution),

(3) award(James Dewar, Smithsonian Institution),

(4) doctoralAdvisor(Thaddeus S.C. Lowe, Smithsonian Institution),

(5) $\supset \subseteq \forall$award.Award,

(6) $\supset \subseteq \forall$doctoralAdvisor.Person,

(7) $\supset \subseteq \forall$owningCompany.Company,

(8) Company $\sqsubseteq$ Organization }

$$
\Theta = \{ \text{Person } \sqsubseteq \neg \text{Organization,} \\
\qquad \text{Award } \sqsubseteq \neg \text{Organization} \}
$$

An important issue for base debugging is the number of
candidate sets of axioms for removal. Even if the set of re-
maining axioms is required to be maximal (wrt set inclu-
sion), which is intuitive, there are still 7 candidates here, i.e.
one could alternatively discard {1}, {7}, {8}, {3,4}, {3,6},
{4,5} or {5,6} to restore the consistency of K ∪ Θ, while
preserving Θ.

Let $\mathcal{R}_{\subseteq}$ designate the 7 corresponding complements in $K$, i.e. the 7 possible sets of remaining statements. If one refuses to choose arbitrarily one element of $\mathcal{R}_{\subseteq}$, a common solution consists in keeping by default the intersection $\bigcap \mathcal{R}_{\subseteq}$ of all of them, extended with $\Theta$ (or possibly their disjunction $\bigvee \mathcal{R}_{\subseteq}$ extended with $\Theta$, depending on the application, as explained in section 3).

But the output in this case may be quite weak, i.e. result in
an important information loss. In this example for instance,
$\bigcap \mathcal{R}_{\subseteq} = \{2\}$, which is clearly not satisfying. Therefore the
need for a principled way of selecting a subset $\mathcal{R}'$ of $\mathcal{R}_{\subseteq}$
such that $\bigcap \mathcal{R}'$ (resp. $\bigvee \mathcal{R}'$) is stronger that $\bigcap \mathcal{R}_{\subseteq}$ (resp.
$\bigvee \mathcal{R}_{\subseteq}$).

The view adopted here, known as prioritized base revision/debugging, is that some preference relation $\preceq_a$ over the axioms of K should guide the process, trying to discard least preferred axioms first, but still not unnecessarily. Section 4 shows that no solution proposed for DLs to our knowledge satisfies both of these requirements, and section 5 provides an algorithm to do it, assuming the set $\mathcal{M}$ of all minimal

<footnote n="1">¹to be distinguished from *belief set* revision/contraction, which primarily considers (deductively closed) theories</footnote>

<footnote n="2">² K is a set of actual DBPedia statements (Mendes et al. 2012).</footnote>
conflicts within $K \cup \Theta$ is known, as well as $\preceq_a$. Section 6 then proposes a generic approach to obtain a semantically motivated preference relation $\preceq_a$ over $K$, and section 7 discusses possible applications of this strategy. Before that, section 2 introduces some notation, whereas section 3 characterizes the problem, borrowing notions to the fields of KB debugging and belief base revision. Proofs are omitted due to the lack of place, but are all available online at the following url: http://www.irit.fr/~Julien.Corman/index_en.php.

# 2 Notation and conventions

## 2.1 Ordering

If $\preceq$ is a total preorder (transitive, reflexive, but not necessarily antisymmetric) over some finite set $\Delta$, then:

* $\sim$ is the equivalence relation over $\Delta$ induced by $\preceq$.

* $\Delta/\sim$ denotes the quotient set of $\Delta$ by $\sim$.

* $\Delta^\simeq = (\Delta_1^\simeq, \dots, \Delta_n^\simeq)$ is the list of ordered elements of $\Delta/\sim$, such that $1 \le i < j \le n$ iff $\forall \phi \in \Delta_i^\simeq, \forall \phi' \in \Delta_j^\simeq : \phi \not\preceq \phi'$.

If $\preceq$ is a (total or partial) preorder over $\Delta$, then:

* $\min_{\preceq} \Delta$ (resp. $\max_{\preceq} \Delta$) is the set of minimal (resp. maximal) elements of $\Delta$ wrt $\preceq$.

* $\phi_1 < \phi_2$ stands for $\phi_1 \preceq \phi_2$ and $\phi_2 \npreceq \phi_1$.

## 2.2 Description logics

The reader is assumed familiar with the syntax and standard model-theoretic semantics of Description Logics (Baader et al. 2003). $\mathcal{L}$ will designate the DL at hand, and a DL KB is simply a finite set of DL formulas, called axioms.

Logical inconsistency is understood in the usual way, i.e. a set $\Gamma$ of formulas is inconsistent (noted $\Gamma \vdash \bot$) iff it has no model. A slightly different notion used in the DL community is logical incoherence. A set $\Gamma$ of formulas is said to be incoherent iff there is an atomic concept (like “Person” or “Organization”) in its signature such that the interpretation of this concept is empty in every model of $\Gamma$.

# 3 Knowledge base debugging/belief base revision

The problem of discarding axioms of $K$ in order to restore the consistency/coherence of $K \cup \Theta$ (or get rid of undesired consequences of it) has been studied both in the fields of belief base revision/contraction and KB debugging (usually with $\Theta = \emptyset$ in the latter case). In order to avoid possible confusions, belief base revision/contraction should be distinguished from belief set revision/contraction, whose most influential framework (the AGM framework) focuses on (deductively closed) theories, abstracting from the syntax. On the contrary, belief base revision/contraction requires the output to be a syntactic subset of $K \cup \Theta$, adapting several notions from the belief set revision/contraction literature, but with sometimes very different implications.

This syntactic requirement may be viewed as too constraining, because it results in weaker theories than what

could be obtained by considering belief sets. But it is nonetheless required in many practical debugging applications where traceability matters, i.e where identifying faulty axioms is relevant from an engineering point of view, for instance in an OWL KB when axioms have been obtained from different sources. This article exclusively focuses on base revision/debugging, therefore most works in the field of belief set revision for DLs, like (Flouris 2006; Qi and Du 2009; Wang et al. 2010; Ribeiro 2013) fall out of its scope, and will not be reviewed.

A comprehensive series of base revision and contraction operators applicable to Description Logics have been defined in (Ribeiro and Wassermann 2009), and part of the terminology used in this article is borrowed from that work. Precisely, the operations of interest here are named partial meet and kernel base revision without negation (with weak or full success) in (Ribeiro and Wassermann 2009). Due to the lack of place though, a simplified notation will be used, and some limit and/or trivial cases will not be explicitly addressed, in order to focus on the practical problem at hand. In particular, the set of statements $\Theta$ to be preserved is supposed to be consistent.

For the sake of readability still, an important reduction of scope is also made. The need for weakening $K$ may appear when $K \cup \Theta$ is inconsistent, incoherent, or has undesired consequences. Some authors (Qi et al. 2006; Qi et al. 2008) actually distinguish revision wrt inconsistency from revision wrt incoherence, proposing specific algorithms for each task. These distinctions will be ignored here, and the focus put by default on inconsistency, unless explicitly mentioned. But all propositions made in this article can be adapted to the cases of incoherence and undesired consequences, provided minor modifications. It is also assumed that $K \cup \Theta$ is actually inconsistent, otherwise the output of the process is trivially $K \cup \Theta$.

## 3.1 Remainders and selection function

An important notion for base revision/debugging is that of a (base) remainder, which is intuitively an admissible subset of $K \cup \Theta$ maximal wrt set inclusion. Because the focus is on inconsistency here, let $\mathcal{R}$ designate all subsets of $K$ consistent with $\Theta$, i.e.:

**Definition 3.1.** $\mathcal{R} = \{R \subseteq K \mid R \cup \Theta \nvdash \bot\}$

Then the remainder set $\mathcal{R}_\subseteq$ is defined by:<fnref n="3" />

**Definition 3.2.** $\mathcal{R}_\subseteq = \{R \in \mathcal{R} \mid \forall \phi \in (K \setminus R) : R \cup \{\phi\} \notin \mathcal{R}\}$

A remainder is any $R \in \mathcal{R}_\subseteq$. A strong intuition here is that if $R \in \mathcal{R}_\subseteq$, then $R \cup \Theta$ is a candidate output, and discarding any additional axiom can be viewed as an unnecessary information loss, unless there are several elements in $\mathcal{R}_\subseteq$, and no indication as to which one should be preferred. In this last case, according to the fairness principle, the output of the process may be either the in-

<footnote n="3">³$\mathcal{R}_\subseteq$ is actually defined for $K, \Theta$ and $\bot$. But given the lack of ambiguity here, it will only be noted $\mathcal{R}_\subseteq$, without explicit references to $K$ and $\Theta$.</footnote>
tersection $\bigcap(\mathcal{R}_{\subseteq}) \cup \Theta,^4$ or, depending on the engineering constraints, the disjunction $\bigvee_{R \in \mathcal{R}_{\subseteq}} (R \cup \Theta)$ (Meyer et al. 2005).

This last construction is not natively representable in DLs, but can be simulated as a multibase, by requiring that $\text{Cn}(\bigvee_{R \in \mathcal{R}_{\subseteq}} (R \cup \Theta)) = \bigcap_{R \in \mathcal{R}_{\subseteq}} \text{Cn}(R \cup \Theta)$.

Additionally, in order to give up less information, it may be desirable to select some remainders only (or equivalently some elements of $\mathcal{R}_{\subseteq}$), and yield as an output the intersection (or disjunction) of these selected remainders, or even submit them to the user if their number is small enough.

The notion of a selection function, once again adapted from the belief set revision literature, formalizes this idea. In the specific case of an inconsistent $K \cup \Theta$ considered here, a selection function must select a nonempty subset of the remainder set.<fnref n="5" /> Aside from its intuitive appeal, a good argument for the notion of remainder in the context of base revision is the representation theorem given by (Ribeiro and Wassermann 2009). It states that for any selection of a nonempty subset of the remainder set, the operation that takes $K$ and $\Theta$ as an input and yields the intersection of these selected remainders extended with $\Theta$ satisfies a set of very intuitive rationality postulates for base revision (namely inclusion, weak consistency, strong success, pre-expansion and relevance), and conversely.

## 3.2 Prioritized base revision/debugging

Prioritized base revision formalizes the simple idea that all axioms within $K$ are not equal, or in other words, that some preference relation $\preceq_a$ (total preorder, i.e. intuitively a ranking) over the axioms of $K$ is available, such that all other things being equal, if $\phi_1 < \phi_2$, then $\phi_1$ should be preferably discarded when trying to restore the consistency of $K \cup \Theta$. The way $\preceq_a$ may be obtained is discussed in sections 6 and 7.

Assuming $\preceq_a$ is known, prioritized base revision has been characterized by (Nebel 1992) with a total order $\preceq_r$ over $\mathcal{R}$, defined by $R \prec_r R'$ iff there is $1 \le i \le n$ such that :

$$R_i^{\preceq_a} \subset R'_i^{\preceq_a} \text{ and } \forall j \ 1 \le j < i : R_j^{\preceq_a} = R'_j^{\preceq_a}.$$

The following observation (proven in section ??) states that any subbase obtained by performing prioritized revision is actually a remainder, i.e.:

**Proposition 3.1.** $\mathcal{R}_{\preceq_r} \subseteq \mathcal{R}_{\subseteq}$

In other words, each $R \in \mathcal{R}_{\preceq_r}$ is a base remainder for An immediate consequence of proposition 3.1 is that no axiom of $K \setminus \bigcup \mathcal{V}$ needs to be discarded, and therefore it is sufficient for the preference relation $\preceq_a$ introduced in section 3.2 to be defined over $\bigcup \mathcal{J}$ (or equivalently, for some authors, over $K \cup \Theta$, but with $\max_{\preceq_a}(K \cup \Theta) = (K \cup \Theta) \setminus \bigcup \mathcal{J}$).

## 3.3 Conflicts

To our knowledge, most practical attempts in DLs to compute the remainder set, or simply part of it, are based on so-called justifications, also known as MIPS or minimal conflicts, depending on the authors, and on whether $K \cup \Theta$ is inconsistent, incoherent, or has undesired consequences.<fnref n="6" /> A justification will be defined here as an inconsistent subset of $K \cup \Theta$ which is minimal wrt set inclusion. The set $\mathcal{M}$ of all such justifications is sometimes called the kernel for $K \cup \Theta$ and $\perp$ (Ribeiro and Wassermann 2009), defined by :

**Definition 3.3.** $\mathcal{M} = \{M \subseteq (K \cup \Theta) \mid M \vdash \perp \text{ and } \forall M' \subset M : M' \not\vdash \perp\}$

Then the family $\mathcal{J}$ will designate these justifications reduced to their respective intersections with $K$, and which are minimal wrt set inclusion, i.e. :

**Definition 3.4.** $\mathcal{J} = \min_{\subseteq} \{M \cap K \mid M \in \mathcal{M}\}$

As an illustration, in example 1, $\mathcal{J} = \{\{1, 7, 8, 3, 5\}, \{1, 7, 8, 4, 6\}\}$.

Computing $\mathcal{J}$ and $\mathcal{R}_{\subseteq}$ can be viewed as two sides of the same problem. Intuitively, discarding one axiom from each $\mathcal{J} \in \mathcal{J}$ is necessary and sufficient to obtain a subset of $K$ consistent with $\Theta$. Additionally, one would like the set of discarded axioms to be minimal wrt set inclusion among those satisfying this property. More formally, let $\text{hs} : 2^{\mathcal{J}} \to 2^{\mathcal{J}}$ be the function which returns all hitting sets for an input family of sets, i.e. :

**Definition 3.5.** hitting sets
$\text{hs}(\mathcal{X}) = \{\Delta \subseteq \bigcup \mathcal{X} \mid \forall X \in \mathcal{X} : X \cap \Delta \neq \emptyset\}$

A hitting set for $\mathcal{J}$ (i.e. an element of $\text{hs}(\mathcal{J})$) will be called an incision, and a minimal incision iff it is minimal wrt set inclusion among all incisions. Then the following theorem, adapted (among others) from (Qi et al. 2008), defines $\mathcal{R}_{\subseteq}$ wrt $\mathcal{J}$, by stating that each element of $\mathcal{R}_{\subseteq}$ is the complement in $K$ of a minimal incision, and conversely.

**Theorem 3.1.** $R \in \mathcal{R}_{\subseteq}$ iff there is a $D \in \min_{\subseteq}(\text{hs}(\mathcal{J}))$ such that $R = K \setminus D$

For instance, in example 1, $D = \{3, 4\} \in \min_{\subseteq}(\text{hs}(\mathcal{J}))$, so $R = \{1, 2, 5, 6, 7\} \in \mathcal{R}_{\subseteq}$. An immediate consequence is that no axiom of $K \setminus \bigcup \mathcal{J}$ needs to be discarded, and therefore it is sufficient for the preference relation $\preceq_a$ introduced in section 3.2 to be defined over $\bigcup \mathcal{J}$ (or equivalently, for some authors, over $K \cup \Theta$, but with $\max_{\preceq_a}(K \cup \Theta) = (K \cup \Theta) \setminus \bigcup \mathcal{J}$).

An equivalent way of viewing this correspondence between $\mathcal{J}$ and $\mathcal{R}_{\subseteq}$ consists in representing $\mathcal{J}$ as a boolean formula $\tau_{\mathcal{J}}$, expressing the fact that at least one formula in each $\mathcal{J} \in \mathcal{J}$ must be selected for removal. For instance, if $\mathcal{J} = \{\{\phi_1, \phi_2\}, \{\phi_1, \phi_3\}\}, \tau_{\mathcal{J}} = (\phi_1 \lor \phi_2) \land (\phi_1 \lor \phi_3)$. Then the minimal incisions are exactly the prime implicants of $\tau_{\mathcal{J}}$. The converse holds as well, i.e. if $\mathcal{D}$ is the family of all minimal incisions, and if $\rho_{\mathcal{D}} = \bigvee_{D \in \mathcal{D}} (\mathcal{A} \setminus D)$, then $\mathcal{J}$ is the set of all prime implicants of $\rho_{\mathcal{D}}$.

<footnote n="4">⁴This operation should be distinguished from the full meet contraction operation used in the AGM framework, which is the intersection of all maximal subsets of $\text{Cn}(\mathcal{R}_{\subseteq})$ consistent with $\Theta$. In particular, it is not the case in general that $\text{Cn}(\bigcap(\mathcal{R}_{\subseteq}) \cup \Theta) = \text{Cn}(\Theta)$.</footnote>

<footnote n="5">⁵Two additional requirements are made when considering (deductively closed) belief sets, namely that $\gamma$ selects strictly more than one and less than all remainders, but this is generally not relevant for bases.</footnote>

<footnote n="6">⁶Once again, for the sake of readability, only the case of inconsistency is considered here</footnote>
So in theory, any of $|\mathcal{J}|$ and $|\mathcal{R}_{\subseteq}|$ could be at most exponential in the size of each other (but it can be shown that if $n = |\bigcup \mathcal{J}|$, both are bounded by $(\frac{n}{|\subseteq|})$).

Most attempts in DLs to obtain (part of) the remainder set rely on justifications, either by computing the whole kernel beforehand (Qi et al. 2008; Cóbe et al. 2013), or by generating conflicts on demand, using Reiter's hitting set algorithm (Schlobach 2005; Friedrich and Shchekotykhin 2005; Kalyanpur et al. 2006). It should be noted that in the latter case, conflicts do not need to be minimal, but both (Schlobach 2005) and (Friedrich and Shchekotykhin 2005) observed that the computation of minimal conflicts (i.e. justifications), or at least small conflicts, was indeed a more efficient strategy.

A relatively optimistic assumption will be made here, which is also made by several authors (Qi et al. 2008; Ribeiro and Wassermann 2008; Cóbe et al. 2013), namely that the kernel $\mathcal{M}$ (and therefore $\mathcal{J}$ as well) for $K$ and $\Theta$ can actually be computed in a realistic amount of time, for instance using a saturated tableau, like in (Schlobach and Cornet 2003).

But as explained above, obtaining the whole remainder set $\mathcal{R}_{\subseteq}$ out of $\mathcal{J}$ remains intractable. So two problems will be discussed in sections 5 and 6, assuming that $\mathcal{J}$ is known for $K$ and $\Theta$, but not necessarily $\mathcal{R}_{\subseteq}$: how to compute $\mathcal{R}_{\subseteq, \mathcal{J}}$ given a preference relation $\preceq_a$ over $\bigcup \mathcal{J}$, and how to obtain such a preference relation on a semantically grounded basis. But before that, the following section reviews different solutions proposed in the literature in order to deal with the automated selection of axioms of $K$ to be discarded.

# 4 State of the art

A first straightforward strategy to select a subset of $\mathcal{R}_{\subseteq}$ consists in selecting only the set $\mathcal{R}_{\subseteq}$ of elements of $\mathcal{R}$ with maximal cardinality. Obviously, $\mathcal{R}_{\subseteq} \subseteq \mathcal{R}_{\subseteq}$, so for each $R \in \mathcal{R}_{\subseteq}$, $R \cup \Theta$ is indeed a remainder. For DLs, the computation of (some elements of) $\mathcal{R}_{\subseteq}$ has been investigated by (Friedrich and Shchekotykhin 2005) in the case neither $\mathcal{J}$ nor $\mathcal{R}_{\subseteq}$ is known, using Reiter's hitting set algorithm, and by (Qi et al. 2008) in the case $\mathcal{J}$ only is known. But the rationale behind this selection function remains questionable, especially for relatively large datasets: for instance, if $|K| > 1000$, one may arguably wonder why discarding 12 axioms instead of 13 (or even 20) is necessarily preferable. For some real datasets too, (Corman et al. 2015b) observed that this heuristic often failed to discard the expected axioms, or was biased towards the removal of TBox axioms rather than ABox axioms. This is illustrated by example 1, where the best element of $\mathcal{R}_{\subseteq}$ is intuitively $K \setminus \{3, 4\}$, but it is not retained in $\mathcal{R}_{\subseteq}$, because there are 4 subbases in $\mathcal{R}_{\subseteq}$ with strictly higher cardinality (or equivalently, 4 diagnoses in $\mathcal{D}$ with strictly lower cardinality).

As an alternative, the notion of core has been proposed in (Schlobach and Cornet 2003). They define a core of arity $n$ as a set of axioms which appear in $n$ elements of $\mathcal{V}$, the intuition being that an axiom appearing in a core of large arity is more likely to be faulty. Both (Qi et al. 2008) and (Cóbe et al. 2013) implemented this strategy in

the case the whole kernel is already known, by iteratively discarding axioms which appear in the largest number of elements of $\mathcal{J}$ not hit thus far, until consistency is reached. For instance, if $\mathcal{V} = \{\{\phi_1, \phi_2\}, \{\phi_1, \phi_3\}, \{\phi_4, \phi_5\}\}$, then $\phi_1$ will be discarded first, because it appears in 2 elements of $\mathcal{V}$, against only 1 for each other axiom of $\bigcup \mathcal{V}$. Adopting this constraint, the set of minimal incisions in this example would be $\{\{\phi_1, \phi_4\}, \{\phi_1, \phi_5\}\}$. This approach has been criticized by (Friedrich and Shchekotykhin 2005), who showed that an incision $D$ obtained this way is not guaranteed to be minimal wrt cardinality among all incisions, or in other words, that $K \setminus D \notin \mathcal{R}_{\subseteq}$. This should not be a surprise, as this strategy is actually the well-studied greedy algorithm to the (cardinality) minimal hitting set problem, and is known to be an (optimal) approximation. It should also be noted that $K \setminus D$ is not guaranteed to be minimal wrt set inclusion either, as illustrated by this counterexample: $\mathcal{J} = \{\{\phi_1, \phi_2, \phi_3\}, \{\phi_1, \phi_4, \phi_5\}, \{\phi_1, \phi_6, \phi_7\}, \{\phi_2, \phi_4\}, \{\phi_3, \phi_6\}, \{\phi_5, \phi_7\}\}$. No element of $\mathcal{J}$ is a subset of another, so this is a possible configuration. As $\phi_1$ appears in 3 elements of $\mathcal{J}$, its removal will be prioritized, and $D = \{\phi_1, \phi_3, \phi_4, \phi_7\}$ is one of the resulting incisions. But $D \setminus \{\phi_1\}$ is itself an incision, so $D$ is not a minimal incision, or in other words $D \notin \min_{\subseteq}(\text{hs}(\mathcal{J}))$, and therefore $(K \setminus D) \notin \mathcal{R}_{\subseteq}$, i.e. $(K \setminus D) \cup \Theta$ could be extended with $\phi_1$ without compromising consistency. So an additional (polynomial) verification is required, in order to identify the subset(s) of $D$ which are indeed minimal incisions. But whether these minimal incisions are good candidates for removal (or equivalently, whether their respective complements in $K$ should be among the selected remainders) is an open question.

(Qi et al. 2008) also investigated the usage of the kernel in order to perform prioritized base revision, which is the objective pursued in this article. Given a preference relation $\preceq_a$ over $\bigcup \mathcal{J}$, they propose to compute all minimal incisions over the elements of $\mathcal{J}$ reduced to their lower-ranked axioms wrt $\preceq_a$. In other words, if $X_1^{\preceq_a}$ is the equivalence class of lower ranked axioms of $X$ wrt $\preceq_a$, and if $D = \min_{\subseteq}(\text{hs}(\{J_1^{\preceq_a} | J \in \mathcal{J}\}))$, then the procedure selects $\mathcal{R}_m \subseteq R$, defined by $\mathcal{R}_m = \{K \setminus D | D \in \mathcal{D}\}$. Each $R \in \mathcal{R}_m$ is indeed consistent, because all elements of $\mathcal{J}$ are hit, and within each $J$, the removal of axioms with lowest preference has also been prioritized. But once again, $\mathcal{R}_m \subseteq \mathcal{R}_{\subseteq}$ doesn't hold in general, as illustrated by the following example: $\mathcal{J} = \{J, J'\}$, with $J = \{\phi_1, \phi_2\}$, $J' = \{\phi_2, \phi_3\}$, and $\phi_1 \prec_a \phi_2 \prec_a \phi_3$. Then $J_1^{\preceq_a} = \{\phi_1\}$ and $J_1'^{\preceq_a} = \{\phi_2\}$, so the only possible incision is $D = \min_{\subseteq}(\text{hs}(\{J_1^{\preceq_a}, J_1'^{\preceq_a}\})) = \{\phi_1, \phi_2\}$, and therefore $\mathcal{R}_m = \{\{\phi_3\}\}$. But $\{\phi_1, \phi_3\} \cup \Theta \not\models \bot$, so $\phi_1$ has been unnecessarily discarded.

Alternatively, assuming $\mathcal{J}$ is known still, as well as a ranking $\preceq_a$ over $\bigcup \mathcal{J}$ (or a confidence score for each $\phi \in \bigcup \mathcal{J}$), (Kalyanpur et al. 2006) proposed to compute all minimal incisions which maximize the sum of the rankings of axioms to be discarded (or which minimize the sum of their scores). Because the incisions are minimal (wrt set inclu-
sion), the output is this time an actual selection of remainders. But it is easy to show that this procedure does not comply in general to prioritized revision as defined in 3.2.

Another proposal is the so-called lexicographic approach (Benferhat et al. 1993), whose corresponding disjunctive KB can be computed with the disjunctive maxi adjustment procedure (Benferhat et al. 2004) (in the context of propositional logic). If $\leq_a$ is a preference relation over $K \cup \Theta$ (with $\max_{\leq_a}(K \cup \Theta) = (K \cup \Theta) \cup \mathcal{J}$), the procedure yields the set $\mathcal{R}_{\leq_q} = \max_{\leq_q} \mathcal{R}$ of candidate subbases,<fnref n="7" /> with $\leq_q$ a partial order over $\mathcal{R}$ defined by $R \prec_q R'$ iff there is an $i_1 \leq i \leq n$ such that:

$$|R_i^{\leq_a}| < |R_i'^{\leq_a}| \text{ and } \forall j \ 1 \leq j < i : |R_j^{\leq_a}| = |R_j'^{\leq_a}|.$$

In this case too, the output is (the disjunction of) a selection of remainders, or in other words:

**Proposition 4.1.** $\mathcal{R}_{\leq_q} \subseteq \mathcal{R}_{\leq}$

But this option is not completely satisfying either, because it is based on cardinality just like $\mathcal{R}_{\leq}$ above (actually, $\mathcal{R}_{\leq}$ is a specific case of $\mathcal{R}_{\leq_q}$, where $\leq_a$ defines only two equivalence classes, namely $\bigcup \mathcal{J}$ and $(K \cup \Theta) \setminus \bigcup \mathcal{J}$), therefore yielding the same criticism.

# 5 Algorithm for prioritized base revision

Given a preference relation $\leq_a$ over $\bigcup \mathcal{J}$, and assuming $\mathcal{J}$ is known, but not necessarily $\mathcal{R}_{\leq}$, this section provides an algorithm to perform prioritized revision as defined in section 3, i.e. it yields the set $\mathcal{R}_{\leq_r} \subseteq \mathcal{R}_{\leq}$, without the need to compute the whole of $\mathcal{R}_{\leq}$ (unless $\mathcal{R}_{\leq_r} = \mathcal{R}_{\leq}$). The procedure itself is just an improvement over the computation of $\mathcal{R}_{\leq}$ out of $\mathcal{J}$, taking advantage of $\leq_a$. As explained in section 3.3, obtaining $\mathcal{R}_{\leq}$ out of $\mathcal{J}$ amounts to computing $\min_{\leq} \text{hs}(\mathcal{J})$, i.e. all minimal incisions for $\mathcal{J}$, which is a well studied problem.<fnref n="8" /> It is therefore assumed that some procedure to solve this problem is available (prototypically a search tree), which for any finite family of finite sets $\mathcal{X}$ returns $\min_{\leq} \text{hs}(\mathcal{X})$.

Some definitions will be useful. Let hit: $2^{2^c} \times \mathcal{L}^2 \mapsto 2^{2^c}$ be defined by:

**Definition 5.1.** hit($\mathcal{X}$, $Y$) = $\{X \in \mathcal{X} | X \cap Y \neq \emptyset\}$

If $\mathcal{X} \subseteq 2^c$, and $\leq_x$ is a total preorder over $\bigcup \mathcal{X}$, let $(\bigcup \mathcal{X})^{\leq_x} = ((\bigcup \mathcal{X})^{\leq_x})_{1/2}^c, \dots, ((\bigcup \mathcal{X})^{\leq_x})_{n/2}^c$, and $1 \leq i \leq n$. Then the function pHit: $2^{2^c} \times \mathcal{L}^2 \times n \mapsto 2^{2^c}$ is defined by:

**Definition 5.2.** pHit($\mathcal{X}$, $\leq_x$, $i$) = $\{X \in \mathcal{X} | X \in \text{hit}(\mathcal{X}, (\bigcup \mathcal{X})^{\leq_x}) \text{ and } \forall 1 \leq j < i : X \notin \text{hit}((\bigcup \mathcal{X})^{\leq_j})\}$

In particular, if $(\bigcup \mathcal{J})^{\leq_a} = ((\bigcup \mathcal{J})_{1/2}^{\leq_a}, \dots, (\bigcup \mathcal{J})_{n/2}^{\leq_a})$, then pHit($\mathcal{J}$, $\leq_a$, $i$) returns the elements of $\mathcal{J}$ which are hit by $(\bigcup \mathcal{J})_{i/2}^{\leq_a}$, but not by any lower-ranked equivalence class of $(\bigcup \mathcal{J})^{\leq_a}$.

The following observation gives the rationale behind algorithm 1:

**Proposition 5.1.** $R \in \mathcal{R}_{\leq_r}$ iff $R \subseteq K$ and $K \setminus R = D$, with $\forall i_1 \leq i \leq n : D_i^{\leq_a} \in \min_{\leq} \text{hs}(\text{pHit}(\mathcal{J}, \leq_a, i) \setminus (\text{hit}(\mathcal{J}, \bigcup_{1 \leq j < i} D_j^{\leq_a})))$

In other words, starting with the equivalence class $(\bigcup \mathcal{J})^{\leq_n}$ of highest ranked axioms of $\bigcup \mathcal{J}$, the axioms discarded from each equivalence class $(\bigcup \mathcal{J})_{i/2}^{\leq}$ must form a minimal hitting set for all elements of $\mathcal{J}$ not hit thus far, and which cannot be hit by any strictly lower ranked axiom.

Let hitInt: $2^c \times 2^{2^c} \mapsto 2^{2^c}$ be the function which reduces the sets of an input family $\mathcal{X}$ to their respective intersections with an input set $\Delta$, i.e.:

**Definition 5.3.** hitInt($\Delta$, $\mathcal{X}$) = $\{X \cap \Delta | X \in \mathcal{X}\}$

Then the following algorithm yields $\mathcal{R}_{\leq_r}$:

**Algorithm 1** Prioritized base revision with known kernel

1: $D \leftarrow \emptyset$

2: **for** $i \leftarrow n$ **to** 1 **do**

3: &nbsp;&nbsp;&nbsp;&nbsp;D' $\leftarrow \emptyset$

4: &nbsp;&nbsp;&nbsp;&nbsp;PH $\leftarrow$ pHit($\mathcal{J}$, $\leq_a$, $i$)

5: **for all** $D \in D$ **do**

6: &nbsp;&nbsp;&nbsp;&nbsp;J' $\leftarrow$ hitInt((\bigcup \mathcal{J})_{i/2}^{\leq_a}$, PH $\setminus$ hit($\mathcal{J}$, D))

7: **for all** $H \in \min_{\leq} \text{hs}(\mathcal{J}')$ **do**

8: &nbsp;&nbsp;&nbsp;&nbsp;D' $\leftarrow$ D' $\cup$ $\{D \cup H\}$

9: **end for**

10: **end for**

11: &nbsp;&nbsp;&nbsp;&nbsp;D $\leftarrow$ D'

12: **end for**

13: $\mathcal{R}_{\leq_r}$ $\leftarrow$ $\emptyset$

14: **for all** $D \in D$ **do**

15: &nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{R}_{\leq_r}$ $\leftarrow$ $\mathcal{R}_{\leq_r} \cup \{K \setminus D\}$

16: **end for**

The family $D$ is the set of minimal incisions under construction, and the family $D'$ is just a temporary variable to avoid concurrent modification of $D$. The main loop (line 2) iterates over all equivalence classes defined by $\leq_a$, starting with the best ranked equivalence class, i.e. $(\bigcup \mathcal{J})_{n/2}^{\leq_a}$. Line 4, PH is the set of all elements of $\mathcal{J}$ hit by the current equivalence class $(\bigcup \mathcal{J})_{i/2}^{\leq_a}$, and not by any lower ranked equivalence class. Line 5 starts an iteration over all incisions under construction. For each of these incisions $D$, line 6, PH $\setminus$ hit($\mathcal{J}$, $D$) is the set of elements of $\mathcal{J}$ hit by the current equivalence class, by no lower ranked equivalence class, and not hit by $D$ yet. Then $\mathcal{J}'$ (temporarily) contains these, but reduced to their respective intersections with the current equivalence class. The minimal hitting set procedure $\min_{\leq} \text{hs}$ is called line 7, and for each returned minimal hitting set $H$ for $\mathcal{J}'$, $D \cup H$ is a possibly new minimal incision under construction. Finally, line 13 to 16, each $R \in \mathcal{R}_{\leq_r}$ is

<footnote n="7">⁷or a single base equivalent to the disjunction of these subbases in the case of disjunctive maxi adjustment.</footnote>

<footnote n="8">⁸ To avoid confusions, the problem considered here, i.e. obtaining $\min_{\leq} \text{hs}(\mathcal{J})$, differs from the canonical minimal hitting set problem (NP-complete in the size of $\mathcal{J}$), which consists in computing one hitting set minimal wrt cardinality, whereas $\min_{\leq} \text{hs}(\mathcal{J})$ is the set of all hitting sets minimal wrt inclusion. In particular, the decision problem for $\min_{\leq} \text{hs}(\mathcal{J})$ is not polynomial anymore, because $\min_{\leq} \text{hs}(\mathcal{J})$ is exponential in $|\mathcal{J}|$ in the worst case.</footnote>
obtained as the complement in $K$ of some minimal incision $D \in \mathcal{D}$.

In the limit case where all equivalence classes hit distinct elements of $\bigcup \mathcal{J}$, i.e. where all $\mathrm{hit}(\mathcal{J}, (\bigcup \mathcal{J})_{i}^{\le a})$ are mutually disjoint for $1 \le i \le n$ (note that $n=1$ is a particular subcase), computing $\mathcal{R}_{\le r}$ amounts to computing $\mathcal{R}_{\subseteq}$. But in other cases, computing $\mathcal{R}_{\le r}$ with algorithm 1 is strictly less expensive than computing $\mathcal{R}_{\subseteq}$. To see this, consider the worst possible scenario, where all elements of $\mathcal{J}$ are mutually disjoint, with $m = |\mathcal{J}|$, and for simplicity, let us assume that they all have the same cardinality $k$. Then $|\mathcal{R}_{\subseteq}| = k^m$. But if $f_i = \max_{J \in \mathrm{pHit}(\mathcal{J}, \le a, i)} |J \cap (\bigcup \mathcal{J})_i^{\le a}|$ and $q_i = |\mathrm{pHit}(\mathcal{J}, \le a, i)|$, then inside each equivalence class $(\bigcup \mathcal{J})_i^{\le a}$, the number of incisions to compute is at most $(f_i)^{q_i}$. Then by hypothesis, for some $1 \le j < l \le n$, $\mathrm{hit}(\mathcal{J}, (\bigcup \mathcal{J})_j^{\le a})$ and $\mathrm{hit}(\mathcal{J}, (\bigcup \mathcal{J})_l^{\le a})$ overlap, therefore not only $f_l < k$, but more importantly, $\sum_{i=1}^n q_i < m$. Therefore the total number of minimal incisions computed during the execution is:

$$|\mathcal{D}| \le \prod_{i=1}^{n} (f_i)^{q_i} < \prod_{i=1}^{n} (k)^{q_i} = (k)^{\sum_{i=1}^{n} q_i} < k^m.$$

An additional (exponential) gain may come line 6 from the fact that reducing the elements of $\mathrm{pHit}(\mathcal{J}, \le a, i) \setminus \mathrm{hit}(\mathcal{J}, D)$ to their respective intersections with $(\bigcup \mathcal{J})_i^{\le a}$ can also reduce their overall number. Finally, for each $i$ from $n$ to 1, the hitting set tree procedure is called once per hitting set computed thus far, i.e. $|\mathcal{D}|$ times, which may turn out to be costly. Observing that the set $PH \setminus \mathrm{hit}(\mathcal{J}, D)$ may be identical for multiple $D \in \mathcal{D}$, a simple optimization consists in keeping track of the hitting sets computed for each $D$, which guarantees that the number of calls to the hitting set tree procedure line 7 is bounded by the smallest value between $|\mathcal{D}|$ and $2^{\mathrm{hitInt}((\bigcup \mathcal{J})_i^{\le a}, PH))}$.

# 6 Obtaining a preference relation $\leq_a$ over axioms

In the previous sections, it has been assumed that a preference relation $\leq_a$ over the axioms of $\bigcup \mathcal{J}$ (i.e. a ranking of these axioms) was available, and the efforts have been centered on the computation of $R_{\le r}$, guided by this relation. This assumption is often made in works dealing with prioritized base revision, where $\leq_a$ is supposed to be obtained from external confidence scores for axioms, or from a manual review of these axioms. Syntactic criteria have also been proposed to define $\leq_a$, for instance favoring TBox over ABox axioms (or the opposite), favoring axioms whose signatures contain elements with more syntactic occurrences within $K \cup \Theta$, or penalizing axioms based on some syntactic patterns (frequent modeling errors) ... For consistent but incoherent KBs, (Kalyanpur et al. 2006) also used as a ranking criterion the number of consequences of a given syntactic form which would be necessarily lost if an axiom $\phi$ was discarded. This section follows this last intuition, although it does not provide a specific $\leq_a$ (possible concrete preference relations are discussed in section 7). Instead, it

shows that if the kernel is known, for each uncertain axiom $\phi \in \bigcup \mathcal{J}$, two subbases of $K \cup \Theta$ can be computed in polynomial time, which respectively reflect what retaining or discarding $\phi$ necessarily implies.

The intuition is simple, and can be summarized with only two questions. Let $\phi \in \bigcup \mathcal{J}$, i.e. $\phi$ is involved in the inconsistency of $K \cup \Theta$ but is not part of $\Theta$, and is therefore a candidate for removal. The first question one may ask is, if $\phi$ was retained, which part of the initial base $K \cup \Theta$ would necessarily be retained with it. Let $S_\phi$ be the set of all remainders which contain $\phi$, i.e.:

$$\textbf{Definition 6.1.} \quad S_{\phi} = \{R \in \mathcal{R}_{\subseteq} | \phi \in R\} \cup \Theta$$

Then the knowledge necessarily retained together with $\phi$ can be conveniently represented by $\cap S_\phi$. Whatever the selected remainders are, if they contain $\phi$, then the output of the process is guaranteed to be at least as strong as $\cap S_\phi$. Or in other words, if one adheres to the assumption made throughout this article that all selected subbases should be maximal wrt to set-inclusion, and if additionally one would like to retain $\phi$, then $\cap S_\phi$ must be retained as well. In particular, some properties of $\cap S_\phi$ considered as a theory (i.e. $\mathrm{Cn}(\cap S_\phi)$) may be exploited to obtain a score or ranking for $\phi$, setting a basis for a semantically grounded computation of $\leq_a$ (note that because all elements of $S_\phi$ are remainders, they are also consistent, so $\cap S_\phi$ is consistent as well).

A first legitimate objection to this proposition can be made, which is intuitively that $\cap S_\phi$ as a theory does not fully reflect the impact of $\phi$ within $K \cup \Theta$. In particular, it misses consequences of some elements of $S_\phi$. Arguably, if all elements of $S_\phi$ could be studied individually, this would provide a much more accurate understanding of the impact of $\phi$. But if all $S_\phi$ were known for all $\phi$, then the whole remainder set would be known as well, and it was assumed in section 3.3 that this is not necessarily the case. And even if the whole remainder was known, evaluating all remainders independently as theories can be simply prohibitive : if $n = |\bigcup \mathcal{J}|$, there are at most $\binom{n}{2}$ of them, whereas there is obviously just one $\cap S_\phi$ for each $\phi$, i.e. $n$ of them. Actually, if the complete remainder set could be computed, and if its cardinality was reasonable as well, there would be reason to perform prioritized base revision in the first place. So $\cap S_\phi$ should be viewed as a convenient computational compromise, altogether semantically motivated and easy to obtain if $\mathcal{J}$ is already known, as will be shown below.

A case could also be made for considering the disjunctive KB $\bigvee S_\phi$ (defined in section 3.1) instead of $\cap S_\phi$ for this purpose. Arguably, $\bigvee S_\phi$ is a better representation of the knowledge being retained together with $\phi$. But because disjunctive KBs cannot be natively represented in most DLs, $\bigvee S_\phi$ must be manipulated as a family of KBs, namely $S_\phi$ (and the corresponding theory is set to be $\cap_{\Delta \in S_\phi} \mathrm{Cn}(\Delta)$),

which leads back to the previous objection.

A second base can also be computed to answer a second dual question, which is what part of the input KB would necessarily remain if $\phi$ was discarded. This base is $\cap S_{\phi}$, with $S_{\phi}$ defined by:

$$\textbf{Definition 6.2.} \quad S_{\phi} = \{R \in \mathcal{R}_{\subseteq} | \phi \notin R\} \cup \Theta$$
This gives two KBs $\bigcap S_{\phi}$ and $\bigcap S_{\setminus \phi}$ for each uncertain axiom $\phi \in \bigcup \mathcal{J}$, i.e. $2^*|\bigcup \mathcal{J}|$ KBs in total, which can serve as a basis to evaluate the axioms of $\bigcup \mathcal{J}$, and eventually compute the preference relation $\preceq_a$.

If $\mathcal{R} \subseteq$ is known, obtaining $\bigcap S_{\phi}$ and $\bigcap S_{\setminus \phi}$ is trivial from their definitions. But a more interesting observation is that even if only $\mathcal{J}$ is known, and not $\mathcal{R} \subseteq$, then the intersections $\bigcap S_{\phi}$ and $\bigcap S_{\setminus \phi}$ can still be obtained in time polynomial in the size of $\mathcal{J}$, without the need to compute $S_{\phi}$ and $S_{\setminus \phi}$.

A few additional definitions are useful. $K_s$ will designate the “safe” part of $K$, i.e. the axioms of $K$ which are not involved in the inconsistency of $K \cup \Theta$, or equivalently, which do not appear in any element of $\mathcal{J}$.

**Definition 6.3.** $K_s = K \setminus \bigcup \mathcal{J}$

Finally, given a family of sets $\mathcal{X}$, and two elements $x_1$ and $x_2$, the function hitDiff : $2^{2^L} \times L \times L \mapsto 2^{2^L}$ returns the elements of $\mathcal{X}$ to which $x_1$ belongs, but not $x_2$, i.e. :

**Definition 6.4.** hitDiff($\mathcal{X}$, $x_1$, $x_2$) = hit($\mathcal{X}$, {$x_1$}) \setminus hit($\mathcal{X}$, {$x_2$})

Then the two following equalities give two straightforward procedures to compute $\bigcap S_{\phi}$ and $\bigcap S_{\setminus \phi}$ for each $\phi \in \bigcup \mathcal{J}$, provided $\mathcal{J}$ is known :<fnref n="9" />

**Proposition 6.1.** Let $\phi \in \bigcup \mathcal{J}$.
If {$\phi$} $\cup$ $\Theta \vdash \bot$, then $\bigcap S_{\phi} = \emptyset$.
Otherwise, $\bigcap S_{\phi} = K_s \cup \{\phi\} \cup \Theta \cup \{\psi \in \bigcup \mathcal{J} \setminus \bigcup \text{hit}(\mathcal{J}, \{\phi\}) | \forall J_1 \in \text{hit}(\mathcal{J}, \{\psi\}), \exists J_2 \in \text{hit}(\mathcal{J}, \{\phi\}) : J_2 \setminus \{\phi\} \subseteq J_1\}$

The first precaution is just a limit case, where no remainder contains $\phi$. Otherwise, trivially, $K_s \cup \{\phi\} \cup \Theta \subseteq \bigcap S_{\phi}$. Then given any other $\psi \in \bigcup \mathcal{J}$ which does not appear in an element of $\mathcal{J}$ hit by $\{\phi\}$, in order to decide whether $\psi \in \bigcap S_{\phi}$, it is sufficient to check for each element $J_1$ of $\mathcal{J}$ which contains $\psi$ if there is another element $J_2$ of $\mathcal{J}$ which contains $\phi$, and such that $J_2 \setminus \{\phi\} \subseteq J_1$. Such a verification remains polynomial in $|\mathcal{J}|$.

**Proposition 6.2.** Let $\phi \in \bigcup \mathcal{J}$.
Then $\bigcap S_{\phi} = K_s \cup \Theta \cup \{\psi \in ((\bigcup \mathcal{J}) \setminus \{\phi\}) | \text{ if hitDiff}(\mathcal{J}, \psi, \phi) \neq \emptyset \text{ and hitDiff}(\mathcal{J}, \phi, \psi) \neq \emptyset, \text{ then } \forall J_1 \in \text{hitDiff}(\mathcal{J}, \psi, \phi), \forall J_2 \in \text{hitDiff}(\mathcal{J}, \phi, \psi) : ((J_1 \cup J_2) \setminus \{\phi, \psi\}) \cup \Theta \vdash \bot \} $

Again, trivially, $K_s \cup \Theta \subseteq \bigcap S_{\setminus \phi}$. Then any $\psi \neq \phi$ such that $\psi \in \bigcup \mathcal{J}$ and either hit($\mathcal{J}$, {$\phi$}) $\subseteq$ hit($\mathcal{J}$, {$\psi$}) or hit($\mathcal{J}$, {$\psi$}) $\subseteq$ hit($\mathcal{J}$, {$\phi$}) will be retained as well. Otherwise, for $\psi$ to be retained, for each element $J_1$ only hit by {$\psi$}, for each element $J_2$ only hit by {$\phi$}, (($J_1 \cup J_2$) \ {$\phi, \psi$}) $\cup$ $\Theta \vdash \bot$ must hold. This very last condition may suggest a consistency check, but it is actually not required. Because $\mathcal{J}$ is known, it is sufficient instead to check whether there is a $J_3 \in \mathcal{J}$ such that $J_3 \subseteq ((J_1 \cup J_2) \setminus \{\phi, \psi\})$.

## 7 Applications

As explained in the previous section, this article does not define a unique preference relation $\preceq_a$ over the set $\bigcup \mathcal{J}$ of

potentially undesired axioms, but instead provides a way to compute two bases $\bigcap S_{\phi}$ and $\bigcap S_{\setminus \phi}$ for each $\phi$, which respectively reflect the impact of retaining or discarding $\phi$. A wide array of existing strategies to evaluate the quality of a KB on a semantic basis can then be used to evaluate $\bigcap S_{\phi}$ and $\bigcap S_{\setminus \phi}$, and rank all $\phi \in \bigcup \mathcal{J}$ accordingly. This section only lists a few of them.

From an engineering perspective, a traditional approach to evaluate a knowledge base is through requirements or so-called *competency questions* (Pinto and Martins 2004), which can generally be viewed as a set $\Psi$ of statements the KB should entail (or sometimes not entail) for a given application. Let us assume that a base debugging algorithm, whichever it is (for instance the one proposed in section 5), produces as an output some selection of remainders (or their intersection, or their disjunction). And let $\Psi_{\phi}^{+} = \Psi \cap \text{Cn}(\bigcap S_{\phi})$. Then $\psi \in \Psi_{\phi}^{+}$ iff $\psi$ is guaranteed to be a consequence of any output KB containing $\phi$. In other words, if $\phi$ is retained, then the requirements in $\Psi_{\phi}^{+}$ will all necessarily be met, and there is no other requirement in $\Psi$ for which this is guaranteed. Similarly, if $\Psi_{\phi}^{-} = \Psi \cap \text{Cn}(\bigcap S_{\setminus \phi})$, then $\psi \in \Psi_{\phi}^{-}$ iff $\psi$ is guaranteed to be entailed by any output KB which does not contain $\phi$. So $\preceq_a$ may be computed on this simple basis, depending on the importance given to the respective requirements in $\Psi$. The main limitation here is that it cannot be guaranteed that some requirement $\psi$ will not be met if $\phi$ is retained (resp. discarded).

As an alternative, the evaluation of $\bigcap S_{\phi}$ (resp. $\bigcap S_{\setminus \phi}$) may be based on the complete derivation of some syntactically defined subset of $\text{Cn}(\bigcap S_{\phi})$ (resp. $\text{Cn}(\bigcap S_{\setminus \phi})$). This has been experimented by (Kalyanpur et al. 2006; Cóbé et al. 2013) or (Corman et al. 2015a).

But more theoretically motivated approaches are conceivable as well. In particular, model-theoretic distances used for belief set revision (Qi et al. 2006; Qi and Du 2009) or update (Liu et al. 2006) may be used here to obtain $\preceq_a$, considering for each $\phi \in \bigcup \mathcal{J}$ the distance between the set of models of $K$ and the set of models of $\bigcap S_{\phi}$ (resp. $\bigcap S_{\setminus \phi}$).

## 8 Conclusion

This article investigates the applicability of prioritized base revision/debugging in Description Logics, requiring that the output be a selection of base remainders, and that this selection be independent from the cardinality of these remainders. It is shown that propositions made in the literature do not satisfy both these requirements, and an effective algorithm for this task is provided, assuming the kernel is known.

The second main contribution concerns the prior computation of a preference relation $\preceq_a$ over the axioms of the input base, which is necessary for prioritized base revision/debugging. Assuming once again that the kernel is known, it is shown that for each candidate axiom $\phi$ for removal, two bases $\bigcap S_{\phi}$ and $\bigcap S_{\setminus \phi}$ can immediately be obtained, which respectively represent what part of the initial knowledge will necessarily be preserved if $\phi$ is retained or discarded, allowing the computation of $\preceq_a$ on a semantic basis, thus offering a good compromise between computational and more theoretical requirements.

<footnote n="9">⁹Again, all proofs are available at the abovementioned url.</footnote>
An interesting continuation of this work would be to determine whether and/or to what extent the computation of the whole kernel beforehand could be avoided, for both tasks, i.e. obtaining $\bigcap S_{\phi}$ and $\bigcap S_{\setminus \phi}$ on the one hand, and debugging on the other hand.

## References

[Baader et al. 2003] Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, and Peter Patel-Schneider. *The description logic handbook: theory, implementation and applications*. Cambridge university press, 2003.

[Benferhat et al. 1993] Salem Benferhat, Claudette Cayrol, Didier Dubois, Jerome Lang, and Henri Prade. Inconsistency management and prioritized syntax-based entailment. In *IJCAI proceedings*, 1993.

[Benferhat et al. 2004] Salem Benferhat, Souhila Kaci, Daniel Le Berre, and Mary-Anne Williams. Weakening conflicting information for iterated revision and knowledge integration. *Artificial Intelligence*, 153(1), 2004.

[Corman et al. 2015a] Julien Corman, Nathalie Aussenac-Gilles, and Laure Vieu. Distributional semantics for ontology verification. In *StarSem proceedings*, 2015.

[Corman et al. 2015b] Julien Corman, Laure Vieu, and Nathalie Aussenac-Gilles. Ontological analysis for practical knowledge base debugging in Description Logics. In *CommonSense proceedings*, 2015.

[Cóbe et al. 2013] Raphael Cóbe, Fillipe Resina, and Renata Wassermann. Merging Ontologies via Kernel Contraction. *ONTOBRAS proceedings*, pages 94–105, 2013.

[Flouris 2006] Giorgos Flouris. *On Belief Change and Ontology Evolution*. PhD thesis, University of Crete, 2006.

[Friedrich and Shchekotykhin 2005] Gerhard Friedrich and Kostyantyn Shchekotykhin. A general diagnosis method for ontologies. In *ISWC proceedings*, 2005.

[Horrocks et al. 2006] Ian Horrocks, Oliver Kutz, and Ulrike Sattler. The Even More Irresistible SROIQ. *KR proceedings*, 2006.

[Kalyanpur et al. 2006] Aditya Kalyanpur, Bijan Parsia, Evren Sirin, and Bernardo Cuenca-Grau. Repairing unsatisfiable concepts in OWL ontologies. In *ESWC proceedings*, 2006.

[Liu et al. 2006] Hongkai Liu, Carsten Lutz, Maja Milicic, and Frank Wolter. Updating Description Logic ABoxes. In *KR proceedings*, 2006.

[Mendes et al. 2012] Pablo N Mendes, Max Jakob, and Christian Bizer. DBpedia: A Multilingual Cross-domain Knowledge Base. In *LREC proceedings*, 2012.

[Meyer et al. 2005] Thomas Meyer, Kevin Lee, and Richard Booth. Knowledge integration for description logics. In *AAAI proceedings*, 2005.

[Nebel 1992] Bernhard Nebel. Syntax-based approaches to belief revision. *Belief revision*, 29:52–88, 1992.

[Pinto and Martins 2004] Helena Sofia Pinto and João P Martins. Ontologies: How can they be built? *Knowledge and Information Systems*, 6(4):441–464, 2004.

[Qi and Du 2009] Guilin Qi and Jianfeng Du. Model-based Revision Operators for Terminologies in Description Logics. In *IJCAI proceedings*, 2009.

[Qi et al. 2006] Guilin Qi, Weiru Liu, and David Bell. A revision-based approach to handling inconsistency in description logics. *Artificial Intelligence Review*, 26(1-2), 2006.

[Qi et al. 2008] Guilin Qi, Peter Haase, Zhisheng Huang, Qiu Ji, Jeff Z Pan, and Johanna Völker. A kernel revision operator for terminologies - algorithms and evaluation. In *ISWC proceedings*, 2008.

[Ribeiro and Wassermann 2008] Márcio Moretto Ribeiro and Renata Wassermann. The Ontology Reviser Plug-In for Protégé. In *WONTO proceedings*, 2008.

[Ribeiro and Wassermann 2009] Márcio M Ribeiro and Renata Wassermann. Base revision for ontology debugging. *Journal of Logic and Computation*, 19(5), 2009.

[Ribeiro 2013] Márcio Moretto Ribeiro. *Belief revision in non-classical logics*. Springer, 2013.

[Schlobach and Cornet 2003] Stefan Schlobach and Ronald Cornet. Non-standard reasoning services for the debugging of description logic terminologies. In *IJCAI proceedings*, 2003.

[Schlobach 2005] Stefan Schlobach. Diagnosing terminologies. In *AAAI proceedings*, 2005.

[Wang et al. 2010] Zhe Wang, Kewen Wang, and Rodney W Topor. A New Approach to Knowledge Base Revision in DL-Lite. In *AAAI proceedings*, 2010.