Sihem Belabbes

Salem Benferhat

Computing a Possibility Theory Repair for Partially Preordered Inconsistent Ontologies

We address the problem of handling inconsistency in uncertain knowledge bases that are specified in the lightweight fragments of Description Logics DL-Lite. More specifically, we assume that the TBox component is coherent, stable and fully reliable. However, the ABox component may be inconsistent with respect to the TBox, partially preordered and uncertain. Uncertainty is encoded in the framework of possibility theory. In this context, we propose an extension of standard possibilistic DL-Lite. We represent the ABox as a symbolic weighted base, where the weights attached to the assertions are ordered according to a strict partial order. We define a tractable method for computing a single possibilistic repair for a partially preordered weighted ABox. The idea is to consider the possibilistic compatible bases of such an ABox, which intuitively encode all the possible extensions of a partial order, and compute the possibilistic repair of each compatible base. We then compute the intersection of all these possibilistic repairs to obtain a single repair for the initial ABox. We also provide an equivalent characterization by introducing the notion of π-accepted assertions. This ensures that the computation of the partially preordered possibilistic repair can be achieved in polynomial time in DL-Lite.

Introduction

Possibility theory has been widely studied since the seminal work of Zadeh [START_REF] Lofti | Fuzzy sets as a basis for a theory of probability[END_REF]. Basically, it is an uncertainty theory that handles incomplete, uncertain, qualitative and prioritized information and supports reasoning in the presence of inconsistency [START_REF] Dubois | Generalized possibilistic logic: Foundations and applications to qualitative reasoning about uncertainty[END_REF][START_REF] Finger | Advances in weighted logics for artificial intelligence[END_REF]. Possibility theory has strong connections with ordinal conditional functions [START_REF] Spohn | The Laws of Belief -Ranking Theory and Its Philosophical Applications[END_REF] as well as with consonant belief functions [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF][START_REF] Fagin | Reasoning About Knowledge[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF].

Standard Possibilistic Logic [START_REF] Dubois | Possibility theory and its applications: Where do we stand?[END_REF], an extension of propositional logic, provides a natural logic-based framework for reasoning with inconsistent and uncertain information that is prioritized by way of a total preorder. In fact, Standard 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. A weight (or degree) is considered as a lower bound on the formula's certainty (or priority) level.

An important problem in knowledge representation is how to deal with and reason from inconsistent information. A research domain that has gained considerable interest is that of inconsistency management in formal ontologies, in particular those specified in the lightweight fragments of Description Logics known as DL-Lite. For instance, fuzzy extensions have been proposed for Description Logics [START_REF] Bobillo | Reasoning within fuzzy OWL 2 EL revisited[END_REF][START_REF] Borgwardt | Fuzzy description logics -a survey[END_REF][START_REF] Straccia | Foundations of Fuzzy Logic and Semantic Web Languages[END_REF] and also for DL-Lite [START_REF] Pan | Expressive querying over fuzzy DL-Lite ontologies[END_REF][START_REF] Straccia | Towards top-k query answering in description logics: The case of DL-Lite[END_REF]. Other research efforts have focused on possibilistic extensions of Description Logics [START_REF] Dubois | Possibilistic uncertainty and fuzzy features in description logic. a preliminary discussion. Fuzzy Logic and the Semantic Web[END_REF][START_REF] Qi | Extending description logics with uncertainty reasoning in possibilistic logic[END_REF] alongside probabilistic extensions [START_REF] Baader | The complexity of the consistency problem in the probabilistic description logic ALC me[END_REF][START_REF] Borgwardt | Recent advances in querying probabilistic knowledge bases[END_REF][START_REF] Lutz | Probabilistic description logics for subjective uncertainty[END_REF].

Furthermore, a framework for possibilistic DL-Lite has been proposed [START_REF] Benferhat | Min-based possibilistic DL-Lite[END_REF]. In essence, the assertions in the ABox are assigned weights to reflect the fact that some pieces of information are considered as more reliable than others. A nice feature of possibilistic DL-Lite is that query answering is tractable. This means that applying a total preorder over the assertions enhances the expressiveness of standard DL-Lite without incurring an additional computational cost.

Nonetheless, in several applications and notably in ontology engineering, the pieces of information can potentially be heterogeneous, large-scale, multi-source, outdated, erroneous and contradictory. In this respect, one may not be able to compare the reliability of the assertions. This requires the application of a strict partial order to the weights that are attached to the assertions. This means that ties or equalities between the weights are not allowed. On the other hand, the resulting order relation over the assertions is a partial preorder, since the same weight could be attached to more than one assertion (i.e., ties between the assertions are allowed). In this case, the corresponding ABox may be partially preordered.

Extensions of Standard Possibilistic Logic have been proposed to support reasoning with partially preordered information, mainly using the notion of compatible bases. The core notions of Standard Possibilistic Logic such as possibilistic inference have been revisited in [START_REF] Benferhat | Reasoning with partially ordered information in a possibilistic logic framework[END_REF]. Propositional logic formulas are assigned degrees belonging to a partially ordered uncertainty scale instead of the unit interval [0, 1]. The idea of assigning partially ordered symbolic weights to beliefs has also been studied in the context of weighted propositional logics [START_REF] Benferhat | How to infer from inconsistent beliefs without revising[END_REF][START_REF] Touazi | Possibilistic reasoning with partially ordered beliefs[END_REF]. However, these approaches are computationally expensive (∆ 2 p -hard). This makes them unsuitable for applications where query answering is the most important reasoning task.

In order to mitigate this issue, we are interested in extending the framework of standard possibilistic DL-Lite [START_REF] Benferhat | Min-based possibilistic DL-Lite[END_REF] to cater for partially preordered knowledge bases, without increasing the computational complexity of query answering.

Recently, an efficient method, called "Elect", has been proposed for handling inconsistency in partially preordered lightweight ontologies [START_REF] Belabbes | Elect: An inconsistency handling approach for partially preordered lightweight ontologies[END_REF]. The Elect method encompasses both the well-known IAR semantics [START_REF] Lembo | Inconsistencytolerant semantics for description logics[END_REF] (if the ABox is flat) as well as the so-called non-defeated semantics [START_REF] Benferhat | How to select one preferred assertionalbased repair from inconsistent and prioritized DL-Lite knowledge bases?[END_REF][START_REF] Benferhat | Some syntactic approaches to the handling of inconsistent knowledge bases : A comparative study. Part 2 : the prioritized case[END_REF] (if the ABox is totally preordered). The intuition consists in interpreting the partially preordered ABox as a family of totally preordered ABoxes. Consistent sub-bases of the total ABoxes are computed. Their intersection yields a single consistent sub-base for the initial ABox.

The present paper investigates whether the tractability of possibilistic DL-Lite can be maintained when the expressiveness is enriched to represent partially preordered weighted ABoxes. We show that this can be achieved by first considering a family of compatible ABoxes (which amount to a family of possibilistic DL-Lite ABoxes), then computing the possibilistic repair of each compatible ABox, followed by intersecting those repairs. The result is a single consistent sub-base for the initial partially pre-ordered weighted ABox.

Our main contribution is the provision of an equivalent characterization that identifies all the accepted assertions, called π-accepted. We show that they constitute a consistent (w.r.t. the TBox) sub-base which can be computed in polynomial time (w.r.t. the size of the initial ABox), without explicitly computing all the compatible ABoxes of the initial ABox. Moreover, we show that when the comparative relation between the symbolic weights of the assertions is a total order, the produced sub-base amounts to the possibilistic repair, as computed in standard possibilistic DL-Lite.

This paper is a revised and extended version of the conference paper [START_REF] Belabbes | On dealing with conflicting, uncertain and partially ordered ontologies[END_REF] and the French conference paper [START_REF] Belabbes | Ontologies légères inconsistantes partiellement pré-ordonnées en théorie des possibilités[END_REF]. We start by briefly recalling the underpinnings of DL-Lite in Description Logic, followed by its extension to a possibilistic logic framework. We introduce our tractable method for computing a consistent sub-base for a partially preordered weighted ABox. We discuss future work before concluding.

The Description Logic DL-Lite

The Description Logic DL-Lite [START_REF] Calvanese | Tractable reasoning and efficient query answering in description logics: The DL-Lite family[END_REF] is a family of knowledge representation languages that have gained popularity in several application domains such as formalizing lightweight ontologies, thanks to their expressive power and good computational properties. For instance, query answering from a DL-Lite knowledge base can be carried out efficiently using query rewriting [START_REF] Kontchakov | The combined approach to query answering in DL-Lite[END_REF]. Broadly speaking, the task of computing answers is reduced to a set of standard database query evaluations.

In this paper, we present DL-Lite R , one of the most popular DL-Lite dialects, which provides the logical underpinning for the OWL 2 QL profile designed for query answering [START_REF] Motik | OWL 2 Web Ontology Language Profiles[END_REF].

A Knowledge Base (KB) is built upon three countably infinite and mutually disjoint sets, C, R and I, containing respectively concept names, role names, and individual names.

The DL-Lite R language is recursively defined according to the following grammar:

• R := P | P -denotes a basic role, with P ∈ R and P -∈ R is the inverse of P .

• E := R | ¬R denotes a complex role.

• B := A | ∃R, with A ∈ C, stands for a basic concept.

• C := B | ¬B represents a complex concept.
In terms of semantics, an interpretation is a tuple I = ∆ I , • I , where ∆ I = ∅ and • I is an interpretation function mapping concept names A to A I ⊆ ∆ I , role names P to P I ⊆ (∆ I × ∆ I ), and individual names a to a I ∈ ∆ I . We extend the interpretation function • I to interpret complex concepts and roles of DL-Lite R as follows:

(P -) I = {(y, x) ∈ (∆ I × ∆ I ) | (x, y) ∈ P I }; (∃R) I = {x ∈ ∆ I | ∃y ∈ ∆ I s.t. (x, y) ∈ R I }; (¬B) I = ∆ I \ B I ; (¬R) I = (∆ I × ∆ I ) \ R I .
An inclusion axiom on concepts (resp. on roles) is a statement of the form B C (resp. R E). Concept inclusions with (resp. without) the negation symbol to the right of the inclusion symbol are called negative (resp. positive) inclusion axioms. An assertion (or ground fact) is a statement of the form A(a) or P (a, b), where a, b ∈ I.

An interpretation I satisfies an inclusion axiom B C (resp. R E), denoted by A DL-Lite R knowledge base is a pair K = T , A , where T is a finite set of inclusion axioms, a.k.a. TBox, and A is a finite set of assertions, a.k.a. ABox.

I B C (resp. I R E), if B I ⊆ C I (resp. R I ⊆ E I ).
An interpretation I is a model of a TBox T (resp. an ABox A), denoted by I T (resp. I A), if I α for every α in T (resp. in A). We say that I is a model of a KB K = T , A if I T and I A.

A knowledge base K is said to be consistent if it admits at least one model, otherwise it is inconsistent.

A TBox T is said to be incoherent if there is A ∈ C such that A I = ∅ for each interpretation I that is a model of T . Otherwise, T is coherent.

In the rest of this paper, we shall refer to the DL-Lite R dialect simply as DL-Lite.

Example 1. Consider the following sets of concept names, role names and individuals:

• C = {Tradi, Modern, WProp, WoProp, Prop}. They represent: traditional dance, modern dance, dance with props, dance without props, and the props used in dance performances.

• R = {hasProp}. This role links a dance to the prop used in the performance.

• I = {d 1 , d 2 , d 3 , r}. Each element d i ∈ I represents a dance. The element "r" represents a ribbon.

Let K = T , A be a DL-Lite KB built from the vocabulary introduced above. The TBox is given by:

T =    1. Tradi ¬Modern 2. WProp ¬WoProp 3. Modern ¬WProp 4. ∃hasProp WProp 5. ∃hasProp -Prop   
Axioms 1, 2 and 3 are negative inclusion axioms. They express pairwise disjointness between the concepts: traditional and modern dances, dances with props and without props, modern dances and dances with props. Axiom 4 requires that an element using a prop is a dance with props. Axiom 5 requires that an element used by a dance with props is indeed a prop. Consider a flat ABox (assertions without weights):

A =    Tradi(d 1 ), Modern(d 1 ), WoProp(d 1 ), Tradi(d 2 ), WProp(d 2 ), WoProp(d 2 ), hasProp(d 2 , r), Modern(d 3 ), WProp(d 3 ), Prop(r)   
One can easily check that the KB K is inconsistent. For instance, the individual "d 2 " is an instance of both the concepts "WProp" and "WoProp", which contradicts Axiom 2.

Anything can be derived from an inconsistent knowledge base, hence it is pointless to reason with it (i.e., evaluate queries over it). One way to tackle this problem is to compute repairs for the inconsistent ABox. A (maximal) repair is usually defined as a maximal (w.r.t. set inclusion) subset of the ABox that is consistent w.r.t. the TBox. 1Example 2. In the ABox A, it can be seen that:

• Tradi(d 1 ) and Modern(d 1 ) contradict Axiom 1.

• WProp(d 2 ) and WoProp(d 2 ) contradict Axiom 2.

• hasProp(d 2 , r) and WoProp(d 2 ) contradict Axiom 2, under Axiom 4.

• Modern(d 3 ) and WProp(d 3 ) contradict Axiom 3.

Since repairs are free of conflicts, the assertions that contradict some axiom may not belong to the same repair. It follows that A admits eight maximal repairs, R 1 , . . . , R 8 . This is summarized as follows:

R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 Tradi(d 1 ) Modern(d 1 ) WoProp(d 1 ) Tradi(d 2 ) WProp(d 2 ) WoProp(d 2 ) hasProp(d 2 , r) Modern(d 3 ) WProp(d 3 ) Prop(r)
Given an ABox that is inconsistent w.r.t. the TBox and its set of maximal repairs. Various strategies, known as inconsistency-tolerant semantics, have been proposed to perform meaningful query answering. The idea is to reason over the repairs instead of the initial inconsistent ABox.

Amongst the most well-known semantics, one can cite the ABox Repair (AR) semantics [START_REF] Lembo | Inconsistencytolerant semantics for description logics[END_REF] in which a query is considered to be valid if it follows from all the maximal repairs of the inconsistent ABox. However, the computational cost of the AR semantics is expensive, even in DL-Lite.

The Intersection ABox Repair (IAR) semantics [START_REF] Lembo | Inconsistencytolerant semantics for description logics[END_REF] is a tractable under-approximation of the AR semantics. Using the IAR semantics, queries are evaluated over one consistent sub-base of the ABox obtained from the intersection of all the maximal repairs.

These strategies have been extended to the case where the assertions of the ABox are totally preordered. For instance, the so-called non-defeated repair semantics [START_REF] Benferhat | How to select one preferred assertionalbased repair from inconsistent and prioritized DL-Lite knowledge bases?[END_REF] amounts to a prioritized version of the IAR semantics. Similarly, the so-called preferred sub-theories [START_REF] Bienvenu | Querying inconsistent description logic knowledge bases under preferred repair semantics[END_REF][START_REF] Brewka | Preferred subtheories: An extended logical framework for default reasoning[END_REF] amount to an extended version of the AR semantics. Several other strategies can also be found in the literature (see for example [START_REF] Baget | A general modifierbased framework for inconsistency-tolerant query answering[END_REF][START_REF] Bienvenu | Inconsistency-tolerant querying of description logic knowledge bases[END_REF][START_REF] Calvanese | Evolution of DL-Lite knowledge bases[END_REF][START_REF] Trivela | Query rewriting for DL ontologies under the ICAR semantics[END_REF]).

In this work, we consider the case of a partially preordered inconsistent knowledge base. We address the difficult problem of computing a possibilistic repair in a tractable way. We first recall the underpinnings of standard possibilistic DL-Lite.

Possibilistic DL-Lite Knowledge Base

Possibilistic logic and possibility theory [START_REF] Banerjee | On the relation between possibilistic logic and modal logics of belief and knowledge[END_REF][START_REF] Dubois | Possibilistic logic -an overview[END_REF][START_REF] Dubois | A crash course on generalized possibilistic logic[END_REF] are important frameworks for reasoning under uncertainty. Uncertain information can either be represented in extension by means of the so-called possibility distributions, or in a compact way by means of the so-called weighted logics or graphical models.

Possibility distributions

The semantics of a possibility theory is based on the concept of a possibility distribution. Let I be an interpretation (either a propositional logic interpretation in standard possibilistic logic, or a DL-Lite one in DL-Lite logics). A possibility distribution is a function π from the set of interpretations Ω (of the considered language) to the unit interval [0, 1]. A possibility degree π(I) represents the consistency degree of I, given the available pieces of information.

If π(I) = 1, then I is the most preferred (or the most normal, fully consistent, fully possible) interpretation. A possibility distribution π is normalized if it admits a fully possible interpretation. This reflects the fact that the set of available information is consistent. If there is no interpretation I ∈ Ω such that π(I) = 1, then π is subnormalized. In this case, the normalization degree of π which is obtained by:

h(π) = max I∈Ω π(I) . . . ( * )
measures to what extent the available pieces of information represented by π are consistent.

If π(I) < 1, then I is not a solution to the problem and it violates some available piece of information. More generally, for two interpretations I and I , if π(I) > π(I ), then I is more preferred (or more plausible) than I . Finally, when π(I) = 0, it is impossible for I to be a solution as it falsifies a fully certain information.

A possibility theory can be of two major forms: min-based and product-based [START_REF] Dubois | Possibility theory: qualitative and quantitative aspects[END_REF]. Both forms share the same definitions of possibility distributions, possibility measures and normalized possibility distributions. However, they differ on the meaning of the uncertainty scale [0, 1] and also on the definition of conditioning. In product-based possibility theory, possibility degrees may represent degrees of surprise, in the spirit of Spohn's Ordinal Conditional Functions (OCF) [START_REF] Spohn | The Laws of Belief: Ranking Theory and its Philosophical Applications[END_REF][START_REF] Spohn | Ordinal conditional functions. a dynamic theory of epistemic states[END_REF], or the result of transforming a probability distribution into a possibility distribution [START_REF] Benferhat | Probability-possibility transformations: Application to credal networks[END_REF][START_REF] Dubois | Practical methods for constructing possibility distributions[END_REF][START_REF] Dubois | On possibility/probability transformations[END_REF][START_REF] Sudkamp | On probability-possibility transformations[END_REF]. In min-based possibility theory, the uncertainty scale is used as an ordinal scale, thus only the order induced by the uncertainty degrees is used.

This paper falls within the framework of min-based possibility theory, where the focus is mainly on the relative plausibility relations between the formulas (here ABox assertions). Thus, possibility distributions are a means to rank-order the interpretations of a language (here DL-Lite interpretations).

Possibilistic DL-Lite

In what follows, we focus on compact representations of possibility distributions and describe possibilistic DL-Lite.

Possibilistic Description Logics [START_REF] Dubois | Possibilistic uncertainty and fuzzy features in description logic. a preliminary discussion. Fuzzy Logic and the Semantic Web[END_REF][START_REF] Hollunder | An alternative proof method for possibilistic logic and its application to terminological logics[END_REF] are extensions of standard Description Logic frameworks based on possibility theory that support reasoning and query answering with inconsistent and uncertain knowledge. Possibilistic DL-Lite [START_REF] Benferhat | Min-based possibilistic DL-Lite[END_REF] is an extension of the lightweight fragments DL-Lite. Similarly to standard possibilistic logic, the main idea consists in assigning priority degrees (or weights) to TBox axioms and ABox assertions to express their relative certainty (or confidence) in an inconsistent knowledge base. The inconsistency degree of the knowledge base can then be computed from those weights, making provision for possibilistic inference.

In the rest of this paper, we assume that the axioms in the TBox are fully certain (or fully reliable), thus uncertainty concerns only the assertions in the ABox. Definition 1. A possibilistic DL-Lite knowledge base is a weighted KB defined as a tuple WK = T , WA , where:

• T is a TBox in which all the axioms are fully certain.

• WA is a weighted ABox, i.e., the assertions are equipped with priority degrees from the unit interval ]0, 1], s.t.:

WA = {(f, α) | f is a DL-Lite assertion, α ∈]0, 1]}
We assume that a unique priority degree α is assigned to each assertion f ∈ WA. Nonetheless, this uniqueness hypothesis is not restrictive. Indeed, if some assertion f is assigned two different weights, say (f, α 1 ) and (f, α 2 ), then it is equivalent to consider only the assertion (f, max(α 1 , α 2 )).

Furthermore, we do not explicitly assign weights to TBox axioms since they are considered as fully certain. The assertions in WA with a priority degree α = 1 are considered to be fully certain and cannot be questioned, whereas the assertions with a priority degree α ∈]0, 1[ are said to be somewhat certain. The assertions with higher priority degrees are more certain than those with lower priority degrees. We ignore the assertions with α = 0, thus only the assertions that are somewhat or fully certain are stated explicitly.

In Definition 1, the uncertainty associated with the assertions is defined over the unit interval. In some situations, a total preorder relation is defined over all the available information (here the ABox) instead of weights in the unit interval (e.g. [START_REF] Telli | Polynomial algorithms for computing a single preferred assertionalbased repair[END_REF]). A total preorder relation can be represented with well-ordered partitions (or stratifications) of an ABox A of the form A = (S 1 , S 2 , . . . , S n ), where:

• S 1 ∪ S 2 ∪ . . . ∪ S n = A, • ∀i ∈ {1, . . . , n}, ∀j ∈ {1, . . . , n}, S i ∩ S j = ∅ for i = j,
• the assertions of a stratum S i are of equal priority and have a higher priority than any assertion in S j with j < i.

In this paper, we choose to follow the standard representation of the uncertainty scale (namely, the unit interval [0, 1]).

Example 3. We continue Example 1 and equip the flat ABox A with weights. Let WK = T , WA be the corresponding weighted KB. The TBox remains unchanged. The weighted ABox is given by:

WA =            (Tradi(
          
As in standard possibilistic logic, weighted or possibilistic DL-Lite knowledge bases are compact representations of possibility distributions. Indeed, each possibilistic DL-Lite knowledge base WK = T , WA induces a unique possibility distribution, denoted by π WK , over DL-Lite interpretations.

Let I be a DL-Lite interpretation. If I is not a model of T , then I is impossible and its possibility degree is π WK (I) = 0. Indeed, in this paper, we assume that the TBox is stable, fully certain and coherent. Similarly, an interpretation is impossible if it falsifies some fully certain assertion in WA. Now, if I is a model (in the sense of standard DL-Lite) of both T and WA, then π WK (I) = 1. This indicates that I is fully compatible with the information given in the KB.

Lastly, interpretations that are models of T but falsify somewhat certain assertions are compared according to the most important assertions that they falsify. For two interpretations I and I , we have π WK (I) > π WK (I ) if the certainty degree of the most important assertion falsified by I is lower than its counterpart in I . In this case, I is said to be more compatible with the KB than I .

The above explanations are captured as follows:

Definition 2. Let WK = T , WA be a possibilistic DL-Lite KB. The possibility distribution induced by WK is given by:

π WK (I) =        1 if ∀φ i ∈ T , I φ i and ∀(f i , α i ) ∈ WA, I f i 0 if ∃φ i ∈ T , s.t. I φ i min{(1 -α i )|(f i , α i ) ∈ WA, I f i } otherwise
• Tradi I 1 = {d 1 }, Modern I 1 = {d 1 }. • Tradi I 2 = {d 1 , d 2 }, Modern I 2 = {d 3 }, WProp I 2 = {d 2 }, WoProp I 2 = {d 1 }, Prop I 2 =
{r}, hasProp I 2 = {(d 2 , r)}.

• Tradi I 3 = {d 2 }, Modern I 3 = {d 3 }, hasProp I 3 = {(d 2 , r)}, WProp I 3 = WoProp I 3 = Prop I 3 = ∅.
For each I i above, we assume that (a I i = a) for every individual name a ∈ I.

Here, I 1 is impossible because it falsifies the fully certain axiom Tradi ¬Modern. So, π WK (I 1 ) = 0, since As for I 2 , it satisfies all the axioms of T but it falsifies the assertions (Modern(d 1 ), .3), (WProp(d 3 ), .3) and (WoProp(d 2 ), .2). Hence, π WK (I 2 ) = .7.

Lastly, I 3 is also a model of T but it falsifies seven assertions in WA. The highest falsified assertion is (Tradi(d1), .9). Hence, π WK (I 3 ) = .1. None of I 1 , I 2 or I 3 is a model of WK. One can also check that there is no interpretation that satisfies both T and WA. Hence, π WK is sub-normalized. Its normalization degree, given by equation ( * ) in Section 3.1, is h(π WK ) = .7.

Inconsistency degree and possibilistic repair

In the rest of this paper, for any given weighted assertional base WB, we shall denote by WB * the corresponding set of assertions after removing the priority degrees. For instance, if WB = {(A(a), .9), (A(b), .8)}, then WB * = {A(a), A(b)}.

We also assume that the weighted KB WK may be inconsistent. Furthermore, we assume the TBox to be coherent and stable, thus the inconsistency of WK is caused by conflicts between the assertions of WA w.r.t. the axioms of T .

An assertional conflict is defined as a minimal (w.r.t. set inclusion) subset of assertions that is inconsistent with the TBox, where inconsistency is understood in the sense of standard DL-Lite. Formally: Definition 3. Let WK = T , WA be a weighted KB. A sub-base C ⊆ WA is an assertional conflict in WK if:

• T , C * is inconsistent, and

• ∀f ∈ C * , T , C * \ {f } is consistent.
We denote by Cf(WA) the set of all the assertional conflicts of WA. It is important to note that computing the set of conflicts of an inconsistent KB is done in polynomial time in DL-Lite [START_REF] Calvanese | Evolution of DL-Lite knowledge bases[END_REF].

Furthermore, we assume that there is no assertion f ∈ WA * such that T , {f } is inconsistent. Since the TBox is coherent, any conflict C in Cf(WA) involves two assertions [START_REF] Calvanese | Evolution of DL-Lite knowledge bases[END_REF]. We denote a conflict by a pair:

C ij = {(f i , α i ), (f j , α j )}, where (f i , α i ), (f j , α j ) ∈ WA.
We say that the assertions f i , f j ∈ WA * are conflicting w.r.t. T . Indeed, conflicts are actually between the assertions, no matter their weights. However, in this paper, we also keep the weights in the definition of the conflicts in order to better illustrate the subsequent definitions and results.

Example 5. We continue Example 3. The set of assertional conflicts of WA is given by:

Cf(WA) =        {(Tradi(d 1 ), .9), (Modern(d 1 ), .3)}, {(Modern(d 3 ), .7), (WProp(d 3 ), .3)}, {(WProp(d 2 ), .6), (WoProp(d 2 ), .2)}, {(hasProp(d 2 , r), .4), (WoProp(d 2 ), .2)}       
As it shall be made clear later, we are interested in the highest priority degree where inconsistency is met in the ABox, known as the inconsistency degree. Let us first introduce the notion of β-cut of a weighted ABox. Definition 4. Let WK = T , WA be a weighted KB. Consider a weight β ∈]0, 1].

• The β-cut of WA is:

A ≥β = {f | (f, α) ∈ WA, α ≥ β}.
• The strict β-cut of WA is:

A >β = {f | (f, α) ∈ WA, α > β}.
The inconsistency degree is formally defined as follows: Definition 5. Let WK = T , WA be a weighted KB. The inconsistency degree of WA, denoted by Inc(WA), is defined as:

Inc(WA) =    0 if T , WA * is consistent β if T , A ≥β is inconsistent and T , A >β is consistent
We illustrate this notion on our running example.

Example 6. Consider T of Example 1 and WA of Example 3. It is easy to check that:

A >.3 = {Tradi(d 1 ), WoProp(d 1 ), Modern(d 3 ), WProp(d 2 ), hasProp(d 2 , r), Prop(r)} is consistent with T .
Besides, one can also check that:

A ≥.3 = A >.3 ∪ {Modern(d 1 ), WProp(d 3 )} is inconsistent with T .
Thus, Inc(WA) = .3.

The inconsistency degree serves as a means for restoring the consistency of an ABox w.r.t. the TBox. Indeed, only the assertions with a certainty degree that is strictly higher than the inconsistency degree are included in the possibilistic repair. This ensures the safety of the results and has the advantage of being efficient. Basically, for a weighted ABox WA equipped with n different weights, the inconsistency degree Inc(WA) can be computed in a tractable way using log 2 (n) consistency checks of a classical ABox (without the weights) w.r.t. the TBox. Since checking the consistency of a standard DL-Lite ABox is tractable, it follows that computing the inconsistency degree Inc(WA) is also tractable.

The possibilistic repair, also referred to as the π-repair, is formally defined as follows:

Definition 6. Let WK = T , WA be a weighted KB. Let Inc(WA) be the inconsistency degree of WA. The π-repair (possibilistic repair) of WA, denoted by R π (WA), is:

R π (WA) = {f | (f, α) ∈ WA, α > Inc(WA)}.
Note that all the assertions contained in R π (WA) have a priority degree that is strictly higher than Inc(WA). Hence by Definition 5, the π-repair R π (WA) is consistent with T .

Moreover, when WK is consistent (i.e., Inc(WA) = 0), then the π-repair R π (WA) amounts to WA * (i.e., the assertions of WA without the priority degrees). Let π WK be the possibility distribution associated with a weighted possibilistic DL-Lite KB WK = T , WA . Then one can check that:

• The normalisation degree of π WK (see equation ( * ) in Section 3.1) and the inconsistency degree of WA (see Definition 5) are related by:

h(π WK ) = Inc(WA). • Let I be a DL-Lite interpretation. Then I is a model of R π (WA) iff π WK (I) = h(π WK ).
So far, we have considered the case of a weighted ABox such that a total preorder can be induced from the weights attached to the assertions. In the next section, we scale the results to the case where the priority degrees are partially ordered.

Partially Preordered Knowledge Base

In this section, we continue to assume that the TBox axioms are fully reliable. However, the priority degrees associated with the ABox assertions are partially ordered, i.e., the reliability levels associated with some assertions may be incomparable to each other. This is often the case when the pieces of information are obtained from multiple sources. Thus we may not be able to decide on a clear preference between two assertions f i and f j . For instance, according to one source, the assertion f i should be preferred to f j , whereas according to another source, it should be the opposite. Let us introduce the notion of partially ordered uncertainty scale L = (U, ), defined over:

• a non-empty set of elements U = {u 1 , . . . , u n }, called a partially ordered set (POS), and

• a strict partial order (i.e., an irreflexive and transitive relation).

Intuitively, the elements of a POS denoted by U represent priority degrees applied to the ABox assertions. We assume that U contains a special element denoted by 1 and representing full certainty, such that:

∀u i ∈ U \ {1}, 1 u i .
Moreover, if u i u j and u j u i , we say that u i and u j are incomparable and we denote it by u i u j . In this context, a partially preordered DL-Lite KB is a triple K = T , A , L with:

• A = {(f i , u i ) | f i is a DL-Lite assertion, u i ∈ U}
, where a unique weight u i is assigned to each assertion f i .

u 4 u 3 u 2 u 1 (a) A partial order u 4 u 3 u 2 u 1 u 4 u 2 u 3 u 1 u 4 u 3 = u 2 u 1 (b)
The total extensions of Figure 1: A partial order over U and its total extensions.

• L = (U, ).

Given two assertions (f i , u i ), (f j , u j ) ∈ A , we shall sometimes abuse the notation and simply write f i f j to mean u i u j (i.e., f i is strictly preferred to f j ), and write f i f j to mean u i u j (i.e., f i and f j are incomparable). 2

Compatible bases

A natural way for representing a partially preordered ABox is to consider the set of all the compatible ABoxes. Namely, these are the ABoxes that preserve the strict preference ordering between the assertions, in the spirit of the proposals made in the context of propositional possibilistic logic [START_REF] Benferhat | Reasoning with partially ordered information in a possibilistic logic framework[END_REF] or interval-based possibilistic logic [START_REF] Benferhat | Interval-based possibilistic logic[END_REF]. Formally:

Definition 7. Let L = (U, ) be a partially ordered uncertainty scale. Let K = T , A , L be a partially preordered DL-Lite KB. Let WK = T , WA be a weighted KB, obtained from K by replacing each symbolic weight u ∈ U by a real number in the unit interval ]0, 1], where:

WA = {(f, α) | (f, u) ∈ A , α ∈]0, 1]}.
The weighted ABox WA is compatible with A if:

∀(f i , α i ) ∈ WA, ∀(f j , α j ) ∈ WA, if f i f j then α i > α j .
Note that the compatible bases are not unique, actually there is an infinite number thereof. In fact, the actual values of the weights do not really matter, only the ordering between the assertions matters, as it shall be shown later.

Example 7. Let L = (U, ) be an uncertainty scale defined over the set U = {u 1 , u 2 , u 3 , u 4 }, and the partial order is depicted by Figure 1.(a). Namely:

(u 4 u 3 u 1 ) and (u 4 u 2 u 1 ) and (u 2 u 3 ). Let K = T , A , L be a partially preordered KB, where T is from Example 1, and A is given by:

A =        (Tradi(d 1 ), u 4 ), (WoProp(d 1 ), u 4 ), (Modern(d 3 ), u 4 ), (WProp(d 2 ), u 3 ), (hasProp(d 2 , r), u 3 ), (Prop(r), u 3 ), (Modern(d 1 ), u 2 ), (WProp(d 3 ), u 2 ), (WoProp(d 2 ), u 1 ), (Tradi(d 2 ), u 1 )        2
The relation on U is a strict partial order. Namely, ∀u i ∈ U, ∀u j ∈ U, if u i u j holds, then u j u i does not hold. However the ABox A is partially preordered since a given weight could be assigned to several assertions. Let {.2, .4, .6, .8} be a set of weights. The bases WA 1 , WA 2 and WA 3 below are compatible with A :

WA 1 =          (Tradi(d 1 ), .
         WA 2 =          (Tradi(d 1 ), .
         WA 3 =          (Tradi(d 1 ), .
        
For WA 3 , any subset of three weights chosen among {.2, .4, .6, .8} and which preserve the priority order between the assertions is suitable. The bases WA 1 , WA 2 and WA 3 are represented by Figure 2.

(a) The assertions of WA

n 9 : WoProp(d 2 ), n 10 : Tradi(d 2 )
Figure 2: The compatible bases of A : the assertions (grouped by certainty degree), and the conflicts (dotted lines).

The following result establishes that the notion of inconsistency degree (Definition 5) can be defined equivalently using the notion of assertional conflict (Definition 3).

Proposition 1. Let WK = T , WA be a weighted KB. Let Cf(WA) be the set of assertional conflicts. Then:

Inc(WA) = max C∈Cf(WA) min{α | (f, α) ∈ C} with max(∅) = 0. Proof. (i) Assume that T , WA * is consistent, then Cf(WA) = ∅. Therefore, Inc(WA) = 0 is vacuously true. (ii) Assume that Inc(WA) = β. Let C 12 = {(f 1 , α 1 ), (f 2 , α 2 )} be any conflict of Cf(WA). By Definition 5, T , A >β is consistent means that α 1 ≤ β or α 2 ≤ β, i.e., min(α 1 , α 2 ) ≤ β. Hence: max C∈Cf(WA) min{α | (f, α) ∈ C} ≤ β = Inc(WA) . . . (1)
Since T , A ≥β is inconsistent, then there is a conflict

C 34 = {(f 3 , α 3 ), (f 4 , α 4 )} in Cf(WA) such that α 3 = β or α 4 = β, namely: min(α 3 , α 4 ) = β . . . (2)
From equations ( 1) and ( 2) we have:

max C∈Cf(WA) min{α | (f, α) ∈ C} = β = Inc(WA).
(iii) The other direction is shown in a similar way. Assume:

max C∈Cf(WA) min{α | (f, α) ∈ C} = β . . . (3)
This means:

∀C ∈ Cf(WA), min{α | (f, α) ∈ C} ≤ β . . . (4)
Hence

A >β = {f | (f, α) ∈ WA, α > β} is consistent . . . (5) Statement (5)
holds, otherwise there is some

C in Cf(WA) s.t. min{α | (f, α) ∈ C} > β, which contradicts equation (4). Equation (3)
also means that there is some

C in Cf(WA) s.t. min{α | (f, α) ∈ C} = β.
This means:

A ≥β = {f | (f, α) ∈ WA, α ≥ β} is inconsistent . . . (6)
Applying Definition 5 to statements ( 5) and ( 6), we obtain Inc(WA) = β.

Example 8. Consider WA of Example 3 and its set of conflicts Cf(WA) of Example 5. The inconsistency degree is:

Inc(WA) = max min{.9, .3}, min{.7, .3}, min{.6, .2}, min{.4, .2} = .3. This is the same result obtained in Example 6.

Computing the partially preordered possibilistic repair

We are interested in computing a single repair for a partially preordered ABox. However, the family of compatible ABoxes is infinite, which means that selecting one compatible ABox over others would be arbitrary. A better approach for computing the partially preordered possibilistic repair consists in:

(i) defining the compatible ABoxes (Definition 7) with weights defined over ]0, 1],

(ii) computing the π-repair associated with each compatible ABox (Definition 6), and finally (iii) intersecting all the π-repairs.

This approach ensures the safety of the results since all the compatible ABoxes are taken into account.

Definition 8. Consider L = (U, ) and K = T , A , L . Consider the set of π-repairs associated with all the compatible bases of A :

F(A ) = {R π (WA) | WA is compatible with A }.
The partially preordered possibilistic repair of A , denoted by R π (A ), is given by:

R π (A ) = {R π (WA) | R π (WA) ∈ F(A )}. Namely: R π (A ) = {f | (f, u) ∈ A , ∀WA compatible with A and f ∈ R π (WA)}.
The set F(A ) is infinite because there are infinitely many weighted ABoxes that are compatible with A . However, in order to compute R π (A ), we do not need to consider all the compatible bases of A . We consider only the bases (and their associated πrepairs) that define a different ordering between the assertions. This is captured by the following lemma.

Lemma 1. Let WA 1 be a weighted ABox such that the weights belong to the set S = {α | (f, α) ∈ WA 1 }. Consider an assignment function ω : S -→]0, 1] s.t.:

• ∀α ∈ S, ω(α) = 1 iff α = 1. • ∀α 1 ∈ S, ∀α 2 ∈ S, α 1 = 1, α 2 = 1 we have: α 1 ≥ α 2 iff ω(α 1 ) ≥ ω(α 2 ).
Let WA 2 = {(f, ω(α)) | (f, α) ∈ WA 1 } be a weighted ABox obtained by applying the assignment function ω(•) to the weights in WA 1 . Then: R π (WA 1 ) = R π (WA 2 ).

Proof. Let us show that Inc(WA 1 ) = β iff Inc(WA 2 ) = ω(β). First, observe that given a conflict

C ij = {(f i , α i ), (f j , α j )} of WA 1 , then obviously C ij = {(f i , ω(α i )), (f j , ω(α j ))}
(α) | (f, ω(α)) ∈ C 12 } = ω(α 1 ) (resp. ω(α 2 )). Similarly, if min{α | (f, α) ∈ C 12 } > min{α | (f, α) ∈ C 34 }, then min{ω(α) | (f, ω(α)) ∈ C 12 } > min{ω(α) | (f, ω(α)) ∈ C 34 }. Hence, if: Inc(WA 1 ) = β, then trivially Inc(WA 2 ) = ω(β). Assume that Inc(WA 1 ) = β. Let (f, α) ∈ WA 1 such that α > β.
Then by the definition of the π-repair, we have f ∈ R π (WA 1 ). By applying ω(•), we get ω(α) > ω(β) = Inc(WA 2 ). This means f ∈ R π (WA 2 ).

Similarly, let (f, α) ∈ WA 1 such that α ≤ β. Then f / ∈ R π (WA 1 ). By applying ω(•), we get ω(α) ≤ ω(β) = Inc(WA 2 ). This means that f / ∈ R π (WA 2 ). Therefore we conclude that R π (WA 1 ) = R π (WA 2 ).

In Lemma 1, although WA 2 is different from WA 1 , the former ABox preserves the ordering on the assertions of the latter. Thus WA 2 is said to be order-preserving and in this case, the two weighted bases generate the same π-repairs, as shown in the following example.

Example 8. (continued) Consider the weighted ABox:

WA 4 =       
(Tradi(d 1 ), .9), (WoProp(d 1 ), .9), (Modern(d 3 ), .9), (WProp(d 2 ), .7), (hasProp(d 2 , r), .7), (Prop(r), .7), (Modern(d 1 ), .5), (WProp(d 3 ), .5), (WoProp(d 2 ), .3), (Tradi(d 2 ), .3)

      
The inconsistency degree is: Inc(WA 4 ) = .5. Note that despite the fact that Inc(WA 4 ) = Inc(WA 1 ), both bases WA 1 and WA 4 have the same ordering over the assertions, hence they both admit the same π-repair. Indeed, one can check that: R π (WA 4 ) = R π (WA 1 ) = {Tradi(d 1 ), WoProp(d 1 ), Modern(d 3 ), WProp(d 2 ), hasProp(d 2 , r), Prop(r)}.

The next example illustrates the computation of the partially preordered possibilistic repair.

Example 9. Thanks to Lemma 1, the repair R π (A ) can be computed by considering only the three bases WA 1 , WA 2 and WA 3 of Example 7 as the compatible bases of A . Using Figure 2, it is easy to check that the inconsistency degree of each base is:

• Inc(WA 1 ) = .4.
• Inc(WA 2 ) = .6.

• Inc(WA 3 ) = .6.

Their associated π-repairs are given by:

• R π (WA 1 ) = {Tradi(d 1 ), WoProp(d 1 ), Modern(d 3 ), WProp(d 2 ), Prop(r), hasProp(d 2 , r)}.

• R π (WA 2 ) = {Tradi(d 1 ), WoProp(d 1 ), Modern(d 3 )}.

• R π (WA 3 ) = {Tradi(d 1 ), WoProp(d 1 ), Modern(d 3 )}.

The partially preordered possibilistic repair of A is:

R π (A ) = R π (WA 1 ) ∩ R π (WA 2 ) ∩ R π (WA 3 ). = {Tradi(d 1 ), WoProp(d 1 ), Modern(d 3 )}.
We do not need to consider any other compatible base since the partial order (Figure 1.(a)) admits only three total extensions (Figure 1.(b)), where an arrow represents a strict preference between the elements of the set U.

The next section deals with the issue of how to compute the partially preordered possibilistic repair R π (A ) without enumerating all the compatible bases.

5 Characterization and Properties of the Partially Preordered Possibilistic Repair

Characterizing the partially preordered possibilistic repair

We have shown that computing the repair of a partially preordered ABox A requires the enumeration of the order-preserving compatible bases of A (see Definition 8 and Lemma 1). However, this method can be impractical. In this section, we provide an equivalent characterization by introducing the notion of π-accepted assertions. Intuitively, an assertion is π-accepted if it is strictly preferred to at least one assertion of each conflict of A .

Definition 9. Consider L = (U, ) and K = T , A , L . Let Cf(A ) denote the set of assertional conflicts of A . An assertion

(f i , u i ) ∈ A is π-accepted if: ∀C ∈ Cf(A ), ∃(f j , u j ) ∈ C, f i = f j , s.t. f i f j (i.e., u i u j ).
Note that the set of assertional conflicts Cf(A ) is obtained by using Definition An important result of this paper is that the set of π-accepted assertions corresponds exactly to the repair of the partially preordered ABox A (where the weights are omitted). Proposition 2. Consider R π (A ) given by Definition 8. Recall that the notion of π-accepted is given by Definition 9. Then an assertion

(f, u) ∈ A is π-accepted iff f ∈ R π (A ). Proof. (i) Assume that (f, u) ∈ A is π-accepted but f / ∈ R π (A ).
This means that there is a compatible base WA of A and a weight α ∈]0, 1] such that: (f, α) ∈ WA and f / ∈ R π (WA). Let Inc(WA) = β. By Definition 5, the sub-base A ≥β is inconsistent but the base A >β is consistent. Consider a conflict

C ij = {(f i , α i ), (f j , α j )} ∈ Cf(WA)
where the assertions f i , f j are such that f i ∈ A ≥β and f j ∈ A ≥β , and α i , α j ∈]0, 1].

There is always such a conflict since A ≥β is inconsistent. Namely, the assertions of the conflict C ij are selected from the sub-base A >β ∪ {f |(f, β) ∈ WA}. Thus, necessarily α i ≥ β and α j ≥ β. By Definition 6, f / ∈ R π (WA) means that α ≤ β. Hence α i ≥ α and α j ≥ α. But this contradicts the fact that (f, u) is π-accepted, which ensures that f f i or f f j , in other words, α > α i or α > α j .

(ii) Assume that (f, u) is not π-accepted but f ∈ R π (A ). Since (f, u) is not π-accepted, then there is a conflict {(f i , u i ), (f j , u j )} ∈ Cf(A ) s.t. f f i and f f j , i.e., u u i and u u j . There are three distinct cases to consider: (a) Both f i f and f j f hold, i.e., u i u and u j u. In other words, f i and f j are strictly preferred to f . This means that in all the compatible bases of A , both f i and f j are preferred to f . Let WA be a compatible base containing (f, α), (f i , α i ) and (f j , α j ), with α, α i , α j ∈]0, 1], and where α i > α and α j > α. By convention, the numerical weights α, α i and α j are associated with the symbolic weights u, u i and u j respectively. Since f i and f j are conflicting, then Inc(WA) ≥ min(α i , α j ).

Hence Inc(WA) ≥ α, thus f / ∈ R π (WA). But this contradicts the fact that f ∈ R π (A ).

(b) Both f i f and f j f hold, i.e., u i u and u j u. In other words, f i and f are incomparable and f j is strictly preferred to f . In this case, it is enough to have a compatible base WA containing (f, α), (g, α i ) and (h, α j ), with α, α i , α j ∈]0, 1], α i > α and α j > α. There is always such a compatible base. Clearly, with this compatible base, f / ∈ R π (WA), and this contradicts the assumption that f ∈ R π (A ). Note that the case where f i f but f j f (i.e., f i is strictly preferred to f while f j and f are incomparable) is also valid by symmetry. (c) Both f i f and f j f hold, i.e., u i u and u j u. In other words, f i and f are incomparable and f j and f are also incomparable. Then it is enough to have a compatible base WA containing (f, α), (f i , α i ) and (f j , α j ) where α i > α and α j > α. This amounts to case (a) above.

Example 11. From Examples 9 and 10, one can check that the π-accepted assertions (without the weights) are exactly those of R π (A ), namely: {Tradi(d 1 ), WoProp(d 1 ), Modern(d 3 )}.

Properties of the partially preordered possibilistic repair

Using the characterization of the partially preordered possibilistic repair provided in Definition 9 and Proposition 2, we are able to state the following two results. Proposition 3. Consider R π (A ) given by Definition 8. Then:

(1) The base R π (A ) is consistent w.r.t. the TBox.

(2) The time complexity for its computation is polynomial w.r.t. the size of the ABox.

Proof.

(1) The consistency of R π (A ) is straightforward. For each compatible base WA of A , the π-repair R π (WA) is consistent. So the intersection of all the π-repairs is also consistent.

(2) Regarding the computational complexity, we recall that computing the set of assertional conflicts Cf(A ) is done in polynomial time w.r.t. the size of A in DL-Lite. Hence, computing the set of π-accepted assertions R π (A ) is also done in polynomial time. Indeed, checking if some assertion (f, u) ∈ A is π-accepted amounts to parsing all the conflicts in Cf(A ). This is done in linear time w.r.t. the size of Cf(A ) (the size is itself bounded by O(|A | 2 )).

Note that by the construction of R π (A ), when the relation is a total order, then the partially preordered possibilistic repair R π (A ) collapses with the π-repair R π (A ) (Definition 6). In this case, all the compatible bases have exactly the same π-repair, thanks to Lemma 1.

Furthermore, for a weighted ABox WA, recall that the π-repair is: R π (WA) = {f | (f, α) ∈ WA, α > Inc(WA)} (Definition 6). From Proposition 1, if f i ∈ R π (WA) where (f i , α i ) ∈ WA, then α i > max C∈Cf(WA) min{α | (f, α) ∈ C}. This is equivalent to: ∀C ∈ Cf(WA), α i > min{α | (f, α) ∈ C}. In other words: ∀C ∈ Cf(WA), ∃(f j , α j ) ∈ C such that α i > α j . This corresponds to the notion of π-accepted assertion (Definition 9). We conclude that answering queries from a partially preordered inconsistent KB amounts to replacing the initial ABox A with its partial possibilistic repair R π (A ). Indeed, we established the consistency of the repair w.r.t. the TBox, but also the tractability of its computation. Furthermore, we showed that when the preference relation is a total order, our method amounts to computing a standard possibilistic repair.

Conclusion

In this paper, we proposed an extension of possibilistic DL-Lite to handle inconsistency in partially preordered knowledge bases. We introduced a method for computing a single repair on which queries can be posed. The method first interprets a partially preordered ABox as a family of compatible weighted ABoxes, then it computes the possibilistic repair of each compatible base, and finally it intersects all the possibilistic repairs. This produces a single repair for the partially preordered ABox. We proposed an equivalent characterization and introduced the notion of π-accepted assertions. We showed that the partially preordered possibilistic repair amounts to computing the set of π-accepted assertions. Most notably, as an important result, we showed that this computation can be achieved in polynomial time in DL-Lite.

In future work, we plan to investigate methods for enhancing the productivity of the partial repair. For instance, one could consider the closure of the possibilistic repairs associated with the compatible ABoxes. A crucial question is whether the computation of the closed partial possibilistic repair can be achieved in polynomial time in DL-Lite. We expect to show that this is indeed the case by reducing the problem to answering an instance checking query. More generally, we plan to investigate whether methods for computing repairs that are polynomial in the flat and prioritized cases are also polynomial in the presence of a partial order for description logic languages that are more expressive than DL-Lite. Another avenue of investigation consists in assigning possibilistic degrees to TBox axioms.

  Similarly, I satisfies an assertion A(a) (resp. P (a, b)), denoted by I A(a) (resp. I P (a, b)), if a I ∈ A I (resp. (a I , b I ) ∈ P I ).

Example 4 .

 4 where is the satisfaction relation between a DL-Lite interpretation and a DL-Lite formula. Consider T of Example 1 and WA of Example 3. Let {d 1 , d 2 , d 3 , r} be a domain and consider three interpretations I 1 , I 2 and I 3 defined over it, such that:

Example 6 .

 6 (continued) The π-repair of WA is: R π (WA) = {Tradi(d 1 ), WoProp(d 1 ), Modern(d 3 ), WProp(d 2 ), Prop(r), hasProp(d 2 , r)}.

  8), (WoProp(d 1 ), .8), (Modern(d 3 ), .8), (WProp(d 2 ), .6), (hasProp(d 2 , r), .6), (Prop(r), .6), (Modern(d 1 ), .4), (WProp(d 3 ), .4), (WoProp(d 2 ), .2), (Tradi(d 2 ), .2)

  8), (WoProp(d 1 ), .8), (Modern(d 3 ), .8), (Modern(d 1 ), .6), (WProp(d 3 ), .6), (WProp(d 2 ), .4), (hasProp(d 2 , r), .4), (Prop(r), .4), (WoProp(d 2 ), .2), (Tradi(d 2 ), .2)

  8), (WoProp(d 1 ), .8), (Modern(d 3 ), .8), (WProp(d 2 ), .6), (hasProp(d 2 , r), .6), (Prop(r), .6), (Modern(d 1 ), .6), (WProp(d 3 ), .6), (WoProp(d 2 ), .4), (Tradi(d 2 ), .4)

  d 1 ), .9), (WoProp(d 1 ), .8),

	(Modern(d 3 ), .7), (WProp(d 2 ), .6),
	(Prop(r), .5), (hasProp(d 2 , r), .4),
	(Modern(d 1 ), .3), (WProp(d 3 ), .3),
	(WoProp(d 2 ), .2), (Tradi(d 2 ), .1)

  is a conflict of WA 2 . Consider C 12 and C 34 two conflicts of WA 1 , and C 12 and C 34 two conflicts of WA 2 . By the definition of ω(•), if we have min{α | (f, α) ∈ C 12 } = α 1 (resp. α 2 ), then we also have min{ω

  [START_REF] Banerjee | On the relation between possibilistic logic and modal logics of belief and knowledge[END_REF], where the weighted KB WK and the weighted ABox WA are replaced with the partially preordered knowledge base K and the partially preordered ABox A . Example 10. Consider A of Example 7. The conflict set Cf(A ) is the same as in Example 3, but the assertions are equipped with the symbolic weights in {u 1 , . . . , u 4 }.It is easy to check that (Tradi(d 1 ), u 4 ), (WoProp(d 1 ), u 4 ) and (Modern(d 3 ), u 4 ) are strictly preferred to at least one assertion of each conflict, since u 4 is the most preferred symbolic weight in A . Hence, these three assertions are all π-accepted and: R π (A ) = {Tradi(d 1 ), WoProp(d 1 ), Modern(d 3 )}. This is the same result obtained in Example 9 by considering the compatible bases of A .

In the literature, a repair is a maximal and consistent subset of assertions. In this paper, we use the term repair to refer to a subset of assertions that is consistent, even if it is not maximal.

Acknowledgement

This work got support by the European project H2020-MSCA-RISE AniAge: High dimensional heterogeneous data based animation techniques for Southeast Asian intangible cultural heritage digital content. This work is supported by the AAP A2U QUID (QUeryIng heterogeneous Data) project.