# How to tractably compute a productive repair for possibilistic partially ordered DL-Lite_R ontologies?

Ahmed Laouar, Sihem Belabbes, Salem Benferhat

► To cite this version:

Ahmed Laouar, Sihem Belabbes, Salem Benferhat. How to tractably compute a productive repair for possibilistic partially ordered DL-Lite_R ontologies?. Fuzzy Sets and Systems, 2025, 510, pp.109361. 10.1016/j.fss.2025.109361. hal-05128102

HAL Id: hal-05128102

https://hal.science/hal-05128102v1

Submitted on 27 Nov 2025

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>
# How to Tractably Compute a Productive Repair for Possibilistic Partially Ordered DL-Lite<sub>R</sub> Ontologies?

Ahmed Laouar<sup>a,*</sup>, Sihem Belabbes<sup>b</sup> and Salem Benferhat<sup>a</sup>

## ARTICLE INFO

**Keywords:**

Inconsistency

Ontologies

Data Repairs

Partial Orders.

## ABSTRACT

The lightweight description logic dialect DL-Lite<sub>R</sub> offers a framework for specifying and reasoning with formal inconsistent ontologies. Basically, an ontology is a knowledge base composed of a TBox, modelling conceptual knowledge of some domain of interest, and an ABox, asserting factual knowledge about specific entities of the domain. Inconsistency in an ontology is usually handled by evaluating queries over maximal conflict-free subsets of the ABox, called data repairs. Several inconsistency-tolerant semantics, with different levels of cautiousness and computational cost, propose strategies for selecting the repairs to consider when deriving new conclusions from an inconsistent ontology. In this paper, we focus on partially ordered ontologies where a partial order relation captures the reliability levels of the ABox elements. We propose a new tractable method, called "C<sub>π</sub>-repair", which leverages possibility theory in repairing a partially ordered ABox. It proceeds in four steps as follows. First, the partial order relation is extended into a family of total orders, thus inducing as many compatible totally ordered ABoxes. Second, a single repair is computed for each compatible ABox. Third, these repairs are closed deductively in order to improve their productivity, i.e., to derive more facts. Finally, the closed repairs are intersected to produce a single repair for the initial partially ordered ABox. The main contribution of this paper is an equivalent characterization that determines the validity of the conclusions drawn with the "C<sub>π</sub>-repair" method, but without eliciting the compatible ABoxes or computing their repairs. This allows us to establish the tractability of the method by reformulating the problem using the notions of support for an assertion and dominance over the conflicts that arise between the ABox elements. Essentially, the valid conclusions are those derived from the supports that dominate all conflicts. In the last part of the paper, we explore the rationality properties of our method. We show that increasing repair productivity does not alter the satisfaction of the rationality properties. We also discuss the applicability of our proposed method to languages richer than DL-Lite<sub>R</sub> and to other inconsistency-tolerant semantics.

## 1. Introduction

The issue of reasoning with inconsistent ontologies has been widely investigated over the past two decades. The lightweight family of description logics [1], and more specifically the DL-Lite<sub>R</sub> dialect, offers a framework of choice to formalise and reason with ontologies under favourable computational properties. An ontology can be represented as a knowledge base (KB) with two components: the TBox encodes knowledge about the concepts and relationships within a particular domain of interest and is assumed to be free of errors and contradictions; the ABox contains data pieces which may contradict some conceptual rules stated in the TBox. Standard inference mechanisms fail to provide meaningful conclusions in the presence of contradictory information, since anything can be inferred.

A typical approach to dealing with inconsistency does not seek to recover consistency by rewriting or discarding some facts from the ABox. It rather computes data repairs, defined as inclusion-maximal subsets of the ABox that are consistent with respect to the TBox. Then, it evaluates the queries over the repairs instead of the inconsistent ABox. For instance, the ABox Repair (AR) semantics [2] returns the answers that follow from every repair as valid conclusions.

Furthermore, several methods focus on querying a single repair of the ABox and differ in terms of cautiousness and classes of computational complexity (refer to [3, 4] for a comprehensive survey). Some methods are adventurous because they consider conclusions to be valid if they follow from any repair of the ABox, chosen arbitrarily among all the repairs (e.g. the brave semantics [5]). In contrast, other methods are cautious and take into consideration all

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

<footnote><sup>a</sup>CRIL, Univ. Artois & CNRS, UMR 8188, Lens, 62300, France</footnote>

<footnote><sup>b</sup>LIASD, IUT de Montreuil, Univ. Paris 8, Saint-Denis, 93200, France</footnote>

<footnote>*Corresponding author.</footnote>

<footnote>laouar@cril.fr (A. Laouar); belabbes@iut.univ-paris8.fr (S. Belabbes); benferhat@cril.fr (S. Benferhat)</footnote>

<footnote>ORCID(s): 0009-0002-0028-3234 (A. Laouar); 0000-0002-8159-7122 (S. Belabbes); 0000-0002-4853-3637 (S. Benferhat)</footnote>
the repairs of the ABox when drawing conclusions. For instance, the well-known Intersection of ABox Repair (IAR) semantics [2] is considered cautious. It underestimates the AR semantics and returns the answers that follow from the intersection of all the repairs. This amounts to discarding all the elements of the ABox that are involved in conflicts, defined as inclusion-minimal subsets of the ABox that are inconsistent with respect to the TBox. Unlike the AR semantics, reasoning with the IAR semantics has the advantage of being tractable in DL-Lite<sub>R</sub> ontologies.

Initially, the IAR semantics was defined for flat ontologies where all the data pieces are considered equally reliable. In practice, however, information may not have the same level of importance or reliability. Totally ordered ontologies were then introduced to factor in different certainty levels for the data pieces. Similarly, partially ordered ontologies have been proposed to offer greater flexibility in expressing the preference relation over the data pieces, particularly when the reliability levels of the data may not be comparable on the same scale. This usually occurs when information is obtained from multiple sources. For instance, consider the case where two equally reliable sources disagree about the preference of some data piece over another. Then, a natural way to avoid assigning a higher importance level to the information provided by one of the sources is to use a partial order relation.

In the literature, only a few frameworks allow handling inconsistency in partially ordered ontologies in a tractable manner. Mainly, one can cite the Elect method [6], and the possibilistic repair method [7]. Both Elect and the possibilistic repair methods extend the partial order over the ABox into a family of total orders, thereby flattening the partially ordered ABox into a family of compatible totally ordered ABoxes. Furthermore, both methods proceed in the spirit of the IAR semantics and produce a single repair for the initial inconsistent ABox by intersecting all the repairs of its compatible ABoxes.

We focus on partially ordered ontologies and endeavour to increase the productivity of the repair, i.e., to produce more valid conclusions, without hampering tractability. The obvious approach for deriving all the consequences of the TBox axioms in terms of the ABox assertions is to use the deductive closure [8]. In fact, two extensions of the IAR semantics for flat ontologies apply the notion of deductive closure. First, the Intersection of Closed ABox Repair (ICAR) semantics [2] consists in applying the IAR semantics to the deductively closed ABox. Hence, ICAR returns all the elements of the closed ABox that are not involved in conflicts. On the one hand, ICAR is more productive (i.e., returns more conclusions) than IAR. On the other hand, ICAR may infer undesirable conclusions which follow from assertions involved in conflicts in the initial (unclosed) ABox. A second closure-based version of the IAR semantics is the Intersection of Closed Repairs (ICR) semantics [9], where the deductive closure is rather applied to all the repairs of the initial (unclosed) ABox, such that their intersection yields a single repair. The ICR semantics is more productive than IAR. However, it is well-known that closing the repairs is computationally expensive, even for flat lightweight ontologies. Indeed, while query-answering with the IAR semantics and the ICAR semantics is tractable in DL-Lite ontologies, it is coNP-complete with the ICR semantics in data complexity [9, 3].

In this paper, we define a closure-based method for partially ordered ontologies, called C<sub>π</sub>-repair, that is in full agreement with a qualitative interpretation of possibility theory. The method proceeds in four steps as follows. First, the partial order relation over the assertions of the ABox is extended into a family of total orders, thus inducing as many compatible totally ordered ABoxes. Second, a single possibilistic repair is computed for each compatible ABox. Third, each of these repairs is closed deductively in order to produce more facts. Finally, the closed repairs are intersected to yield a single repair for the initial partially ordered (unclosed) ABox. We show that the possibilistic repair computed with this method is indeed more productive than its unclosed counterpart.

Moreover, we propose an equivalent characterization for C<sub>π</sub>-repair which does not enumerate all the compatible totally ordered ABoxes and also does not compute their repairs. It intuitively considers an assertion to be a valid conclusion under the C<sub>π</sub>-repair method if it admits within the ABox supports that dominate all the conflicts of the ABox. More specifically, a support is an inclusion-minimal consistent subset of the ABox from which the assertion follows. The notion of dominance requires that for each conflict, there is a support for the said assertion where all the elements of the support are strictly more preferred than at least one element of the conflict. We use this characterization to establish the tractability of the C<sub>π</sub>-repair method in DL-Lite<sub>R</sub> ontologies.

In addition to the tractability result, we provide an in-depth analysis of the rationality properties of the C<sub>π</sub>-repair method, in terms of unconditional and conditional query-answering mechanisms. In particular, we show that the satisfaction of the properties when possibilistic query-answering is performed over the intersection of the unclosed totally ordered repairs is preserved when the deductive closure is employed.

This paper is a revised and extended version of the conference paper [10]. It is organized as follows. Section 2 recalls the basics of DL-Lite<sub>R</sub>. Section 3 discusses related work on reasoning in the presence of contradictory information under various frameworks, such as propositional logic, databases, and description logics. Section 4 recalls
the underpinnings of the methods for totally ordered and partially ordered possibilistic repairs. Section 5 defines the closure-based method Cπ-repair. Section 6 introduces the equivalent characterization, alongside the notions of support and dominance, and establishes the consistency and tractability of Cπ-repair in DL-Lite<sub>R</sub>. Section 7 studies its rationality properties for both unconditional and conditional inference relations. Section 8 discusses how the method can be applied in the context of a richer language, such as DL-Lite<sub>R,Π</sub>, which incorporates conjunction in the TBox axioms [11], as well as in the context of a different semantics, such as lexicographic preferred-based repair [12]. The last section concludes the paper.

## 2. Preliminaries

### 2.1. The description logic DL-Lite<sub>R</sub>

The lightweight family of description logics DL-Lite [1] are decidable knowledge representation languages, based on first-order predicate logic, and that are used to formalise ontologies. They have been designed to capture conceptual modelling constructs in applications with large datasets and where query answering is the most important reasoning task. Indeed, query answering from a DL-Lite knowledge base can be carried out efficiently, by reducing the problem to standard database query evaluation using query rewriting [13].

There are several variants of DL-Lite [14] such as DL-Lite<sub>core</sub>, DL-Lite<sub>R</sub>, DL-Lite<sub>F</sub>, DL-Lite<sub>A</sub> and DL-Lite<sub>Horn</sub>. In this work, we focus on DL-Lite<sub>R</sub>, also known as DL-Lite<sub>core</sub><sup>H</sup>, the dialect that provides the logical underpinning for the OWL 2 QL profile [15] which is devoted to query answering.

The DL-Lite<sub>R</sub> language is built upon a vocabulary consisting of three sets, denoted N<sub>C</sub>, N<sub>R</sub>, and N<sub>I</sub>, which are pairwise disjoint and countably infinite, and which contain concept names, role names, and individual names respectively. Let A ∈ N<sub>C</sub>, P ∈ N<sub>R</sub> and P<sup>-</sup> ∈ N<sub>R</sub> is the inverse of P. Let the negation symbol “¬” encode complement sets (of concepts and of roles). Let the existential quantifier symbol “∃” denote existential restriction. The DL-Lite<sub>R</sub> language is defined according to the following rules:

$$R := P \mid P^{-} \quad E := R \mid \neg R$$

$$B := A \mid \exists R \quad C := B \mid \neg B$$

where R denotes a basic role, and E denotes a complex role. B stands for a basic concept and C is a complex concept.

A DL-Lite<sub>R</sub> knowledge base (KB) is a pair K = (T, A) where T is a TBox and A is an ABox.

A TBox is a finite set of inclusion axioms on concepts and on roles as follows:

$$B \sqsubseteq C \quad R \sqsubseteq E$$

A concept inclusion of the form ∃P ⊑ B (respectively ∃P<sup>-</sup> ⊑ B), which requires that the domain (respectively the range) of a role P be included in a concept B, is a “domain restriction” (respectively “range restriction”). Inclusions on concepts (respectively on roles) of the type B<sub>1</sub> ⊑ B<sub>2</sub> (respectively R<sub>1</sub> ⊑ R<sub>2</sub>) are called “positive inclusion axioms”. Inclusions on concepts (respectively on roles) with the negation symbol “¬” in the right-hand side of the inclusion, such as B<sub>1</sub> ⊑ ¬B<sub>2</sub> (respectively R<sub>1</sub> ⊑ ¬R<sub>2</sub>), are called “negative inclusion axioms”. In DL-Lite<sub>R</sub>, negative axioms make it possible to specify the disjointness of at most two concepts (respectively two roles) [16].

An ABox is a finite set of membership assertions (or ground facts) of individuals on atomic concepts and atomic roles of the form:

$$A(a) \quad P(a, b) \quad \text{where } a \text{ and } b \text{ are individuals.}$$

The semantics of DL-Lite<sub>R</sub> is the standard set-theoretic semantics. An interpretation is defined as a tuple I = (Δ<sup>I</sup>, .<sup>I</sup>), where Δ<sup>I</sup> ≠ ∅ is a non-empty domain and .<sup>I</sup> is an interpretation function. The function .<sup>I</sup> associates concept names A ∈ N<sub>C</sub> to A<sup>I</sup> ⊑ Δ<sup>I</sup>, role names P ∈ N<sub>R</sub> to P<sup>I</sup> ⊑ Δ<sup>I</sup> × Δ<sup>I</sup>, and individual names a ∈ N<sub>I</sub> to a<sup>I</sup> ∈ Δ<sup>I</sup>.

In addition, the interpretation function is extended to interpret complex concepts and roles of DL-Lite<sub>R</sub> as follows:

$$(P^{-})^{I} = \{(y, x) \in \Delta^{I} \times \Delta^{I} \mid (x, y) \in P^{I}\};$$

$$(\exists R)^{I} = \{x \in \Delta^{I} \mid \text{there is } y \in \Delta^{I} \text{ such that } (x, y) \in R^{I}\};$$

$$(\neg B)^{I} = \Delta^{I} \setminus B^{I};$$

$$(\neg R)^{I} = \Delta^{I} \times \Delta^{I} \setminus R^{I}.$$
An interpretation $I$ is a model of an inclusion axiom on concepts $B \subseteq C$, denoted by $I \models B \subseteq C$, if $B^I \subseteq C^I$. Similarly, $I$ is a model of an inclusion axiom on roles $R \subseteq E$, denoted by $I \models R \subseteq E$, if $R^I \subseteq E^I$.

An interpretation $I$ is a model of a TBox $\mathcal{T}$, denoted by $I \models \mathcal{T}$, if for every axiom $\alpha$ in $\mathcal{T}$, $I \models \alpha$. A TBox $\mathcal{T}$ is incoherent if for each interpretation $I$ that is a model of $\mathcal{T}$, there is $A \in \mathcal{N}_C$, respectively $P \in \mathcal{N}_R$, such that $A^I = \emptyset$, respectively $P^I = \emptyset$. Otherwise, $\mathcal{T}$ is coherent.

An interpretation $I$ satisfies an assertion $A(a)$, denoted by $I \models A(a)$, if $a^I \in A^I$. Similarly, $I$ satisfies an assertion $P(a, b)$, denoted by $I \models P(a, b)$, if $(a^I, b^I) \in P^I$.

An interpretation $I$ is a model of an ABox $\mathcal{A}$, denoted by $I \models \mathcal{A}$, if for every assertion $\varphi$ in $\mathcal{A}$, $I \models \varphi$.

A model of the knowledge base $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ is an interpretation $I$ such that $I \models \mathcal{T}$ and $I \models \mathcal{A}$. A knowledge base is consistent if it admits at least one model, otherwise, it is inconsistent.

For more details, we refer the reader to the work given in [1]. In the remainder of this paper, we consider a DL-Lite$_R$ knowledge base, unless stated otherwise. We also assume that the TBox is coherent and stable (i.e., it does not evolve).

**Remark.** The tractability offered by DL-Lite$_R$ for reasoning and query-answering comes at the cost of expressiveness. In particular, it does not allow conjunctions on the left side of axioms, but they can be represented on the right side, where $B \subseteq C_1 \sqcap C_2$ is equivalent to $B \subseteq C_1$ and $B \subseteq C_2$. Also, union cannot be used on the right side of axioms, but it can be represented on the left side, where $B_1 \sqcup B_2 \subseteq C$ is equivalent to the axioms $B_1 \subseteq C$ and $B_2 \subseteq C$.

## 2.2. Inconsistency and conflicts

A KB in which the TBox contains only positive axioms is obviously consistent. Moreover, the positive axioms can be used to derive new assertions from the ABox. A KB in which the TBox contains negative axioms may be inconsistent, and the negative axioms serve to identify the conflicts within the ABox with respect to the TBox [1]. An assertional conflict is an inclusion-minimal inconsistent subset of ABox assertions that contradict the TBox.

**Definition 1.** (*Conflict*) Let $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ be an inconsistent KB. A conflict is a subset $C \subseteq \mathcal{A}$ such that $\langle \mathcal{T}, C \rangle$ is inconsistent, and $\forall \varphi \in C, \langle \mathcal{T}, C \setminus \{\varphi\} \rangle$ is consistent.

We denote by Cf($\mathcal{A}$) the set of all the conflicts (or the conflict set) of $\mathcal{A}$. We assume that there is no singleton ABox that violates negative axioms of the TBox, hence all the conflicts in Cf($\mathcal{A}$) are composed of exactly two assertions [1].

An important property of the DL-Lite$_R$ dialect is that computing and generating the conflict set is done in polynomial time w.r.t. the size of the ABox. Moreover, the size of the conflict set is bounded by $O(|cln(\mathcal{T})| * |\mathcal{A}|)$, where $cln(\mathcal{T})$ denotes the negative closure of the TBox (i.e., all the negative axioms that can be inferred from $\mathcal{T}$).

Note that the notion of conflict used in this work (given by Definition 1) can be seen as a particular case of the notion of justification in description logics, where the conclusion is the contradiction. Indeed, a justification is a minimal subset of an ontology (a set of TBox axioms and ABox assertions) that is sufficient to derive a conclusion (e.g. [17, 18]).

In our proposed method, conflicts play an important role in computing the repair, hence we prefer to keep the notion of conflict distinct from that of justification. This is already the case in the literature on inconsistency-tolerant semantics, like in propositional logic or lightweight description logics [4]. In other contexts, such as in ATMS (Assumption-based Truth Maintenance Systems) framework [19], the two notions are also distinct: justifications are known as labels, while conflicts are referred to as no-goods.

## 2.3. Running example

Our running example, inspired by the LUBM *univ-bench* ontology [20], describes a domain associated with the organizational structure of a university, in the context of a staff-exchange project. A faculty member can be on secondment, and an external member can visit the university. In addition, access to the university's IT resources can take two values: confidential access and shared access. Let $\mathcal{N}_C$, $\mathcal{N}_R$ and $\mathcal{N}_I$ be as follows:

- $\mathcal{N}_C = \{\text{Prof, FullProf, Head, FacMember, VisitingProf, Secondee, Resource, Confidential}\}$. Here, Prof, FullProf, Head, FacMember represent permanent positions within a university with obvious meanings. VisitingProf represents the position held by a professor visiting a university through the staff-exchange project. Secondee indicates that a faculty member is seconded in a different university than their own. Resource stands for an IT resource used at a university, and Confidential indicates that access to a resource is confidential.

- $\mathcal{N}_R = \{\text{ConfAccess}\}$. This represents the binary relation linking a user to a resource with confidential access.

- $\mathcal{N}_I = \{\text{Mary, Bob, Alice, } r_1\}$. These are individuals.
**Example 1.** Let $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ be a DL-Lite<sub>R</sub> KB, where the TBox $\mathcal{T}$ is as follows:

$$ \mathcal{T} = \left\{ \begin{array}{ll} 1. & \text{Prof} \sqsubseteq \text{FacMember} \\ 2. & \text{Head} \sqsubseteq \text{FacMember} \\ 3. & \text{FullProf} \sqsubseteq \text{Prof} \end{array} \right. \quad \left\{ \begin{array}{ll} 4. & \text{FullProf} \sqsubseteq \neg \text{VisitingProf} \\ 5. & \text{Head} \sqsubseteq \neg \text{Secondee} \\ 6. & \text{VisitingProf} \sqsubseteq \neg \exists \text{ConfAccess} \end{array} \right. \quad \left\{ \begin{array}{ll} 7. & \text{Confidential} \sqsubseteq \text{Resource} \\ 8. & \exists \text{ConfAccess} \neg \sqsubseteq \text{Confidential} \end{array} \right\} $$

Axioms 1 and 2 state that professors and department heads are faculty members. Axiom 3 states that full professors are also considered professors. Axiom 4 states that full professors and visiting professors are disjoint classes. Axiom 5 indicates that a head of department cannot be seconded to another university. Axiom 6 states that a visiting professor does not have confidential access. Axiom 7 expresses that confidential material is a resource. Axiom 8 states that the range of the role ConfAccess is Confidential (i.e., access to some resource is confidential).

The ABox $\mathcal{A}$ contains the following assertions:

$$ \mathcal{A} = \{\text{Head}(\text{Mary}), \text{ConfAccess}(\text{Bob}, r_1), \text{FullProf}(\text{Alice}), \text{Prof}(\text{Alice}), \text{Secondee}(\text{Mary}), \text{VisitingProf}(\text{Alice}), \text{VisitingProf}(\text{Bob})\} $$

These assertions state that Mary is a head of a department, Bob has confidential access to the resource $r_1$, Alice holds the positions of full professor, professor, and visiting professor, Mary is a secondee and Bob is a visiting professor.

One can easily compute the conflict set $\mathcal{Cf}(\mathcal{A}) = \{C_1, C_2, C_3\}$, where:

- $C_1 = \{\text{FullProf}(\text{Alice}), \text{VisitingProf}(\text{Alice})\}$, which contradicts axiom 4.

- $C_2 = \{\text{Head}(\text{Mary}), \text{Secondee}(\text{Mary})\}$, which contradicts axiom 5.

- $C_3 = \{\text{ConfAccess}(\text{Bob}, r_1), \text{VisitingProf}(\text{Bob})\}$, which contradicts axiom 6.

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

## 3. Related work

The problem of reasoning in the presence of contradictory information has been widely studied in various frameworks, such as propositional logic, databases, and description logics. In description logics, two kinds of logical contradictions can be distinguished. On the one hand, incoherence occurs if there is one or more unsatisfiable concepts in the ontology [18]. On the other hand, inconsistency is defined by the absence of a model for the knowledge base. Inconsistency is usually handled under the assumption that the TBox is coherent and stable [2, 4, 3] and that the ABox is inconsistent with respect to the TBox. The contributions presented in this paper fall under the scope of inconsistency.

In propositional logic, a primary method for restoring consistency uses one or more inclusion-maximal consistent sub-bases, often called repairs [21, 22, 23]. A consequence that follows from all the maximal consistent sub-bases is called a universal or inevitable consequence, and a consequence that follows from at least one consistent sub-base is called an existential consequence [23, 24]. Some approaches choose not to modify the inconsistent bases but instead modify the inference relation, like in paraconsistent logics [25]. This is the case for logics with three-valued semantics (e.g. [26]) or those based on distributive lattices[27]. Still, in the spirit of reasoning with inconsistent bases without modifying them, there are the argumentation-based methods, with or without priority (e.g. [28, 29, 30, 31]). The notion of argument (or justification) plays a key role in deciding in favour of a conclusion or its opposite. Although in our proposed method we use the notion of support similarly to that of an argument (or a justification), ultimately, our approach produces a repair for the inconsistent base. Thus, our method aligns more with methods that restore consistency, with a particular focus on tractability.

The concept of repair has also been well studied in database settings, where research efforts focus on computing consistent query answers from a database in which some facts violate the integrity constraints [32, 33, 34, 35]. Moreover, the notion of optimal repair has been proposed to identify the best repairs in a prioritized database [32]. Like in description logics, computing the repairs for a database amounts to ignoring facts or data pieces, and does not call into question the integrity constraints. To the best of our knowledge, our semantics based on partial orders has not yet been proposed in database settings.

In the context of formal ontologies and description logics, a large body of work has focused on reasoning with an inconsistent knowledge base [36, 2, 9, 3], assuming the terminological base is coherent, and taking advantage of the natural separation that description logics offer between generic information (TBox) and ground facts (ABox). This separation leads to considering the TBox as a reference for querying the information contained in the ABox. The notion
of repair in this case corresponds to an inclusion-maximal subset of the ABox that is consistent with respect to the
TBox. The main feature of this approach is that it derives consistent answers by evaluating the queries over one or
several repairs of the ABox [37, 38, 39].

The ABox Repair (AR) semantics [2, 40] runs queries universally on all the repairs of an inconsistent knowledge
base, which is a cautious approach. Query-answering under the AR semantics is usually intractable in data complex-
ity [2, 9]. The brave semantics [9], which considers a consequence to be valid if it follows from any given repair,
is more adventurous. The issue with the brave semantics is that it can potentially entail contradictory statements,
which in general is undesirable. The Intersection of ABox Repair (IAR) semantics [2] computes a single repair by
intersecting all the repairs of the ABox. IAR is tractable in data complexity in DL-Lite. However, considering the
intersection of the repairs may result in losing some consequences that have different supports in different repairs. The
semantics based on *k*-supporters and *k*-defeaters were then introduced in [5] to provide approximations for the AR
semantics. The idea is that a consequence is *k*-supported if there are *k* consistent subsets of the ABox to infer it, and
each repair of the ABox contains at least one of these consistent subsets. Other parametrized approaches for dealing
with inconsistency in related frameworks can be found in the literature, such as in Datalog ± [41, 42, 43, 44], and
existential rules [45, 46, 47, 48, 49]. Several strategies for repair selection within the framework of existential rules
have been discussed in [3]. A particular focus on computational complexity can be found in [9, 50].

Semantics such as the AR and the IAR consider all the assertions to have the same priority level. Nonetheless,
taking into account different priority levels facilitates the resolution of conflicts, for example, by retaining only
the information with a priority level considered sufficiently important. These different priority levels also serve to
differentiate repairs, by keeping only the more preferred repairs. For instance, the preferred inclusion-based repair
(PAR) semantics [51, 12, 39] extends the AR semantics when the ABox is prioritized, leading to a reduction in the
number of repairs compared to computing the non-prioritized inclusion-maximal ABox repairs. Cardinality was also
largely used as a factor for selecting the most preferred repairs [52, 39]. We shall discuss in detail the cardinality
approach in Section 8, where we explain how our proposed approach can be adapted to this semantics.

Methods that consider multiple preferred repairs, or even all the repairs such as the PAR semantics, are often
intractable. One way to achieve tractability is to generate a single preferred repair. This is already the case with the
IAR semantics in the non-prioritized case. In the presence of a priority order, several tractable approaches that generate
a single repair have been proposed. One can cite the possibilistic repair (presented in detail in Section 4), the so-called
linear repair [53, 54], the so-called non-defeated repair [12] and the Elect method [6] which extend the IAR semantics
in the case of a totally or partially ordered ABox, the grounded repair [55] where the order relation is defined only
between the assertions that are involved in conflicts. Like these inconsistency-tolerant methods which are tractable in
DL-Lite, our proposed method also aims to produce a single repair for a partially ordered ABox in a tractable way.

We wrap up this overview of related work by discussing the notion of closure, which is used in description logics to
generate larger repairs. The principle is to apply the positive axioms of the TBox to the assertions of the ABox in order to
infer all the assertions that can be derived from both. Among the approaches that have applied the deductive closure, one
can cite: the Closed ABox Repair (CAR) semantics [2], the Intersection of Closed ABox Repair (ICAR) semantics [2]
and the Intersection of Closed Repairs (ICR) semantics [9]. The CAR semantics extends the AR semantics, while both
the ICAR and ICR semantics extend the IAR semantics.

In the CAR and ICAR semantics, the closure is performed on the initial ABox before computing its repairs. The
ICAR semantics is tractable in DL-Lite [2], and returns a larger repair than with the IAR semantics. However, ICAR
may return undesirable conclusions. For instance, consider a TBox with the concept inclusion axiom FullProf ⊑ Prof, and
the concept disjointness axiom FullProf ⊑ ¬ VisitingProf. Assume now that the ABox contains two facts, FullProf(Sam)
and VisitingProf(Sam), which are in conflict according to the disjointness axiom. ICAR returns Prof(Sam) as a valid
conclusion, although it follows from FullProf(Sam), which is involved in a conflict.

The ICR semantics deductively closes the repairs of the ABox before computing their intersection. The repair
computed with ICR is larger than with IAR. However, inference with the ICR semantics has been shown to be coNP-
complete in data complexity [9, 3]. In our work, we also utilize the notion of deductive closure to yield a more
productive possibilistic repair in the case of partially ordered ontologies. However, we do not apply the deductive
closure on the ABox before computing the repairs, in order to avoid inferring undesirable results like the example
identified above with the ICAR semantics. Instead, we follow the same approach as the ICR semantics and apply the
deductive closure on the repairs of the ABox. The main advantage of our closure-based approach is that it admits an
equivalent characterization, which ensures its tractability.
# 4. Possibilistic DL-Lite<sub>R</sub>

Possibility theory and its logical counterpart possibilistic logic [56, 57, 58] are well-established frameworks for reasoning with and about incomplete and uncertain information. They are particularly suitable for capturing a priority relation among various information pieces according to some uncertainty scale. Moreover, they share close connections with Spohn's Ordinal Conditional Functions (OCF) [59] and consonant belief functions [60, 61, 62].

Uncertainty can be represented in extension using possibility distributions or in a compact way using either weighted logic (i.e., assigning weights to formulas), or graphical models (e.g. Bayesian networks [63] and credal networks [64]). Possibility theory can be defined either qualitatively or quantitatively. The main difference concerns the interpretation of the unit interval [0, 1] (which may be seen as an ordinal scale) used to quantify the plausibility of some piece of information. Qualitative possibility theory is appropriate when the uncertainty scale only encodes an order of plausibility (by means of a total preorder) on the formulas. Quantitative possibility theory is appropriate when the uncertainty degree represents a level of surprise in the sense of Spohn's OCF [65, 59] or it results from the transformation of a probability distribution into a possibility distribution [66]. An in-depth discussion about the different interpretations of possibility theory can be found in [67].

Possibilistic logic is a weighted logic where formulas are encoded in propositional logic and are assigned weights in the unit interval [0, 1] (which may be seen as an ordinal scale). The higher the weight attached to a formula, the more important or certain the formula is. A weight (or degree) is considered as a lower bound on the formula's certainty (or priority) level. The authors in [7] provide a more comprehensive overview of possibility theory in DL-Lite<sub>R</sub>.

In this paper, we choose a qualitative representation of the preference relation over the assertions of the ABox, and focus solely on the plausibility ordering between the assertions.

## 4.1. Totally Preordered Possibilistic Ontology

Let $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ be a DL-Lite<sub>R</sub> KB, where the TBox $\mathcal{T}$ is coherent, and its axioms are fully certain, while the elements of $\mathcal{A}$ may be uncertain and conflicting with respect to the TBox $\mathcal{T}$ (namely, only the ABox may be questionable).

A total preorder defined over $\mathcal{A}$, denoted by $\geq$, is a reflexive and transitive binary relation such that for any two assertions $\varphi_j$ and $\varphi_k$ in the ABox, we have either $\varphi_j \geq \varphi_k$ or $\varphi_k \geq \varphi_j$. Let $> \geq$ be the associated strict order (defined as $\varphi_j > \varphi_k$ if and only if $\varphi_j \geq \varphi_k$ holds and $\varphi_k \geq \varphi_j$ does not hold). Let $\equiv$ be the associated equivalence relation (defined by $\varphi_k \equiv \varphi_j$ if both $\varphi_k \geq \varphi_j$ and $\varphi_j \geq \varphi_k$ hold). In order to define a repair more easily, we also represent a totally preordered ABox, denoted by $\mathcal{A}_{\geq}$, as a well-ordered partition $(S_1, \dots, S_n)$ such that:

$$- S_1 \cup \dots \cup S_n = \mathcal{A}_{\geq}.$$

$$- S_1 = \{ \varphi_j \in \mathcal{A}_{\geq} : \forall \varphi_k \in \mathcal{A}_{\geq}, \varphi_j \geq \varphi_k \}.$$

$$- S_i = \{ \varphi_j \in \mathcal{A}_{\geq} \setminus (S_1 \cup \dots \cup S_{i-1}) : \forall \varphi_k \in \mathcal{A}_{\geq} \setminus (S_1 \cup \dots \cup S_{i-1}), \varphi_j \geq \varphi_k \}, \text{ for } i = 2, \dots, n.$$

The assertions in $S_1$ are the most certain and those in $S_n$ are the least certain in the ABox. The assertions in any stratum $S_i$ ($i = 1, \dots, n$) are equally certain. Partitioning the ABox into strata is in full agreement with qualitative possibility theory. It yields the same repair as in the case where priority degrees from the unit interval $[0, 1]$ are assigned to the assertions, where the assertions in the same stratum have the same priority degree. In what follows, we use stratification to express the ordering of the priority levels of the assertions.

**Definition 2.** (possibilistic repair) Let $\mathcal{K}_{\geq} = \langle \mathcal{T}, \mathcal{A}_{\geq} \rangle$ be a totally preordered KB. Let $(S_1, \dots, S_n)$ be the well-ordered partition associated with the ABox $\mathcal{A}_{\geq}$. The possibilistic repair [12] is defined by $\mathcal{R}(\mathcal{A}_{\geq}) = S_1 \cup \dots \cup S_i$ such that:

$$- \langle \mathcal{T}, S_1 \cup \dots \cup S_i \rangle \text{ is consistent, and;}$$

$$- \langle \mathcal{T}, S_1 \cup \dots \cup S_{i+1} \rangle \text{ is inconsistent (where } 1 \le i < n).$$

Note that if $\mathcal{K}_{\geq}$ is consistent, then $\mathcal{R}(\mathcal{A}_{\geq}) = \mathcal{A}_{\geq}$, and if $\langle \mathcal{T}, S_1 \rangle$ is inconsistent, then $\mathcal{R}(\mathcal{A}_{\geq}) = \emptyset$.

**Example 2.** Consider the KB from Example 1. Let Figure 1a illustrate the totally preordered ABox $\mathcal{A}_{\geq}$, represented by the well-ordered partition $S_1 \cup S_2 \cup S_3 \cup S_4 \cup S_5$. The dashed lines represent the conflicts of $\mathcal{A}_{\geq}$, as computed in Example 1. Then, Figure 1b represents the possibilistic repair $\mathcal{R}(\mathcal{A}_{\geq})$, where the crossed-out partitions are not included in the repair. One can easily check that $\langle \mathcal{T}, S_1 \cup S_2 \cup S_3 \rangle$ is consistent, but $\langle \mathcal{T}, S_1 \cup S_2 \cup S_3 \cup S_4 \rangle$ is inconsistent. Consequently, $\mathcal{R}(\mathcal{A}_{\geq}) = \{\text{Head}(\text{Mary}), \text{ConfAccess}(\text{Bob}, r_1), \text{FullProf}(\text{Alice}), \text{Prof}(\text{Alice})\}$.

<figure><img src="image_4.png" /></figure>
<figure><img src="image_5.png" /><figcaption>**Figure 1:** → denotes strict preference. — — — denotes a conflict.</figcaption></figure>

## 4.2. Partially Preordered Possibilistic Ontology

An order relation—whether total or partial—on the assertions of a knowledge base serves as a key facilitator for managing conflicts within that base. This approach, as already mentioned in the related work section, has been thoroughly studied in various logical frameworks, including propositional logic and argumentation systems (e.g., [21, 68]), databases (e.g., [69, 32, 33, 34]), conditional rules, default logics (e.g., [70, 51]), and description logics, including lightweight ontologies (e.g., [4, 12]). These studies also include benchmarks addressing totally or partially ordered information. For instance, the CQAPri benchmark provides a method for managing inconsistent lightweight knowledge bases [39, 71]. This benchmark enables the definition of both partial and total orders over an ABox (by incorporating prioritizations) to apply inconsistency-tolerant semantics, such as the preferred repair semantics [39].

Order relations can arise from various sources, such as the reliability of information sources (e.g., [72, 73]), degrees of surprise (as in Ordinal Conditional Functions, OCF [65, 74, 75]), or levels of specificity in defeasible rules that tolerate exceptions computed implicitly [76, 77, 78, 79]. Additionally, they may be based on criteria such as recency (e.g., giving priority to more recent information over older data).

Partial orders provide a flexible approach when imposing a total order on all the information is not feasible. When only a part of the priority relations is known, the known relations can be expressed, while the missing relations are treated as cases of incomparability, allowing for the management of data that cannot be fully ordered.

The need for partial orders arises, for instance, in situations where multiple sources provide distinct data, each applying its own total order based on separate ranking criteria. In such cases, comparing all the data with a single total order is not always meaningful. A partial order, with incomparability relations between elements from different sources, is therefore more suitable. This situation is exemplified by Brewka's work [51], which highlights how to obtain a partial order derived from total specificity relations, but applied individually within different parts of a knowledge base. This partial order thus avoids the need to force comparisons between unrelated elements from separate parts of the knowledge base.

In the same context, information sources may totally order the same set of assertions differently based on varying criteria, such as creation timestamps or the reliability of the source. When combined, these different total orders can induce a partial order over the same set of assertions. For instance, such a partial order can be obtained using the Pareto principle: an assertion $\varphi$ is more prioritized than another $\varphi'$ if, for all criteria (or data sources), $\varphi$ is preferred over $\varphi'$ according to each respective criterion (or data source). An example of work that uses this idea is the optimal repairs in prioritized databases proposed in [32], which uses the Pareto relation. Since inconsistency-tolerant semantics defined in databases or in description logics share the same concepts when it comes to defining assertional repairs, the methods used to define preferences in relational databases, as in [32], can thus be adapted to the framework of ABoxes used in this paper. Indeed, the work done by the authors in [55] adapts the notion of optimal repairs to DL-Lite ontologies, while using an order relation that is locally defined on conflicts. Finally, a partial order may arise due to missing data. For example, suppose a priority relation between assertions is based on a given criterion. When this criterion is well-defined for all assertions, a total order can then be established. The situation differs when the value of certain assertions is unavailable for this criterion. In this case, a partial order is more appropriate. We will discuss this situation in the conclusion with an example of geographical data from wastewater networks.
<figure><img src="image_6.png" /><figcaption>**Figure 2:** The ABox $\mathcal{A}_{\geq}$, where $\rightarrow$ denotes strict preference, and `---` denotes a conflict.</figcaption></figure>

In this section, we consider a partial preorder $\geq$ defined over an ABox $\mathcal{A}$ as a reflexive and transitive binary relation, for which some elements may be incomparable. Let $▷$ be the associated strict order, $\equiv_{▷}$ be the associated equivalence, and $▷▷$ be the incomparability relation. Then, for any two assertions $\varphi_j$ and $\varphi_k$ of the ABox, $\varphi_j \succcurlyeq \varphi_k$ means that neither $\varphi_j \geq \varphi_k$ nor $\varphi_k \geq \varphi_j$ holds. We denote by $\mathcal{A}_{\geq}$ the partially preordered ABox.

The possibilistic repair was extended in [7] to cover the case of partially preordered DL-Lite<sub>R</sub> KBs. The fundamental idea is to extend the partial preorder into a family of total preorders, which preserve the ordering between the assertions. This induces totally preordered ABoxes called compatible bases. Formally, a totally preordered ABox $\mathcal{A}_{\geq}$ is said to be compatible with the partially preordred ABox $\mathcal{A}_{\geq}$, if for all $\varphi_j$ and $\varphi_k$ of $\mathcal{A}_{\geq}$, whenever $\varphi_j \geq \varphi_k$, we also have $\varphi_j \geq \varphi_k$. Intuitively, each case of incomparability $\varphi_j \succcurlyeq \varphi_k$ may be extended into one of the three total order relations: (i) $\varphi_j > \varphi_k$, (ii) $\varphi_k > \varphi_j$ or (iii) $\varphi_j \equiv \varphi_k$.

**Definition 3.** (partially preordered $\pi$-repair) Let $\mathcal{K}_{\geq} = \langle \mathcal{T}, \mathcal{A}_{\geq} \rangle$ be a partially preordered KB. The possibilistic repair for a partially preordered ABox, denoted $\pi(\mathcal{A}_{\geq})$, is computed as follows:

1. First, extend the partial preorder $\geq$ into a family of m total preorders, denoted by $\geq_i$, for $i = 1, \dots, m$. Then each extension $\geq_i$ defines an ABox $\mathcal{A}_{\geq_i}$ that is compatible with $\mathcal{A}_{\geq}$.

2. For each compatible base $\mathcal{A}_{\geq_i}$, compute the totally preordered possibilistic repair $\mathcal{R}(\mathcal{A}_{\geq_i})$, given by Definition 2.

3. Finally, intersect the repairs $\mathcal{R}(\mathcal{A}_{\geq_i})$ to obtain the partially preordered possibilistic repair: $\pi(\mathcal{A}_{\geq}) = \bigcap_{i=1}^{m} \mathcal{R}(\mathcal{A}_{\geq_i})$.

The repair $\pi(\mathcal{A}_{\geq})$ has been characterized tractably [7], without exhibiting the extensions $\geq_i$ of $\geq$, using the notion of $\pi$-accepted assertions. Intuitively, an assertion is $\pi$-accepted if it is strictly more certain than at least one assertion from each conflict. The conflict set $\text{Cf}(\mathcal{A}_{\geq})$ can be computed in a similar fashion as in the case of a flat KB.

**Definition 4.** ($\pi$-accepted assertion) Let $\mathcal{K}_{\geq} = \langle \mathcal{T}, \mathcal{A}_{\geq} \rangle$ be a partially preordered KB, and $\text{Cf}(\mathcal{A}_{\geq})$ its conflict set. An assertion $\varphi_j \in \mathcal{A}_{\geq}$ is $\pi$-accepted if, for all $\tilde{C} \in \text{Cf}(\mathcal{A}_{\geq})$, there is $\varphi_k \in \tilde{C}$, $\varphi_j \neq \varphi_k$, such that $\varphi_j \succcurlyeq \varphi_k$.

The repair $\pi(\mathcal{A}_{\geq})$ is the set of all the $\pi$-accepted assertions in $\mathcal{A}_{\geq}$, and it can be computed in polynomial time in the size of $\mathcal{A}_{\geq}$ in DL-Lite<sub>R</sub> ontologies [7].

**Example 3.** We continue our example. Let Figure 2 illustrate the partially preordered ABox $\mathcal{A}_{\geq}$, where $\geq$ is given by:

- Head(Mary)▷ FullProf(Alice)▷ Secondee(Mary)

- Head(Mary)▷ Prof(Alice)▷ VisitingProf(Alice)

- Head(Mary) and ConfAccess(Bob, r<sub>1</sub>) are equally certain

- VisitingProf(Alice) and VisitingProf(Bob) are equally certain.

Both Head(Mary) and ConfAccess(Bob, r<sub>1</sub>) are strictly preferred to at least one element of each conflict, namely, VisitingProf(Alice) ∈ C<sub>1</sub>, Secondee(Mary) ∈ C<sub>2</sub> and VisitingProf(Bob) ∈ C<sub>3</sub>. Thus, both assertions are $\pi$-accepted.

None of the remaining assertions is $\pi$-accepted. For instance, we have the conflict $C_2 = \{\text{Head(Mary), Secondee(Mary)}\}$ and Prof(Alice)▷ Head(Mary), Prof(Alice)▷ Secondee(Mary). Therefore, the partially preordered possibilistic repair is:

$$ \pi(\mathcal{A}_{\geq}) = \{\text{Head(Mary), ConfAccess(Bob, r<sub>1</sub>)}\}. $$

<figure><img src="image_7.png" /></figure>
## 5. Closure-Based Possibilistic Repair for Partially Preordered Ontologies

In this section, we present a new method for repairing partially preordered knowledge bases, which yields more productive repairs, using the notion of positive deductive closure. Formally, productivity is defined as follows [46]:

**Definition 5.** Let $s_1$ and $s_2$ be two inconsistency-tolerant semantics. We say that $s_1$ is more productive than $s_2$, if for any knowledge base $K = \langle \mathcal{T}, A \rangle$ and any query $q$, if $K \models^{s_2} q$, then $K \models^{s_1} q$. Where $\models^s$ denotes the inference using a given inconsistency-tolerant semantics $s$.

Intuitively, productivity (Definition 5) refers to the idea that an inconsistency-tolerant semantics generates more answers to a query than another semantics. For example, consider two well-known inconsistency-tolerant semantics: the AR semantics [2] (where a query answer is valid if it can be derived from every repair of the ABox) and the IAR semantics [2] (which evaluates queries solely on the intersection of the repairs). Then, the AR semantics is more productive than the IAR semantics.

Another example is the ICR semantics [9], which deductively closes the repairs, is more productive than the IAR semantics [2]. However, ICR is not tractable. Let us first recall the definition of the closure operator in the case of a flat KB [1, 12], which can also be applied in the partially preordered case.

**Definition 6.** (Closed ABox) Let $K = \langle \mathcal{T}, A \rangle$ be a DL-Lite<sub>R</sub> KB. Let $\mathcal{T}_p$ denote the set of all the positive inclusion axioms of $\mathcal{T}$. The deductive closure of $A$ with respect to the TBox $\mathcal{T}$ is defined as:

$$ \mathrm{cl}(A) = \{ B(a) \mid \langle \mathcal{T}_p, A \rangle \models B(a) \text{ such that } B \text{ is a concept name in } \mathcal{T}, a \text{ is an individual in } A \} \cup \\ \{ R(a, b) \mid \langle \mathcal{T}_p, A \rangle \models R(a, b) \text{ such that } R \text{ is a role name in } \mathcal{T}, a \text{ and } b \text{ are individuals in } A \}. $$

Where $\models^s$ is the standard DL-Lite<sub>R</sub> inference relation.

The positive deductive closure takes into consideration all the assertions that are implied by the positive inclusion axioms of the TBox and the elements of the ABox, alongside the assertions that are explicitly included in the ABox. It is similar to the notion of ABox completion, which was used in the context of the combined approach for reasoning with DL-Lite<sub>R</sub> knowledge bases [80]. The main difference between the two notions is that the deductive closure only considers the individuals that are present in the ABox.

**Example 4.** Consider the KB of Example 1. The set of positive inclusion axioms of $\mathcal{T}$, denoted by $\mathcal{T}_p$ contains the axioms 1, 2, 3, 7, and 8 of $\mathcal{T}$, namely:

$$ \mathcal{T}_p = \left\{ \begin{array}{ll} 1. & \text{Prof} \sqsubseteq \text{FacMember} \\ 2. & \text{Head} \sqsubseteq \text{FacMember} \end{array} \right. \quad \begin{array}{ll} 3. & \text{FullProf} \sqsubseteq \text{Prof} \\ 7. & \text{Confidential} \sqsubseteq \text{Resource} \end{array} \quad \begin{array}{ll} 8. & \exists \text{ConfAccess}^- \sqsubseteq \text{Confidential} \\ \end{array} $$

The ABox $A$ is:

$$ A = \{ \text{Head}(\text{Mary}), \text{ConfAccess}(\text{Bob}, r_1), \text{FullProf}(\text{Alice}), \text{Prof}(\text{Alice}), \text{Secondee}(\text{Mary}), \text{VisitingProf}(\text{Alice}), \text{VisitingProf}(\text{Bob}) \}. $$

The positive deductive closure of $A$, denoted by $\mathrm{cl}(A)$, is given by:

$$ \mathrm{cl}(A) = A \cup \{ \text{FacMember}(\text{Mary}), \text{Confidential}(r_1), \text{Resource}(r_1), \text{FacMember}(\text{Alice}) \}. $$

The new assertions are obtained as follows:

- FacMember(Mary) from the assertion Head(Mary) applied to axiom 2.

- Confidential(r<sub>1</sub>) from the assertion ConfAccess(Bob, r<sub>1</sub>) applied to axiom 8.

- Resource(r<sub>1</sub>) from the assertion ConfAccess(Bob, r<sub>1</sub>) applied to axioms 8 and 7.

- FacMember(Alice) from Prof(Alice) applied to axiom 1 and also from FullProf(Alice) applied to axioms 3 and 1.

□

For partially preordered ABoxes, the deductive closure can be applied at two different levels to obtain a larger repair. The first option involves closing the initial ABox $A \triangleright$, in the spirit of the ICAR semantics for flat ontologies [2].
Step 1: Extend the partially preordered ABox $\mathcal{A}_{\supseteq}$ into a family of $m$ totally preordered ABoxes, $A_{\ge 1}, \dots, A_{\ge m}$.

Step 2: Compute the repair $\mathcal{R}(A_{\ge i})$ of each compatible base.

Step 3: Deductively close each repair $cl(\mathcal{R}(A_{\ge i}))$.

Step 4: Intersect all the closed repairs to obtain the closure-based repair $c\pi(\mathcal{A}_{\supseteq})$.

<figure><img src="image_8.png" /><figcaption>Figure 3: The process of computing the Cπ-repair</figcaption></figure>

The second option closes each one of the possibilistic repairs $\mathcal{R}(A_{\ge i})$ associated with the compatible ABoxes $A_{\ge i}$, in the spirit of the ICR semantics for flat ontologies [9].

In the first option, closing the ABox $\mathcal{A}_{\supseteq}$ before computing the repair may lead to undesirable conclusions. For instance, assume a DL-Lite<sub>R</sub> KB where $\mathcal{T} = \{\text{FullProf} \sqsubseteq \text{Prof}, \text{FullProf} \sqsubseteq \neg \text{VisitingProf}\}$ and $\mathcal{A}_{\supseteq} = \{\text{FullProf}(\text{Alice}), \text{VisitingProf}(\text{Alice})\}$. Then the positive deductive closure is $cl(\mathcal{A}_{\supseteq}) = \{\text{FullProf}(\text{Alice}), \text{VisitingProf}(\text{Alice}), \text{Prof}(\text{Alice})\}$ and the conflict set is $Cf(cl(\mathcal{A}_{\supseteq})) = \{\text{FullProf}(\text{Alice}), \text{VisitingProf}(\text{Alice})\}$. Assume the following partial order $\text{Prof}(\text{Alice}) \supset \text{VisitingProf}(\text{Alice}) \supset \text{FullProf}(\text{Alice})$. Using Definition 4, both $\text{Prof}(\text{Alice})$ and $\text{VisitingProf}(\text{Alice})$ are $\pi$-accepted in $cl(\mathcal{A}_{\supseteq})$. However, including $\text{Prof}(\text{Alice})$ in the repair is questionable, since it is supported by $\text{FullProf}(\text{Alice})$ which conflicts with the $\pi$-accepted assertion $\text{VisitingProf}(\text{Alice})$. Another issue with this approach concerns the reliability of the assertions that are inferred from incomparable elements. For instance, assume a KB where the TBox is $\mathcal{T} = \{\text{Head} \sqsubseteq \text{Prof}, \text{FullProf} \sqsubseteq \text{Prof}\}$ and the ABox is $\mathcal{A}_{\supseteq} = \{\text{FullProf}(\text{Bob}), \text{Head}(\text{Bob})\}$, where $\text{FullProf}(\text{Bob}) \not\supseteq \text{Head}(\text{Bob})$. The deductive closure is $cl(\mathcal{A}_{\supseteq}) = \{\text{FullProf}(\text{Bob}), \text{Head}(\text{Bob}), \text{Prof}(\text{Bob})\}$ and all the assertions are $\pi$-accepted (since the KB is consistent). The question is which certainty level should be assigned to $\text{Prof}(\text{Bob})$. The intuition is to consider $\text{Prof}(\text{Bob})$ to be at least as certain as $\text{FullProf}(\text{Bob})$ and $\text{Head}(\text{Bob})$, but this cannot be easily defined in general.

In this paper, we opt for closing the possibilistic repairs $\mathcal{R}(A_{\ge i})$ of the compatible ABoxes $A_{\ge i}$. A more productive repair for $\mathcal{A}_{\supseteq}$ can then be computed from the intersection of the closed repairs $cl(\mathcal{R}(A_{\ge i}))$. Formally:

**Definition 7.** (Cπ-repair) Let $\mathcal{A}_{\supseteq}$ be a partially preordered ABox. Let $A_{\ge i}$, with $i = 1, \dots, m$, denote all its compatible bases and let $\mathcal{R}(A_{\ge i})$ be the associated possibilistic repair. The closure-based partially preordered possibilistic repair of $\mathcal{A}_{\supseteq}$, denoted $c\pi(\mathcal{A}_{\supseteq})$, is obtained as follows:

$$c\pi(\mathcal{A}_{\supseteq}) = \bigcap_{i=1}^{m} \{cl(\mathcal{R}(A_{\ge i})) \mid A_{\ge i} \text{ is compatible with } \mathcal{A}_{\supseteq.}\}$$

Figure 3 shows the Cπ-repair process of Definition 7. Obviously, this method is naive and computationally expensive, since enumerating all the compatible ABoxes may be exponential in the worst case.

**Example 5.** Consider the KB of Example 3, with the conflicts and the partial preorder illustrated in Figure 2. Extending the partial preorder $\supseteq$ into $m$ compatible total preorders $\ge_i$ always returns the subset $\{\text{Head}(\text{Mary}), \text{ConfAccess}(\text{Bob}, r_1)\}$ as the most certain stratum in any $A_{\ge i}$. Moreover, since $\text{Prof}(\text{Alice}) \not\supseteq \text{FullProf}(\text{Alice})$, the second most certain stratum in any $A_{\ge i}$ contains either $\text{Prof}(\text{Alice})$ or $\text{FullProf}(\text{Alice})$ or both. Hence, in any $A_{\ge i}$ compatible with $\mathcal{A}_{\supseteq}$, the first two strata are like one of the three cases depicted by Figure 4. Therefore, for any $A_{\ge i}$, the associated repair $\mathcal{R}(A_{\ge i})$ either contains $\text{FullProf}(\text{Alice})$, or $\text{Prof}(\text{Alice})$, or both. Since the TBox contains the axiom $\text{FullProf} \sqsubseteq \text{Prof}$, we conclude that for any $A_{\ge i}$, we have $\langle \mathcal{T}, \mathcal{R}(A_{\ge i}) \rangle \models \text{Prof}(\text{Alice})$. Moreover, using the axiom $\text{Prof} \sqsubseteq \text{FacMember}$, we also obtain $\langle \mathcal{T}, \mathcal{R}(A_{\ge i}) \rangle \models \text{FacMember}(\text{Alice})$. This means that for any $A_{\ge i}$, both $\text{Prof}(\text{Alice})$ and $\text{FacMember}(\text{Alice})$ are in $cl(\mathcal{R}(A_{\ge i}))$. Therefore:

$$c\pi(\mathcal{A}_{\supseteq}) = \left\{ \begin{array}{l} \text{Head}(\text{Mary}), \text{FacMember}(\text{Mary}), \text{ConfAccess}(\text{Bob}, r_1), \text{Confidential}(r_1), \text{Resource}(r_1), \\ \text{Prof}(\text{Alice}), \text{FacMember}(\text{Alice}) \end{array} \right\}$$

<figure><img src="image_9.png" /></figure>
<figure><img src="image_10.png" /><figcaption>Figure 4: → denotes strict preference. — — denotes a conflict.</figcaption></figure>

*Remark.* Consider the ABox $\mathcal{A}_{\Delta}$ shown in Example 5. In Example 3, we obtained its partially preordered possibilistic repair as $\pi(\mathcal{A}_{\Delta}) = \{\text{Head(Mary), ConfAccess(Bob, r_1)}\}$. Using the operator from Definition 6 to close this repair returns:

$$cl(\pi(\mathcal{A}_{\Delta})) = \{\text{Head(Mary), FacMember(Mary), ConfAccess(Bob, r_1), Confidential(r_1), Resource(r_1)}\}.$$

The repair $c\pi(\mathcal{A}_{\Delta})$ is larger than both $\pi(\mathcal{A}_{\Delta})$ and its closure $cl(\pi(\mathcal{A}_{\Delta}))$. Namely:

$$\pi(\mathcal{A}_{\Delta}) \subseteq cl(\pi(\mathcal{A}_{\Delta})) \subseteq c\pi(\mathcal{A}_{\Delta}).$$

The proof of this result will be given in the next section.

# 6. Characterization

In this section, we propose an equivalent characterization of the closure-based repair introduced in Definition 7, without enumerating all the compatible bases. We first introduce two notions called support and dominance. The support (or an argument) of an assertion is an inclusion-minimal consistent subset of the ABox that allows deriving it.

**Definition 8.** (Support) Let $\mathcal{K} = \langle \mathcal{T}, \mathcal{A} \rangle$ be a DL-Lite<sub>R</sub> KB. Let $B$ be a concept name and $R$ be a role name in $\mathcal{T}$. Let a and b be two individuals in $\mathcal{A}$. The subset $B \subseteq \mathcal{A}$ is a support for $B(a)$ (resp. $R(a, b)$) in $\mathcal{A}$ if:

- $\langle \mathcal{T}, B \rangle$ is consistent, and

- $\langle \mathcal{T}, B \rangle \models B(a)$, (resp. $\langle \mathcal{T}, B \rangle \models R(a, b)$), and

- $\forall B' \subsetneq B, \langle \mathcal{T}, B' \rangle \not\models B(a)$, (resp. $\langle \mathcal{T}, B' \rangle \not\models R(a, b)$).

Where $\models$ is the standard DL-Lite<sub>R</sub> inference relation. Note that supports in DL-Lite<sub>R</sub> contain at most one assertion.

A support can also be seen as a particular case of a justification, which is defined as the minimal subset of an ontology (a set of TBox axioms and ABox assertions) that is sufficient to derive a conclusion [17, 18]. In this work, a support consists of only ABox assertions, as it has been used in the context of inconsistency handling.

**Example 6.** We continue Example 5. The subset $\{\text{Prof(Bob)}\}$ of the ABox supports $\text{FacMember}(\text{Bob})$ since it is consistent with respect to the TBox, it is minimal with respect to the set inclusion relation, and we have $\langle \mathcal{T}, \{\text{Prof}(\text{Bob})\} \rangle \models \text{FacMember}(\text{Bob})$. $\square$

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

Next, we introduce the dominance relation, which represents a way to extend the partial preorder defined over an ABox into a partial preorder defined over subsets of the ABox. This allows to compare supports and conflicts. Intuitively, the dominance of a partially preordered subset over another requires that each element of the former be strictly more certain than at least one element of the latter.

**Definition 9.** (Dominance) Let $\mathcal{K}_{\Delta} = \langle \mathcal{T}, \mathcal{A}_{\Delta} \rangle$ be a partially preordered KB. Let $B_1 \subseteq \mathcal{A}_{\Delta}$ and $B_2 \subseteq \mathcal{A}_{\Delta}$. We say that $B_1$ dominates $B_2$ if: for all $\varphi_j \in B_1$, there is $\varphi_k \in B_2$ such that $\varphi_j \triangleright \varphi_k$.
<figure><img src="image_12.png" /><figcaption>**Figure 5:** $\rightarrow$ denotes strict preference.</figcaption></figure>

**Example 7.** Let $B_1, B_2$ and $B_3$ be three subsets of $A_\geq$ of Example 3, as illustrated by Figure 5. $B_1$ dominates $B_2$ because: Head(Mary) $\triangleright$ Prof(Alice) and FullProf(Alice) $\triangleright$ Secondee(Mary). However, $B_1$ does not dominate $B_3$ because: FullProf(Alice) $\not\triangleright$ Prof(Alice) and FullProf(Alice) $\not\triangleright$ VisitingProf(Alice). $\square$

Before characterizing $C\pi$-repair in general, we first discuss the special case where the KB is consistent, i.e., the conflict set is empty. Hence, $C\pi$-repair simply amounts to applying standard DL-Lite<sub>R</sub> inference.

**Lemma 1.** Let $K_\geq = \langle \mathcal{T}, A_\geq \rangle$ be a consistent, partially preordered KB, and $\text{Cf}(A_\geq) = \emptyset$. Consider $\text{cl}(\cdot)$, given by Definition 6. Let $\varphi$ be an assertion. Then: $c\pi(A_\geq) = \text{cl}(A_\geq)$. Equivalently:

$$ \varphi \in c\pi(A_\geq) \text{ if and only if there is } B \subseteq A_\geq \text{ such that } \langle \mathcal{T}, B \rangle \models \varphi. $$

*Proof.* The proof is straightforward. Let $K_\geq = \langle \mathcal{T}, A_\geq \rangle$ be a consistent KB. Let $c\pi(A_\geq)$ be as given in Definition 7. Since $A_\geq$ is consistent, for each compatible base $A_{\geq i}$, $i = 1, \dots, m$, the possibilistic repair is simply the whole ABox, namely $\mathcal{R}(A_{\geq i}) = A_{\geq i}$ (see Definition 2). Hence, $c\pi(A_\geq) = \bigcap_{i=1}^m \{\text{cl}(A_{\geq i})\}$, which is equivalent to $\text{cl}(A_\geq)$. $\square$

In the rest of this paper, we focus on inconsistent KB's. We use the notions of dominance and support (see Definitions 8 and 9) to equivalently characterize the assertions in the $C\pi$-repair. The aim is to avoid enumerating all the totally preordered extensions of $A_\geq$. Intuitively, an assertion $\varphi$ belongs to $C\pi$-repair if and only if, for every conflict C in the ABox, there is a support B for $\varphi$ that dominates C. We provide two propositions to establish this result.

**Proposition 1.** Let $K_\geq = \langle \mathcal{T}, A_\geq \rangle$ be an inconsistent, partially preordered KB. Let $\text{Cf}(A_\geq)$ be its conflict set and let $\varphi$ be an assertion. If for all $C \in \text{Cf}(A_\geq)$, there is $B \subseteq A_\geq$ such that:

1. B supports $\varphi$ (as per Definition 8), and

2. B dominates C (as per Definition 9),

$$ \text{then } \varphi \in c\pi(A_\geq). $$

*Proof.* Let $K_\geq = \langle \mathcal{T}, A_\geq \rangle$ be a partially preordered KB, $\text{Cf}(A_\geq)$ be its non-empty conflict set, and $\varphi$ be an assertion. Assume that the following condition (from our proposition) is true, and let us show that $\varphi \in c\pi(A_\geq)$:

$$ \text{for all } C \in \text{Cf}(A_\geq), \text{ there is } B \subseteq A_\geq \text{ such that } B \text{ supports } \varphi \text{ and } B \text{ dominates } C \dots (*) $$

From Definition 7, $\varphi \in c\pi(A_\geq)$ means that for each total preorder $\geq$ compatible with $\geq$, we have $\langle \mathcal{T}, \text{cl}(\mathcal{R}(A_{\geq})) \rangle \models \varphi$, and thus, $\langle \mathcal{T}, \mathcal{R}(A_{\geq}) \rangle \models \varphi$. Let $\geq_1$ be a given compatible total preorder and $(S_1, \dots, S_n)$ be its associated well-ordered partition. Let $\mathcal{R}(A_{\geq_1}) = (S_1 \cup \dots \cup S_i)$ be the possibilistic repair as given in Definition 2.

Now let us show that indeed $\langle \mathcal{T}, \mathcal{R}(A_{\geq_1}) \rangle \models \varphi$. Recall from Definition 2 that:

- $\langle \mathcal{T}, \mathcal{R}(A_{\geq_1}) \rangle$ is consistent, and;

- $\langle \mathcal{T}, \mathcal{R}(A_{\geq_1}) \cup S_{i+1} \rangle$ is inconsistent.

Hence, there is at least one conflict $C' \in \text{Cf}(A_\geq)$ such that $C' \subseteq (\mathcal{R}(A_{\geq_1}) \cup S_{i+1})$.

By (*): the assertion $\varphi$ has a support $B$, such that $B$ dominates $C'$. By Definition 9, $B$ dominates $C'$ means that for all $\phi \in B$, there is $\psi \in C'$ such that $\phi \triangleright \psi$. Since $\geq_1$ extends $\geq$, this also means that for all $\phi \in B$, there is $\psi \in C'$ such that $\phi >_1 \psi$.

Therefore, for all $\phi \in B$, we have $\phi \in S_1 \cup \dots \cup S_i$. Hence, $B \subseteq \mathcal{R}(A_{\geq_1})$. By Definition 8, $\langle \mathcal{T}, B \rangle \models \varphi$, so $\langle \mathcal{T}, \mathcal{R}(A_{\geq_1}) \rangle \models \varphi$. Since this result applies to all the compatible preorders, we conclude that $\varphi \in c\pi(A_\geq)$. $\square$
We illustrate this result with our running example.

**Example 8.** Let us use Proposition 1 to check that the assertion *Prof(Alice) is indeed in cπ(A_≥)*, as established in Example 5. Recall the conflicts $C_1 = \{\text{FullProf}(Alice), \text{VisitingProf}(Alice)\}$, $C_2 = \{\text{Head}(Mary), \text{Secondee}(Mary)\}$ and $C_3 = \{\text{ConfAccess}(Bob, r_1), \text{VisitingProf}(Bob)\}$. For each conflict, we exhibit a dominating support for Prof(Alice), namely:

- $B_1 = \{\text{Prof}(Alice)\}$ supports Prof(Alice) and $B_1$ dominates $C_1$, since Prof(Alice) $\triangleright$ VisitingProf(Alice),

- $B_2 = \{\text{FullProf}(Alice)\}$ supports Prof(Alice) and $B_2$ dominates $C_2$, since FullProf(Alice) $\triangleright$ Secondee(Mary), and;

- $B_1$ dominates $C_3$, since Prof(Alice) $\triangleright$ VisitingProf(Bob).

☐

Proposition 2 shows that the other direction of Proposition 1 is also true. It also covers the particular case of an assertion without support, which cannot belong to $C\pi$-repair.

**Proposition 2.** Let $K_\ge = \langle T, A_\ge \rangle$ be an inconsistent, partially preordered KB. Let $Cf(A_\ge)$ be its conflict set and $\varphi$ be an assertion. If $\varphi \in c\pi(A_\ge)$, then for all $C \in Cf(A_\ge)$, there is $B \subseteq A_\ge$ such that:

- *B* supports *φ* (as per *Definition 8*), and

- *B* dominates *C* (as per *Definition 9*).

*Proof.* Let $\varphi \in c\pi(A_\ge)$ and assume that the following condition is false:

for all $C \in Cf(A_\ge)$, there is $B \subseteq A_\ge$ such that *B* supports $\varphi$ and *B* dominates *C* ... (*)

We distinguish two cases:

1. There is no support for $\varphi$. This means that for any total preorder $\ge$ compatible with $\ge'$, there will be no support in $A_\ge$ (the notion of support is independent of the fact that the ABox is flat, totally preordered or partially preordered). This also means there will be no support in $R(A_\ge)$. Hence, this means that $\varphi$ belongs neither to $R(A_\ge)$ nor to its closure $cl(R(A_\ge))$. But this contradicts our assumption that $\varphi \in c\pi(A_\ge)$.

2. There is at least one support for $\varphi$. Then, (*) is false means that there is a conflict that is not dominated by any support of $\varphi$. Let $C'$ be such a conflict. Then:

for any $B \subseteq A_\ge$ a support of $\varphi$, *B* does not dominate $C'$ ... (**)

*B* does not dominate $C'$ means that there is $\phi \in B$ an assertion such that for all $\psi \in C'$, either $\psi \triangleright \phi$ or $\psi \equiv_\ge \phi$ or $\psi \bowtie \phi$ (namely, $\phi$ is not strictly preferred to $\psi$). $\psi \equiv_\ge \phi$ means that both $\psi \ge \phi$ and $\phi \ge \psi$ hold. The idea is then to construct a sequence of partial preorders ($\ge_0, \ge_1, \dots, \ge_m$) where $\ge_0 = \ge$ and $\ge_i$ ($i \ge 1$) is obtained from $\ge_{i-1}$ by transforming one case of incomparability between an element $\psi$ of *C* and an element $\phi$ of a support *B* of $\varphi$ into a preference of $\psi$ over $\phi$. The last partial preorder $\ge_m$ is such that there is no incomparability between the elements of $C'$ and of *B*. One can easily check that each compatible preorder of $\ge_i$ is also a compatible preorder of any $\ge_j$ (with $j < i$) and so of $\ge_0 = \ge$. One can also check that the condition (***) holds for each $\ge_i$. At step *m*, *B* does not dominate $C'$ means that there is $\phi \in B$ s.t. for all $\psi \in C'$ we have, either $\psi \ge_m \phi$ or $\psi \triangleright_m \phi$ because there is no incomparability relation in $\ge_m$. Lastly, let $\ge$ be a total preorder compatible with $\ge_m$ and let ($S_1, \dots, S_n$) be its associated well-ordered partition and $R(A_\ge) = S_1 \cup \dots \cup S_n$ its repair. It is easy to see that there is no support *B* of $\varphi$ s.t. $B \subseteq R(A_\ge)$. Indeed, if this were the case, then $C' \subseteq R(A_\ge)$, which is impossible since $R(A_\ge)$ is consistent. The fact that $\varphi$ has no support in $R(A_\ge)$ also means that $\varphi \notin cl(R(A_\ge))$. This contradicts our assumption $\varphi \in c\pi(A_\ge)$. ☐

We illustrate this result with a revised version of our running example.

**Example 9.** Let $K_\ge' = \langle T, A_\ge' \rangle$ be a KB where the TBox *T* and the assertions of the ABox $A_\ge'$ are the same from Example 1. However, a different partial preorder $\ge'$ is applied over the assertions as illustrated in Figure 6a, alongside the conflicts of $A_\ge'$.

Consider the assertion *Prof(Alice)*. Let us show that it cannot belong to $c\pi(A_\ge')$ if there is a conflict $C_i \in Cf(A_\ge')$ such that none of its supports dominates $C_i$. *Prof(Alice)* has two supports in the ABox, namely, $B_1 = \{\text{Prof}(Alice)\}$ and $B_2 = \{\text{FullProf}(Alice)\}$. The conflict set is $Cf(A_\ge') = \{C_1, C_2, C_3\}$ where:
<figure><img src="image_13.png" /><figcaption>Figure 6: → : strict preference, — — : conflict.</figcaption></figure>

- $C_1 = \{\text{FullProf}(\text{Alice}), \text{VisitingProf}(\text{Alice})\}$.

- $C_2 = \{\text{Head}(\text{Mary}), \text{Secondee}(\text{Mary})\}$.

- $C_3 = \{\text{ConfAccess}(\text{Bob}, r_1), \text{VisitingProf}(\text{Bob})\}$.

We only focus on $C_1$ and $C_3$, because $C_2$ is dominated by $B_2$.

Both assertions in $C_3$ are more certain than the only assertion in the support $B_1$, hence $B_1$ does not dominate $C_3$. Similarly, $\text{FullProf}(\text{Alice}) \in C_1$ is incomparable with $\text{Prof}(\text{Alice}) \in B_1$ and $\text{VisitingProf}(\text{Alice}) \in C_1$ is strictly preferred to $\text{Prof}(\text{Alice}) \in B_1$, hence $B_1$ does not dominate $C_1$.

Regarding the support $B_2$, following the proof of Proposition 2, we transform the incomparability $\text{VisitingProf}(\text{Alice}) \not\prec_1^\prime \text{FullProf}(\text{Alice})$ into the strict preference $\text{VisitingProf}(\text{Alice}) \succ_1^\prime \text{FullProf}(\text{Alice})$ to obtain the partial preorder $\succeq_1^\prime$ as illustrated in Figure 6b (represented by the thick arrow). At this step, the support $B_2$ does not dominate $C_1$ and does not dominate $C_3$. Moreover, the possibilistic repair of any totally preordered ABox $A_{\ge i}$ that is compatible with $A_{\ge i'}$ (which is, by definition, compatible with $A_{\ge i'}$), is given by $R(A_{\ge i}) = \{\text{Head}(\text{Mary}), \text{ConfAccess}(\text{Bob}, r_1)\}$. Hence, neither of the supports of $\text{Prof}(\text{Alice})$ is in $R(A_{\ge i})$. Therefore, $\text{Prof}(\text{Alice})$ does not belong to $c\pi(A_{\ge i'})$.

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

**Proposition 1 and 2** provide a full characterization for membership in $c\pi(A_{\ge}),$ based on the notions of support and dominance. The next proposition states (as expected) that $c\pi(A_{\ge})$ is consistent and more productive than $\pi(A_{\ge})$.

**Proposition 3.** Let $K_{\ge} = \langle T, A_{\ge} \rangle$ be partially preordered KB. Let $c\pi(A_{\ge})$ and $\pi(A_{\ge})$ be the C$\pi$-repair and the $\pi$-repair of $A_{\ge}$, as given by Definitions 7 and 3, respectively.

1. $\langle T, c\pi(A_{\ge}) \rangle$ is consistent.

2. $\pi(A_{\ge}) \subseteq c\pi(A_{\ge})$.

*Proof.*

1. The consistency of $c\pi(A_{\ge})$ follows from the fact that for any totally preordered ABox $A_{\ge i}$, $i = 1, \dots, m$, the sub-base $R(A_{\ge i})$ given by Definition 2 is consistent. Therefore, the positive deductive closure $cl(R(A_{\ge i}))$ is also consistent, and so is the intersection of all these closed repairs.

2. The proof is immediate since, for each ABox $A_{\ge i}$ compatible with $A_{\ge}$, we have $R(A_{\ge i}) \subseteq cl(R(A_{\ge i}))$. Therefore:

$$ \bigcap_{i=1}^{m} \{R(A_{\ge i}) | A_{\ge i} \text{ is compatible with } A_{\ge}\} \subseteq \bigcap_{i=1}^{m} \{cl(R(A_{\ge i})) | A_{\ge i} \text{ compatible with } A_{\ge}\} $$

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

*Remark.* The converse of $\pi(A_{\ge}) \subseteq c\pi(A_{\ge})$ is false. Namely, one can exhibit a KB such that $c\pi(A_{\ge}) \not\subseteq \pi(A_{\ge})$. Example 5 illustrates a case where the C$\pi$-repair $c\pi(A_{\ge})$ is strictly larger than the $\pi$-repair $\pi(A_{\ge})$. Note that there are also situations where the converse is not false. For instance, when the knowledge base is consistent, the C$\pi$-repair $c\pi(A_{\ge})$ and the $\pi$-repair $\pi(A_{\ge})$ are equivalent.

The next proposition establishes the tractability of $c\pi(A_{\ge})$. This follows from the characterization given in Propositions 1 and 2, based on the notions of dominance and support.
**Proposition 4.** Let $\mathcal{K}_{\Delta} = \langle \mathcal{T}, A_{\Delta} \rangle$ be a partially preordered KB and $\varphi$ be an assertion. Checking if $\varphi \in c\pi(A_{\Delta})$ is done in polynomial time in DL-Lite<sub>R</sub>.

*Proof.* Proofing the tractability of checking if a given assertion $\varphi$ belongs to $c\pi(A_{\Delta})$ comes first from our characterization of C<sub>π</sub>-repair given in Propositions 1 and 2, which does not enumerate all the compatible totally preordered ABoxes. We recall that this characterization consists in saying that $\varphi \in c\pi(A_{\Delta})$ if and only if, for any conflict C, there is a support B of $\varphi$ such that B dominates C. Note that, in DL-Lite<sub>R</sub>, the size of a given conflict is at most two assertions and a given support is one assertion, so checking if B dominates C is in O(1) (in DL-Lite<sub>R</sub>, computing the conflict set is done in polynomial time [1]). Therefore, the number of conflicts and supports is bounded by $O(|c\ln(\mathcal{T})| * |A_{\Delta}|)$ (where $c\ln(\mathcal{T})$ denotes the negative closure of the TBox T, i.e., all the negative axioms that can be inferred from it). Moreover, the size of the TBox is often considered negligible compared to the size of the ABox, thus the main focus is on data complexity. Now, once the conflict set and all supports are computed, a simple algorithm iterates over the conflict set, and for each conflict C, it parses the set of supports to check if there is some support B that dominates C. Then the whole process of checking if $\varphi$ belongs to C<sub>π</sub>-repair is achieved in polynomial time. □

# 7. Rationality properties

We study the rationality properties of query answering using the possibilistic semantics and its closure-based extension. We distinguish two situations: either query answers are obtained solely from the knowledge base (unconditional inference) or from the knowledge base and a given observation, considered as fully reliable (conditional inference).

## 7.1. Unconditional inference

Let us start with unconditional query-answering, which amounts to checking whether a query $q$ follows from the partially preordered possibilistic repair (Definition 3) and the closure-based possibilistic repair (Definition 7), denoted with the symbols $\models^{\pi}$ and $\models^{c\pi}$, respectively. Formally:

**Definition 10.** (Unconditional inference) Let $\mathcal{K}_{\Delta} = \langle \mathcal{T}, A_{\Delta} \rangle$ be a partially preordered knowledge base. Let $q$ be a query. The query $q$ follows from the repair $\pi(A_{\Delta})$ (resp. $c\pi(A_{\Delta})$), denoted by $\mathcal{K}_{\Delta} \models^{\pi} q$ (resp. $\mathcal{K}_{\Delta} \models^{c\pi} q$), if and only if:

$$ \langle \mathcal{T}, \pi(A_{\Delta}) \rangle \models q \text{ (resp. } \langle \mathcal{T}, c\pi(A_{\Delta}) \rangle \models q) $$

Where $\models$ denotes standard DL-Lite<sub>R</sub> inference.

The following result states that the unconditional inferences $\models^{\pi}$ and $\models^{c\pi}$ meet the rationality properties of unconditional inconsistency-tolerant semantics defined in [46]. Namely:

**Proposition 5.** The unconditional possibilistic inference relation $\models^s$ (with $s \in \{\pi, c\pi\}$) satisfies the following properties:

- **QCE (Query Conjunction Elimination):** if $\mathcal{K}_{\Delta} \models^s q_1 \wedge q_2$, then $\mathcal{K}_{\Delta} \models^s q_1$ and $\mathcal{K}_{\Delta} \models^s q_2$.

- **QCI (Query Conjunction Introduction):** if $\mathcal{K}_{\Delta} \models^s q_1$ and $\mathcal{K}_{\Delta} \models^s q_2$ then $\mathcal{K}_{\Delta} \models^s q_1 \wedge q_2$.

- **Cons (Consistency):** For any set of assertions B, if $\mathcal{K}_{\Delta} \models^s B$ then $\langle \mathcal{T}, B \rangle$ is consistent.

- **ConsC (Consistency of Conjunction):** For any set of assertions B, if $\forall \varphi \in B$, $\mathcal{K}_{\Delta} \models^s \varphi$, then $\langle \mathcal{T}, B \rangle$ is consistent.

- **ConsS (Consistency of Support):** For any set of assertions B, if $\mathcal{K}_{\Delta} \models^s B$ then $\exists A'$, a maximally consistent subset of $A_{\Delta}$ such that $\langle \mathcal{T}, A' \rangle \models B$.

*Proof.* Let $\mathcal{K}_{\Delta} = \langle \mathcal{T}, A_{\Delta} \rangle$ be a partially preordered knowledge base and $q$ be a query. Let $\models^{\pi}$ (resp. $\models^{c\pi}$) be the unconditional query answering relations using the $\pi$-accepted assertions (resp. C<sub>π</sub>-repair) methods. The proof of Proposition 5 is straightforward. It first follows from the fact that both repairs $\pi(A_{\Delta})$ and $c\pi(A_{\Delta})$ are consistent (Proposition 3). It also follows from the fact that the unconditional query answering relation $\mathcal{K}_{\Delta} \models^{\pi} q$ (resp. $\mathcal{K}_{\Delta} \models^{c\pi} q$) amounts to a standard inference relation from one consistent knowledge base: $\langle \mathcal{T}, \pi(A_{\Delta}) \rangle \models q$ (resp. $\langle \mathcal{T}, c\pi(A_{\Delta}) \rangle \models q$). As for any consistent and certain knowledge base, the standard entailment $\models$ satisfies **QCE**, **QCI**, **Cons**, and **ConsC** [3]. Therefore, since $\pi(A_{\Delta})$ and $c\pi(A_{\Delta})$ are both consistent, they both satisfy these properties. The proof of **ConsS** is also immediate. As stated in Proposition 3, $\pi(A_{\Delta})$ (resp. $c\pi(A_{\Delta})$) is consistent, then it is enough to start with $\pi(A_{\Delta})$ (resp. $c\pi(A_{\Delta})$) and extend it to get a maximally consistent repair. □
## 7.2. Conditional inference

We now consider conditional query answering. This involves querying a partially preordered knowledge base under a given observation, represented by a set of fully reliable assertions. These assertions, denoted by $\mathcal{O}$, are assumed to be consistent with the TBox.

We write $\mathcal{O} \Vdash_{\mathcal{K}_{\sqsuperscript{\mathcal{O}}}}^s q$ to indicate that $q$ follows from the knowledge base $\mathcal{K}_{\sqsuperscript{\mathcal{O}}}$, under the observation $\mathcal{O}$, using the inconsistency-tolerant semantics $s$ (here $s = \pi$ for the possibilistic repair and $s = c\pi$ for the closure-based possibilistic repair). A standard way to proceed is to first add $\mathcal{O}$ to the ABox with the highest priority, then apply the possibilistic repair method and the closure-based possibilistic repair to unconditionally answer queries from the augmented knowledge base, defined above in Definition 10.

Let us denote by $\mathcal{K}_{\sqsuperscript{\mathcal{O}}}=\langle\mathcal{T}, \mathcal{A}_{\sqsuperscript{\mathcal{O}}}\rangle$ the augmented knowledge base where $\mathcal{A}_{\sqsuperscript{\mathcal{O}}} = (\mathcal{A}_{\sqsuperscript{\mathcal{O}}} \cup \mathcal{O})$ results from adding $\mathcal{O}$ to $\mathcal{A}_{\sqsuperscript{\mathcal{O}}}$ with the highest priority. The partial preorder $\sqsuperscript{\mathcal{O}}$ over $(\mathcal{A}_{\sqsuperscript{\mathcal{O}}} \cup \mathcal{O})$ is obtained from $\sqsuperscript{\mathcal{O}}$ as follows:

(i) $\forall \varphi_i \in \mathcal{O}, \forall \varphi_j \in \mathcal{O}: \varphi_i \sqsuperscript{\mathcal{O}} \varphi_j$ and $\varphi_j \sqsuperscript{\mathcal{O}} \varphi_i$ (i.e., $\varphi_i$ and $\varphi_j$ are equally reliable).

(ii) $\forall \varphi_i \in \mathcal{O}, \forall \varphi_j \in \mathcal{A}_{\sqsuperscript{\mathcal{O}}} \setminus \mathcal{O}: \varphi_i \sqsuperscript{\mathcal{O}} \varphi_j$ (i.e., every $\varphi_i \in \mathcal{O}$ is strictly more preferred than any $\varphi_j \in \mathcal{A}_{\sqsuperscript{\mathcal{O}}} \setminus \mathcal{O}$. This serves to give higher priority to the assertions in $\mathcal{O}$).

(iii) $\forall \varphi_i \in \mathcal{A}_{\sqsuperscript{\mathcal{O}}} \setminus \mathcal{O}, \forall \varphi_j \in \mathcal{A}_{\sqsuperscript{\mathcal{O}}} \setminus \mathcal{O}: \varphi_i \sqsuperscript{\mathcal{O}} \varphi_j$ if and only if $\varphi_i \sqsuperscript{\mathcal{O}} \varphi_j$ (i.e., the relative ordering between the elements of $\mathcal{A}_{\sqsuperscript{\mathcal{O}}}$ that are not in $\mathcal{O}$ is preserved).

**Example 10.** Let $\mathcal{A}_{\sqsuperscript{\mathcal{O}}} = \{\text{Secondee}(\text{Bob}), \text{VisitingProf}(\text{Alice}), \text{Prof}(\text{Bob})\}$ be an ABox where $\text{Secondee}(\text{Bob}) \succ \text{Prof}(\text{Bob})$ and the remaining relations are incomparable. Let $\mathcal{O} = \{\text{Prof}(\text{Bob}), \text{FacMember}(\text{Bob})\}$ be an observation. The augmented ABox $\mathcal{A}_{\sqsuperscript{\mathcal{O}}} = (\mathcal{A}_{\sqsuperscript{\mathcal{O}}} \cup \mathcal{O})$ results from adding $\mathcal{O}$ to $\mathcal{A}_{\sqsuperscript{\mathcal{O}}}$ with the highest priority such that:

- $\text{Prof}(\text{Bob}) \succ_{\mathcal{O}} \text{FacMember}(\text{Bob})$ and $\text{FacMember}(\text{Bob}) \succ_{\mathcal{O}} \text{Prof}(\text{Bob})$.

- $\text{Prof}(\text{Bob}) \succ_{\mathcal{O}} \text{Secondee}(\text{Bob}), \text{Prof}(\text{Bob}) \succ_{\mathcal{O}} \text{VisitingProf}(\text{Alice})$.

- $\text{FacMember}(\text{Bob}) \succ_{\mathcal{O}} \text{Secondee}(\text{Bob}), \text{FacMember}(\text{Bob}) \succ_{\mathcal{O}} \text{VisitingProf}(\text{Alice})$.

The remaining relations of $\sqsuperscript{\mathcal{O}}$ are preserved in $\sqsuperscript{\mathcal{O}}$.

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

Next, we define the partially preordered conditional query-answering relation as follows:

**Definition 11.** (Conditional inference) Let $\mathcal{K}_{\sqsuperscript{\mathcal{O}}} = \langle\mathcal{T}, \mathcal{A}_{\sqsuperscript{\mathcal{O}}}\rangle$ be a partially preordered knowledge base, $\mathcal{O}$ an observation and $q$ a query. Then $q$ follows from $\mathcal{K}_{\sqsuperscript{\mathcal{O}}}$ and $\mathcal{O}$, denoted $\mathcal{O} \Vdash_{\mathcal{K}_{\sqsuperscript{\mathcal{O}}}}^s q$, if $\mathcal{K}_{\sqsuperscript{\mathcal{O}}} \Vdash^s q$ ($\text{with } s \in \{\pi, c\pi\}$), where $\mathcal{K}_{\sqsuperscript{\mathcal{O}}} = \langle\mathcal{T}, \mathcal{A}_{\sqsuperscript{\mathcal{O}}}\rangle$ is the augmented knowledge base and $\sqsuperscript{\mathcal{O}}$ its associated partial preorder (described in the steps (i), (ii), (iii)), and $\Vdash^s$ is the unconditional query-answering relation given in Definition 10.

One can check that $\mathcal{O} \Vdash_{\mathcal{K}_{\sqsuperscript{\mathcal{O}}}}^s q$ is non-monotonic, for both semantics (the possibilistic repair and the closure-based possibilistic repair). For instance, consider a knowledge base where the TBox is $\mathcal{T} = \{\text{Head} \sqsubseteq \neg \text{VisitingProf}\}$ and the ABox is $\mathcal{A}_{\sqsuperscript{\mathcal{O}}} = \{\text{FullProf}(\text{Alice}), \text{Head}(\text{Bob}), \text{VisitingProf}(\text{Bob})\}$. Assume a partial order where $\text{FullProf}(\text{Alice}) \succ \text{Head}(\text{Bob})$ and the remaining relations are incomparable. One can check that there is one conflict $C = \{\text{Head}(\text{Bob}), \text{VisitingProf}(\text{Bob})\}$, and that the assertion $\text{FullProf}(\text{Alice})$ is the only one accepted in both of the repairs $\pi(\mathcal{A}_{\sqsuperscript{\mathcal{O}}})$ and $c\pi(\mathcal{A}_{\sqsuperscript{\mathcal{O}}})$. Assume now an observation $\mathcal{O} = \{\text{Head}(\text{Bob})\}$. The assertion $\text{FullProf}(\text{Alice})$ is no longer accepted in both of the repairs since $\mathcal{O}$ is given the highest priority, the partial preorder becomes $\text{Head}(\text{Bob}) \succ_{\mathcal{O}} \text{FullProf}(\text{Alice})$ and $\text{Head}(\text{Bob}) \succ_{\mathcal{O}} \text{VisitingProf}(\text{Bob})$ (the remaining relations are incomparable). That is because $\text{FullProf}(\text{Alice})$ is no longer more certain than an element from the conflict $C$.

One of the well-known sets of rational properties that have been proposed to study non-monotonic inference relations is System P [81]. Originally defined in the context of propositional logic, it has also been adapted to DL-Lite$_R$ in [3] (see also [82, 83] for an adaptation to richer DLs). In the following, except in particular cases or when stated differently, any observation $\mathcal{O}$ is assumed to be consistent with respect to the TBox $\mathcal{T}$, i.e., $\langle\mathcal{T}, \mathcal{O}\rangle$ is consistent.

The adaptation of System P's rules is given below, where $\mathcal{K}_{\sqsuperscript{\mathcal{O}}} = \langle\mathcal{T}, \mathcal{A}_{\sqsuperscript{\mathcal{O}}}\rangle$ is a knowledge base, $\mathcal{O}_1, \mathcal{O}_2, \mathcal{O}_3$ are observations, $s$ is an inconsistency-tolerant semantics with $s \in \{\pi, c\pi\}$, $\Vdash$ and $\equiv$ denote standard DL-Lite$_R$ inference and equivalence:

- **R** (Reflexivity): $\mathcal{O}_1 \Vdash_{\mathcal{K}_{\sqsuperscript{\mathcal{O}}}}^s \mathcal{O}_1$.

- **LLE** (Left Logical Equivalence): if $\langle\mathcal{T}, \mathcal{O}_1\rangle \equiv \langle\mathcal{T}, \mathcal{O}_2\rangle$ and $\mathcal{O}_1 \Vdash_{\mathcal{K}_{\sqsuperscript{\mathcal{O}}}}^s \mathcal{O}_3$ then $\mathcal{O}_2 \Vdash_{\mathcal{K}_{\sqsuperscript{\mathcal{O}}}}^s \mathcal{O}_3$.

- **RW** (Right Weakening): if $\langle\mathcal{T}, \mathcal{O}_1\rangle \Vdash \mathcal{O}_2$ and $\mathcal{O}_3 \Vdash_{\mathcal{K}_{\sqsuperscript{\mathcal{O}}}}^s \mathcal{O}_1$, then $\mathcal{O}_3 \Vdash_{\mathcal{K}_{\sqsuperscript{\mathcal{O}}}}^s \mathcal{O}_2$.
<figure><img src="image_17.png" /><figcaption>**Figure 7:** →: strict preference. —: conflict.</figcaption></figure>

- **Cut**: if $\mathcal{O}_1 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_2$ and $\mathcal{O}_1 \cup \mathcal{O}_2 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_3$, then $\mathcal{O}_1 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_3$.

- **CM (Cautious Monotony)**: if $\mathcal{O}_1 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_2$ and $\mathcal{O}_1 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_3$, then $\mathcal{O}_1 \cup \mathcal{O}_2 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_3$.

- **AND**: if $\mathcal{O}_1 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_2$ and $\mathcal{O}_1 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_3$, then $\mathcal{O}_1 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_2 \cup \mathcal{O}_3$.

In this paper, we propose to also consider two additional properties, originally defined in propositional logic [81, 84], and which go beyond cautious monotony:

- **RM (Rational Monotony)**: if $\mathcal{O}_1 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_2$, then $\mathcal{O}_1 \cup \mathcal{O}_3 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_2$ or $\langle \mathcal{T}, (\mathcal{O}_1 \cup \mathcal{O}_3 \cup \mathcal{A}_{\Delta}) \rangle$ is inconsistent.

- **Comp (Completeness)**: if $\mathcal{O}_1 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_2$, then either $\mathcal{O}_1 \cup \mathcal{O}_3 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_2$ or $\langle \mathcal{T}, (\mathcal{O}_1 \cup \mathcal{O}_2 \cup \mathcal{O}_3 \cup \mathcal{A}_{\Delta}) \rangle$ is inconsistent.

Note that in the adaptation of the last two properties, we propose to use the notion of inconsistency instead of negation in the original definition of rational monotony, and use a disjunctive interpretation of **RM**. In propositional logic, **RM** is defined as: if $\alpha \vdash_{\mathcal{K}} \gamma$ and $\alpha \not\vdash_{\mathcal{K}} \neg \beta$, then $\alpha \wedge \beta \vdash_{\mathcal{K}} \gamma$, where $\alpha, \beta$ and $\gamma$ are propositional logic formulas. Our adaptation consists first in rewriting **RM** equivalently in a disjunctive way: if $\alpha \vdash_{\mathcal{K}} \gamma$, then $\alpha \wedge \beta \vdash_{\mathcal{K}} \gamma$ or $\alpha \vdash_{\mathcal{K}} \neg \beta$. Lastly, we replace $\alpha \vdash_{\mathcal{K}} \neg \beta$ with $\alpha \wedge \beta$ is inconsistent with the knowledge base. Here, **RM** states that given a new observation, we can continue to believe in the previous plausible consequences of the knowledge base, or the new observation conflicts with the knowledge base.

In propositional logic, **Comp** is defined as: if $\alpha \vdash_{\mathcal{K}} \gamma$, then either $\alpha \wedge \beta \vdash_{\mathcal{K}} \gamma$ or $\alpha \wedge \beta \vdash_{\mathcal{K}} \neg \gamma$. Here, we simply replace $\alpha \wedge \beta \vdash_{\mathcal{K}} \neg \gamma$ with $\alpha \wedge \beta \wedge \gamma$ is inconsistent with the knowledge base. The **Comp** rule is stronger than **RM**, and states that given a new observation $\mathcal{O}_3$, then either $\mathcal{O}_2$ continues to be derived from both $\mathcal{O}_1$ and $\mathcal{O}_3$, or $\mathcal{O}_3$ contradicts the whole knowledge base (plus itself). Intuitively, this means that either we continue to believe in $\mathcal{O}_2$, or we should believe in its negation (there is no room for ignoring $\mathcal{O}_2$).

The next proposition summarizes the results of the conditional properties:

**Proposition 6.** Let $\mathcal{K}_{\Delta} = (\mathcal{T}, \mathcal{A}_{\Delta})$ be a partially preordered knowledge base, $\mathcal{O}$ be an observation and $q$ be a query. The query-answering relations $\vdash_{\mathcal{K}_{\Delta}}^{\pi}$ and $\vdash_{\mathcal{K}_{\Delta}}^{c\pi}$ satisfy the System P properties: **R** (Reflexivity), **LLE** (Left Logical Equivalence), **RW** (Right Weakening), **Cut**, **CM** (Cautious Monotony) and **AND**.

**Remark** Note that the query-answering relations $\vdash_{\mathcal{K}_{\Delta}}^{\pi}$ and $\vdash_{\mathcal{K}_{\Delta}}^{c\pi}$ fail to satisfy **RM** (Rational Monotony) and **Comp** (Completeness). The following example illustrates a case where the inference relations $\vdash_{\mathcal{K}_{\Delta}}^{\pi}$ and $\vdash_{\mathcal{K}_{\Delta}}^{c\pi}$ do not satisfy the properties **RM** and **Comp**.

**Example 11.** Let $\mathcal{K}_{\Delta} = (\mathcal{T}, \mathcal{A}_{\Delta})$ be a partially preordered knowledge base, where the TBox $\mathcal{T}$ and the assertions of the ABox $\mathcal{A}_{\Delta}$ are given by:

$$ \mathcal{T} = \{ \text{Head} \sqsubseteq \neg \text{VisitingProf}, \text{FullProf} \sqsubseteq \text{Prof} \} \qquad \mathcal{A}_{\Delta} = \{ \text{FullProf}(\text{Alice}), \text{Head}(\text{Bob}), \text{VisitingProf}(\text{Bob}) \} $$

The partial preorder $\supseteq$ over the ABox $\mathcal{A}_{\Delta}$ and the conflict set $\mathcal{Cf}(\mathcal{A}_{\Delta})$ are depicted in Figure 7a.

1. We provide a counterexample to **RM**, namely:

If $\mathcal{O}_1 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_2$, then $\mathcal{O}_1 \cup \mathcal{O}_3 \vdash_{\mathcal{K}_{\Delta}}^s \mathcal{O}_2$ or $\langle \mathcal{T}, \mathcal{O}_1 \cup \mathcal{O}_3 \cup \mathcal{A}_{\Delta} \rangle$ is inconsistent.

One can check that the partially preordered possibilistic repair is $\pi(\mathcal{A}_{\Delta}) = \{\text{FullProf}(\text{Alice})\}$ and the C$\pi$-repair is $c\pi(\mathcal{A}_{\Delta}) = \{\text{FullProf}(\text{Alice}), \text{Prof}(\text{Alice})\}$.

Assume the following sets of assertions:

$$ \mathcal{O}_1 = \emptyset, \mathcal{O}_2 = \{\text{Prof}(\text{Alice})\} \text{ and } \mathcal{O}_3 = \{\text{Head}(\text{Bob})\} $$
Then $\langle \mathcal{T}, A_{\ge} \rangle \models^{\pi} \mathcal{O}_2$ (resp. $\langle \mathcal{T}, A_{\le} \rangle \models^{c\pi} \mathcal{O}_2$). Since $\mathcal{O}_1$ is the empty set, by definition of the conditional inference:

$$ \mathcal{O}_1 \vdash_{\mathcal{K}_{\ge}}^{\pi} \mathcal{O}_2 \text{ and } \mathcal{O}_1 \vdash_{\mathcal{K}_{\le}}^{c\pi} \mathcal{O}_2 $$

Now, assume that $\mathcal{O}_3$ is a new observation, this means that Head(Bob) is given the highest priority in the augmented ABox $A_{\ge_{\mathcal{O}_3}}$. The new augmented partial order is given in Figure 7b. After observing $\mathcal{O}_3$, we only obtain $\pi(A_{\ge_{\mathcal{O}_3}}) = \{\text{Head}(\text{Bob})\}$ and $c\pi(A_{\le_{\mathcal{O}_3}}) = \{\text{Head}(\text{Bob})\}$. One can easily check that $\langle \mathcal{T}, A_{\ge} \rangle \not\models^{\pi} \mathcal{O}_2$ and $\langle \mathcal{T}, A_{\le} \rangle \not\models^{c\pi} \mathcal{O}_2$. Hence, we cannot infer $\mathcal{O}_2$ any more, namely:

$$ \mathcal{O}_1 \cup \mathcal{O}_3 \vdash_{\mathcal{K}_{\ge}}^{\pi} \mathcal{O}_2 \text{ and } \mathcal{O}_1 \cup \mathcal{O}_3 \vdash_{\mathcal{K}_{\le}}^{c\pi} \mathcal{O}_2 $$

Besides, one can easily check that $\langle \mathcal{T}, \mathcal{O}_1 \cup \mathcal{O}_3 \cup \pi(A_{\ge}) \rangle$ and $\langle \mathcal{T}, \mathcal{O}_1 \cup \mathcal{O}_3 \cup c\pi(A_{\ge}) \rangle$ are both consistent. This contradicts the definition of the **RM** property. Therefore, **RM** (Rational Monotony) is not satisfied by both of the conditional inference relations $\vdash_{\mathcal{K}_{\ge}}^{\pi}$ and $\vdash_{\mathcal{K}_{\le}}^{c\pi}$.

2. Now, in the same way, we provide a counterexample to **Comp**, namely, If $\mathcal{O}_1 \vdash_{\mathcal{K}_{\ge}}^s \mathcal{O}_2$, then either $\mathcal{O}_1 \cup \mathcal{O}_3 \vdash_{\mathcal{K}_{\ge}}^{c\pi} \mathcal{O}_2$ or $\langle \mathcal{T}, (\mathcal{O}_1 \cup \mathcal{O}_2 \cup \mathcal{O}_3 \cup A_{\ge}) \rangle$ is inconsistent.

Assume the same sets of assertions $\mathcal{O}_1, \mathcal{O}_2$ and $\mathcal{O}_3$ from above. We already showed that $\mathcal{O}_1 \vdash_{\mathcal{K}_{\ge}}^{\pi} \mathcal{O}_2$ and $\mathcal{O}_1 \vdash_{\mathcal{K}_{\le}}^{c\pi} \mathcal{O}_2$. Moreover, after giving $\mathcal{O}_3$ the highest priority, we cannot infer $\mathcal{O}_2$ any more:

$$ \mathcal{O}_1 \cup \mathcal{O}_3 \vdash_{\mathcal{K}_{\ge}}^{\pi} \mathcal{O}_2 \text{ and } \mathcal{O}_1 \cup \mathcal{O}_3 \vdash_{\mathcal{K}_{\le}}^{c\pi} \mathcal{O}_2 $$

One can also easily check that $\langle \mathcal{T}, \mathcal{O}_1 \cup \mathcal{O}_2 \cup \mathcal{O}_3 \cup \pi(A_{\ge}) \rangle$ is consistent, and $\langle \mathcal{T}, \mathcal{O}_1 \cup \mathcal{O}_2 \cup \mathcal{O}_3 \cup c\pi(A_{\ge}) \rangle$ is consistent. This contradicts the definition of **Comp**. Therefore, **Comp** is not satisfied by both of the conditional inference relations $\vdash_{\mathcal{K}_{\ge}}^{\pi}$ and $\vdash_{\mathcal{K}_{\le}}^{c\pi}$.

□

### 7.3. Satisfaction of the System P properties

In this section, we provide an in-depth study of the satisfaction of the System P properties by the conditional inference relations of the Cπ-repair and the π-repair, as established by Proposition 6. The proofs of the properties **R**, **RW** and **AND** are directly given since they are relatively easy to establish. Then, in Subsection 7.3.1 we establish intermediary results on the satisfaction of the properties **LLE**, **Cut** and **CM** in the context of totally preordered ABoxes before showing how their satisfaction is achieved in the case of partially preordered ABoxes, in Subsections 7.3.2 and 7.3.3.

**Lemma 2.** Let $\mathcal{K}_{\ge} = \langle \mathcal{T}, A_{\ge} \rangle$ be a partially preordered knowledge base, $\mathcal{O}$ be an observation and $q$ be a query. The conditional query-answering relations $\vdash_{\mathcal{K}_{\ge}}^{\pi}$ and $\vdash_{\mathcal{K}_{\le}}^{c\pi}$ satisfy the properties **R**, **RW** and **AND**.

*Proof.*

1. The proof of **R** is immediate. The property of reflexivity states that, for a given observation $\mathcal{O}, \mathcal{O} \vdash_{\mathcal{K}_{\ge}}^{s} \mathcal{O}$ holds (where $s \in \{\pi, c\pi\}$). By Definition 11 of the conditional inference, $\mathcal{O} \vdash_{\mathcal{K}_{\ge}}^{s} \mathcal{O}$ amounts to $\mathcal{K}_{\ge_{\mathcal{O}}} \models^{s} \mathcal{O}$ holds, where $\mathcal{K}_{\ge_{\mathcal{O}}} = \langle \mathcal{T}, A_{\ge_{\mathcal{O}}} \rangle$, such that $A_{\ge_{\mathcal{O}}}$ is the augmented ABox (as described in steps (i), (ii), (iii) from Section 7.2), and $\models^s$ is the unconditional inference relation (Definition 10).

Let $A_{\ge_{\mathcal{O}}}$ be a totally preordered ABox compatible with $A_{\ge_{\mathcal{O}}}$. Let $S_1 \cup \dots \cup S_n$ be its associated well-ordered partition. One can easily see that $S_1 = \mathcal{O}$. Indeed, by construction of $\ge_{\mathcal{O}}$, we have $\forall \varphi_j \in \mathcal{O}, \forall \varphi_k \in \mathcal{O}, \varphi_j \ge_{\mathcal{O}} \varphi_k$ and $\varphi_k \ge_{\mathcal{O}} \varphi_j$, hence, we also have $\varphi_j \ge_{\mathcal{O}} \varphi_k$ and $\varphi_k \ge_{\mathcal{O}} \varphi_j$ since $\ge_{\mathcal{O}}$ is compatible with $\ge_{\mathcal{O}}$. Besides, again by construction of $\ge_{\mathcal{O}}, \forall \varphi_j \in \mathcal{O}, \forall \varphi_k \in (\mathcal{A} \setminus \mathcal{O})$, we have $\varphi_j >_{\mathcal{O}} \varphi_k$, hence, $\varphi_j >_{\mathcal{O}} \varphi_k$. The possibilistic repair (Definition 2) of $A_{\ge_{\mathcal{O}}}$ is necessarily of the form:

- $\mathcal{R}(A_{\ge_{\mathcal{O}}}) = A_{\ge_{\mathcal{O}}}$ if $\langle \mathcal{T}, (S_1 = \mathcal{O}) \cup S_2 \cup \dots \cup S_n \rangle$ is consistent.

- $\mathcal{R}(A_{\ge_{\mathcal{O}}}) = (S_1 = \mathcal{O}) \cup S_2 \cup \dots \cup S_i$ if $\langle \mathcal{T}, (S_1 = \mathcal{O}) \cup S_2 \cup \dots \cup S_{i+1} \rangle$ is inconsistent (with $1 \le i < n$).
Therefore, $\mathcal{R}(A_{\ge \emptyset})$ contains at least $\emptyset$ (by assumption $\langle \mathcal{T}, \emptyset \rangle$ is consistent). Since this result applies to all the totally preordered ABoxes compatible with $A_{\ge \emptyset}$, we conclude that $\emptyset \subseteq \pi(A_{\ge \emptyset})$ (resp. $\emptyset \subseteq c\pi(A_{\ge \emptyset})$). Hence, $\langle \mathcal{T}, \pi(A_{\ge \emptyset}) \rangle \models \emptyset$ (resp. $\langle \mathcal{T}, c\pi(A_{\ge \emptyset}) \rangle \models \emptyset$).

2. **RW states** that if $\langle \mathcal{T}, \mathcal{O}_1 \rangle \models \mathcal{O}_2$ and $\mathcal{O}_3 \vdash_{\mathcal{K}_{\ge}}^s \mathcal{O}_1$ then $\mathcal{O}_3 \vdash_{\mathcal{K}_{\ge}}^s \mathcal{O}_2$ (where $s \in \{\pi, c\pi\}$). The proof is immediate. Indeed, $\mathcal{O}_3 \vdash_{\mathcal{K}_{\ge}}^s \mathcal{O}_1$ amounts to apply the standard entailment $\langle \mathcal{T}, \pi(A_{\ge \emptyset}) \rangle \models \mathcal{O}_1$ (resp. $\langle \mathcal{T}, c\pi(A_{\ge \emptyset}) \rangle \models \mathcal{O}_1$). By definition of a possibilistic repair, $\langle \mathcal{T}, \pi(A_{\ge \emptyset}) \rangle$ (resp. $\langle \mathcal{T}, c\pi(A_{\ge \emptyset}) \rangle$) is consistent. Furthermore, from the result of Proposition 5, consistency (Cons) is satisfied by the unconditional inference relation, thus, we can infer that $\langle \mathcal{T}, \mathcal{O}_1 \rangle$ is consistent from $\langle \mathcal{T}, \pi(A_{\ge \emptyset}) \rangle \models \mathcal{O}_1$ (resp. $\langle \mathcal{T}, c\pi(A_{\ge \emptyset}) \rangle \models \mathcal{O}_1$). Therefore, having $\langle \mathcal{T}, \mathcal{O}_1 \rangle \models \langle \mathcal{T}, \mathcal{O}_2 \rangle$, one can directly infer $\langle \mathcal{T}, \pi(A_{\ge \emptyset}) \rangle \models \mathcal{O}_2$ (resp. $\langle \mathcal{T}, c\pi(A_{\ge \emptyset}) \rangle \models \mathcal{O}_2$).

3. **AND states** that $\mathcal{O}_1 \vdash_{\mathcal{K}_{\ge}}^s \mathcal{O}_2$ and $\mathcal{O}_1 \vdash_{\mathcal{K}_{\ge}}^s \mathcal{O}_3$, then $\mathcal{O}_1 \vdash_{\mathcal{K}_{\ge}}^s \mathcal{O}_2 \cup \mathcal{O}_3$ (where $s \in \{\pi, c\pi\}$). The proof of AND is also immediate. Indeed, $\mathcal{O}_1 \vdash_{\mathcal{K}_{\ge}}^s \mathcal{O}_2$ amounts to derive $\mathcal{K}_{\ge \emptyset} \models^s \mathcal{O}_2$, where $\models^s$ is the unconditional inference relation. Similarly, $\mathcal{O}_1 \vdash_{\mathcal{K}_{\ge}}^s \mathcal{O}_3$ amounts to derive $\mathcal{K}_{\ge \emptyset} \models^s \mathcal{O}_3$ (where $s \in \{\pi, c\pi\}$).

Proposition 5 shows that both inference relations $\models^\pi$ and $\models^{c\pi}$ satisfy the **QCI** property, which states that if $\mathcal{K}_{\ge \emptyset} \models^s q_1$ and $\mathcal{K}_{\ge \emptyset} \models^s q_2$ then $\mathcal{K}_{\ge \emptyset} \models^s q_1 \wedge q_2$. In our case, we have $\mathcal{K}_{\ge \emptyset_1} \models^\pi \mathcal{O}_2$ and $\mathcal{K}_{\ge \emptyset_1} \models^\pi \mathcal{O}_3$ (resp. $\mathcal{K}_{\ge \emptyset_1} \models^{c\pi} \mathcal{O}_2$ and $\mathcal{K}_{\ge \emptyset_1} \models^{c\pi} \mathcal{O}_3$), therefore, we conclude that $\mathcal{K}_{\ge \emptyset_1} \models^\pi \mathcal{O}_2 \cup \mathcal{O}_3$ (resp. $\mathcal{K}_{\ge \emptyset_1} \models^{c\pi} \mathcal{O}_2 \cup \mathcal{O}_3$). (Note that when $\mathcal{O}_1 = \emptyset$ (no assertions observed) and $q_1$ and $q_2$ are sets of assertions, then AND is equivalent to QCI [3]).

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

### 7.3.1. Some preliminaries on the conditional inference for totally preordered ABoxes

In this subsection, we first establish the satisfaction of **LLE** in the context of a totally preordered ABox. We also discuss the behaviour of the conditional inference relation when previously derived results are added to the base, still within the context of totally preordered ABoxes.

In the following, we use the expression “conditioning a partial preorder $\ge$ by $\emptyset$” to denote the process of adding an observation $\emptyset$ with the highest priority to a partially preordered ABox $A_{\ge}$ following steps (i), (ii), (iii) from Section 7.2. The obtained partial preorder $\ge_{\emptyset}$ is also called a conditioned partial preorder.

The following definition introduces the instantiation (given in steps (i), (ii), (iii) from Section 7.2) of conditioning a total preorder $\ge$ by an observation $\emptyset$.

**Definition 12.** (Conditioned total preorder) Let $A_{\ge}$ be a totally preordered ABox, and $S_1 \cup \cdots \cup S_n$ be its associated well-ordered partition. Let $\emptyset$ be an observation.

The conditioned total preorder $\ge_{\emptyset}$ of $\ge$ by $\emptyset$ is obtained by adding $\emptyset$ to $A_{\ge}$ with the highest priority as follows:

1. $\forall \phi_j \in \emptyset, \forall \phi_k \in \emptyset, \phi_j \ge_{\emptyset} \phi_k$ and $\phi_k \ge_{\emptyset} \phi_j$.

2. $\forall \phi_j \in \emptyset, \forall \phi_k \in (S_i \setminus \emptyset)$ (with $1 \le i \le n$), $\phi_j >_{\emptyset} \phi_k$.

3. $\forall \phi_j \in (S_i \setminus \emptyset), \forall \phi_k \in (S_l \setminus \emptyset)$ (with $1 \le i, l \le n$), $\phi_j \ge_{\emptyset} \phi_k$ if and only if $\phi_j \geq \phi_k$.

The resulting ABox is given by the well-ordered partition: $A_{\ge_{\emptyset}} = \emptyset \cup (S_1 \setminus \emptyset) \cup \cdots \cup (S_n \setminus \emptyset)$

Let us begin by establishing the property **LLE**.

**Lemma 3.** (LLE for totally preordered KBs) Let $\mathcal{K}_\ge = \langle \mathcal{T}, A_\ge \rangle$ be a totally preordered knowledge base, $\emptyset$ be an observation and $q$ be a query. The query-answering relation $\emptyset \vdash_{\mathcal{K}_\ge}^s q$ satisfies **LLE** (where $s \in \{\pi, c\pi\}$).

*Proof.* We recall that **LLE** is defined by:

If $\langle \mathcal{T}, \mathcal{O}_1 \rangle \equiv \langle \mathcal{T}, \mathcal{O}_2 \rangle$ and $\mathcal{O}_1 \vdash_{\mathcal{K}_\ge}^s \mathcal{O}_3$ then $\mathcal{O}_2 \vdash_{\mathcal{K}_\ge}^s \mathcal{O}_3$ (where $s \in \{\pi, c\pi\}$).

In the case of totally preordered knowledge base, it is enough to show that if $\langle \mathcal{T}, \mathcal{O}_1 \rangle \equiv \langle \mathcal{T}, \mathcal{O}_2 \rangle$ then $\langle \mathcal{T}, \mathcal{R}(A_{\ge \emptyset_1}) \rangle \equiv \langle \mathcal{T}, \mathcal{R}(A_{\ge \emptyset_2}) \rangle$.

We will first use the following observation: let $S$ be a set of assertions. Then if $\langle \mathcal{T}, \mathcal{O}_1 \rangle \equiv \langle \mathcal{T}, \mathcal{O}_2 \rangle$ and $\langle \mathcal{T}, \mathcal{O}_1 \cup S \rangle$ is consistent then $\langle \mathcal{T}, \mathcal{O}_2 \cup S \rangle$ is also consistent, and if $\langle \mathcal{T}, \mathcal{O}_1 \cup S \rangle$ is inconsistent then $\langle \mathcal{T}, \mathcal{O}_2 \cup S \rangle$ is also inconsistent ... (*).

Let $S_1 \cup \cdots \cup S_n$ be the well-ordered partition associated with $A_{\ge}$. The result of the conditioning of $\ge$ by $\emptyset_1$ is given by: $A_{\ge \emptyset_1} = \emptyset_1 \cup (S_1 \setminus \emptyset_1) \cup \cdots \cup (S_n \setminus \emptyset_1)$. Assume that the possibilistic repair $\mathcal{R}(A_{\ge \emptyset_1}) = \emptyset_1 \cup (S_1 \setminus \emptyset_1) \cup \cdots \cup (S_i \setminus \emptyset_1)$,
then, $\langle \mathcal{T}, \mathcal{O}_1 \cup (S_1 \setminus \mathcal{O}_1) \cup \dots \cup (S_i \setminus \mathcal{O}_1) \rangle$ is consistent and $\langle \mathcal{T}, \mathcal{O}_1 \cup (S_1 \setminus \mathcal{O}_1) \cup \dots \cup (S_{i+1} \setminus \mathcal{O}_1) \rangle$ is inconsistent.
In a trivial way, $\mathcal{O}_1 \cup (S_1 \setminus \mathcal{O}_1) \cup \dots \cup (S_i \setminus \mathcal{O}_1)$ can be simplified to $\mathcal{O}_1 \cup S_1 \cup \dots \cup S_i$. Therefore, the possibilistic repair is given by $\mathcal{R}(A_{\ge \mathcal{O}_1}) = \mathcal{O}_1 \cup S_1 \cup \dots \cup S_i$.

In the same way, the conditioning of $\ge$ by $\mathcal{O}_2$ gives as result $A_{\ge \mathcal{O}_2} = \mathcal{O}_2 \cup (S_1 \setminus \mathcal{O}_2) \cup \dots \cup (S_n \setminus \mathcal{O}_2)$. This can also be simplified by $A_{\ge \mathcal{O}_2} = \mathcal{O}_2 \cup S_1 \cup \dots \cup S_n$. Thus, based on the observation (*), if $\langle \mathcal{T}, \mathcal{O}_1 \cup S_1 \cup \dots \cup S_i \rangle$ is consistent then $\langle \mathcal{T}, \mathcal{O}_2 \cup S_1 \cup \dots \cup S_i \rangle$ is consistent, and if $\langle \mathcal{T}, \mathcal{O}_1 \cup S_1 \cup \dots \cup S_{i+1} \rangle$ is inconsistent then $\langle \mathcal{T}, \mathcal{O}_2 \cup S_1 \cup \dots \cup S_{i+1} \rangle$ is inconsistent. This yields a repair for $A_{\ge \mathcal{O}_2}$ such that $\mathcal{R}(A_{\ge \mathcal{O}_2}) = \mathcal{O}_2 \cup S_1 \cup \dots \cup S_i$. Therefore, since $\langle \mathcal{T}, \mathcal{O}_1 \rangle \equiv \langle \mathcal{T}, \mathcal{O}_2 \rangle$, we conclude that $\langle \mathcal{T}, \mathcal{R}(A_{\ge \mathcal{O}_1}) \rangle \equiv \langle \mathcal{T}, \mathcal{R}(A_{\ge \mathcal{O}_2}) \rangle$. $\square$

Now, we introduce two properties regarding the notion of repair in totally preordered ABoxes. These two properties will be useful to establish the satisfaction of **Cut** and **CM** when dealing with partially preordered ABoxes, see Subsection 7.3.3. The first property (given by Lemma 4) states that, in the context of a totally preordered knowledge base, adding plausible conclusions to a possibilistic repair does not change the repair; to be more precise, the result of these additions leads to an equivalent result. More formally:

**Lemma 4.** Let $\mathcal{K}_{\ge} = \langle \mathcal{T}, A_{\ge} \rangle$ be a totally preordered knowledge base such that $\langle \mathcal{T}, \mathcal{R}(A_{\ge}) \rangle \models f$, where $f$ is a given assertion (not necessarily in $A_{\ge}$). Let $\ge_f$ be the conditioning of $\ge$ by $\{f\}$. Then $\langle \mathcal{T}, \mathcal{R}(A_{\ge}) \rangle \equiv \langle \mathcal{T}, \mathcal{R}(A_{\ge_f}) \rangle$ and $\{f\} \cup \mathcal{R}(A_{\ge}) = \mathcal{R}(A_{\ge_f})$.

*Proof.* Assume that $\langle \mathcal{T}, \mathcal{R}(A_{\ge}) \rangle \models f$ and let us show that indeed:

$$ \langle \mathcal{T}, \mathcal{R}(A_{\ge}) \rangle \equiv \langle \mathcal{T}, \mathcal{R}(A_{\ge_f}) \rangle $$

Let $S_1 \cup \dots \cup S_n$ be the well-ordered partition associated with $A_{\ge}$. By Definition 2, the possibilistic repair is given by $\mathcal{R}(A_{\ge}) = S_1 \cup \dots \cup S_i$ such that $\langle \mathcal{T}, S_1 \cup \dots \cup S_i \rangle$ is consistent and $\langle \mathcal{T}, S_1 \cup \dots \cup S_{i+1} \rangle$ is inconsistent. From the assumption, we have $\langle \mathcal{T}, S_1 \cup \dots \cup S_i \rangle \models f$. The conditioning of $\ge$ by $\{f\}$ is given by $A_{\ge_f} = \{f\} \cup (S_1 \setminus \{f\}) \cup \dots \cup (S_n \setminus \{f\})$. Since $\langle \mathcal{T}, S_1 \cup \dots \cup S_{i+1} \rangle$ is inconsistent, one can directly infer that $\langle \mathcal{T}, \{f\} \cup (S_1 \setminus \{f\}) \cup \dots \cup (S_{i+1} \setminus \{f\}) \rangle$ is inconsistent. Moreover, since $\langle \mathcal{T}, \mathcal{R}(A_{\ge}) \rangle \models f$ then $\langle \mathcal{T}, \{f\} \cup S_1 \cup \dots \cup S_i \rangle$ is consistent, thus $\langle \mathcal{T}, \{f\} \cup (S_1 \setminus \{f\}) \cup \dots \cup (S_i \setminus \{f\}) \rangle$ is consistent. It follows that $\mathcal{R}(A_{\ge_f}) = \{f\} \cup (S_1 \setminus \{f\}) \cup \dots \cup (S_i \setminus \{f\})$. Therefore, $\mathcal{R}(A_{\ge})$ and $\mathcal{R}(A_{\ge_f})$ are equivalent with respect to the TBox $\mathcal{T}$. $\square$

The second property is simply a generalization of Lemma 4 to the case where a set of assertions (instead of just one assertion) is derived:

**Lemma 5.** Let $\mathcal{K}_{\ge} = \langle \mathcal{T}, A_{\ge} \rangle$ be a totally preordered knowledge base such that $\langle \mathcal{T}, \mathcal{R}(A_{\ge}) \rangle \models \mathcal{O}$, where $\mathcal{O}$ is a set of assertions consistent with respect to $\mathcal{T}$. Let $\ge_{\mathcal{O}}$ be the conditioning of $\ge$ by $\mathcal{O}$. Then $\langle \mathcal{T}, \mathcal{R}(A_{\ge}) \rangle \equiv \langle \mathcal{T}, \mathcal{R}(A_{\ge_{\mathcal{O}}}) \rangle$ and $\mathcal{O} \cup \mathcal{R}(A_{\ge}) = \mathcal{R}(A_{\ge_{\mathcal{O}}})$.

*Proof.* The proof of this lemma follows directly from the proof of Lemma 4, where it is enough to apply Lemma 4 iteratively to each assertion from $\mathcal{O}$. $\square$

### 7.3.2. On the relationship between a partial preorder and its compatible total preorders when conditioning

This subsection introduces the relationship between the set of the total preorders compatible with the initial partial preorder, and the set of the total preorders compatible with the partial preorder obtained after adding a new observation with the highest priority.

Lemma 6 makes it possible to establish the link between the conditioning of a partial preorder and the conditioning of the total preorders which are compatible with it. More precisely, the lemma states that:

i) if you start from a set (noted $X$ in Lemma 6) of total preorders compatible with a partial preorder $\supseteq$; and

ii) you condition each of the total preorders by the observation $\mathcal{O}$;

iii) then the set obtained (noted $Y$ in Lemma 6) is equal to the set (noted $Z$ in Lemma 6) of the total preorders compatible with the partial preorder conditioned by the observation $\mathcal{O}$.

More formally:

**Lemma 6.** Let $A_{\ge}$ be a partially preordered ABox. Let $\mathcal{O}$ be an observation. Let $A_{\ge_{\mathcal{O}}}$ be the result of conditioning $\supseteq$ by $\mathcal{O}$. Consider the following sets:
- $X = \{\ge_i : \ge_i \text{ is compatible with } \ge\}$

- $Y = \{\ge_j : \ge_j \text{ is compatible with } \ge_\emptyset\}$

- $Z = \{\ge_{i_\emptyset} : \ge_{i_\emptyset} \text{ the result of conditioning } \ge_i \text{ by } \emptyset \text{ and where } \ge_i \in X\}$, where orderings in $X$, $Y$ and $Z$ are all defined on $\mathcal{A}$.

Then $Y = Z$.

*Proof.*

1. Let us show that $Z \subseteq Y$. Let $\ge_i \in X$ be a total preorder compatible with $\ge$. Let us show that its conditioned preorder $\ge_{i_\emptyset}$ preserves the ordering relation in $\ge_\emptyset$ (namely, $\ge_{i_\emptyset}$ is compatible with $\ge_\emptyset$). The ordering between the elements of $\emptyset$ is immediately preserved in $\ge_{i_\emptyset}$ by the Definition 12 of the conditioning. In the same way, the ordering between the elements of $\emptyset$ and the elements in $\mathcal{A} \setminus \emptyset$ is also preserved in $\ge_{i_\emptyset}$. The partial preorder $\ge_\emptyset$ is given by:

- $\forall \phi \in \emptyset, \forall \psi \in \emptyset: \phi \ge_\emptyset \psi$ and $\psi \ge_\emptyset \phi$, this ordering is preserved in $\ge_{i_\emptyset}$ by step 1 of the conditioning ... (¹).

- $\forall \phi \in \emptyset, \forall \psi \in \mathcal{A} \setminus \emptyset: \phi \triangleright_\emptyset \psi$, this ordering is preserved in $\ge_{i_\emptyset}$ by step 2 of the conditioning ... (²).

It remains to show that the ordering between the elements in $\mathcal{A} \setminus \emptyset$ is also preserved in $\ge_{i_\emptyset} \in Z$. For these elements, the partial preorder $\ge_\emptyset$ is simply equal to $\ge$, since $\forall \phi \in \mathcal{A} \setminus \emptyset, \forall \psi \in \mathcal{A} \setminus \emptyset: \phi \ge_\emptyset \psi$ if and only if $\phi \ge \psi$. Since $\ge_i \in X$ is compatible with $\ge$, the ordering is preserved by the extension such that: if $\phi \triangleright \psi$ then $\phi > \psi$ and if $\phi \ge \psi$ and $\psi \ge \phi$ then $\phi \ge \psi$ and $\psi \ge \phi$.

Finally, for any conditioned total preorder $\ge_{i_\emptyset} \in Z$, the step 3 of the conditioning guarantees that the ordering $\ge_i$ of the elements in $\mathcal{A} \setminus \emptyset$ is preserved. Therefore, $\ge_{i_\emptyset} \in Z$ also preserves the ordering $\ge$ of the elements in $\mathcal{A} \setminus \emptyset$ ... (³).

From (¹), (²), (³), we conclude that any $\ge_{i_\emptyset} \in Z$ is compatible with $\ge_\emptyset$.

2. Let $\ge_j \in Y$. Let us show that $Y \subseteq Z$. Let us first focus on the sub-ordering of $\ge_j$ only defined on $\mathcal{A} \setminus \emptyset$. Recall that the ordering $\ge_j$ is obtained by extending the partial preorder $\ge_\emptyset$ such that $\forall \phi \in \mathcal{A} \setminus \emptyset, \forall \psi \in \mathcal{A} \setminus \emptyset$, if $\phi \ge_\emptyset \psi$ then $\phi \ge_j \psi$ (a compatible total preorder preserves the ordering of the partial preorder by definition). $\ge_\emptyset$ is obtained by adding $\emptyset$ to $\mathcal{A} \setminus \emptyset$, $\ge_\emptyset$ preserves then the ordering of $\ge$. Therefore, it is also the case for the assertions in $\mathcal{A} \setminus \emptyset$, $\ge_j$ preserves the ordering of $\ge_\emptyset$ ... (¹).

It remains to consider the elements in $\emptyset$ in the ordering $\ge_j$. The ordering in $\ge_\emptyset$ is preserved by any $\ge_j \in Y$. The assertions in $\emptyset$ are equally reliable and strictly more certain than the assertions in $\mathcal{A} \setminus \emptyset$ ... (²).

From (¹), the sub-ordering of $\ge_j$ only defined on $\mathcal{A} \setminus \emptyset$ is compatible with $\ge$. From (²), adding the assertions in $\emptyset$ to $\mathcal{A} \ge_j$ with the highest priority collapses with the conditioning of a compatible with $\ge$ (i.e., $\ge_i \in X$) by $\emptyset$ to obtain $\ge_{i_\emptyset} \in Z$. We conclude that $\ge_j \in Y$ is also compatible with $\ge_\emptyset$.

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

### 7.3.3. Satisfaction of LLE, Cut and CM for partially preordered ABoxes

Now, we are ready to provide the proofs of the satisfaction of the remaining properties, namely, **LLE**, **Cut** and **CM**, which are based on the properties presented in the above subsections 7.3.1 and 7.3.2. Namely, the properties for totally preordered ABoxes, and the relationship between the set of the total preorders compatible with the initial partial preorder, and the set of the total preorders compatible with the partial preorder obtained after adding a new observation with the highest priority.

More precisely, using Lemmas 3 and 6, we can show that **LLE** (Left Logical Equivalence) is also valid in the case of partial preorders.

**Lemma 7. (LLE for partially preordered KBs)** Let $\mathcal{K}_\ge = \langle \mathcal{T}, \mathcal{A}_\ge \rangle$ be a partially preordered knowledge base, $\mathcal{O}$ be an observation and $q$ be a query. The query-answering relations $\Vdash_{\mathcal{K}_\ge}^\pi$ and $\Vdash_{\mathcal{K}_\ge}^{c\pi}$ satisfy **LLE**.

*Proof.* Let $\mathcal{A}_{\ge \emptyset_1}$ and $\mathcal{A}_{\ge \emptyset_2}$ be the result of adding $\emptyset_1$ and $\emptyset_2$ respectively to $\mathcal{A}_\ge$ with the highest priority. In order to prove the satisfaction of **LLE** for both inference relations $\Vdash_{\mathcal{K}_\ge}^\pi$ and $\Vdash_{\mathcal{K}_\ge}^{c\pi}$, it is enough to show that if $\langle \mathcal{T}, \emptyset_1 \rangle \equiv \langle \mathcal{T}, \emptyset_2 \rangle$ then $\langle \mathcal{T}, \pi(\mathcal{A}_{\ge \emptyset_1}) \rangle \equiv \langle \mathcal{T}, \pi(\mathcal{A}_{\ge \emptyset_2}) \rangle$ (resp. $\langle \mathcal{T}, c\pi(\mathcal{A}_{\ge \emptyset_1}) \rangle \equiv \langle \mathcal{T}, c\pi(\mathcal{A}_{\ge \emptyset_2}) \rangle$).
Based on Lemma 6, each $\geq_{\mathcal{O}_1}$ (resp. $\geq_{\mathcal{O}_2}$) that is compatible with $\geq_{\mathcal{O}_1}$ (resp. $\geq_{\mathcal{O}_2}$) can be obtained equivalently by
conditioning a compatible $\geq$ with $\sqsupseteq$ by $\mathcal{O}_1$ (resp. $\mathcal{O}_2$).

Based on the result of Lemma 3, $\forall A_{\geq} \text{ compatible with } A_{\geq}, \text{ if } \langle T, O_1 \rangle \equiv \langle T, O_2 \rangle \text{ then } \langle T, R(A_{\geq_{O_1}}) \rangle \equiv \langle T, R(A_{\geq_{O_2}}) \rangle$. It follows that, by intersection, if $\langle T, O_1 \rangle \equiv \langle T, O_2 \rangle$ then $\langle T, \pi(A_{\geq_{O_1}}) \rangle \equiv \langle T, \pi(A_{\geq_{O_2}}) \rangle$. Hence, LLE is satisfied by the partially preordered possibilistic repair.

In the same way, $\forall A_{\geq}$ compatible with $A_{\geq}$, if $\langle T, O_1 \rangle \equiv \langle T, O_2 \rangle$ then $\langle T, cl(R(A_{\geq_{O_1}})) \rangle \equiv \langle T, cl(R(A_{\geq_{O_2}})) \rangle$. Hence, by intersection, if $\langle T, O_1 \rangle \equiv \langle T, O_2 \rangle$ then $\langle T, c\pi(A_{\geq_{O_1}}) \rangle \equiv \langle T, c\pi(A_{\geq_{O_2}}) \rangle$. Therefore, LLE is satisfied by the Cπ-repair. $\square$

Finally, the next lemma shows that the properties CUT and CM (Cautious Monotony) hold for partially preordered knowledge bases, thanks to Lemmas 4 and 5.

**Lemma 8.** Let $\mathcal{K}_{\geq} = \langle \mathcal{T}, \mathcal{A}_{\geq} \rangle$ be a partially preordered knowledge base, $\mathcal{O}$ be an observation and $q$ be a query. The query-answering relations $\Vdash_{\mathcal{K}_{\geq}}^\pi$ and $\Vdash_{\mathcal{K}_{\geq}}^{c\pi}$ satisfy **Cut** and **CM**.

*Proof.*

1. **Cut** states that if $\mathcal{O}_1 \Vdash_{\mathcal{K}_{\geq}}^s \mathcal{O}_2$ and $\mathcal{O}_1 \cup \mathcal{O}_2 \Vdash_{\mathcal{K}_{\geq}}^s \mathcal{O}_3$ then $\mathcal{O}_1 \Vdash_{\mathcal{K}_{\geq}}^s \mathcal{O}_3$ (where $s \in \{\pi, c\pi\}$).

- Proof for $s = \pi$, we already showed in Lemmas 4 and 5 that, for a totally preordered ABox $A_{\geq}$, if $\langle \mathcal{T}, \mathcal{R}(A_{\geq}) \rangle \models \mathcal{O}$ then $\langle \mathcal{T}, \mathcal{R}(A_{\geq}) \rangle \equiv \langle \mathcal{T}, \mathcal{R}(A_{\geq_{\mathcal{O}}}) \rangle$.

This result can be generalized to the partially preordered possibilistic repair. By definition, if $\langle T, \pi(A_{\geq}) \rangle \models \mathcal{O}$ then $\forall \geq \text{ compatible with } \geq, \langle T, R(A_{\ge}) \rangle \models \mathcal{O}$. This means that $\forall A_{\geq}, \langle T, R(A_{\ge}) \rangle \equiv \langle T, R(A_{\geq_{\mathcal{O}}}) \rangle$. Therefore, by intersection, we obtain $\langle T, \pi(A_{\ge}) \rangle \equiv \langle T, \pi(A_{\ge_{\mathcal{O}}}) \rangle$.

Let $A_{\geq_{\mathcal{O}_1}}$ be the ABox obtained through the conditioning of $\geq$ by $\mathcal{O}_1$. Let $A_{\geq_{\mathcal{O}_{1,2}}}$ be the ABox obtained through the conditioning of $\geq$ by $\mathcal{O}_1$ and $\mathcal{O}_2$. Based on the previous result, one can infer that if $\langle T, \pi(A_{\geq_{\mathcal{O}_1}}) \rangle \models \mathcal{O}_2$ then $\langle T, \pi(A_{\geq_{\mathcal{O}_1}}) \rangle \equiv \langle T, \pi(A_{\geq_{\mathcal{O}_1}}) \rangle$. Therefore, for a set of assertions $\mathcal{O}_3$ if $\langle T, \pi(A_{\geq_{\mathcal{O}_{1,2}}}) \rangle \models \mathcal{O}_3$, then $\langle T, \pi(A_{\geq_{\mathcal{O}_1}}) \rangle \models \mathcal{O}_3$.

- When $s = c\pi$, thanks to the use of the deductive closure, showing that if $\langle T, c\pi(A_{\geq_{\mathcal{O}_1}}) \rangle \models \mathcal{O}_2$ then $\langle T, c\pi(A_{\geq_{\mathcal{O}_1}}) \rangle \equiv \langle T, c\pi(A_{\geq_{\mathcal{O}_1}}) \rangle$ can be done directly. In fact, $\langle T, c\pi(A_{\geq_{\mathcal{O}_1}}) \rangle \models \mathcal{O}_2$ means that for any totally preordered ABox $A_{\geq_{\mathcal{O}_1}}$ compatible with $A_{\geq_{\mathcal{O}_1}} : \langle T, cl(R(A_{\geq_{\mathcal{O}_1}})) \rangle \models \mathcal{O}_2$. Which means that $\mathcal{O}_2 \subseteq cl(R(A_{\geq_{\mathcal{O}_1}}))$, hence, $\mathcal{O}_2 \subseteq c\pi(A_{\geq_{\mathcal{O}_1}})$. Therefore, $\langle T, c\pi(A_{\geq_{\mathcal{O}_1}}) \rangle \equiv \langle T, c\pi(A_{\geq_{\mathcal{O}_{1,2}}}) \rangle$ is verified. We conclude that if $\langle T, c\pi(A_{\geq_{\mathcal{O}_{1,2}}}) \rangle \models \mathcal{O}_3$ then $\langle T, c\pi(A_{\geq_{\mathcal{O}_1}}) \rangle \models \mathcal{O}_3$.

2. **CM** (Cautious Monotony) states that $\mathcal{O}_1 \Vdash_{\mathcal{K}_{\geq}}^s \mathcal{O}_2$ and $\mathcal{O}_1 \Vdash_{\mathcal{K}_{\geq}}^s \mathcal{O}_3$ then $\mathcal{O}_1 \cup \mathcal{O}_2 \Vdash_{\mathcal{K}_{\geq}}^s \mathcal{O}_3$ (where $s \in \{\pi, c\pi\}$). Recall that $\mathcal{O}_1 \Vdash_{\mathcal{K}_{\geq}}^s \mathcal{O}_2$ amounts to applying the standard entailment $\langle T, \pi(A_{\geq_{\mathcal{O}_1}}) \rangle \models \mathcal{O}_2$ (resp. $\langle T, c\pi(A_{\geq_{\mathcal{O}_1}}) \rangle \models \mathcal{O}_2$).

- For $s = \pi$, we start from the result of Lemmas 4 and 5 for totally preordered knowledge bases. If $\langle T, R(A_{\geq}) \rangle \models \mathcal{O}$ then $\mathcal{O} \cup R(A_{\geq}) = R(A_{\geq_{\mathcal{O}}})$.

This result can be generalized to the partially preordered possibilistic repair. Let $A_{\geq_{\mathcal{O}_1}}$ be the ABox obtained through the conditioning of $\geq$ by $\mathcal{O}_1$. Let $A_{\geq_{\mathcal{O}_{1,2}}}$ be the ABox obtained through the conditioning of $\geq$ by $\mathcal{O}_1$ and $\mathcal{O}_2$. By definition, if $\langle T, \pi(A_{\geq_{\mathcal{O}_1}}) \rangle \models \mathcal{O}_2$ then $\forall \geq_{\mathcal{O}_1}$ compatible with $\geq_{\mathcal{O}_1}, \langle T, R(A_{\geq_{\mathcal{O}_1}}) \rangle \models \mathcal{O}_2$. This means that $\forall A_{\geq_{\mathcal{O}_1}}, \mathcal{O}_2 \cup R(A_{\geq_{\mathcal{O}_1}}) = R(A_{\geq_{\mathcal{O}_{1,2}}})$ (by Lemmas 4 and 5). Thus, by intersection, we obtain $\mathcal{O}_2 \cup \pi(A_{\geq_{\mathcal{O}_1}}) = \pi(A_{\geq_{\mathcal{O}_{1,2}}})$. Therefore, $\pi(A_{\geq_{\mathcal{O}_1}}) \subseteq \pi(A_{\geq_{\mathcal{O}_{1,2}}})$. One can infer directly that if $\langle T, \pi(A_{\geq_{\mathcal{O}_1}}) \rangle \models \mathcal{O}_3$, then $\langle T, \pi(A_{\geq_{\mathcal{O}_{1,2}}}) \rangle \models \mathcal{O}_3$.

- For $s = c\pi$, the proof that if $\langle T, c\pi(A_{\geq_{\mathcal{O}_1}}) \rangle \models \mathcal{O}_2$ then $c\pi(A_{\geq_{\mathcal{O}_1}}) \subseteq c\pi(A_{\geq_{\mathcal{O}_{1,2}}})$ is immediate thanks to the use of the deductive closure.

The entailment $\langle T, c\pi(A_{\geq_{\mathcal{O}_1}}) \rangle \models \mathcal{O}_2$ means that $\forall \geq_{\mathcal{O}_1}$ compatible with $\geq_{\mathcal{O}_1}, \langle T, R(A_{\geq_{\mathcal{O}_1}}) \rangle \models \mathcal{O}_2$. From Lemma 5, $\mathcal{O}_2 \cup R(A_{\geq_{\mathcal{O}_1}}) = R(A_{\geq_{\mathcal{O}_{1,2}}})$. This means that for any $A_{\geq_{\mathcal{O}_1}}, R(A_{\geq_{\mathcal{O}_1}}) \subseteq R(A_{\geq_{\mathcal{O}_{1,2}}})$. By introducing the deductive
closure: $cl(R(A_{\ge \vartheta_1})) \subseteq cl(R(A_{\ge \vartheta_2})).$ Thus, by intersection, $c\pi(A_{\ge \vartheta_1}) \subseteq c\pi(A_{\ge \vartheta_{1,2}})$. Therefore, one can also infer that if $\langle \mathcal{T}, c\pi(A_{\ge \vartheta_1}) \rangle \models \mathcal{O}_3$ then $\langle \mathcal{T}, c\pi(A_{\ge \vartheta_{1,2}}) \rangle \models \mathcal{O}_3$.

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

# 8. Beyond DL-Lite$_R$ and the possibilistic semantics

In this section, we discuss to what extent the methods proposed in this paper can be extended to expressive description languages and other inconsistency-tolerant semantics.

From a semantic point of view, the definitions of Cπ-repair given in Section 5, established within the framework of DL-Lite$_R$, remain valid. Indeed, the general process presented in Figure 3 is not exclusive to DL-Lite$_R$ and easily applies to richer description languages (e.g., Existential Rules). The important assumption that must first be satisfied is that the notion of ABox in the rich language is the same as that in DL-Lite$_R$. For the π-repair, it is sufficient to use the consistency test of the rich language, instead of the consistency test defined in DL-Lite$_R$. In the context of cπ-repair, the language must also support the notion of deductive closure of an ABox with respect to a TBox. With these two small changes, from a semantic point of view, our methods can thus easily adapt to richer description logic languages.

On the computational level, the characterization proposed in this paper to avoid the generation of all total orders is more complex. Clearly, the challenge here is at the computational level, since we need first to find an equivalent characterization (like we did in this paper using support/dominance) and then show that it is tractable. For instance, in many description logics where conflicts may be composed of any number of assertions (unlike DL-Lite$_R$ where conflicts consist of at most two assertions [16]), the extension of the support/dominance characterization is possible. However, even if the conflict set is computed in polynomial time, the size of this set itself can be exponential with respect to the size of the ABox. In this case, tractability cannot be preserved. To illustrate our statements, we will utilize a slightly more expressive language than DL-Lite$_R$ in the following subsection (8.1). This language, referred to as DL-Lite$_{R,\Pi}$, enables the representation of conjunctions on the left-hand side of axioms, a feature not available in DL-Lite$_R$. The presence of conjunctions in the language has consequences for the structure of conflicts, which are no longer binary. We will show that it is possible to achieve the same characterization with DL-Lite$_{R,\Pi}$ as proposed in our paper for DL-Lite$_R$. However, since the set of conflicts is no longer guaranteed to be polynomial, this results in the computation of repair being non-tractable.

Regarding the applicability of our methods to inconsistency-tolerant semantics, we first distinguish those that are not directly based on repairs, such as paraconsistent multivalued description logics, etc. These approaches do not align with the spirit of the methods developed in this paper; therefore, their adaptation is not immediate for reasoning with partially ordered ABoxes. In the context of multivalued semantics, the ABox remains unchanged, but the query-answering mechanisms need to be adapted, which can generate additional computational costs. A necessary first step would be to start with an existing multivalued semantics for standard DL-Lite$_R$ (for example, the 4-valued semantics provided in [85]), and then extend it to the possibilistic framework with a totally ordered ABox. This requires an adaptation of existing work (for a flat ABox) to define preferred 4-valued canonical models. The final step involves taking all the extensions of the total orders and defining the 4-valued canonical models of the partial ABox as the union of the preferred 4-valued canonical models of each total ABox extension. For inconsistency-tolerant semantics based on repairs, the extension is also feasible from a semantic point of view. However, it should be noted that the strategy we used in our approach produces a single repair for each total order. In the general case, using a different strategy, each total order may return multiple repairs. In subsection 8.2, we will use the semantic adaptation of our method with the inconsistency-tolerant semantics known as lexicographic or cardinality-based semantics [12]. Whether for semantics based on repairs or not, the challenge is to have an equivalent characterization (without generating all the extensions of the partial order) as provided in this paper (Propositions 1 and 2).

## 8.1. On the extension of the Cπ-repair to DL-Lite$_{R,\Pi}$

This subsection briefly discusses the applicability of our method to the language DL-Lite$_{R,\Pi}$ [11], which extends the DL-Lite$_R$ language with the ability to specify conjunctions on the left-hand side of an inclusion axiom, and for which query answering is first-order logic (FOL) reducible [11]. The main message in this subsection is that the extension of our method to DL-Lite$_{R,\Pi}$ is possible from both a semantic perspective and a characterization perspective. The primary reason is that the key concepts used in the definition of our method for DL-Lite$_R$ (closure, conflict, support, dominance) remain the same as those in DL-Lite$_{R,\Pi}$. However, there remains a major difference: in DL-Lite$_R$, conflicts are binary,
while in DL-Lite<sub>R,Π</sub>, a conflict can involve any number of elements. As a consequence, the set of all conflicts, which is polynomial in DL-Lite<sub>R</sub>, is no longer polynomial in DL-Lite<sub>R,Π</sub>.

Let us briefly recall the language DL-Lite<sub>R,Π</sub>, which is an extension of DL-Lite<sub>R</sub> with the addition of two complex concept constructors (highlighted in bold below). More formally, the language DL-Lite<sub>R,Π</sub> is defined by :

$B := A \mid \exists R \mid B_1 \sqcap B_2$

$C := A \mid \exists R \mid \neg A \mid \neg \exists R \mid \exists R.A$

$R := P \mid P^{-}$

$E := R \mid \neg R$

A and P are atomic concepts and roles, respectively. B, C, R and E are basic concepts, complex concepts, basic roles and complex roles, respectively. The negation symbol $\neg$ denotes complement sets, and the existential quantifier $\exists$ denotes existential restriction. In addition, $B_1 \sqcap B_2$ denotes conjunction of concepts and $\exists R.A$ denotes qualified existential quantification.

A knowledge base is a pair $\mathcal{K} = (\mathcal{T}, \mathcal{A})$ where $\mathcal{T}$ is a TBox containing a finite set of inclusion axioms of the form: $B \sqsubseteq C$ and $R \sqsubseteq E$, and $\mathcal{A}$ is the ABox, which contains a finite set of assertions (or ground facts) of the form: $\mathcal{A}(a)$ and $P(a, b)$, where $a, b$ are individuals. Concerning the semantics, the equations of the interpretation function (of DL-Lite<sub>R</sub>) given in Section 2 hold, in addition to the two following equations for the two newly added connectors:

$$ (B_1 \sqcap B_2)^I = B_1^I \sqcap B_2^I; $$

$$ (\exists R.A)^I = \{x \in \Delta^I | \exists y \in \Delta^I \text{ such that } (x, y) \in R^I \text{ and } y \in A^I\}. $$

### 8.1.1. The similarity of DL-Lite<sub>R</sub> and DL-Lite<sub>R,Π</sub> in the definition of C<sub>π</sub>-repair.

Although the language DL-Lite<sub>R,Π</sub> is more expressive than DL-Lite<sub>R</sub>, it nonetheless belongs to the same family of DL-Lite, and as such, it shares most of the concepts used in this paper, which makes our method easily adaptable to the language DL-Lite<sub>R,Π</sub>. More precisely, in the context of this work, DL-Lite<sub>R,Π</sub> and DL-Lite<sub>R</sub> share the following concepts:

* The ABox is defined in the same way in both languages. As a result, the concept of the partially preordered ABox and its compatible total preorders remains identical to that presented in Section 4.2.

* In both languages, a knowledge base is consistent if it admits at least one model, and is inconsistent otherwise. As a result, the notion of conflict given in Definition 1 remains the same. Of course, the mechanisms for testing consistency in DL-Lite<sub>R,Π</sub> and DL-Lite<sub>R</sub> are not the same, but this does not affect the definition of conflicts. Similarly, since the notion of possibilistic repair, given in Definition 2, in the total order used in DL-Lite<sub>R</sub> is based solely on consistency tests, this definition directly adapts to the language DL-Lite<sub>R,Π</sub>. We denote by $R^\Delta$ the result of the repair, as given by Definition 2, but using the language DL-Lite<sub>R,Π</sub> to test the consistency of a knowledge base.

* The notion of positive deductive closure, as given in Definition 6, is immediately applicable to a DL-Lite<sub>R,Π</sub> knowledge base (KB). Indeed, this definition is general, and to instantiate it in the DL-Lite<sub>R,Π</sub> language, it suffices to use the standard entailment relation (from sets of positive axioms) of the DL-Lite<sub>R,Π</sub> language. We denote by $cl_\Pi$ the result of the closure of the ABox, as given by Definition 6, but using the inference relation of language DL-Lite<sub>R,Π</sub>.

* From these first observations, we can already see that the computation of C<sub>π</sub>-repair, from a semantic point of view, using repairs on all total compatible orders applies directly to the language DL-Lite<sub>R,Π</sub>, as follows:

$$ c\pi(A_\Delta) = \bigcap_{i=1}^{m} \{cl_\Pi R^\Delta(A_{\ge i}) \mid A_{\ge i} \text{ is compatible with } A_\Delta\} $$

Where $A_{\ge i}$ denotes a totally preordered ABox that is compatible with $A_\Delta$.

* Finally, the definition of the notion of support can be applied as is to the language DL-Lite<sub>R,Π</sub>, with the understanding that the standard inference relation of DL-Lite<sub>R,Π</sub> is used instead of that of DL-Lite<sub>R</sub>. Similarly, the definition of dominance, as presented in Definition 9, applies to subsets of the ABox (whether binary or not), and therefore its application does not require any adaptation to the language DL-Lite<sub>R,Π</sub>. These two observations
allow us to use the syntactic characterization given in Proposition 2, which remains valid for the language DL-Lite<sub>R,Π</sub>. The proofs of Propositions 1 and 2 also hold in the case of a DL-Lite<sub>R,Π</sub> KB, since they have been established for the case of conflicts and supports of arbitrary sizes.

To summarize the points above, whether at the level of the semantic definition of C<sub>π</sub>-repair based on compatible total orders or at the level of characterization (Proposition 2), our method easily adapts to the language DL-Lite<sub>R,Π</sub>. Let us illustrate the computation of C<sub>π</sub>-repair with an example described in the language DL-Lite<sub>R,Π</sub>.

To show how our method can be applied to DL-Lite<sub>R,Π</sub> knowledge bases, let us consider the example of three research teams working on two (different) work packages each. We make the following considerations:

1. Each work package is led by a faculty-member, and;

2. A faculty-member cannot lead all the work packages across teams.

We employ the individuals $wp_1, wp_2, wp_3, wp_4, wp_5$ and $wp_6$ to represent the work packages and the roles $Leads_1, Leads_2$ and $Leads_3$ to designate the leader of a work package in each team. We use the TBox axiom $∃Leads_1 ∩ ∃Leads_2 ⊑ ¬∃Leads_3$ to express the second consideration "a faculty-member cannot lead all the work packages across teams", more precisely, the existential quantification over the three roles $Leads_1, Leads_2$ and $Leads_3$ must be disjoint.

**Example 12.** Let $\mathcal{K} \triangleq \langle \mathcal{T}, \mathcal{A}_\triangle \rangle$ be a DL-Lite<sub>R,Π</sub> knowledge base given by the TBox $\mathcal{T} = \{∃Leads_1 ∩ ∃Leads_2 ⊑ ¬∃Leads_3\}$, and the ABox $\mathcal{A}_\triangle$ such that:

$$ 
\begin{array}{l}
\mathcal{A}_\triangle = \{ \text{Leads}_1(\text{Mary}, \text{wp}_1), \text{Leads}_1(\text{Mary}, \text{wp}_2) \} \\
\cup \quad \{ \text{Leads}_2(\text{Mary}, \text{wp}_3), \text{Leads}_2(\text{Mary}, \text{wp}_4) \} \\
\cup \quad \{ \text{Leads}_3(\text{Mary}, \text{wp}_5), \text{Leads}_3(\text{Mary}, \text{wp}_6) \}
\end{array}
$$

Figure 8 illustrates the partial preorder $\triangleq$ over the ABox $\mathcal{A}_\triangle$.

Let us now exhibit the conflict set of the ABox $\mathcal{A}_\triangle$, using the axiom $∃Leads_1 ∩ ∃Leads_2 ⊑ ¬∃Leads_3$. We can easily check that the conflicts are of the form:

$$ C = \{ \text{Leads}_1(\text{Mary}, \text{wp}_i), \text{Leads}_2(\text{Mary}, \text{wp}_j), \text{Leads}_3(\text{Mary}, \text{wp}_k) \}, \text{ where } i \in \{1, 2\}, j \in \{3, 4\} \text{ and } k \in \{5, 6\}. $$

Namely, there are exactly (8) conflicts:

$$ \text{Cf}(\mathcal{A}_\triangle) = \{ 
\begin{aligned}
& \{ \text{Leads}_1(\text{Mary}, \text{wp}_1), \text{Leads}_2(\text{Mary}, \text{wp}_3), \text{Leads}_3(\text{Mary}, \text{wp}_5) \}, \{ \text{Leads}_1(\text{Mary}, \text{wp}_1), \text{Leads}_2(\text{Mary}, \text{wp}_3), \text{Leads}_3(\text{Mary}, \text{wp}_6) \}, \\
& \{ \text{Leads}_1(\text{Mary}, \text{wp}_1), \text{Leads}_2(\text{Mary}, \text{wp}_4), \text{Leads}_3(\text{Mary}, \text{wp}_5) \}, \{ \text{Leads}_1(\text{Mary}, \text{wp}_1), \text{Leads}_2(\text{Mary}, \text{wp}_4), \text{Leads}_3(\text{Mary}, \text{wp}_5) \}, \\
& \{ \text{Leads}_1(\text{Mary}, \text{wp}_2), \text{Leads}_2(\text{Mary}, \text{wp}_3), \text{Leads}_3(\text{Mary}, \text{wp}_5) \}, \{ \text{Leads}_1(\text{Mary}, \text{wp}_2), \text{Leads}_2(\text{Mary}, \text{wp}_3), \text{Leads}_3(\text{Mary}, \text{wp}_6) \}, \\
& \{ \text{Leads}_1(\text{Mary}, \text{wp}_2), \text{Leads}_2(\text{Mary}, \text{wp}_4), \text{Leads}_3(\text{Mary}, \text{wp}_5) \}, \{ \text{Leads}_1(\text{Mary}, \text{wp}_2), \text{Leads}_2(\text{Mary}, \text{wp}_4), \text{Leads}_3(\text{Mary}, \text{wp}_6) \}
\end{aligned}
\} $$

Indeed, the assertions $Leads_1(Mary, wp_1)$, $Leads_2(Mary, wp_3)$ and $Leads_3(Mary, wp_5)$ contradict the axiom $∃Leads_1 ∩ ∃Leads_2 ⊑ ¬∃Leads_3$ and form the first conflict, the same applies for the other conflicts.

Let us now compute the C<sub>π</sub>-repair of $\mathcal{A}_\triangle$:

- The assertions $Leads_1(Mary, wp_1)$ and $Leads_1(Mary, wp_2)$ are both strictly preferred to all the remaining assertions, and thus, each one of them forms a support for itself, and dominates all the conflicts.

- The assertion $Leads_2(Mary, wp_3)$ does not belong to $c\pi(\mathcal{A}_\triangle)$, because it is the only support for itself, and it does not dominate the conflict $\{Leads_1(Mary, wp_2), Leads_2(Mary, wp_4), Leads_3(Mary, wp_6)\}$, namely, not strictly preferred to an assertion from the conflict. The remaining assertions do not belong to $c\pi(\mathcal{A}_\triangle)$ and can be checked in the same way.

Therefore, the C<sub>π</sub>-repair of $\mathcal{A}_\triangle$ is given by:

$$ c\pi(\mathcal{A}_\triangle) = \{ \text{Leads}_1(\text{Mary}, \text{wp}_1), \text{Leads}_1(\text{Mary}, \text{wp}_2) \} $$
<figure><img src="image_21.png" /><figcaption>Figure 8: The partially preordered ABox $\mathcal{A}_{\Delta}$, $\rightarrow :$ the strict preference $\succ$.</figcaption></figure>

### 8.1.2. The main difference of DL-Lite<sub>R</sub> and DL-Lite<sub>R,Π</sub> in the definition of C<sub>π</sub>-repair.

The main difference between the application of the characterization on a DL-Lite<sub>R</sub> knowledge base and a DL-Lite<sub>R,Π</sub> knowledge base is the size of the conflicts and supports. In particular, each conflict in a DL-Lite<sub>R</sub> knowledge base has a size of at most 2. However, when working in the language DL-Lite<sub>R,Π</sub>, a conflict can be of any size. In the previous example, for instance, the conflicts were of size 3. This observation impacts the size of the set of all conflicts, which can be exponential with respect to the size of the ABox. In contrast, in DL-Lite<sub>R</sub>, this size is always polynomial with respect to the size of the ABox. This statement is illustrated through the following example:

**Example 12 (Continued).** In the knowledge base $\mathcal{K}_{\Delta} = \langle \mathcal{T}, \mathcal{A}_{\Delta} \rangle$, we limited ourselves to 3 research teams and 2 work packages by team. This also limits the number of concepts involved in the disjointness axiom used in the TBox. Assume now an arbitrary number of teams, then, the disjointness axiom becomes $\exists \text{Leads}_1 \sqcap \exists \text{Leads}_2 \sqcap \dots \sqcap \text{Leads}_{k-1} \sqsubseteq \neg \exists \text{Leads}_k$, where k represents the number of research teams (number of concepts ($\exists \text{Leads}_i$) involved in the disjointness axiom). In this case, with an arbitrary number (p) of work packages per team, the size of the conflict set can be given by:

$$|\text{Cf}(\mathcal{A}_{\Delta})| = O(p^k)$$

This is because conflicts are obtained by combining any k-tuple of assertions, each from a different role $\text{Leads}_i$.

The above example shows how the size of the conflicts can exponentially grow with respect to the two factors used to construct the ABox, namely, k and p. Thus, the application of the C<sub>π</sub>-repair characterization, which is based on support and dominance, can be impractical when dealing with conflicts of an arbitrary size.

## 8.2. A Lexicographic-Based semantics for the C<sub>π</sub>-repair

In this subsection, we propose the application of a different repairing semantics on the totally preordered extensions of the initial partially preordered ABox, which is in this case the Lexicographic Preferred-Based Repair ($\text{PAR}_{\text{lex}}$) [12]. The aim is to show that it is possible to achieve such an extension for any given repair semantics, but it is not always possible to find a tractable characterization. First, we recall the notion of a Lexicographical Preferred-Based Repair.

**Definition 13 (lexicographic preferred-based repair).** Let $\mathcal{K}_{\Delta} = \langle \mathcal{T}, \mathcal{A}_{\Delta} \rangle$ be a totally preordered KB. Let $(S_1, \dots, S_n)$ be the well-ordered partition associated with the ABox $\mathcal{A}_{\Delta}$. Let $R_1$ and $R_2$ be two consistent subsets of $(S_1, \dots, S_n)$.

- $R_1$ is as preferred as $R_2$ if $|R_1 \cap S_i| = |R_2 \cap S_i|$, for $i = 1, \dots, n$.

- $R_1$ is strictly preferred to $R_2$ if $|R_1 \cap S_i| > |R_2 \cap S_i|$, for some $i \in \{1, \dots, n\}$ and $|R_1 \cap S_j| = |R_2 \cap S_j|$, $\forall j$ such that $1 \le j < i$.

Where $|X|$ is the cardinality of the set X.

Then $R \subseteq \mathcal{A}_{\Delta}$ is a lexicographical preferred-based repair of $\mathcal{A}_{\Delta}$ if there is no $R' \subseteq \mathcal{A}_{\Delta}$ such that $R'$ is strictly preferred to $R$. The set of all the lexicographic preferred repairs of $\mathcal{A}_{\Delta}$ is denoted $\text{PAR}_{\text{lex}}(\mathcal{A}_{\Delta})$, and the intersection of all the lexicographic preferred-based repairs of $\mathcal{A}_{\Delta}$ is given by $\text{IPR}_{\text{lex}}(\mathcal{A}_{\Delta}) = \bigcap \{\mathcal{R} | \mathcal{R} \in \text{PAR}_{\text{lex}}(\mathcal{A}_{\Delta})\}$.

The lexicographic preferred-based repair, as given by Definition 13, can be extended to partially preordered ABoxes by deductively closing all the sets obtained from the intersection of the lexicographic preferred-based repairs of the totally preordered ABoxes compatible with the initial partially preordered ABox. Formally, for a given partially preordered knowledge base $\mathcal{K}_{\Delta} = \langle \mathcal{T}, \mathcal{A}_{\Delta} \rangle$:

$$\text{ICLR}_{\Delta}(\mathcal{A}_{\Delta}) = \bigcap_{i=1}^{m} \{cl(\text{IPR}_{\text{lex}}(\mathcal{A}_{\ge i})) | \mathcal{A}_{\ge i} \text{ is compatible with } \mathcal{A}_{\Delta}\}$$
Step 1: First, extend the partially preordered ABox $A_\Delta$ into a family of totally preordered ABoxes, denoted $A_{\ge 1}, \dots, A_{\ge m}$.

Step 2: Then, compute the set of lexicographical preferred-based repairs $PAR_{lex}(A_{\ge i})$ for each obtained totally preordered ABox $A_{\ge j}$.

Step 3: Compute the intersection of lexicographical preferred-based repairs $IPR_{lex}(A_{\ge i})$ of each obtained set of lexicographical preferred-based repairs $PAR_{lex}(A_{\ge j})$.

Step 4: Compute the deductive closure, as per Definition 6, of each intersection of lexicographical preferred-based repairs $cl(IPR_{lex}(A_{\ge i}))$.

Step 5: Intersect all the closed repairs to obtain a single closure-based repair $ICLR_\Delta(A_\Delta)$ (the Intersection of Closed Lexicographic Preferred-Based Repairs of a partially preordered ABox).

<figure><img src="image_22.png" /><figcaption>Figure 9: The process of computing $ICLR_\Delta(A_\Delta)$</figcaption></figure>

Where $ICLR_\Delta(A_\Delta)$ denotes the Intersection of Closed Lexicographic Preferred-Based Repairs of a partially preordered ABox. The process of applying the lexicographic preferred-based repair to a partially preordered knowledge base, $K_\Delta = \langle T, A_\Delta \rangle$ then applying the deductive closure operator is depicted in Figure 9.

The following example applies the above description on a partially preordered knowledge base $K_\Delta$.

**Example 13.** Let $K_\Delta = \langle T, A_\Delta \rangle$ be a partially preordered knowledge base, where the TBox T is given by the following axioms:

$$ T = \left\{ \begin{array}{l} 1. \ \mathrm{FullProf} \sqsubseteq \mathrm{Prof} \\ 2. \ \mathrm{Prof} \sqsubseteq \mathrm{FacMember} \\ 3. \ \mathrm{Dean} \sqsubseteq \mathrm{FacMember} \\ 4. \ \mathrm{FullProf} \sqsubseteq \neg \mathrm{VisitingProf} \\ 5. \ \mathrm{PostDoc} \sqsubseteq \neg \mathrm{Dean} \end{array} \right\} $$

Axiom 1 states that individuals holding the title of full professor are considered professors. Axioms 2 and 3 state that individuals holding the title of professor and dean are considered faculty-members. Axioms 4 and 5 express that the sets of full professors and visiting professors, and the sets of post-doctorates and deans, respectively, are mutually disjoint.

$$ A = \{\mathrm{Dean}(\mathrm{Bob}), \mathrm{FullProf}(\mathrm{Alice}), \mathrm{PostDoc}(\mathrm{Bob}), \mathrm{Prof}(\mathrm{Alice}), \mathrm{VisitingProf}(\mathrm{Alice}), \mathrm{Secondee}(\mathrm{Mary})\} $$

Such that the partial preorder $\supseteq$ over the assertions of the ABox is given by:

- $\mathrm{Dean}(\mathrm{Bob}) \supset \mathrm{FullProf}(\mathrm{Alice}) \supset \mathrm{PostDoc}(\mathrm{Bob}) \supset \mathrm{Secondee}(\mathrm{Mary})$, and;

- $\mathrm{Dean}(\mathrm{Bob}) \supset \mathrm{Prof}(\mathrm{Alice}) \supset \mathrm{VisitingProf}(\mathrm{Alice}) \supset \mathrm{Secondee}(\mathrm{Mary})$.

The remaining relations are incomparable, namely: $\mathrm{FullProf}(\mathrm{Alice}) \not\supseteq \mathrm{Prof}(\mathrm{Alice}), \mathrm{FullProf}(\mathrm{Alice}) \not\supseteq \mathrm{VisitingProf}(\mathrm{Alice}), \mathrm{VisitingProf}(\mathrm{Alice}) \not\supseteq \mathrm{PostDoc}(\mathrm{Bob})$ and $\mathrm{Prof}(\mathrm{Alice}) \not\supseteq \mathrm{PostDoc}(\mathrm{Bob})$.

As per Definition 1, one can exhibit the conflict set of $A_\Delta$: $\mathrm{Cf}(A_\Delta) = \{C_1, C_2\}$ where $C_1 = \{\mathrm{Dean}(\mathrm{Bob}), \mathrm{PostDoc}(\mathrm{Bob})\}$ and $C_2 = \{\mathrm{FullProf}(\mathrm{Alice}), \mathrm{VisitingProf}(\mathrm{Alice})\}$. Figure 10 depicts the conflicts and the partial preorder of the ABox $A_\Delta$.

Let us now consider the total preorder extensions, denoted $\ge 1, \dots, \ge m$ of the partial preorder $\supseteq$. Some obtained totally preordered ABoxes are given as follows:

- $A_{\ge 1}$, where $\ge 1$ is given by: $\mathrm{Dean}(\mathrm{Bob}) > \mathrm{FullProf}(\mathrm{Alice}) > \mathrm{PostDoc}(\mathrm{Bob}) > \mathrm{Prof}(\mathrm{Alice}) > \mathrm{VisitingProf}(\mathrm{Alice}) > \mathrm{Secondee}(\mathrm{Mary})$.

- $A_{\ge 2}$, where $\ge 2$ is given by: $\mathrm{Dean}(\mathrm{Bob}) > \mathrm{Prof}(\mathrm{Alice}) > \mathrm{VisitingProf}(\mathrm{Alice}) > \mathrm{FullProf}(\mathrm{Alice}) > \mathrm{PostDoc}(\mathrm{Bob}) > \mathrm{Secondee}(\mathrm{Mary})$.

- $A_{\ge 3}$, where $\ge 3$ is given by: $\mathrm{Dean}(\mathrm{Bob}) > \mathrm{Prof}(\mathrm{Alice}) > \mathrm{VisitingProf}(\mathrm{Alice}) \equiv \mathrm{FullProf}(\mathrm{Alice}) > \mathrm{PostDoc}(\mathrm{Bob}) > \mathrm{Secondee}(\mathrm{Mary})$.
<figure><img src="image_23.png" /><figcaption>Figure 10: →: strict preference. —: conflict.</figcaption></figure>

By applying the Lexicographic Preferred-Based Repair of Definition 13, the totally preordered ABoxes $A_{\ge 1}$, $A_{\ge 2}$ and $A_{\ge 3}$ return the following subsets:

- $PAR_{lex}(A_{\ge 1}) = \{\{\text{Dean}(\text{Bob}), \text{FullProf}(\text{Alice}), \text{Prof}(\text{Alice}), \text{Secondee}(\text{Mary})\}\}$.

- $PAR_{lex}(A_{\ge 2}) = \{\{\text{Dean}(\text{Bob}), \text{Prof}(\text{Alice}), \text{VisitingProf}(\text{Alice}), \text{Secondee}(\text{Mary})\}\}$.

- $PAR_{lex}(A_{\ge 3}) = \{\{\text{Dean}(\text{Bob}), \text{FullProf}(\text{Alice}), \text{Prof}(\text{Alice}), \text{Secondee}(\text{Mary})\}, \{\text{Dean}(\text{Bob}), \text{Prof}(\text{Alice}), \text{VisitingProf}(\text{Alice}), \text{Secondee}(\text{Mary})\}\}$.

Note that for the above total preorders, the method either returns a single preferred repair or returns two repairs with the same cardinality at each partition.

The intersection of the two lexicographic preferred-based repairs in $PAR_{lex}(A_{\ge 3})$ gives $IPR_{lex}(A_{\ge 3}) = \{\text{Dean}(\text{Bob}), \text{Prof}(\text{Alice})\}$. Applying the deductive closure, given by Definition 6, gives the following results:

- $cl(IPR_{lex}(A_{\ge 1})) = \{\text{Dean}(\text{Bob}), \text{FullProf}(\text{Alice}), \text{Prof}(\text{Alice}), \text{FacMember}(\text{Bob}), \text{FacMember}(\text{Alice}), \text{Secondee}(\text{Mary})\}$.

- $cl(IPR_{lex}(A_{\ge 2})) = \{\text{Dean}(\text{Bob}), \text{Prof}(\text{Alice}), \text{VisitingProf}(\text{Alice}), \text{FacMember}(\text{Bob}), \text{FacMember}(\text{Alice}), \text{Secondee}(\text{Mary})\}$.

- $cl(IPR_{lex}(A_{\ge 3})) = \{\text{Dean}(\text{Bob}), \text{Prof}(\text{Alice}), \text{FacMember}(\text{Bob}), \text{FacMember}(\text{Alice}), \text{Secondee}(\text{Mary})\}$.

The intersection of all the closed repairs returns the following consistent subset of the ABox:

$$ICLR_{\ge}(A_{\ge}) = \{\text{Dean}(\text{Bob}), \text{Prof}(\text{Alice}), \text{FacMember}(\text{Bob}), \text{FacMember}(\text{Alice}), \text{Secondee}(\text{Mary})\}$$

The application of the partially preordered possibilistic repair given by Definition 3 and the closure-based partially preordered possibilistic repair given by Definition 7 on this example's knowledge base gives the following sets:

$$\pi(A_{\ge}) = \{\text{Dean}(\text{Bob})\} \qquad c\pi(A_{\ge}) = \{\text{Dean}(\text{Bob}), \text{Prof}(\text{Alice}), \text{FacMember}(\text{Bob}), \text{FacMember}(\text{Alice})\}$$

In this example, we can already see that the described method returns a repair that is larger than both the $\pi$-repair $\pi(A_{\ge})$ and the $C\pi$-repair.

The main issue with the method described above is computational, since even in the case of a total preorder over the assertions, the lexicographic preferred-based repair semantics are not tractable [12]. The characterization, which was defined for the $C\pi$-repair and based on support and dominance, does not apply in this case. Indeed, finding a tractable characterization when dealing with semantics for partially preordered knowledge bases is not guaranteed.

## 9. Concluding discussions

This paper follows a long line of research, where the aim is to develop tractable and safe methods to repair inconsistent large-scale knowledge bases. The main issue here is to maintain tractability when computing a productive repair. The use of the positive deductive closure to produce larger repairs increases time complexity. For instance, the extension of the well-known IAR semantics [2] with the ICR semantics [9] is no longer tractable.

We tackled the issue of computing a productive repair for possibilistic partially preordered ontologies. We defined the $C\pi$-repair method which interprets a partial preorder into a family of compatible total preorders, computes their possibilistic repairs, closes those repairs and intersects them to yield a more productive repair. An important result
of this paper is that we characterized this method equivalently using the notions of dominance and support, which ensures the tractable computation of the repair. Moreover, checking whether an assertion belongs to the Cπ-repair can be performed by progressively examining the conflicts. This incremental feature is particularly beneficial for evolving ABoxes.

The two possibilistic semantics studied in this paper, namely the Cπ-repair and the π-repair, satisfy the unconditional properties (Proposition 5) and the System P rules (Proposition 6). If these propositions seem natural, even minimal, some inconsistency-tolerant semantics do not always satisfy them. For example, the so-called majority semantics (a query is valid if it is obtained from the majority of the repairs of an inconsistent ABox) does not satisfy these minimal properties. More precisely, in [3], it has been shown that majority-based inference does not satisfy Cut, CM, and properties, even in DL-Lite<sub>R</sub>. Another example where System P is not satisfied is existential inference, where a query is valid if it follows from one repair. On the non-satisfaction of the rational monotony (RM) property, the result is expected if we draw a parallel with standard possibilistic propositional logic and with the properties of non-monotonic relations. Indeed, there is a representation theorem (KLM [81]) which shows that any non-monotonic relation which satisfies System P and RM is necessarily representable by a total order on the set of interpretations of propositional logic. Future work will explore whether rational monotonicity can be satisfied in specific cases when considering particular partial orders, such as lattices.

As we have discussed in detail in Section 8, our characterization can be generalized to more expressive description languages or other semantics. It is sufficient to replace the DL-Lite<sub>R</sub> inference relation in the support definition with that of a more expressive language. However, tractability is guaranteed only if the computation of the conflicts and supports is performed in polynomial time and their size also remains polynomial in the size of the ABox. Another intriguing question (to be addressed in the future) pertains to whether similar characterizations can be obtained for other tractable repair-based strategies when ABox are totally ordered, such as linear-based repair [53].

Future work involves applying the inconsistency management techniques developed in this paper to wastewater network data. The wastewater network domain presents challenges with large-scale, heterogeneous datasets from various sources. In the Starwars project (described in the acknowledgments section), we have collected and continue to collect significant data in different formats, such as Geographic Information Systems (GIS), pipe inspection videos (ITV), images, analogue maps, etc.

If we focus solely on GIS data, we have gathered five private or public datasets for the Montpellier metropolitan area in southern France. Each dataset is stored in the Shapefile model, a widely used geospatial vector data model for Geographic Information System (GIS) software, where information for each element of the wastewater network (e.g., manholes, pipes) is represented in separate and distinct datasets.

These datasets present several challenges. First, they are large in scale. For the Montpellier metropolitan area alone, data on pipes and manholes account for approximately 100,000 components (for the largest GIS collected), each with dozens of attributes, resulting in a substantial set of assertional facts.

Since these datasets are incrementally built and integrate data from diverse sources, conflicts inevitably arise. For instance, a pipe might appear disconnected from the network based on GIS data, which is physically impossible in reality. Various criteria can be applied to resolve such inconsistencies, including prioritization based on geographical distances or temporal information corresponding to the installation dates of elements. When timestamps are available for all data, a total order can be established. However, wastewater network GIS data suffer from incompleteness across various attributes. This includes the installation date attribute, where this information for certain network elements (including manholes and pipes) is not always available or may only be given as time intervals. In such cases, a total order cannot be established among the network elements. Instead, a partial order becomes more appropriate and natural. The approaches proposed in this paper enable conflict resolution while taking partial orders into account. Partial ordering becomes even more necessary when dealing with heterogeneous data, where it involves aggregating network structures derived from GIS data [86] with those extracted from pipe inspection videos (ITV) [87] or analogue maps.

## Acknowledgements

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). This research was also 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] and in part
by the ANR project EXPIDA (EXplainable and parsimonious Preference models to get the most out of Inconsistent DTabases) [grant number ANR-22-CE23-0017]. We would like to express our gratitude to “Montpellier Méditerranée Métropole” and “La Régie des eaux de Montpellier Méditerranée Métropole” for providing the data essential for our research. Finally, we thank the anonymous referees for their valuable feedback on this paper.

## References

[1] 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 (3) (2007) 385-429. doi:https://doi.org/10.1007/s10817-007-9078-x.

[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. doi:https://doi.org/10.1007/978-3-642-15918-3_9.

[3] J. Baget, S. Benferhat, Z. Bouraoui, M. Croitoru, M. Mugnier, O. Papini, S. Rocher, K. Tabia, Inconsistency-tolerant query answering: Rationality properties and computational complexity analysis, in: European Conference Logics in Artificial Intelligence, JELIA, Vol. 10021 of LNCS, 2016, pp. 64-80. doi:https://doi.org/10.1007/978-3-319-48758-8_5.

[4] M. Bienvenu, C. Bourgaux, Inconsistency-tolerant querying of description logic knowledge bases, in: Reasoning Web: Logical Foundation of Knowledge Graph Construction and Query Answering, Vol. 9885, LNCS. Springer, 2016, pp. 156-202. doi:https://doi.org/10.1007/978-3-319-49493-7_5.

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

[6] S. Belabbes, S. Benferhat, J. Chomicki, Handling inconsistency in partially preordered ontologies: the Elect method, Journal of Logic and Computation 31 (5) (2021) 1356-1388. doi:https://doi.org/10.1093/logcom/exab024.

[7] S. Belabbes, S. Benferhat, Computing a possibility theory repair for partially preordered inconsistent ontologies, IEEE Transactions on Fuzzy Systems (2021) 1-10doi:https://doi.org/10.1109/TFUZZ.2021.3107776.

[8] D. Calvanese, E. Kharlamov, W. Nutt, D. Zheleznyakov, Evolution of dl- lite knowledge bases, in: The Semantic Web-ISWC 2010: 9th International Semantic Web Conference, ISWC 2010, Shanghai, China, November 7-11, 2010, Revised Selected Papers, Part I 9, Springer, 2010, pp. 112-128.

[9] M. Bienvenu, On the complexity of consistent query answering in the presence of simple ontologies, in: Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 26, 2012, pp. 705-711. doi:https://doi.org/10.1609/aaai.v26i1.8218.

[10] 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. doi:https://doi.org/10.1007/978-3-031-43619-2_25.

[11] D. Calvanese, G. D. Giacomo, D. Lembo, M. Lenzerini, R. Rosati, Data complexity of query answering in description logics, in: P. Doherty, J. Mylopoulos, C. A. Welty (Eds.), Proceedings, Tenth International Conference on Principles of Knowledge Representation and Reasoning, Lake District of the United Kingdom, June 2-5, 2006, AAAI Press, 2006, pp. 260-270.

[12] 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.

[13] R. Kontchakov, C. Lutz, D. Toman, F. Wolter, M. Zakharyaschev, The combined approach to query answering in DL-Lite, in: 12th International Conference on Principles of Knowledge Representation and Reasoning (KR), Toronto, Canada, 2010, pp. 247-257.

[14] A. Artale, D. Calvanese, R. Kontchakov, M. Zakharyaschev, The DL-Lite family and relations, Journal of Artificial Intelligence Research (JAIR) 36 (2009) 1-69.

[15] B. Motik, B. C. Grau, I. Horrocks, Z. Wu, A. Fokoue, C. Lutz, OWL 2 Web Ontology Language Profiles. W3C Recommendation, Available at https://www.w3.org/TR/owl2-profiles/ (11 December 2012.).

[16] 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. doi:https://doi.org/10.1007/978-3-642-17746-0_8.

[17] A. Kalyanpur, B. Parsia, M. Horridge, E. Sirin, Finding all justifications of OWL DL entailments, in: The Semantic Web: 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007+ ASWC 2007, Busan, Korea, November 11-15, 2007. Proceedings, Springer, 2007, pp. 267-280.

[18] Q. Ji, W. Li, S. Zhou, G. Qi, Y. Li, Benchmark construction and experimental evaluations for incoherent ontologies, Knowledge-Based Systems 239 (2022) 108090.

[19] J. de Kleer, R. Reiter, Foundations for assumption-based truth maintenance systems: Preliminary report, in: Proc. American Assoc. for Artificial Intelligence Nat. Conf, 1987, pp. 183-188.

[20] Y. Guo, Z. Pan, J. Heflin, Lubm: A benchmark for owl knowledge base systems, Journal of Web Semantics 3 (2-3) (2005) 158-182. doi:https://doi.org/10.1016/j.websem.2005.06.005.

[21] C. Baral, S. Kraus, J. Minker, V. S. Subrahmanian, Combining knowledge bases consisting of first-order theories, Computational intelligence 8 (1) (1992) 45-71.

[22] A. C. Finkelstein, D. Gabbay, A. Hunter, J. Kramer, B. Nuseibeh, Inconsistency handling in multiperspective specifications, IEEE Transactions on Software Engineering 20 (8) (1994) 569-578.

[23] N. Rescher, R. Manor, On inference from inconsistent premisses, Theory and decision 1 (2) (1970) 179-217.

[24] S. Benferhat, D. Dubois, H. Prade, Some syntactic approaches to the handling of inconsistent knowledge bases: A comparative study part 1: The flat case, Studia Logica 58 (1997) 17-45.

[25] A. Anderson, N. Belnap, Entailment: The logic of relevance and necessity, vol. i (1975).
[26] O. Arieli, A. Avron, A. Zamansky, Maximal and premaximal paraconsistency in the framework of three-valued semantics, Studia Logica 97 (2011) 31–60.

[27] F. Esteva, A. Figallo-Orellano, T. Flaminio, L. Godo, Logics of formal inconsistency based on distributive involutive residuated lattices, Journal of Logic and Computation 31 (5) (2021) 1226–1265.

[28] S. Benferhat, D. Dubois, H. Prade, Argumentative inference in uncertain and inconsistent knowledge bases, in: Uncertainty in Artificial Intelligence, Elsevier, 1993, pp. 411–419.

[29] P. Besnard, A. Hunter, Elements of argumentation, Vol. 47, MIT press Cambridge, 2008.

[30] P. M. Dung, On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games, Artificial intelligence 77 (2) (1995) 321–357.

[31] S. E. Toulmin, The uses of argument, Cambridge university press, 2003.

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

[33] L. E. Bertossi, Database Repairing and Consistent Query Answering, Synthesis Lectures on Data Management, Morgan & Claypool Publishers, 2011.

[34] M. Arenas, E. L. Bertossi, J. Chomicki, Consistent query answers in inconsistent databases, in: Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Philadelphia, Pennsylvania, USA, 1999, pp. 68–79.

[35] A. D. Fuxman, R. J. Miller, First-order query rewriting for inconsistent databases, in: International Conference on Database Theory, Springer, 2005, pp. 337–351.

[36] P. Haase, F. Van Harmelen, Z. Huang, H. Stuckenschmidt, Y. Sure, A framework for handling inconsistency in changing ontologies, in: The Semantic Web–ISWC 2005: 4th International Semantic Web Conference, ISWC 2005, Galway, Ireland, November 6-10, 2005. Proceedings 4, Springer, 2005, pp. 353–367.

[37] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Query rewriting for inconsistent dl-lite ontologies, in: International Conference on Web Reasoning and Rule Systems, Springer, 2011, pp. 155–169.

[38] D. Lembo, M. Lenzerini, R. Rosati, M. Ruzzi, D. F. Savo, Inconsistency-tolerant query answering in ontology-based data access, Journal of Web Semantics 33 (2015) 3–29.

[39] M. Bienvenu, C. Bourgaux, F. Goasdoué, Querying inconsistent description logic knowledge bases under preferred repair semantics, in: AAAI, 2014, pp. 996–1002.

[40] D. Lembo, M. Ruzzi, Consistent query answering over description logic ontologies, in: International Conference on Web Reasoning and Rule Systems, Springer, 2007, pp. 194–208.

[41] T. Lukasiewicz, E. Malizia, A. Vaicenavičius, Complexity of inconsistency-tolerant query answering in datalog+/- under cardinality-based repairs, Proceedings of the AAAI Conference on Artificial Intelligence 33 (01) (2019) 2962–2969. doi:10.1609/aaai.v33i01.33012962. URL https://ojs.aaai.org/index.php/AAAI/article/view/4152

[42] T. Lukasiewicz, M. Vanina Martinez, G. I. Simari, Inconsistency handling in datalog+/- ontologies, in: ECAI 2012, IOS Press, 2012, pp. 558–563.

[43] C. A. D. Deagustini, M. V. Martinez, M. A. Falappa, G. R. Simari, Datalog+-ontology consolidation, Journal of Artificial Intelligence Research 56 (2016) 613–656.

[44] A. Cali, G. Gottlob, T. Lukasiewicz, A general datalog-based framework for tractable query answering over ontologies, in: Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 2009, pp. 77–86.

[45] J.-F. Baget, M. Leclère, M.-L. Mugnier, E. Salvat, On rules with existential variables: Walking the decidability line, Artificial Intelligence 175 (9-10) (2011) 1620–1654.

[46] J. Baget, S. Benferhat, Z. Bouraoui, M. Croitoru, M. Mugnier, O. Papini, S. Rocher, K. Tabia, A general modifier-based framework for inconsistency-tolerant query answering, in: Principles of Knowledge Representation and Reasoning (KR), Cape Town, South Africa, 2016, pp. 513–516.

[47] M.-L. Mugnier, M. Thomazo, An introduction to ontology-based query answering with existential rules, Reasoning Web. Reasoning on the Web in the Big Data Era: 10th International Summer School 2014, Athens, Greece, September 8-13, 2014. Proceedings 10 (2014) 245–278.

[48] M.-L. Mugnier, Data access with horn ontologies: Where description logics meet existential rules, KI-Künstliche Intelligenz 34 (4) (2020) 475–489.

[49] T. Lukasiewicz, M. V. Martinez, A. Pieris, G. Simari, From classical to consistent query answering under existential rules, Proceedings of the AAAI Conference on Artificial Intelligence 29 (1) (Feb. 2015). doi:10.1609/aaai.v29i1.9414. URL https://ojs.aaai.org/index.php/AAAI/article/view/9414

[50] R. Rosati, On the complexity of dealing with inconsistency in description logic ontologies, in: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence - Volume Two, IJCAI’11, AAAI Press, 2011, p. 1057–1062.

[51] G. Brewka, Preferred subtheories: An extended logical framework for default reasoning, in: IJCAI, Detroit, USA, 1989, pp. 1043–1048.

[52] S. Benferhat, D. Dubois, H. Prade, Some syntactic approaches to the handling of inconsistent knowledge bases: A comparative study part 2: The prioritized case, Logic at work: essays dedicated to the memory of Helena Rasiowa 24 (Chapter 26) (1998) 473–511.

[53] B. Nebel, Base revision operations and schemes: Semantics, representation and complexity, in: A. G. Cohn (Ed.), Proceedings of the Eleventh European Conference on Artificial Intelligence, Amsterdam, The Netherlands, August 8-12, 1994, John Wiley and Sons, Chichester, 1994, pp. 341–345.

[54] G. Qi, Q. Ji, J. Z. Pan, J. Du, Extending description logics with uncertainty reasoning in possibilistic logic, International journal of intelligent systems 26 (4) (2011) 353–381.

[55] 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.
[56] D. Dubois, H. Prade, Possibilistic logic - an overview, Computational Logic 9 (2014) 197-255. doi:https://doi.org/10.1684/abc.2014.0944.

[57] D. Dubois, H. Prade, A crash course on generalized possibilistic logic, in: D. Ciucci, G. Pasi, B. Vantaggi (Eds.), Scalable Uncertainty Management - 12th International Conference, SUM, Milan, Italy, Vol. 11142 of Lecture Notes in Computer Science, Springer, 2018, pp. 3-17. doi:https://doi.org/10.1007/978-3-030-00461-3_1.

[58] M. Banerjee, D. Dubois, L. Godo, H. Prade, On the relation between possibilistic logic and modal logics of belief and knowledge, Journal of Applied Non-Classical Logics 27 (3-4) (2017) 206-224. doi:https://doi.org/10.1080/11663081.2018.1439357.

[59] W. Spohn, The Laws of Belief - Ranking Theory and Its Philosophical Applications, Oxford University Press, 2014. doi:https://doi.org/10.1093/acprof:oso/9780199697502.001.0001.

[60] R. Fagin, J. Y. Halpern, Y. Moses, M. Y. Vardi, Reasoning About Knowledge, MIT Press, 2003.

[61] A. P. Dempster, Upper and lower probabilities induced by a multivalued mapping, The Annals of Mathematical Statistics 38 (1967) 325-339. doi:https://doi.org/10.1007/978-3-540-44792-4_3.

[62] G. Shafer, A Mathematical Theory of Evidence, Princeton University Press, 1976.

[63] S. Benferhat, L. Garcia, Handling locally stratified inconsistent knowledge bases, Studia Logica 70 (1) (2002) 77-104.

[64] F. G. Cozman, Credal networks, Artificial Intelligence 120 (2000) 199-233.

[65] W. Spohn, Ordinal conditional functions: A dynamic theory of epistemic states, in: Causation in decision, belief change, and statistics: Proceedings of the Irvine Conference on Probability and Causation, Springer, 1988, pp. 105-134. doi:https://doi.org/10.1007/978-94-009-2865-7_6.

[66] D. Dubois, H. Prade, S. Sandri, On possibility/probability transformations, Fuzzy logic: State of the art (1993) 103-112doi:https://doi.org/10.1007/978-94-011-2014-2_10.

[67] D. Dubois, H. Prade, Possibility Theory: Qualitative and Quantitative Aspects, Springer Netherlands, Dordrecht, 1998, Ch. 6, pp. 169-226. doi:https://doi.org/10.1007/978-94-017-1735-9_6.

[68] L. Amgoud, S. Vesic, Rich preference-based argumentation frameworks, International Journal of Approximate Reasoning 55 (2) (2014) 585-606.

[69] Counting and enumerating preferred database repairs, Theoretical Computer Science 837 (2020) 115-157.

[70] D. Poole, On the comparison of theories: Preferring the most specific explanation., in: IJCAI, Vol. 85, Citeseer, 1985, pp. 144-147.

[71] 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.

[72] P. Snow, Diverse confidence levels in a probabilistic semantics for conditional logics, Artificial Intelligence 113 (1-2) (1999) 269-279.

[73] D. Dubois, H. Fargier, A unified framework for order-of-magnitude confidence relations, in: Proceedings of the 20th conference on Uncertainty in artificial intelligence, 2004, pp. 138-145.

[74] W. Spohn, A survey of ranking theory, in: Degrees of belief, Springer, 2009, pp. 185-228.

[75] G. Kern-Isberner, A. Hahn, J. Haldimann, C. Beierle, Total preorders vs ranking functions under belief revision—the dynamics of empty layers, in: Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, Vol. 21, 2024, pp. 498-508.

[76] J. Pearl, System z: A natural ordering of defaults with tractable applications to nonmonotonic reasoning, in: Probabilistic and Causal Inference: The Works of Judea Pearl, 2022, pp. 201-214.

[77] V. Chama, S. Wang, T. A. Meyer, G. Casini, Defeasible justification for kml-style logic, in: L. Giordano, J. C. Jung, A. Ozaki (Eds.), Proceedings of the 37th International Workshop on Description Logics (DL 2024), Bergen, Norway, June 18-21, 2024, Vol. 3739 of CEUR Workshop Proceedings, CEUR-WS.org, 2024.

[78] G. Casini, U. Straccia, Defeasible RDFS via rational closure, Inf. Sci. 643 (2023) 118409.

[79] G. Casini, U. Straccia, T. Meyer, A polynomial time subsumption algorithm for nominal safe elo⊥ under rational closure, CoRR abs/1802.08201 (2018).

[80] 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.

[81] S. Kraus, D. Lehmann, M. Magidor, Nonmonotonic reasoning, preferential models and cumulative logics, Artificial Intelligence Journal 44 (1-2) (1990) 167-207. doi:https://doi.org/10.1016/0004-3702(90)90101-5.

[82] K. Britz, G. Casini, T. Meyer, K. Moodley, U. Sattler, I. Varzinczak, Principles of klm-style defeasible description logics, ACM Trans. Comput. Log. 22 (1) (2021) 1:1-1:46. doi:https://doi.org/10.1145/3420258.

[83] L. Everett, E. Morris, T. Meyer, Explanation for klm-style defeasible reasoning, in: E. Jembere, A. J. Gerber, S. Viriri, A. W. Pillay (Eds.), Artificial Intelligence Research - Second Southern African Conference, SACAIR 2021, Durban, South Africa, 2021, Proceedings, Vol. 1551 of Communications in Computer and Information Science, Springer, 2021, pp. 192-207. doi:https://doi.org/10.1007/978-3-030-95070-5_13.

[84] D. Makinson, General patterns in nonmonotonic reasoning, in: C. J. H. DOV M. GABBAY, J. A. ROBINSON (Eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, Volume 3, Nonmonotonic Reasoning and Uncertain Reasoning, Oxford University Press, 1994, Ch. 2, pp. 35-110.

[85] L. Zhou, H. Huang, G. Qi, Y. Ma, Z. Huang, Y. Qu, Paraconsistent query answering over dl-lite ontologies, Web Intelligence and Agent Systems: An International Journal 10 (1) (2012) 19-31. doi:https://doi.org/10.3233/WIA-2012-0228.

[86] O. Ettarguy, C. Delenne, S. Benferhat, A. Begdouri, T. Do, T. Ma, From GIS to graphical representation for maintaining connectivity of wastewater network elements, SN Comput. Sci. 5 (7) (2024) 851.

[87] M.-T. Tran-Nguyen, S. Benferhat, N. Chahinian, C. Delenne, T.-N. Do, Building a wastewater network graph from inspection videos, in: Intelligent Systems and Data Science, Springer Nature Singapore, Singapore, 2025, pp. 188-202.