# On the Computation of a Productive Partially Ordered
Possibilistic Repair

Ahmed Laouar, Sihem Belabbes, Salem Benferhat

► To cite this version:

Ahmed Laouar, Sihem Belabbes, Salem Benferhat. On the Computation of a Productive Partially Ordered Possibilistic Repair. DL 2024: 37th International Workshop on Description Logics, Ana Ozaki; Laura Giordano; Jean Christoph Jung, Jun 2024, Bergen, Norway. hal-04622237

HAL Id: hal-04622237

https://univ-artois.hal.science/hal-04622237

Submitted on 24 Jun 2024

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
# On the Computation of a Productive Partially Ordered Possibilistic Repair

Ahmed Laouar, Sihem Belabbes, Salem Benferhat

► To cite this version:

Ahmed Laouar, Sihem Belabbes, Salem Benferhat. On the Computation of a Productive Partially Ordered Possibilistic Repair. DL 2024: 37th International Workshop on Description Logics, Ana Ozaki; Laura Giordano; Jean Christoph Jung, Jun 2024, Bergen, Norway. hal-04622237v3

HAL Id: hal-04622237

https://univ-artois.hal.science/hal-04622237v3

Submitted on 26 Aug 2024

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
# On the Computation of a Productive Partially Ordered Possibilistic Repair

Ahmed Laouar<fnref n="1" />, Sihem Belabbes<fnref n="2" /> and Salem Benferhat<fnref n="1" />

**Abstract**

We deal with repairing inconsistent partially ordered lightweight ontologies in the possibilistic setting. More specifically, we consider the closure-based $C_π$-repair method, which yields a more productive partially ordered possibilistic repair and is tractable in DL-Lite$_R$. In this work, we refine the characterization of the $C_π$-repair method and propose an equivalent algorithm that is more efficient. We illustrate our findings with an experimental analysis. In particular, we highlight the main situations in which the $C_π$-repair method achieves the best performance both in terms of productivity and computational cost.

**Keywords**

Lightweight Ontologies, Inconsistency, Partial orders, Data repairs

## 1. Introduction

Reasoning with inconsistent lightweight ontologies commonly consists in evaluating queries over the repairs of the ABox, defined as maximal subsets of the ABox that are consistent with respect to the TBox. Inconsistency-tolerant semantics are strategies for selecting which repairs to query in order to derive valid conclusions from an inconsistent ontology. Some of the most prominent semantics have been implemented in reasoning systems. For example, the CQAPri system (Consistent Query Answering with Priorities) [1] resolves conjunctive queries in DL-Lite$_R$ ontologies over the repairs of the ABox. It returns as valid conclusions the query answers that follow: from every repair under the ABox Repair (AR) semantics [2], from the intersection of all the repairs under the Intersection of ABox Repair (IAR) semantics [2], and from any repair under the brave semantics [3]. Another example is the QuID system [4] which implements conjunctive query answering under the IAR semantics in ontologies specified in DL-Lite$_A$.

The issue of inconsistency management in DL-Lite$_R$ has been investigated for both totally ordered ontologies [1, 5] and partially ordered ontologies [6]. Some other methods focus on a preference relation defined only over minimal inconsistent subsets of the ABox. The issue was first investigated in prioritized databases [7] and then adapted to DL-Lite in [8]. Besides, inconsistency has been considered within the framework of possibility theory. One can cite the method for computing a totally ordered possibilistic repair [9], which infers all the assertions that are strictly more certain than the first assertion that makes the ABox inconsistent. The

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

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

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

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

<footnote n="1">¹CRIL, Univ. Artois & CNRS, UMR 8188, Lens, 62300, France</footnote>

<footnote n="2">²LIASD, IUT de Montreuil, Univ. Paris 8, Saint-Denis, 93200, France</footnote>
# On the Computation of a Productive Partially Ordered Possibilistic Repair

Ahmed Laouar<fnref n="1" />, Sihem Belabbes<fnref n="2" /> and Salem Benferhat<fnref n="1" />

**Abstract**

We deal with repairing inconsistent partially ordered lightweight ontologies in the possibilistic setting. More specifically, we consider the closure-based $C_π$-repair method, which yields a more productive partially ordered possibilistic repair and is tractable in DL-Lite$_R$. In this work, we refine the characterization of the $C_π$-repair method and propose an equivalent algorithm that is more efficient. We illustrate our findings with an experimental analysis. In particular, we highlight the main situations in which the $C_π$-repair method achieves the best performance both in terms of productivity and computational cost.

**Keywords**

Lightweight Ontologies, Inconsistency, Partial orders, Data repairs

## 1. Introduction

Reasoning with inconsistent lightweight ontologies commonly consists in evaluating queries over the repairs of the ABox, defined as maximal subsets of the ABox that are consistent with respect to the TBox. Inconsistency-tolerant semantics are strategies for selecting which repairs to query in order to derive valid conclusions from an inconsistent ontology. Some of the most prominent semantics have been implemented in reasoning systems. For example, the CQAPri system (Consistent Query Answering with Priorities) [1] resolves conjunctive queries in DL-Lite$_R$ ontologies over the repairs of the ABox. It returns as valid conclusions the query answers that follow: from every repair under the ABox Repair (AR) semantics [2], from the intersection of all the repairs under the Intersection of ABox Repair (IAR) semantics [2], and from any repair under the brave semantics [3]. Another example is the QuID system [4] which implements conjunctive query answering under the IAR semantics in ontologies specified in DL-Lite$_A$.

The issue of inconsistency management in DL-Lite$_R$ has been investigated for both totally ordered ontologies [1, 5] and partially ordered ontologies [6]. Some other methods focus on a preference relation defined only over minimal inconsistent subsets of the ABox. The issue was first investigated in prioritized databases [7] and then adapted to DL-Lite in [8].

Besides, inconsistency has been considered within the framework of possibility theory. One can cite the method for computing a totally ordered possibilistic repair [9], which infers all the assertions that are strictly more certain than some inconsistency degree of the ABox. The possibilistic repair is tractable in DL-Lite$_R$, because its computation can be reduced to checking the consistency of a subset of the ABox. This makes it more efficient than the other repairs that apply to totally ordered ABoxes [9].

Furthermore, in the case of partially ordered ontologies, there is the method for computing the partially ordered possibilistic repair ($\pi$-repair) [10], and its closure-based counterpart ($C_\pi$-repair) [11], which is more productive. In both methods, the partial order over the ABox is interpreted as a family of total orders which define the compatible totally ordered ABoxes extending the partial order. The $\pi$-repair is obtained from the intersection of the totally ordered possibilistic repairs of the compatible ABoxes, whereas the $C_\pi$-repair intersects their closure. Note that the $\pi$-repair is included in the $C_\pi$-repair.

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

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

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

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

<footnote n="1">¹CRIL, Univ. Artois & CNRS, UMR 8188, Lens, 62300, France</footnote>

<footnote n="2">²LIASD, IUT de Montreuil, Univ. Paris 8, Saint-Denis, 93200, France</footnote>
possibilistic repair is tractable in DL-Lite<sub>R</sub>, because its computation can be reduced to checking the consistency of a subset of the ABox. This makes it more efficient than the other repairs that apply to totally ordered ABoxes [9]. Furthermore, in the case of partially ordered ontologies, there is the method for computing the partially ordered possibilistic repair (π-repair) [10], and its closure-based counterpart (Cπ-repair) [11] which is more productive. In both methods, the partial order over the ABox is interpreted as a family of total orders which define the compatible totally ordered ABoxes that extend the partial order. The π-repair is obtained from the intersection of the totally ordered possibilistic repairs of the compatible ABoxes, whereas the Cπ-repair intersects their closure. Note that the π-repair is included in the Cπ-repair.

Equivalent characterizations have been proposed for the π-repair and the Cπ-repair methods, without exhibiting the all compatible ABoxes, and have been shown to be tractable in DL-Lite<sub>R</sub>. The π-repair method is characterized by the notion of π-accepted assertion [12], which boils down to checking the consistency of the said assertion together with the subset of all the assertions that are at least equally certain or are incomparable to it. The Cπ-repair method is characterized using the notions of support and dominance [11] against the conflicts of the ABox, which are minimal subsets of the ABox that are inconsistent with respect to the TBox. Basically, a valid conclusion is an assertion that can be derived from consistent minimal subsets of the ABox, called supports, that dominate (i.e., are strictly more certain than) all the conflicts.

In this work, we first implement a naive algorithm for the Cπ-repair method, using the tractable characterization based on the notions of support and dominance. We then provide an improved equivalent algorithm by exploiting the fact that Cπ-repair is composed of the π-repair and a complement set. We revise the notion of dominance by exploiting the partial order relation in order to reduce the number of conflicts and supports that need to be processed by the algorithm. Thus, computing Cπ-repair amounts to computing the π-repair with the tractable characterization of π-accepted assertions, and computing the rest by applying the revised notion of dominance to the remaining assertions. We perform an experimental analysis and confirm that computing the Cπ-repair with the new algorithm benefits from the efficiency of computing the π-repair. We highlight the main situations in which the Cπ-repair method achieves the best performance both in terms of productivity and computational cost.

This paper is structured as follows. Section 2 recalls some preliminaries then describes a naive algorithm for the Cπ-repair method. Section 3 studies properties of Cπ-repair which serve to introduce an improved algorithm. Section 4 provides an experimental evaluation of these algorithms. A brief discussion concludes the paper.

## 2. Preliminaries: The Cπ-repair method

**DL-Lite<sub>R</sub> Syntax** A DL-Lite<sub>R</sub> ontology [13] is a finite knowledge base (KB) K = ⟨T, A⟩, built by recursively applying the following grammar:

$$R := P \mid P^{-} \quad E := R \mid \neg R \quad B := A \mid \exists R \quad C := B \mid \neg B$$

where A is a concept name, P is a role name and P<sup>-</sup> is its inverse. The symbol ∼ designates a complement set and ∃ denotes existential restriction on roles.

The TBox T contains axioms of the form B ⊑ C and R ⊑ E. The ABox A contains assertions of the form A(a) and P(a, b), where a and b are individuals. The axioms in T may be positive
Equivalent characterizations have been proposed for the π-repair and the Cπ-repair methods, without exhibiting the all compatible ABoxes, and have been shown to be tractable in DL-Lite<sub>R</sub>. The π-repair method is characterized by the notion of π-accepted assertion [12], which boils down to checking the consistency of the said assertion together with the subset of all the assertions that are at least equally certain or are incomparable to it. The Cπ-repair method is characterized using the notions of support and dominance [11] against the conflicts of the ABox, which are minimal subsets of the ABox that are inconsistent with respect to the TBox. Basically, a valid conclusion is an assertion that can be derived from consistent minimal subsets of the ABox, called supports, that dominate (i.e., are strictly more certain than) all the conflicts.

In this work, we first implement a naive algorithm for the Cπ-repair method, using the tractable characterization based on the notions of support and dominance. We then provide an improved equivalent algorithm by exploiting the fact that Cπ-repair is composed of the π-repair and a complement set. We revise the notion of dominance by exploiting the partial order relation in order to reduce the number of conflicts and supports that need to be processed by the algorithm. Thus, computing Cπ-repair amounts to computing the π-repair with the tractable characterization of π-accepted assertions, and computing the rest by applying the revised notion of dominance to the remaining assertions. We perform an experimental analysis and confirm that computing the Cπ-repair with the new algorithm benefits from the efficiency of computing the π-repair. We highlight the main situations in which the Cπ-repair method achieves the best performance both in terms of productivity and computational cost.

This paper is structured as follows. Section 2 recalls some preliminaries then describes a naive algorithm for the Cπ-repair method. Section 3 studies properties of Cπ-repair which serve to introduce an improved algorithm. Section 4 provides an experimental evaluation of these algorithms. A brief discussion concludes the paper.

## 2. Preliminaries: The Cπ-repair method

**DL-Lite<sub>R</sub> Syntax** A DL-Lite<sub>R</sub> ontology [13] is a finite knowledge base (KB) K = ⟨T, A⟩, built by recursively applying the following grammar:

$$R := P \mid P^{-} \quad E := R \mid \neg R \quad B := A \mid \exists R \quad C := B \mid \neg B$$

where A is a concept name, P is a role name and P<sup>-</sup> is its inverse. The symbol $\neg$ designates a complement set and $\exists$ denotes existential restriction on roles.

The TBox T contains axioms of the form $B \sqsubseteq C$ and $R \sqsubseteq E$. The ABox A contains assertions of the form $A(a)$ and $P(a, b)$, where a and b are individuals. The axioms in T may be positive inclusions of the form $B_1 \sqsubseteq B_2$ or $R_1 \sqsubseteq R_2$ which allow to derive new assertions from A. The axioms in T may also be negative inclusions of the form $B_1 \sqsubseteq \neg B_2$ or $R_1 \sqsubseteq \neg R_2$ which serve to exhibit the conflicts in A. A conflict is a minimal subset of A that is inconsistent with respect to T, with a size of (at most) two assertions in DL-Lite<sub>R</sub> [14]. Inconsistency refers to the absence of a model for the KB. We omit the semantics of DL-Lite<sub>R</sub> for space considerations.

**Partially preordered KB** A partial preorder $\succeq$ over an ABox A is a reflexive and transitive binary relation. Let $\succ$ be the associated strict order. Let $\bowtie$ denote incomparability, i.e., for $\varphi_j$ and $\varphi_k$ two assertions, $\varphi_j \bowtie \varphi_k$ means that neither $\varphi_j \succeq \varphi_k$ nor $\varphi_k \succeq \varphi_j$ applies. The partially preordered ABox is denoted by $A_{\succ}$. In the rest of this paper, we deal with an inconsistent partially preordered KB and denote it by $K = \langle T, A_{\succ} \rangle$.

Next, we provide an algorithmic definition for each of the core notions of the Cπ-repair method, namely the deductive closure, the conflict set and the support of an assertion.

### 2.1. Deductive closure of the ABox

The deductive closure of the ABox contains all the assertions that may be inferred from the KB using the positive axioms of the TBox. The individuals included in the closure are limited to those present
inclusions of the form $B_1 \subseteq B_2$ or $R_1 \subseteq R_2$ which allow to derive new assertions from $\mathcal{A}$. The axioms in $\mathcal{T}$ may also be negative inclusions of the form $B_1 \subseteq \neg B_2$ or $R_1 \subseteq \neg R_2$ which serve to exhibit the conflicts in $\mathcal{A}$. A conflict is a minimal subset of $\mathcal{A}$ that is inconsistent with respect to $\mathcal{T}$, with a size of (at most) two assertions in DL-Lite$_R$ [14]. Inconsistency refers to the absence of a model for the KB. We omit the semantics of DL-Lite$_R$ for space considerations.

**Partially preordered KB** A partial preorder $\succeq$ over an ABox $\mathcal{A}$ is a reflexive and transitive binary relation. Let $▷$ be the associated strict order. Let $▷▷$ denote incomparability, i.e., for $\varphi_j$ and $\varphi_k$ two assertions, $\varphi_j▷▷\varphi_k$ means that neither $\varphi_j\supseteq\varphi_k$ nor $\varphi_k\supseteq\varphi_j$ applies. The partially preordered ABox is denoted by $\mathcal{A}_{\succ}$. In the rest of this paper, we deal with an inconsistent partially preordered KB and denote it by $\mathcal{K} = \langle\mathcal{T}, \mathcal{A}_{\succ}\rangle$.

Next, we provide an algorithmic definition for each of the core notions of the C$\pi$-repair method, namely the deductive closure, the conflict set and the support of an assertion.

## 2.1. Deductive closure of the ABox

The deductive closure of the ABox contains all the assertions that may be inferred from the KB using the positive axioms of the TBox. The individuals included in the closure are limited to those present in the ABox, which makes the closure finite. Algorithm 1 computes the deductive closure of $\mathcal{A}_{\succ}$ by running a set of First Order SQL queries. For each concept or role name in an axiom of the TBox, it creates a conjunctive query (CQ) $q(\vec{x})$ to retrieve the individuals in the corresponding assertion (in line 3). Then, the algorithm reformulates the query into a union of conjunctive queries (UCQ), under classical semantics, to get all the individuals present in any subsume or subrole of the initial concept or role name. Any CQ-rewriting procedure may be used. Here, we use the PerfectRef algorithm [13]. The results of the reformulation are then executed on the ABox (in line 6). This corresponds to computing the set of the answers for each query over $\mathcal{I}_{\mathcal{A}_{\succ}}$, which is the interpretation that satisfies exactly the assertions of $\mathcal{A}_{\succ}$.

<caption>**Algorithm 1: ComputeClosure**</caption>

Input: $\mathcal{K} = \langle\mathcal{T}, \mathcal{A}_{\succ}\rangle$: a KB
Output: $cl(\mathcal{A}_{\succ})$: the deductive closure of $\mathcal{A}_{\succ}$.
1 $cl(\mathcal{A}_{\succ}) \leftarrow \emptyset$
2 **foreach** N : a concept name or role name in $\mathcal{T}$ **do**
3 &nbsp;&nbsp;&nbsp;&nbsp;$q(\vec{x}) \leftarrow \delta(N)$
4 &nbsp;&nbsp;&nbsp;&nbsp;PR $\leftarrow$ PerfectRef($q, \mathcal{T}$)
5 &nbsp;&nbsp;&nbsp;&nbsp;**foreach** $q_i(\vec{x})$ in PR **do**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**foreach** $\vec{d} \in ans(q_i, \mathcal{I}_{\mathcal{A}_{\succ}})$ **do**
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$cl(\mathcal{A}_{\succ}) \leftarrow cl(\mathcal{A}_{\succ}) \cup \{\lambda(N, \vec{d})\}$
8 **return** ($cl(\mathcal{A}_{\succ})$)

* $\delta$: a translation function mapping a concept name $B$ with a variable $x$, and a role name $R$ with the variables $x_1, x_2$ (adapted from [13]).

* $ans(q_i, \mathcal{I}_{\mathcal{A}_{\succ}})$: the result of running the query $q_i$ on the interpretation $\mathcal{I}_{\mathcal{A}_{\succ}}$.

* $\lambda$: a translation function mapping the concept name or the role name $N$ with each of the answers $\vec{d}$ (adapted from [13]).

## 2.2. Conflict set of the ABox

In an inconsistent DL-Lite$_R$ KB, a conflict is a minimal subset of (at most) two assertions that are contradictory in terms of the axioms [14]. In the following, we assume that a conflict contains
in the ABox, which makes the closure finite. Algorithm 1 computes the deductive closure of $\mathcal{A}_{\Delta}$ by running a set of First Order SQL queries. For each concept or role name in an axiom of the TBox, it creates a conjunctive query (CQ) $q(\vec{x})$ to retrieve the individuals in the corresponding assertion (in line 3). Then, the algorithm reformulates the query into a union of conjunctive queries (UCQ), under classical semantics, to get all the individuals present in any subsume or subrole of the initial concept or role name. Any CQ-rewriting procedure may be used. Here, we use the PerfectRef algorithm [13]. The results of the reformulation are then executed on the ABox (in line 6). This corresponds to computing the set of the answers for each query over $\mathcal{I}_{\mathcal{A}_{\Delta}}$, which is the interpretation that satisfies exactly the assertions of $\mathcal{A}_{\Delta}$.

<caption>**Algorithm 1: ComputeClosure**</caption>

Input: $\mathcal{K} = (\mathcal{T}, \mathcal{A}_{\Delta})$: a KB
Output: $cl(\mathcal{A}_{\Delta})$: the deductive closure of $\mathcal{A}_{\Delta}$.
1 $cl(\mathcal{A}_{\Delta}) \leftarrow \emptyset$
2 **foreach** N : a concept name or role name in $\mathcal{T}$ **do**
3 &nbsp;&nbsp;&nbsp;&nbsp;$q(\vec{x}) \leftarrow \delta(N)$
4 &nbsp;&nbsp;&nbsp;&nbsp;PR $\leftarrow$ PerfectRef($q, \mathcal{T}$)
5 &nbsp;&nbsp;&nbsp;&nbsp;**foreach** $q_i(\vec{x})$ **in** PR **do**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**foreach** $\vec{d} \in ans(q_i, \mathcal{I}_{\mathcal{A}_{\Delta}})$ **do**
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$cl(\mathcal{A}_{\Delta}) \leftarrow cl(\mathcal{A}_{\Delta}) \cup \{\lambda(N, \vec{d})\}$
8 **return** ($cl(\mathcal{A}_{\Delta})$)

* $\delta$: a translation function mapping a concept name $B$ with a variable $x$, and a role name $R$ with the variables $x_1, x_2$ (adapted from [13]).

* ans($q_i, \mathcal{I}_{\mathcal{A}_{\Delta}}$): the result of running the query $q_i$ on the interpretation $\mathcal{I}_{\mathcal{A}_{\Delta}}$.

* $\lambda$: a translation function mapping the concept name or the role name $N$ with each of the answers $\vec{d}$ (adapted from [13]).

## 2.2. Conflict set of the ABox

In an inconsistent DL-Lite<sub>R</sub> KB, a conflict is a minimal subset of (at most) two assertions that are contradictory in terms of the axioms [14]. In the following, we assume that a conflict contains exactly two assertions, and denote the conflict set of the ABox $\mathcal{A}_{\Delta}$ by $\text{Cf}(\mathcal{A}_{\Delta})$. Algorithm 2 uses query generation and reformulation (similar to the algorithm in [15]) to compute the conflict set. The algorithm creates a conjunctive query ($q_i(\vec{x})$) for each negative axiom in $\mathcal{T}$. Then it performs CQ-rewriting under classical semantics, to get queries for the negative axioms that are not explicitly stated in the TBox. The size of each query at this step is 2. After that, the obtained queries are evaluated over the ABox to get the individuals ($\vec{d}$) that are present in both assertions of any conflicting concept names or role names. $\vec{d}$ are substituted for the variables $\vec{x}$, and the set of atoms in $q_i(\vec{d})$ are added to the conflict set.

<caption>**Algorithm 2: ComputeConflicts**</caption>

Input: $\mathcal{K} = (\mathcal{T}, \mathcal{A}_{\Delta})$: a KB
Output: $\text{Cf}(\mathcal{A}_{\Delta})$: the conflict set of $\mathcal{A}_{\Delta}$.
1 $\text{Cf}(\mathcal{A}_{\Delta}) \leftarrow \emptyset$
2 $Q \leftarrow \emptyset$
3 **foreach** $\alpha$: a negative axiom in $\mathcal{T}$ **do**
4 &nbsp;&nbsp;&nbsp;&nbsp;$Q \leftarrow Q \cup \{q_i(\vec{x}) \leftarrow \delta(\alpha)\}$
5 PR $\leftarrow \bigcup_{q_i \in Q} \text{PerfectRef}(q_i, \mathcal{T})$
6 **foreach** $q_i(\vec{x})$ **in** PR **do**
7 &nbsp;&nbsp;&nbsp;&nbsp;**foreach** $\vec{d} \in ans(q_i, \mathcal{I}_{\mathcal{A}_{\Delta}})$ **do**
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\text{Cf}(\mathcal{A}_{\Delta}) \leftarrow \text{Cf}(\mathcal{A}_{\Delta}) \cup \{\text{atoms}(q_i(\vec{d}))\}$
9 **return** ($\text{Cf}(\mathcal{A}_{\Delta})$)

* $\delta$: a translation function from a negative axiom $\alpha$ in $\mathcal{T}$ to a conjunctive query (defined in [13]).

* ans($q_i, \mathcal{I}_{\mathcal{A}_{\Delta}}$): the result of running the query $q_i$ on the interpretation $\mathcal{I}_{\mathcal{A}_{\Delta}}$.

* $\text{atoms}(q_i(\vec{d}))$: the set of atoms in the query $q_i(\vec{d})$.

## 2.3. Supports of an assertion

The support of an assertion in an ABox is a minimal consistent subset of the ABox that allows to derive it. In DL-Lite<sub>R</sub>, a support consists of at most a single assertion of the ABox. Algorithm 3 computes
exactly two assertions, and denote the conflict set of the ABox $\mathcal{A}_{\Delta}$ by $\text{Cf}(\mathcal{A}_{\Delta})$. Algorithm 2 uses query generation and reformulation (similar to the algorithm in [15]) to compute the conflict set. The algorithm creates a conjunctive query $(q_i(\vec{x}))$ for each negative axiom in $\mathcal{T}$. Then it performs CQ-rewriting under classical semantics, to get queries for the negative axioms that are not explicitly stated in the TBox. The size of each query at this step is 2. After that, the obtained queries are evaluated over the ABox to get the individuals $(\vec{a})$ that are present in both assertions of any conflicting concept names or role names. $\vec{a}$ are substituted for the variables $\vec{x}$, and the set of atoms in $q_i(\vec{a})$ are added to the conflict set.

<caption>**Algorithm 2: ComputeConflicts**</caption>

**Input:** $\mathcal{K} = (\mathcal{T}, \mathcal{A}_{\Delta})$: a KB
**Output:** $\text{Cf}(\mathcal{A}_{\Delta})$: the conflict set of $\mathcal{A}_{\Delta}$
1 &nbsp;&nbsp;Cf($\mathcal{A}_{\Delta}$) &nbsp;&nbsp;← &nbsp;&nbsp;Ø
2 &nbsp;&nbsp;$Q$ &nbsp;&nbsp;← &nbsp;&nbsp;Ø
3 &nbsp;&nbsp;**foreach** $\alpha$: a negative axiom in $\mathcal{T}$ **do**
4 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$Q$ &nbsp;&nbsp;← &nbsp;&nbsp;$Q \cup \{q_i(\vec{x}) \leftarrow \delta(\alpha)\}$
5 &nbsp;&nbsp;PR &nbsp;&nbsp;← &nbsp;&nbsp;$\bigcup_{q_i \in Q} \text{PerfectRef}(q_i, \mathcal{T})$
6 &nbsp;&nbsp;**foreach** $q_i(\vec{x})$ **in** PR **do**
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**foreach** $\vec{a} \in \text{ans}(q_i, \mathcal{I}_{\mathcal{A}_{\Delta}})$ **do**
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Cf**($\mathcal{A}_{\Delta}$) &nbsp;&nbsp;← &nbsp;&nbsp;Cf($\mathcal{A}_{\Delta}$) &nbsp;&nbsp;∪ $\{\text{atoms}(q_i(\vec{a}))\}$
9 &nbsp;&nbsp;**return** ($\text{Cf}(\mathcal{A}_{\Delta})$)

• $\delta$: a translation function from a negative axiom $\alpha$ in $\mathcal{T}$ to a conjunctive query (defined in [13]).

• $\text{ans}(q_i, \mathcal{I}_{\mathcal{A}_{\Delta}})$: the result of running the query $q_i$ on the interpretation $\mathcal{I}_{\mathcal{A}_{\Delta}}$.

• $\text{atoms}(q_i(\vec{a}))$: the set of atoms in the query $q_i(\vec{a})$.

## 2.3. Support of an assertion

The support of an assertion in an ABox is a minimal consistent subset of the ABox that allows to derive it. In DL-Lite$_R$, a support consists of at most a single assertion of the ABox. Algorithm 3 computes the union of boolean queries that represent the instance checking queries of the supports for a given assertion. This is achieved via the reformulation of the instance checking query of the assertion under classical semantics (using the PerfectRef algorithm). The verified instances are added to the set of supports of the assertion.

<caption>**Algorithm 3: ComputeSupports**</caption>

**Input:** $\mathcal{K} = (\mathcal{T}, \mathcal{A}_{\Delta})$: a KB, $B(a)$, resp. $R(a_1, a_2)$: an assertion in $\text{cl}(\mathcal{A}_{\Delta})$
**Output:** $S$: the supports of $B(a)$, resp. $R(a_1, a_2)$, in $\mathcal{A}_{\Delta}$
1 &nbsp;&nbsp;$S$ &nbsp;&nbsp;← &nbsp;&nbsp;Ø
2 &nbsp;&nbsp;$q(\vec{a})$ &nbsp;&nbsp;← &nbsp;&nbsp;$B(a)$ &nbsp;&nbsp;/* resp. $R(a_1, a_2)$ */
3 &nbsp;&nbsp;PR &nbsp;&nbsp;← &nbsp;&nbsp;PerfectRef($q, \mathcal{T}$)
4 &nbsp;&nbsp;**foreach** $q_i(\vec{a})$ **in** PR **do**
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $\text{ans}(q_i, \mathcal{I}_{\mathcal{A}_{\Delta}})$ **is true** **then**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Cf**($\mathcal{A}_{\Delta}$) &nbsp;&nbsp;← &nbsp;&nbsp;Cf($\mathcal{A}_{\Delta}$) &nbsp;&nbsp;∪ $\{\text{atoms}(q_i(\vec{a}))\}$
7 &nbsp;&nbsp;**return** ($S$)
the union of boolean queries that represent the instance checking queries of the supports for a given assertion. This is achieved via the reformulation of the instance checking query of the assertion under classical semantics (using the PerfectRef algorithm). The verified instances are added to the set of supports of the assertion.

<caption>**Algorithm 3:** ComputeSupports</caption>

**Input:** $\mathcal{K} = (\mathcal{T}, \mathcal{A}_{\Delta})$: a KB, $B(a)$, resp. $R(a_1, a_2)$: an assertion in $cl(\mathcal{A}_{\Delta})$
**Output:** $S$: the supports of $B(a)$, resp. $R(a_1, a_2)$, in $\mathcal{A}_{\Delta}$
1 &nbsp;&nbsp; $S \leftarrow \emptyset$
2 &nbsp;&nbsp; $q(\vec{a}) \leftarrow B(a)$ &nbsp;&nbsp; /* resp. $R(a_1, a_2)$ */
3 &nbsp;&nbsp; PR $\leftarrow \text{PerfectRef}(q, \mathcal{T})$
4 &nbsp;&nbsp; **foreach** $q_i(\vec{a})$ **in** PR **do**
5 &nbsp;&nbsp;&nbsp;&nbsp; **if** $\text{ans}(q_i, \mathcal{A}_{\Delta})$ **is true** **then**
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $S \leftarrow S \cup \{\text{atoms}(q_i(\vec{a}))\}$
7 &nbsp;&nbsp; **return** $(S)$

## 2.4. C<sub>π</sub>-repair algorithm

Given the notions of deductive closure, conflict set and support introduced in Algorithms 1 to 3, the C<sub>π</sub>-repair method also relies on the notion of dominance. This notion is a way for extending the partial preorder defined over an ABox into a partial preorder defined over subsets of the ABox A<sub>Δ</sub>. The dominance is defined as follows.

**Definition 1 (Dominance).** Let two subsets $B_1$ and $B_2$ of A<sub>Δ</sub>. We say that $B_1$ dominates $B_2$ if $\forall \varphi_j \in B_1$, $\exists \varphi_k \in B_2$ such that $\varphi_j \succcurlyeq \varphi_k$.

The C<sub>π</sub>-repair method is characterized as the dominance of the supports of an assertion over the conflicts of the ABox. The characterization solely applies when the KB is inconsistent. Otherwise, The C<sub>π</sub>-repair amounts to the deductive closure of the ABox.

**Definition 2 (C<sub>π</sub>-repair).** A given assertion $\varphi$ is in $c\pi(\mathcal{A}_{\Delta})$ if $\forall C \in \text{Cf}(\mathcal{A}_{\Delta})$, $\exists B \subseteq \mathcal{A}_{\Delta}$ such that B supports $\varphi$ (as per Algorithm 3), and B dominates C (as per Definition 1).

Note that in DL-Lite<sub>R</sub>, a support (a singleton) dominates a conflict (a pair) means that there is an assertion in the ABox that is strictly more certain than at least one element of the conflict.

Algorithm 4 (given in the next page) is a naive implementation of the C<sub>π</sub>-repair method which applies the characterization given in Definition 2 to each assertion of the closed ABox returned by Algorithm 1.

**Lemma 1.** *The algorithm ComputeC<sub>π</sub>-repair (Algorithm 4) runs in polynomial time and space in $|\mathcal{A}_{\Delta}|$ (in data complexity).*

The proofs of all propositions and lemmas are provided in the appendix.

## 3. Revisiting the C<sub>π</sub>-repair method

In this section, we aim at computing C<sub>π</sub>-repair more efficiently. Thus, we propose to improve Algorithm 4 by exploring two ideas. First, we exhibit additional properties of the dominance relation, in order to reduce the number of the processed conflicts and supports. We do so by focusing on subsets of conflicts and of supports called dominant conflicts and dominant supports. Second, since the C<sub>π</sub>-repair contains the π-repair, we start by computing the π-repair using its tractable characterization. We then complete the C<sub>π</sub>-repair by applying the revised characterization to the assertions that cannot be inferred from the π-repair.
## 2.4. Cπ-repair algorithm

Given the notions of deductive closure, conflict set and support introduced in Algorithms 1 to 3, the Cπ-repair method also relies on the notion of dominance in $A_{\Delta}$ defined as follows.

**Definition 1 (Dominance).** Let two subsets $B_1$ and $B_2$ of $A_{\Delta}$. We say that $B_1$ dominates $B_2$ if $\forall \varphi_j \in B_1, \exists \varphi_k \in B_2 \text{ s.t., } \varphi_j \triangleright \varphi_k$.

The Cπ-repair method is characterized as the dominance of the supports of an assertion over the conflicts of the ABox. The characterization solely applies when the KB is inconsistent. Otherwise, The Cπ-repair amounts to the deductive closure of the ABox.

**Definition 2 (Cπ-repair).** A given assertion $\varphi$ is in $c\pi(A_{\Delta})$ if $\forall C \in Cf(A_{\Delta}), \exists B \subseteq A_{\Delta}$ s.t. B supports $\varphi$ (as per Algorithm 3), and B dominates C (as per Definition 1).

Note that in DL-Lite<sub>R</sub>, a support (a singleton) dominates a conflict (a pair) means that there is an assertion in the ABox that is strictly more certain than at least one element of the conflict. Algorithm 4 is a naive implementation of the Cπ-repair method which applies the characterization given in Definition 2 to each assertion of the closed ABox returned by Algorithm 1.

<caption>**Algorithm 4: ComputeCπ-repair**</caption>

Input: $\mathcal{K} = \langle \mathcal{T}, A_{\Delta} \rangle$: a KB
Output: $C\pi(A_{\Delta})$: the Cπ-repair of $A_{\Delta}$
1 $cl(A_{\Delta}) \leftarrow ComputeClosure(\mathcal{K})$
2 $Cf(A_{\Delta}) \leftarrow ComputeConflicts(\mathcal{K})$
3 if $Cf(A_{\Delta}) = \emptyset$ then return $cl(A_{\Delta})$
4 else
5 $C\pi(A_{\Delta}) \leftarrow \emptyset$
6 **foreach** $\varphi$ **in** $cl(A_{\Delta})$ **do**
7 &nbsp;&nbsp;&nbsp;&nbsp;**S**($\varphi$) $\leftarrow$ ComputeSupports($\varphi, \mathcal{K}$)
8 &nbsp;&nbsp;&nbsp;&nbsp;visited $\leftarrow \emptyset$ \quad /* visited: the set of visited conflicts */
9 &nbsp;&nbsp;&nbsp;&nbsp;**repeat**
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**select** $C = \{c_i, c_j\}$ **from** $Cf(A_{\Delta})$
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$Cf(A_{\Delta}) \leftarrow Cf(A_{\Delta}) \setminus \{C\}$
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;visited $\leftarrow$ visited $\cup \{C\}$
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;supported $\leftarrow$ false \quad /* supported: a boolean, true if $\varphi$ has a support */
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**repeat**
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**select** $\{s\}$ **from** $S(\varphi)$
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S(\varphi) \leftarrow S(\varphi) \setminus \{s\}$
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if $s \triangleright c_i$ **or** $s \triangleright c_j$ **then** supported $\leftarrow$ true
18 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**until** supported is true or $S(\varphi) = \emptyset$ \quad /* exit when a support is found or there are no supports */
19 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**until** supported is false or $Cf(A_{\Delta}) = \emptyset$ \quad /* exit after parsing all the conflicts or there is no support */
20 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if supported is true **then** $C\pi(A_{\Delta}) \leftarrow C\pi(A_{\Delta}) \cup \{\varphi\}$ \quad /* $\varphi$ is supported against each conflict */
21 $Cf(A_{\Delta}) \leftarrow Cf(A_{\Delta}) \cup$ visited
22 **return** $(C\pi(A_{\Delta}))$

**Lemma 1.** *The algorithm ComputeCπ-repair (Algorithm 4) runs in polynomial time and space in $|A_{\Delta}|$ (in data complexity)<fnref n="1" />.*

<footnote n="1">¹Proofs of all propositions and lemmas are provided in the appendix.</footnote>
### 3. Revisiting the Cπ-repair method

In this section, we aim at computing Cπ-repair more efficiently. Thus, we propose to improve Algorithm 4 by exploring two ideas. First, we exhibit additional properties of the dominance relation, in order to reduce the number of the processed conflicts and supports. We do so by focusing on subsets of conflicts and of supports called dominant conflicts and dominant supports. Second, since the Cπ-repair contains the π-repair, we start by computing the π-repair using its tractable characterization. We then complete the Cπ-repair by applying the revised characterization to the assertions that cannot be inferred from the π-repair.

**Definition 3 (Dominant conflicts).** The set of dominant conflicts, denoted $Cf_{dom}(A_\Delta)$, is the maximal subset $Cf_{dom}(A_\Delta) \subseteq Cf(A_\Delta)$ s.t. $\forall C_i \in Cf(A_\Delta)$, if $\exists C_j \in Cf(A_\Delta)$ s.t. $C_j$ dominates $C_i$, then $C_i \notin Cf_{dom}(A_\Delta)$.

The following proposition states that it is sufficient to consider only the dominant conflicts within the conflict set to compute the Cπ-repair. This stems from the fact that the dominance relation is transitive, which follows from the transitivity of the partial preorder relation $\supseteq$.

**Proposition 1.** A given assertion $\varphi$ is in $c\pi(A_\Delta)$ if and only if $\forall C \in Cf_{dom}(A_\Delta)$, $\exists B \subseteq A_\Delta$ s.t. $B$ supports $\varphi$ and $B$ dominates $C$.

**Definition 4 (Dominant supports).** Let $S(\varphi)$ be the set of supports of an assertion $\varphi$ in $A_\Delta$. The set of dominant supports of $\varphi$, denoted $S_{dom}(\varphi)$, is the maximal subset $S_{dom}(\varphi) \subseteq S(\varphi)$ s.t. $\forall B_i \in S(\varphi)$, if $\exists B_j \in S(\varphi)$ s.t. $B_j$ dominates $B_i$, then $B_i \notin S_{dom}(\varphi)$.

The following proposition states that it is sufficient to consider only the set of dominant supports of any given assertion $\varphi$ in order to check its membership in Cπ-repair. This result also follows from the transitivity of the partial preorder relation $\supseteq$.

**Proposition 2.** Let $\varphi$ be an assertion and let $S(\varphi)$ be its set of supports in $A_\Delta$. $\varphi$ is in $c\pi(A_\Delta)$ if and only if $\forall C \in Cf_{dom}(A_\Delta)$, $\exists B \in S_{dom}(\varphi)$ s.t. $B$ dominates $C$.

Proposition 2 entails that Algorithm 4 can actually consider (strict) subsets of the conflicts and the supports. This has the potential for considerably reducing the number of elements over which the algorithm iterates to check membership of an assertion in the Cπ-repair. Furthermore, we exploit two key properties of the Cπ-repair [11] to improve Algorithm 4. First, the Cπ-repair (strictly) contains all the assertions of the π-repair [12], which is characterized as follows.

**Definition 5 (π-repair).** Let $\varphi_i \in A_\Delta$ and $\Delta(\varphi_i) = A_\Delta \setminus \{\varphi_j | \varphi_j \in A_\Delta \text{ s.t. } \varphi_i \supset \varphi_j\}$ be the set of assertions that are at least equally certain or incomparable to $\varphi_i$. Then $\varphi_i \in \pi(A_\Delta)$ if $\langle T, \{\varphi_i\} \cup \Delta(\varphi_i) \rangle$ is consistent.

We conclude that Algorithm 4 does not need to consider all the assertions of the deductively closed ABox in order to compute the Cπ-repair. Instead, an improved version of the algorithm first computes the π-repair$^2$, before iterating over the remaining assertions of the closed ABox.

<footnote>$^2$A suggested algorithm for computing the π-repair is provided in the appendix.</footnote>
### 3.3. Properties of the Cπ-repair

We exploit two key properties of the Cπ-repair [11] to improve Algorithm 4. First, the Cπ-repair (strictly) contains all the assertions of the π-repair [12], which is characterized as follows.

**Definition 5 (π-repair).** Let $\varphi_i \in A_\Delta$ and $\Delta(\varphi_i) = A_\Delta \setminus \{\varphi_j | \varphi_j \in A_\Delta \text{ such that } \varphi_i \succ \varphi_j\}$ be the set of assertions that are at least equally certain or incomparable to $\varphi_i$. Then $\varphi_i \in \pi(A_\Delta)$ if $\langle T, \{\varphi_i\} \cup \Delta(\varphi_i) \rangle$ is consistent.

We conclude that Algorithm 4 does not need to consider all the assertions of the deductively closed ABox in order to compute the Cπ-repair. Instead, an improved version of the algorithm first computes the π-repair<fnref n="1" />, before iterating over the remaining assertions of the closed ABox.

Moreover, we explore a second property of the Cπ-repair in order to reduce the number of remaining assertions that need to be checked by the algorithm. This relates to the set difference between the Cπ-repair and the deductive closure of the π-repair. In essence, if an assertion is neither accepted in the π-repair nor its closure, it must have strictly more than one support to be in the Cπ-repair. This is formalized in the following lemma.

**Lemma 2.** Let $\varphi$ be an assertion in $c\pi(A_\Delta)$. Let $S(\varphi)$ be the set of supports of $\varphi$. If $|S(\varphi)| = 1$, then $\varphi \in cl(\pi(A_\Delta))$.

The converse of Lemma 2 does not hold, a non-accepted assertion may have multiple supports.

Algorithm 5 (given in the next page) constitutes an improved version of Algorithm 4. It begins by computing the closed ABox followed by the set of dominant conflicts. If the KB is consistent, the closed ABox is returned. Otherwise, the algorithm computes the assertions of the π-repair and inserts them in the Cπ-repair. Next, it iterates over the assertions of the closed ABox minus the π-repair, and for each such assertion, it computes its set of dominant supports. If one of the supports is in the π-repair, the assertion is added to the Cπ-repair. This step retrieves the assertions that are in the closure of the π-repair. Otherwise, the algorithm checks whether the assertion has more than one support. If it does, then for each conflict, the algorithm checks whether the assertion has a support dominating the conflict (like in Algorithm 4).

**Lemma 3.** *The algorithm ComputeCπ-repair (Algorithm 5) runs in polynomial time and space in $|A_\Delta|$ (in data complexity).*

## 4. Experimental evaluation

We implemented all the algorithms of this paper in Python. Our system relies on the RDFLib library [16] to read the ontology, a SQLite3 relational DBMS [17] to store the ABox, and the Rapid query rewriting engine [18] to reformulate queries. Our system is publicly available at: https://github.com/ahmedlaouar/py_reasoner. We performed the experiments on an Intel 3.60GHz CPU with 32 GB RAM under Ubuntu, and provided instructions for reproducing them. Let us first discuss how to elicit partial orders to obtain a partially ordered KB.

### 4.1. Directed acyclic graphs for partial orders

One way for implementing a partially ordered KB is to assign partially ordered priority degrees to the assertions of the ABox [10]. These degrees can be represented graphically using Hasse diagrams or directed acyclic graphs (DAGs). We opt for transitive DAGs [19], which explicitly represent arcs within the graph. In a transitive DAG, nodes represent the degrees of a partially ordered set (POS), an arc indicates the strict preference of a degree over the other, and the absence of an arc expresses incompatibility of two degrees. A set of random DAGs was generated using the R package bnlearn [20], based on different numbers of nodes (50, 100, 500, 1000, 2500) and different probabilities for the

<footnote n="1">¹A suggested algorithm for computing the π-repair is given in the appendix.</footnote>
Moreover, we explore a second property of the Cπ-repair in order to reduce the number of remaining assertions that need to be checked by the algorithm. This relates to the set difference between the Cπ-repair and the deductive closure of the π-repair. In essence, if an assertion is neither accepted in the π-repair nor its closure, it must have strictly more than one support to be in the Cπ-repair. This is formalized in the following lemma.

**Lemma 2.** Let $\varphi$ be an assertion in $c\pi(A_{\triangle})$. Let $S(\varphi)$ be the set of supports of $\varphi$. If $|S(\varphi)| = 1$, then $\varphi \in cl(\pi(A_{\triangle}))$.

The converse of Lemma 2 does not hold, a non-accepted assertion may have multiple supports.

Algorithm 5 (given in the next page) constitutes an improved version of Algorithm 4. It begins by computing the closed ABox followed by the set of dominant conflicts. If the KB is consistent, the closed ABox is returned. Otherwise, the algorithm computes the assertions of the π-repair and inserts them in the Cπ-repair. Next, it iterates over the assertions of the closed ABox minus the π-repair, and for each such assertion, it computes its set of dominant supports. If one of the supports is in the π-repair, the assertion is added to the Cπ-repair. This step retrieves the assertions that are in the closure of the π-repair. Otherwise, the algorithm checks whether the assertion has more than one support. If it does, then for each conflict, the algorithm checks whether the assertion has a support dominating the conflict (like in Algorithm 4).

**Lemma 3.** *The algorithm ComputeCπ-repair (Algorithm 5) runs in polynomial time and space in $|A_{\triangle}|$ (in data complexity).*

# 4. Experimental evaluation

We implemented all the algorithms of this paper in Python. Our system relies on the RDFLib library [16] to read the ontology, a SQLite3 relational DBMS [17] to store the ABox, and the Rapid query rewriting engine [18] to reformulate queries. Our system is publicly available at: https://github.com/ahmedlaouar/py_reasoner. We performed the experiments on an Intel 3.60GHz CPU with 32 GB RAM under Ubuntu, and provided instructions for reproducing them. Let us first discuss how to elicit partial orders to obtain a partially ordered KB.

## 4.1. Directed acyclic graphs for partial orders

One way for implementing a partially ordered KB is to assign partially ordered priority degrees to the assertions of the ABox [10]. These degrees can be represented graphically using Hasse diagrams or directed acyclic graphs (DAGs). We opt for transitive DAGs [19], which explicitly represent arcs within the graph. In a transitive DAG, nodes represent the degrees of a partially ordered set (POS), an arc indicates the strict preference of a degree over the other, and the absence of an arc expresses incompatibility of two degrees. A set of random DAGs was generated using the R package bnlearn [20], based on different numbers of nodes (50, 100, 500, 1000, 2500) and different probabilities for the presence of arcs (0.1, ..., 0.9). A probability indicates the density of the DAG, hence a less dense DAG has more occurrences of incomparability.
<caption>**Algorithm 5: ComputeCπ-repair**</caption>

Input: $K = \langle T, A_{\Delta} \rangle$: a KB
Output: $C\pi(A_{\Delta})$: the Cπ-repair of $A_{\Delta}$
1 $cl(A_{\Delta}) \leftarrow ComputeClosure(K)$
2 $Cf_{dom}(A_{\Delta}) \leftarrow ComputeDominantConflicts(K)$ \quad /* the set given by Definition 3 */
3 **if** $Cf_{dom}(A_{\Delta}) = \emptyset$ **then**
4 $\lfloor$ **return** $cl(A_{\Delta})$
5 **else**
6 $\quad \pi(A_{\Delta}) \leftarrow Compute\pi$-repair($K$)
7 $\quad cl(A_{\Delta}) \leftarrow cl(A_{\Delta}) \setminus \pi(A_{\Delta})$
8 $\quad C\pi(A_{\Delta}) \leftarrow \pi(A_{\Delta})$
9 **foreach** $\varphi$ **in** $cl(A_{\Delta})$ **do**
10 $\quad \quad S_{dom}(\varphi) \leftarrow ComputeDominantSupports(\varphi, K)$ \quad /* the set given by Definition 4 */
11 $\quad \quad \text{if } S_{dom}(\varphi) \cap \pi(A_{\Delta}) \neq \emptyset \text{ then}$
12 $\quad \quad \quad \lfloor$ $C\pi(A_{\Delta}) \leftarrow C\pi(A_{\Delta}) \cup \{\varphi\}$
13 $\quad \quad \text{else}$
14 $\quad \quad \quad \text{if } \text{size}(S_{dom}(\varphi)) > 1 \text{ then}$
15 $\quad \quad \quad \quad \text{visited} \leftarrow \emptyset$ \quad /* visited: the set of visited conflicts */
16 $\quad \quad \quad \text{repeat}$
17 $\quad \quad \quad \quad \text{select } C = \{c_i, c_j\}$ **from** $Cf_{dom}(A_{\Delta})$
18 $\quad \quad \quad \quad \quad Cf_{dom}(A_{\Delta}) \leftarrow Cf_{dom}(A_{\Delta}) \setminus \{C\}$
19 $\quad \quad \quad \quad \text{visited} \leftarrow \text{visited} \cup \{C\}$
20 $\quad \quad \quad \quad \text{supported} \leftarrow \text{false}$ \quad /* supported: a boolean, true if $\varphi$ has a support */
21 $\quad \quad \quad \text{repeat}$
22 $\quad \quad \quad \quad \text{select } \{s\}$ **from** $S_{dom}(\varphi)$
23 $\quad \quad \quad \quad \quad S_{dom}(\varphi) \leftarrow S_{dom}(\varphi) \setminus \{s\}$
24 $\quad \quad \quad \quad \text{if } s \succ c_i \text{ or } s \succ c_j \text{ then}$
25 $\quad \quad \quad \quad \quad \quad \lfloor$ supported $\leftarrow$ true
26 $\quad \quad \quad \quad \text{until}$ supported is true or $S_{dom}(\varphi) = \emptyset$ \quad /* exit when support is found or no support */
27 $\quad \quad \quad \text{until}$ supported is false or $Cf_{dom}(A_{\Delta}) = \emptyset$ \quad /* exit if all conflicts parsed or no support */
28 $\quad \quad \quad \text{if}$ supported is true then
29 $\quad \quad \quad \quad \lfloor$ $C\pi(A_{\Delta}) \leftarrow C\pi(A_{\Delta}) \cup \{\varphi\}$ \quad /* $\varphi$ is supported against each conflict */
30 $\quad \quad \quad \quad Cf_{dom}(A_{\Delta}) \leftarrow Cf_{dom}(A_{\Delta}) \cup \text{visited}$
31 $\quad \text{return} (C\pi(A_{\Delta}))$

presence of arcs (0.1, ..., 0.9). A probability indicates the density of the DAG, hence a less dense DAG has more occurrences of incomparability.

## 4.2. Experimental setting

We used an OWL ontology as the TBox. We opted for the DL-Lite<sub>R</sub> version of the modified LUBM benchmark (LUBM<sub>20</sub><sup>2</sup>) [21] (available at https://home.uni-leipzig.de/clu/). Since this version does not contain negative axioms, we added a set of negative axioms to the TBox in order to create conflicts. Next, we used the Extended University Data Generator (EUDG) [21] to generate three ABoxes of different sizes, and transformed each ABox into a SQLite database. Then, we introduced inconsistency by adding contradictory assertions in each ABox as follows. For each negative axiom inferred from the TBox, we contradict the presence of an individual in a concept assertion (resp. role assertion) with probability p (resp. p/2). We used different values of p in order to create five different situations within each ABox in terms of inconsistency, which is measured with by the number of conflicts. For each execution of the algorithms, degrees from a previously generated DAG are randomly assigned to the assertions of each ABox. We refer to the π-repair (Definition 5) and Algorithms 4 and 5 by π, cπ and cπ++, respectively. We consider three different cases for the evaluation:

**Case 1:** We analyse both the performance of the algorithms as a function of the size of the ABox and the
<caption>**Algorithm 5: ComputeCπ-repair**</caption>

Input: $\mathcal{K} = \langle \mathcal{T}, \mathcal{A}_{\Delta} \rangle$: a KB
Output: $C\pi(\mathcal{A}_{\Delta})$: the Cπ-repair of $\mathcal{A}_{\Delta}$
1 $cl(\mathcal{A}_{\Delta}) \leftarrow ComputeClosure(\mathcal{K})$
2 $Cf_{dom}(\mathcal{A}_{\Delta}) \leftarrow ComputeDominantConflicts(\mathcal{K})$ /* the set given by Definition 3 */
3 **if** $Cf_{dom}(\mathcal{A}_{\Delta}) = \emptyset$ **then** **return** $cl(\mathcal{A}_{\Delta})$
4 **else**
5 $\pi(\mathcal{A}_{\Delta}) \leftarrow Compute\pi$-repair($\mathcal{K}$)
6 $cl(\mathcal{A}_{\Delta}) \leftarrow cl(\mathcal{A}_{\Delta}) \setminus \pi(\mathcal{A}_{\Delta})$
7 $C\pi(\mathcal{A}_{\Delta}) \leftarrow \pi(\mathcal{A}_{\Delta})$
8 **foreach** $\varphi$ **in** $cl(\mathcal{A}_{\Delta})$ **do**
9 $\quad S_{dom}(\varphi) \leftarrow ComputeDominantSupports(\varphi, \mathcal{K})$ /* the set given by Definition 4 */
10 $\quad$ **if** $S_{dom}(\varphi) \cap \pi(\mathcal{A}_{\Delta}) \neq \emptyset$ **then**
11 $\quad$ $\lfloor C\pi(\mathcal{A}_{\Delta}) \leftarrow C\pi(\mathcal{A}_{\Delta}) \cup \{\varphi\} \rfloor$
12 $\quad$ **else**
13 $\quad$ $\quad$ **if** $size(S_{dom}(\varphi)) > 1$ **then**
14 $\quad$ $\quad$ visited $\leftarrow \emptyset$ /* visited: the set of visited conflicts */
15 $\quad$ **repeat**
16 $\quad$ $\quad$ **select** $\mathcal{C} = \{c_i, c_j\}$ **from** $Cf_{dom}(\mathcal{A}_{\Delta})$
17 $\quad$ $\quad$ $Cf_{dom}(\mathcal{A}_{\Delta}) \leftarrow Cf_{dom}(\mathcal{A}_{\Delta}) \setminus \mathcal{C}$
18 $\quad$ $\quad$ visited $\leftarrow$ visited $\cup \mathcal{C}$
19 $\quad$ $\quad$ supported $\leftarrow$ false /* supported: a boolean, true if $\varphi$ has a support */
20 $\quad$ **repeat**
21 $\quad$ $\quad$ **select** $\{s\}$ **from** $S_{dom}(\varphi)$
22 $\quad$ $\quad$ $S_{dom}(\varphi) \leftarrow S_{dom}(\varphi) \setminus \{s\}$
23 $\quad$ $\quad$ **if** $s \succ c_i$ **or** $s \succ c_j$ **then** supported $\leftarrow$ true
24 $\quad$ **until** supported **is** true **or** $S_{dom}(\varphi) = \emptyset$ /* exit when support is found or no support */
25 $\quad$ **until** supported **is** false **or** $Cf_{dom}(\mathcal{A}_{\Delta}) = \emptyset$ /* exit if all conflicts parsed or no support */
26 $\quad$ **if** supported **is** true **then**
27 $\quad$ $\lfloor C\pi(\mathcal{A}_{\Delta}) \leftarrow C\pi(\mathcal{A}_{\Delta}) \cup \{\varphi\} \rfloor$ /* $\varphi$ is supported against each conflict */
28 $\quad$ $Cf_{dom}(\mathcal{A}_{\Delta}) \leftarrow Cf_{dom}(\mathcal{A}_{\Delta}) \cup visited$
29 **return** $(C\pi(\mathcal{A}_{\Delta}))$

## 4.2. Experimental setting

We used an OWL ontology as the TBox. We opted for the DL-Lite<sub>R</sub> version of the modified LUBM benchmark (LUBM<sub>20</sub><sup>3</sup>) [21] (available at https://home.uni-leipzig.de/clu/). Since this version does not contain negative axioms, we added a set of negative axioms to the TBox in order to create conflicts. Next, we used the Extended University Data Generator (EUDG) [21] to generate three ABoxes of different sizes, and transformed each ABox into a SQLite database. Then, we introduced inconsistency by adding contradictory assertions in each ABox as follows. For each negative axiom inferred from the TBox, we contradict the presence of an individual in a concept assertion (resp. role assertion) with probability p (resp. p/2). We used different values of p in order to create five different situations within each ABox in terms of inconsistency, which is measured with by the number of conflicts. For each execution of the algorithms, degrees from a previously generated DAG are randomly assigned to the assertions of each ABox. We refer to
<table><caption>**Table 1**</caption><thead><tr><th>ID</th><th>#A</th><th># Cf</th><th>Cf (s)</th><th>#π</th><th>π (s)</th><th>#cπ</th><th>cπ (s)</th><th>cπ++ (s)</th></tr></thead><tbody><tr><td>u.5p5e-6</td><td>9156</td><td>111</td><td>1.08</td><td>8078</td><td>1.24</td><td>22740</td><td>27.65</td><td>11.26</td></tr><tr><td>u.5p1e-5</td><td>9158</td><td>387</td><td>1.42</td><td>5344</td><td>1.33</td><td>15859</td><td>30.56</td><td>18.15</td></tr><tr><td>u.5p5e-5</td><td>9193</td><td>1268</td><td>1.43</td><td>742</td><td>1.28</td><td>2473</td><td>30.15</td><td>30.86</td></tr><tr><td>u.5p5e-4</td><td>9228</td><td>3372</td><td>1.6</td><td>1102</td><td>1.41</td><td>3651</td><td>30.75</td><td>29.35</td></tr><tr><td>u.5p1e-3</td><td>9375</td><td>7733</td><td>1.7</td><td>442</td><td>1.57</td><td>1475</td><td>28.83</td><td>28.65</td></tr><tr><td>u1p5e-6</td><td>75671</td><td>753</td><td>2.51</td><td>36083</td><td>4.36</td><td>66867</td><td>203.59</td><td>53.45</td></tr><tr><td>u1p1e-5</td><td>75678</td><td>3049</td><td>2.77</td><td>22804</td><td>8.38</td><td>46257</td><td>261.47</td><td>74.74</td></tr><tr><td>u1p5e-5</td><td>75718</td><td>10388</td><td>4.14</td><td>5856</td><td>5.07</td><td>14992</td><td>267.33</td><td>130.9</td></tr><tr><td>u1p15e-5</td><td>75842</td><td>28553</td><td>4.84</td><td>2378</td><td>6.54</td><td>6834</td><td>258.71</td><td>168.25</td></tr><tr><td>u1p5e-4</td><td>76255</td><td>83863</td><td>6.5</td><td>988</td><td>6.9</td><td>2994</td><td>251.23</td><td>170.61</td></tr><tr><td>u5p5e-6</td><td>463349</td><td>4505</td><td>22.48</td><td>74511</td><td>39.39</td><td>167473</td><td>6635.11</td><td>2160.48</td></tr><tr><td>u5p1e-5</td><td>463400</td><td>8327</td><td>23.6</td><td>30204</td><td>38.89</td><td>78857</td><td>6711.89</td><td>2941.02</td></tr><tr><td>u5p5e-5</td><td>463684</td><td>57054</td><td>26.3</td><td>8693</td><td>35.85</td><td>25921</td><td>5772.07</td><td>3105.82</td></tr><tr><td>u5p1e-4</td><td>464060</td><td>121621</td><td>29.76</td><td>6213</td><td>34.12</td><td>18794</td><td>6492.42</td><td>3566.24</td></tr><tr><td>u5p5e-4</td><td>466785</td><td>544500</td><td>49.95</td><td>1470</td><td>95.88</td><td>4713</td><td>5868.32</td><td>3956.46</td></tr></tbody></table>

ABoxes in terms of: size (#A), conflicts number (# Cf) and computation time (Cf (s)), π-repair size (#π) and computation time (π (s)), Cπ-repair size (#cπ) and computation time (cπ (s)) and cπ++ (s)).

impact of the number of conflicts on the size of the repairs and the running time (for computing the repairs). The results are presented in Table 1 and Figure 1.

Case 2: We consider different configurations for the associated DAG (POS). We analyze the impact of changing the size and density of the DAG. This allows us to measure the difference $cπ(A_\Delta) \setminus cl(\pi(A_\Delta))$. We point out the main situations where the Cπ-repair is more productive than the π-repair. The results are depicted in Figure 2 [left].

Case 3: We use ABox u.5 to compare the proportion of time spent in each step of Algorithms 4 and 5. For each ABox by number of conflicts, we computed the median time from different executions. The results are presented in Figure 2 [middle] and [right].

## 4.3. Experimental results

**Impact of the number of conflicts (Case 1)** First, we compare the running time of Algorithms 4 and 5 (cπ and cπ++) to compute the Cπ-repair, and can see that the improved method largely outruns the naive method. Mainly, in situations of weakly conflicting ABoxes, which correspond to ABoxes with (111, 387) conflicts for u.5, (753, 3049) conflicts for u1 and (4505, 8327) for u5. For these ABoxes, the improved method reduces the running time to a mere 25% of the naive method's. This can be observed in Figure 1 [left], with (753, 3049) conflicts. This also holds for large sized ABoxes, as ABox u5 in Table 1. Moreover, for highly conflicting ABoxes, the improved method takes at most half of the time taken by the naive one. In these ABoxes, the π-repair becomes smaller and more assertions must be checked using the Cπ-repair characterization. We can observe in Figure 1 [left] that the π-repair is computed in a stable time. This is because it runs a constant time verification step for each ABox assertion.

Regarding the size of the obtained repairs, we observe that a large subset of assertions is discarded when the number of conflicts exceeds 10% of the size of the ABox (1268 for ABox u.5, 10388 for ABox u1 and 57054 for ABox u5). This is confirmed by Figure 1 [right]. This outcome is expected. Moreover, it is true even for the IAR semantics, which is considered by nature to be more productive than possibilistic repairs (for more details on IAR, see [4, 1]).

**Impact of the used partial order (Case 2)** In order to point out the main situations where the Cπ-repair is more productive than the π-repair, we illustrate the size of the π-repair (π), the closure of
<table><caption>**Table 1**</caption><thead><tr><th>ID</th><th>#A</th><th># Cf</th><th>Cf (s)</th><th>#π</th><th>π (s)</th><th>#cπ</th><th>cπ (s)</th><th>cπ++ (s)</th></tr></thead><tbody><tr><td>u.5p5e-6</td><td>9156</td><td>111</td><td>1.08</td><td>8078</td><td>1.24</td><td>22740</td><td>27.65</td><td>11.26</td></tr><tr><td>u.5p1e-5</td><td>9158</td><td>387</td><td>1.42</td><td>5344</td><td>1.33</td><td>15859</td><td>30.56</td><td>18.15</td></tr><tr><td>u.5p5e-5</td><td>9193</td><td>1268</td><td>1.43</td><td>742</td><td>1.28</td><td>2473</td><td>30.15</td><td>30.86</td></tr><tr><td>u.5p5e-4</td><td>9228</td><td>3372</td><td>1.6</td><td>1102</td><td>1.41</td><td>3651</td><td>30.75</td><td>29.35</td></tr><tr><td>u.5p1e-3</td><td>9375</td><td>7733</td><td>1.7</td><td>442</td><td>1.57</td><td>1475</td><td>28.83</td><td>28.65</td></tr><tr><td>u1p5e-6</td><td>75671</td><td>753</td><td>2.51</td><td>36083</td><td>4.36</td><td>66867</td><td>203.59</td><td>53.45</td></tr><tr><td>u1p1e-5</td><td>75678</td><td>3049</td><td>2.77</td><td>22804</td><td>8.38</td><td>46257</td><td>261.47</td><td>74.74</td></tr><tr><td>u1p5e-5</td><td>75718</td><td>10388</td><td>4.14</td><td>5856</td><td>5.07</td><td>14992</td><td>267.33</td><td>130.9</td></tr><tr><td>u1p15e-5</td><td>75842</td><td>28553</td><td>4.84</td><td>2378</td><td>6.54</td><td>6834</td><td>258.71</td><td>168.25</td></tr><tr><td>u1p5e-4</td><td>76255</td><td>83863</td><td>6.5</td><td>988</td><td>6.9</td><td>2994</td><td>251.23</td><td>170.61</td></tr><tr><td>u5p5e-6</td><td>463349</td><td>4505</td><td>22.48</td><td>74511</td><td>39.39</td><td>167473</td><td>6635.11</td><td>2160.48</td></tr><tr><td>u5p1e-5</td><td>463400</td><td>8327</td><td>23.6</td><td>30204</td><td>38.89</td><td>78857</td><td>6711.89</td><td>2941.02</td></tr><tr><td>u5p5e-5</td><td>463684</td><td>57054</td><td>26.3</td><td>8693</td><td>35.85</td><td>25921</td><td>5772.07</td><td>3105.82</td></tr><tr><td>u5p1e-4</td><td>464060</td><td>121621</td><td>29.76</td><td>6213</td><td>34.12</td><td>18794</td><td>6492.42</td><td>3566.24</td></tr><tr><td>u5p5e-4</td><td>466785</td><td>544500</td><td>49.95</td><td>1470</td><td>95.88</td><td>4713</td><td>5868.32</td><td>3956.46</td></tr></tbody></table>

ABoxes in terms of: size (#A), conflicts number (# Cf) and computation time (Cf (s)), π-repair size (#π) and computation time (π (s)), Cπ-repair size (#cπ) and computation time (cπ (s) and cπ++ (s)).

the π-repair (Definition 5) and Algorithms 4 and 5 by π, cπ and cπ++, respectively. We consider three different cases for the evaluation:

Case 1: We analyse both the performance of the algorithms as a function of the size of the ABox and the impact of the number of conflicts on the size of the repairs and the running time (for computing the repairs). The results are presented in Table 1 and Figure 1.

Case 2: We consider different configurations for the associated DAG (POS). We analyze the impact of changing the size and density of the DAG. This allows us to measure the difference $c\pi(A_\Delta) \setminus cl(\pi(A_\Delta))$. We point out the main situations where the Cπ-repair is more productive than the π-repair. The results are depicted in Figure 2 [left].

Case 3: We use ABox u.5 to compare the proportion of time spent in each step of Algorithms 4 and 5. For each ABox by number of conflicts, we computed the median time from different executions. The results are presented in Figure 2 [middle] and [right].

### 4.3. Experimental results

**Impact of the number of conflicts (Case 1)** First, we compare the running time of Algorithms 4 and 5 (cπ and cπ++) to compute the Cπ-repair, and can see that the improved method largely outruns the naive method. Mainly, in situations of weakly conflicting ABoxes, which correspond to ABoxes with (111, 387) conflicts for u.5, (753, 3049) conflicts for u1 and (4505, 8327) for u5. For these ABoxes, the improved method reduces the running time to a mere 25% of the naive method's. This can be observed in Figure 1 [left], with (753, 3049) conflicts. This also holds for large sized ABoxes, as ABox u5 in Table 1. Moreover, for highly conflicting ABoxes, the improved method takes at most half of the time taken by the naive one. In these ABoxes, the π-repair becomes smaller and more assertions must be checked using the Cπ-repair characterization. We can observe in Figure 1 [left] that the π-repair is computed in a stable time. This is because it runs a constant time verification step for each ABox assertion.

Regarding the size of the obtained repairs, we observe that a large subset of assertions is discarded when the number of conflicts exceeds 10% of the size of the ABox (1268 for ABox
<figure><img src="image_6.png" /><figcaption>**Figure 1:** Evolution of repair time [left] and repair size [right] w.r.t. the number of conflicts (ABox **u1**).</figcaption></figure>

the $\pi$-repair ($cl(\pi)$) and the additional assertions that are only in the $C\pi$-repair (only $c\pi$), as a function of the density of the used POS. Figure 2 [left] depicts the results of these executions. Note that in this case, we used ABox **u1** with 753, 3049 and 10388 conflicts. The evaluation of the density shows that lower probabilities, which indicate a higher presence of incomparabilities, lead to a more productive $C\pi$-repair. When the probability of having a strict preference between two degrees in the POS is lower than 0.5, the $C\pi$-repair is larger than the $\pi$-repair. Conversely, POSs with higher probabilities corresponds to a decreased likelihood of $C\pi$-repair being more productive than the $\pi$-repair, such partial orders approximate a total order. This result illustrates Lemma 2, with more incomparabilities, there is a higher chance for an assertion to have different supports dominating different conflicts. This is the case for the assertions that are only in the $C\pi$-repair.

We can also observe that, for POSs with many incomparabilities, the $C\pi$-repair returns more answers when the $\pi$-repair is empty. This can be observed in Figure 2 [left], with the densities 0.1 and 0.3. Furthermore, we concluded, through multiple executions with different POS densities, that the $C\pi$-repair returns an important number of assertions in 80% of the cases where the $\pi$-repair contains less than 10% of the ABox assertions. In addition, for weakly conflicting ABoxes, the $C\pi$-repair provided additional assertions in 10% of the times. This percentage falls under 5% for the highly conflicting ABoxes.

**Proportion of time spent by Algorithms 4 and 5 (Case 3)** Figure 2 ([middle] and [right]) illustrates the running time taken by each step of Algorithms 4 and 5. For both algorithms, the computation of the ABox closure is achieved in constant time. The time taken to compute the set of conflicts increases slightly as their number increases. This also results in an increase in total time, as there are more conflicts to go through. In the improved method (Figure 2 [right]), computing the $\pi$-repair is run in constant time with respect to the changing number of conflicts, whereas computing its closure is more time-consuming in weakly conflicting ABoxes. Computing the supports involves processing each assertion in the ABox closure through multiple SQL queries to retrieve them. Although significantly faster in the improved algorithm, as shown in the results of Table 1, supports computation is the most time-intensive step of the process.

# 5. Concluding discussions

In this paper, we conducted an experimental study of data repair methods for partially ordered possibilistic knowledge bases, including three principal phases. Initially, it involved developing suitable algorithms for the computation of repairs. Subsequently, we delved into examining the inherent properties of the repair strategies and the algorithms’ to enhance their efficiency. Finally, we tested the algorithms across various scenarios to evaluate their performance. We provided an algorithmic investigation, complemented by experimental analysis of the closure-based partially ordered possibilistic repair. Starting with the repair’s characterization, we showed that leveraging certain properties allows for a more efficient repair process. Our experiments, conducted across
<figure><img src="image_6.png" /><figcaption>**Figure 1:** Evolution of repair time [left] and repair size [right] w.r.t. the number of conflicts (ABox **u1**).</figcaption></figure>

**u.5**, 10388 for ABox **u1** and 57054 for ABox **u5**). This is confirmed by Figure 1 [right]. This outcome is expected. Moreover, it is true even for the IAR semantics, which is considered by nature to be more productive than possibilistic repairs (for more details on IAR, see [4, 1]).

**Impact of the used partial order (Case 2)** In order to point out the main situations where the Cπ-repair is more productive than the π-repair, we illustrate the size of the π-repair (π), the closure of the π-repair (cl(π)) and the additional assertions that are only in the Cπ-repair (only cπ), as a function of the density of the used POS. Figure 2 [left] depicts the results of these executions. Note that in this case, we used ABox **u1** with 753, 3049 and 10388 conflicts. The evaluation of the density shows that lower probabilities, which indicate a higher presence of incomparabilities, lead to a more productive Cπ-repair. When the probability of having a strict preference between two degrees in the POS is lower than 0.5, the Cπ-repair is larger than the π-repair. Conversely, POSs with higher probabilities corresponds to a decreased likelihood of Cπ-repair being more productive than the π-repair, such partial orders approximate a total order. This result illustrates Lemma 2, with more incomparabilities, there is a higher chance for an assertion to have different supports dominating different conflicts. This is the case for the assertions that are only in the Cπ-repair. We can also observe that, for POSs with many incomparabilities, the Cπ-repair returns more answers when the π-repair is empty. This can be observed in Figure 2 [left], with the densities 0.1 and 0.3. Furthermore, we concluded, through multiple executions with different POS densities, that the Cπ-repair returns an important number of assertions in 80% of the cases where the π-repair contains less than 10% of the ABox assertions. In addition, for weakly conflicting ABoxes, the Cπ-repair provided additional assertions in 10% of the times. This percentage falls under 5% for the highly conflicting ABoxes.

**Proportion of time spent by Algorithms 4 and 5 (Case 3)** Figure 2 ([middle] and [right]) illustrates the running time taken by each step of Algorithms 4 and 5. For both algorithms, the computation of the ABox closure is achieved in constant time. The time taken to compute the set of conflicts increases slightly as their number increases. This also results in an increase in total time, as there are more conflicts to go through. In the improved method (Figure 2 [right]), computing the π-repair is run in constant time with respect to the changing number of conflicts, whereas computing its closure is more time-consuming in weakly conflicting ABoxes. Computing the supports involves processing each assertion in the ABox closure through multiple
<figure><img src="image_7.png" /><figcaption>**Figure 2:** Proportion of assertions in each repair vs POS density [left]. Proportion of repair time for ABox u.5, using Algorithm 4 [middle] and Algorithm 5 [right].</figcaption></figure>

diverse ABoxes, featuring a varying number of conflicts and configuration of partial orders, led to the insight that the Cπ-repair is particularly beneficial in cases where the partial order defined over the ABox incorporates numerous incomparabilities and its subset, the π-repair, includes fewer assertions. Furthermore, the algorithms we developed are capable of batch processing, enabling an incremental computation of repairs for larger ABoxes. Future work involves checking whether polynomial time complexity holds also in combined complexity.

**Acknowledgments:** This research was supported by the European Union's Horizon research and innovation program under the MSCA-SE (Marie Skłodowska-Curie Actions Staff Exchange) [grant agreement 101086252]; Call: HORIZON-MSCA-2021-SE-01; Project title: STARWARS (STormwAteR and WastewAteR networkS heterogeneous data AI-driven management).

Ahmed Laouar's PhD is supported by the French national project ANR (Agence Nationale de la Recherche) Vivah (Vers une intelligence artificielle à visage humain) [grant number ANR-20-THIA-0004]. This research has also received support from the two French national ANR (Agence Nationale de la Recherche) projects EXPIDA (EXplainable and parsimonious Preference models to get the most out of Inconsistent DAtabases) [grant number ANR-22-CE23-0017] and AGGREEY (Une plate-forme basée sur l'argumentation pour la démocratie participative) [ANR-22-CE23-0005]. The authors would like to thank the reviewers for their useful comments.

## References

[1] M. Bienvenu, C. Bourgaux, F. Goasdoué, Querying inconsistent description logic knowledge bases under preferred repair semantics, in: Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014, pp. 996–1002.

[2] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant semantics for description logics, in: Web Reasoning and Rule Systemss, RR 2010, Bressanone/Brixen, Italy, 2010, pp. 103–117.

[3] M. Bienvenu, R. Rosati, Tractable approximations of consistent query answering for robust ontology-based data access, in: IJCAI, 2013, pp. 775–781.

[4] R. Rosati, M. Ruzzi, M. Graziosi, G. Masotti, Evaluation of techniques for inconsistency handling in OWL 2 QL ontologies, in: The Semantic Web-ISWC 2012: 11th International Semantic Web Conference, Boston, MA, USA, November 11-15, 2012, Proceedings, Part II 11, Springer, 2012, pp. 337–349.

[5] S. Benferhat, Z. Bouraoui, K. Tabia, How to select one preferred assertional-based repair from inconsistent and prioritized DL-Lite knowledge bases?, in: International Joint Conference on Artificial Intelligence (IJCAI), Buenos Aires, Argentina, 2015, pp. 1450–1456.

[6] S. Belabbes, S. Benferhat, J. Chomicki, Elect: An inconsistency handling approach for partially preordered lightweight ontologies, in: Logic Programming and Nonmonotonic Reasoning (LPNMR), Philadelphia, USA, 2019, pp. 210–223.
<figure><img src="image_7.png" /><figcaption>**Figure 2:** Proportion of assertions in each repair vs POS density [left]. Proportion of repair time for ABox u.5, using Algorithm 4 [middle] and Algorithm 5 [right].</figcaption></figure>

SQL queries to retrieve them. Although significantly faster in the improved algorithm, as shown in the results of Table 1, supports computation is the most time-intensive step of the process.

# 5. Concluding discussions

In this paper, we conducted an experimental study of data repair methods for partially ordered possibilistic knowledge bases, including three principal phases. Initially, it involved developing suitable algorithms for the computation of repairs. Subsequently, we delved into examining the inherent properties of the repair strategies and the algorithms’ to enhance their efficiency. Finally, we tested the algorithms across various scenarios to evaluate their performance. We provided an algorithmic investigation, complemented by experimental analysis of the closure-based partially ordered possibilistic repair. Starting with the repair’s characterization, we showed that leveraging certain properties allows for a more efficient repair process. Our experiments, conducted across diverse ABoxes, featuring a varying number of conflicts and configuration of partial orders, led to the insight that the Cπ-repair is particularly beneficial in cases where the partial order defined over the ABox incorporates numerous incomparabilities and its subset, the π-repair, includes fewer assertions. Furthermore, the algorithms we developed are capable of batch processing, enabling an incremental computation of repairs for larger ABoxes. Future work involves checking whether polynomial time complexity holds also in combined complexity.

# Acknowledgments

This research was supported by the European Union's Horizon research and innovation program under the MSCA-SE (Marie Skłodowska-Curie Actions Staff Exchange) [grant agreement 101086252]; Call: HORIZON-MSCA-2021-SE-01; Project title: STARWARS (STormwAteR and WastewAteR networkS heterogeneous data AI-driven management).

Ahmed Laouar's PhD is supported by the French national project ANR (Agence Nationale de la Recherche) Vivah (Vers une intelligence artificielle à visage humain) [grant number ANR-20-THIA-0004]. This research has also received support from the French national project ANR (Agence Nationale de la Recherche) EXPIDA (EXplainable and parsimonious Preference models to get the most out of Inconsistent DAtabases) [grant number ANR-22-CE23-0017].

The authors would like to thank the reviewers for their useful comments.
[7] S. Staworko, J. Chomicki, J. Marcinkowski, Prioritized repairing and consistent query answering in relational databases, AMAI 64 (2012) 209–246.

[8] M. Bienvenu, C. Bourgaux, Querying and repairing inconsistent prioritized knowledge bases: Com- plexity analysis and links with abstract argumentation, in: Principles of Knowledge Representation and Reasoning (KR), Virtual Event, 2020, pp. 141–151.

[9] A. Telli, S. Benferhat, M. Bourahla, Z. Bouraoui, K. Tabia, Polynomial algorithms for computing a single preferred assertional-based repair, KI-Künstliche Intelligenz 31 (2017) 15–30.

[10] S. Belabbes, S. Benferhat, Computing a possibility theory repair for partially preordered inconsis- tent ontologies, IEEE Transactions on Fuzzy Systems (2021) 1–10.

[11] A. Laouar, S. Belabbes, S. Benferhat, Tractable closure-based possibilistic repair for partially ordered dl-lite ontologies, in: European Conference on Logics in Artificial Intelligence, Springer, 2023, pp. 353–368.

[12] S. Belabbes, S. Benferhat, Characterizing the possibilistic repair for inconsistent partially ordered assertions, in: Information Processing and Management of Uncertainty in Knowledge-Based Systems - 19th International Conference, IPMU 2022, Milan, Italy, Proceedings, Part II, volume 1602, 2022, pp. 652–666.

[13] D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, R. Rosati, Tractable reasoning and efficient query answering in description logics: The DL-Lite family, Journal of Automated Reasoning 39 (2007) 385–429.

[14] D. Calvanese, E. Kharlamov, W. Nutt, D. Zheleznyakov, Evolution of DL-Lite knowledge bases, in: International Semantic Web Conference (1), Shanghai, China, 2010, pp. 112–128.

[15] M. Bienvenu, C. Bourgaux, F. Goasdoué, Computing and explaining query answers over inconsis- tent dl-lite knowledge bases, Journal of Artificial Intelligence Research 64 (2019) 563–644.

[16] D. Krech, G. A. Grimnes, G. Higgins, J. Hees, I. Aucamp, N. Lindström, N. Arndt, A. Sommer, E. Chuc, I. Herman, A. Nelson, J. McCusker, T. Gillespie, T. Kluyver, F. Ludwig, P.-A. Champin, M. Watts, U. Holzer, E. Summers, W. Morriss, D. Winston, D. Perttula, F. Kovacevic, R. Chateauneu, H. Solbrig, B. Cogrel, V. Stuart, Rdflib, 2023. URL: https://zenodo.org/record/6845245.

[17] R. D. Hipp, SQLite, 2020. URL: https://www.sqlite.org/index.html.

[18] A. Chortaras, D. Trivela, G. Stamou, Optimized query rewriting for owl 2 ql, in: Automated Deduction-CADE-23: 23rd International Conference on Automated Deduction, Wrocław, Poland, July 31-August 5, 2011. Proceedings 23, Springer, 2011, pp. 192–206.

[19] G. Gutin, Acyclic digraphs, Classes of Directed Graphs (2018) 125–172.

[20] M. Scutari, Learning bayesian networks with the bnlearn r package, arXiv preprint arXiv:0908.3817 (2009).

[21] C. Lutz, I. Seylan, D. Toman, F. Wolter, The combined approach to OBDA: taming role hierarchies using filters, in: The Semantic Web - ISWC 2013 - 12th International Semantic Web Conference, Sydney, Australia, 2013, pp. 314–330.
References

[1] M. Bienvenu, C. Bourgaux, F. Goasdoué, Querying inconsistent description logic knowledge bases under preferred repair semantics, in: Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014, pp. 996–1002.

[2] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant semantics for description logics, in: Web Reasoning and Rule Systemss, RR 2010, Bressanone/Brixen, Italy, 2010, pp. 103–117.

[3] M. Bienvenu, R. Rosati, Tractable approximations of consistent query answering for robust ontology-based data access, in: IJCAI, 2013, pp. 775–781.

[4] R. Rosati, M. Ruzzi, M. Graziosi, G. Masotti, Evaluation of techniques for inconsistency handling in OWL 2 QL ontologies, in: The Semantic Web-ISWC 2012: 11th International Semantic Web Conference, Boston, MA, USA, November 11-15, 2012, Proceedings, Part II 11, Springer, 2012, pp. 337–349.

[5] S. Benferhat, Z. Bouraoui, K. Tabia, How to select one preferred assertional-based repair from inconsistent and prioritized DL-Lite knowledge bases?, in: International Joint Conference on Artificial Intelligence (IJCAI), Buenos Aires, Argentina, 2015, pp. 1450–1456.

[6] S. Belabbes, S. Benferhat, J. Chomicki, Elect: An inconsistency handling approach for partially preordered lightweight ontologies, in: Logic Programming and Nonmonotonic Reasoning (LPNMR), Philadelphia, USA, 2019, pp. 210–223.

[7] S. Staworko, J. Chomicki, J. Marcinkowski, Prioritized repairing and consistent query answering in relational databases, AMAI 64 (2012) 209–246.

[8] M. Bienvenu, C. Bourgaux, Querying and repairing inconsistent prioritized knowledge bases: Complexity analysis and links with abstract argumentation, in: Principles of Knowledge Representation and Reasoning (KR), Virtual Event, 2020, pp. 141–151.

[9] A. Telli, S. Benferhat, M. Bourahla, Z. Bouraoui, K. Tabia, Polynomial algorithms for computing a single preferred assertional-based repair, KI-Künstliche Intelligenz 31 (2017) 15–30.

[10] S. Belabbes, S. Benferhat, Computing a possibility theory repair for partially preordered inconsistent ontologies, IEEE Transactions on Fuzzy Systems (2021) 1–10.

[11] A. Laouar, S. Belabbes, S. Benferhat, Tractable closure-based possibilistic repair for partially ordered dl-lite ontologies, in: European Conference on Logics in Artificial Intelligence, Springer, 2023, pp. 353–368.

[12] S. Belabbes, S. Benferhat, Characterizing the possibilistic repair for inconsistent partially ordered assertions, in: Information Processing and Management of Uncertainty in Knowledge-Based Systems - 19th International Conference, IPMU 2022, Milan, Italy, Proceedings, Part II, volume 1602, 2022, pp. 652–666.

[13] D. Calvanese, G. De Giacomo, D. Lembo, M. Lenzerini, R. Rosati, Tractable reasoning and efficient query answering in description logics: The DL-Lite family, Journal of Automated Reasoning 39 (2007) 385–429.

[14] D. Calvanese, E. Kharlamov, W. Nutt, D. Zheleznyakov, Evolution of DL-Lite knowledge bases, in: International Semantic Web Conference (1), Shanghai, China, 2010, pp. 112–128.

[15] M. Bienvenu, C. Bourgaux, F. Goasdoué, Computing and explaining query answers over
inconsistent dl-lite knowledge bases, Journal of Artificial Intelligence Research 64 (2019) 563-644.

[16] D. Krech, G. A. Grimnes, G. Higgins, J. Hees, I. Aucamp, N. Lindström, N. Arndt, A. Sommer, E. Chuc, I. Herman, A. Nelson, J. McCusker, T. Gillespie, T. Kluyver, F. Ludwig, P.-A. Champin, M. Watts, U. Holzer, E. Summers, W. Morriss, D. Winston, D. Pertula, F. Kovacevic, R. Chateauneu, H. Solbrig, B. Cogrel, V. Stuart, Rdflib, 2023. URL: https://zenodo.org/record/6845245.

[17] R. D. Hipp, SQLite, 2020. URL: https://www.sqlite.org/index.html.

[18] A. Chortaras, D. Trivela, G. Stamou, Optimized query rewriting for owl 2 ql, in: Automated Deduction-CADE-23: 23rd International Conference on Automated Deduction, Wrocław, Poland, July 31-August 5, 2011. Proceedings 23, Springer, 2011, pp. 192-206.

[19] G. Gutin, Acyclic digraphs, Classes of Directed Graphs (2018) 125-172.

[20] M. Scutari, Learning bayesian networks with the bnlearn r package, arXiv preprint arXiv:0908.3817 (2009).

[21] C. Lutz, I. Seylan, D. Toman, F. Wolter, The combined approach to OBDA: taming role hierarchies using filters, in: The Semantic Web - ISWC 2013 - 12th International Semantic Web Conference, Sydney, Australia, 2013, pp. 314-330.