Didier Dubois
email: dubois@irit.fr

Henri Prade
email: prade@irit.fr

Fayçal Touazi
email: faycal.touazi@irit.fr

A Possibilistic Logic Approach to Conditional Preference Queries

The paper presents a new approach to deal with database preference queries, where preferences are represented in the style of possibilistic logic, using symbolic weights. The symbolic weights may be processed without the need of a numerical assignment of priority. Still, it is possible to introduce a partial ordering among the symbolic weights if necessary. On this basis, four methods that have an increasing discriminating power for ranking the answers to conjunctive queries, are proposed. The approach is compared to different lines of research in preference queries including skyline-based methods and fuzzy set-based queries. With the four proposed ranking methods the first group of best answers is made of non dominated items. The purely qualitative nature of the approach avoids the commensurability requirement of elementary evaluations underlying the fuzzy logic methods.

Introduction

One may consider that there are two main research trends in the preference queries literature, namely the fuzzy set-based approach [START_REF] Bosc | Some approaches for relational databases flexible querying[END_REF][START_REF] Fagin | Optimal aggregation algorithms for middleware[END_REF] on the one hand, and skyline methods [START_REF] Börzsönyi | The skyline operator[END_REF][START_REF] Chomicki | Preference formulas in relational queries[END_REF][START_REF] Kiessling | Foundations of preferences in database systems[END_REF] on the other hand. Besides, in artificial intelligence, CP-nets [START_REF] Boutilier | CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF] for conditional preference statements developed in the last decade have become a popular setting. It is based on a graphical representation, and obeys the ceteris paribus principle. Its potential use for dealing with preference queries has even been stressed [START_REF] Brafman | Database preference queries revisited[END_REF]. Besides, the use of possibilistic logic for the modeling of preferences queries has been advocated more recently [START_REF] Hadjali | Database preference queries -A possibilistic logic approach with symbolic priorities[END_REF][START_REF] Bosc | A possibilistic logic view of preference queries to an uncertain database[END_REF].

Fuzzy sets have been often proposed for the modeling of flexible queries as it provides a basis for rank-ordering the retrieved items. However, this requires the specification of membership functions, possibly of priority weights, and more importantly it is based on the implicit assumption of the commensurability of the elementary evaluations. Skyline methods single out non dominated elements, but do not rank-order them (if the query is not iterated on the remaining items), up to a few exceptions [START_REF] Hadjali | On different types of fuzzy skylines[END_REF]. In this paper, we investigate the use of a possibilistic logic approach to the handling of data base (conditional) preference queries, which remains as symbolic as possible, but preserves a capability for rank-ordering the answers.

The paper is organized as follows. First, a short background on possibilistic logic, and the use of symbolic weights is provided in Section 2. Then, a running example is proposed, that will be used for comparing the different methods discussed in the paper. Section 3 presents four methods for rank-ordering query answers, with an increasing discriminating power. The first method handles preferences as conditional possibility constraints. The second method, which proves to be more refined, relies on an inclusion-based ordering. In the third and fourth methods, additional constraints are added between the symbolic weights of the possibilistic logic encoding, in the spirit of CP-nets and CP-theories [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF] (a generalization of CP-nets) respectively. Then Section 4 briefly compares our proposal to related work on skyline and fuzzy set approaches.

Technical Prerequisites and Running Example

We consider a propositional language where formulas are denoted by p 1 , ..., p n , and Ω denotes its set of interpretations.The logical conjunctions, disjunctions and negations are denoted by ∧, ∨ and ¬, respectively.

Possibilistic Logic

Let B N = {(p j , α j ) | j = 1, . . . , m} be a possibilistic logic base where α j ∈ L ⊆ [0, 1] is a priority level attached to formula p i [START_REF] Dubois | Possibilistic logic: a retrospective and prospective view[END_REF]. Each formula (p j , α j ) means that N (p j ) ≥ α j , where N is a necessity measure, i.e., a set function satisfying the property N (p ∧ q) = min(N (p), N (q)). A necessity measure is associated to a possibility distribution π on the set of interpretations, as follows:

N (p) = min ω ∈M(p) (1 -π(ω)) = 1 -Π(¬p),
where Π is the possibility measure associated to N and M (p) is the set of models induced by the underlying propositional language for which p is true.

The base B N is associated to the possibility distribution on interpretations:

π N B (ω) = min j=1,...,m π (pj ,αj ) (ω) (1)
where π (pj ,αj) (ω) = 1 if ω ∈ M (p j ), and π (pj ,αj

) (ω) = 1 -α j if ω ∈ M (p j ).
An interpretation ω is all the more possible as it does not violate any formula p j having a higher priority level

α j . So, if ω ∈ M (p j ), π N B (ω) ≤ 1-α j , and if ω ∈ j∈J M (¬p j ), then π N B (ω) ≤ min j∈J (1 -α j ).
It is a description "from above" of π N B , which is the least specific possibility distribution in agreement with the knowledge base B N .

Symbolic Weights

The weights associated to possibilistic logic formulas, which can be understood as priority or certainty levels, may be processed symbolically. By that, we mean that we are not assigning a value to the weights. So doing, we in general lose the benefit of the total ordering existing between values in a scale. Still, a partial ordering remains between symbolic expressions, e.g., we do know that min(α, β) ≤ α whatever the values of α and β. Moreover, one may introduce some further constraints between symbolic weights, when available, e.g., α > β, and exploit them. This includes the particular case where one knows the complete ordering between all the symbolic weights introduced. Generally speaking, when several constraints are introduced, it is important to make sure that they are consistent.

Since one may not know precisely how imperative preferences are in general, it is convenient to handle weights in a symbolic manner, without having to assign precise values. Having symbolic weights still allows us to construct a vector for each outcome that will serve in their rank-ordering. Indeed, a query will be viewed as a (weighted) conjunction of logical formulas, and items in the database are then rank-ordered according to the level to which they satisfy this conjunction. Then, the vector components are nothing but the arguments of the min in equation ( 1) defining the semantics of a possibilistic base made of formulas (p j , α j ) expressing goals and their importance. In this paper we explain how these vectors are obtained, and discuss how vectors can be ordered on this basis.

Running Example

Throughout the paper, we will use the following running example in order to illustrate the proposed approach to preference queries. This example is implemented on an experimental platform in information processing developed at IRIT in Toulouse (http:/www.irit.fr/PRETI) (see [START_REF] De Calmès | Flexibility and fuzzy case-based evaluation in querying: An illustration in an experimental setting[END_REF]). The data base stores pieces of information about houses to let that are described in terms of 25 attributes.

Example 1. We want to express the following preferences:

-The number of persons accommodated should be more than 10, imperatively; -It is preferred to have a house where animals are allowed, -It is preferred to be close to the sea by a distance between 1 and 20 km; -If the house is far from the sea by more than 20 km, it is preferred to have a tennis court at less than 4 km -If moreover the distance of the house to the tennis court is more than 4 km, it is desirable to have a swimming pool be at a distance less than 6 km

These preference constraints can be encoded by the following possibilistic logic formulas. Indeed, in our approach any query is represented by a possibilistic logic base. Here there is one imperative constraint, the other constraints being soft.

-Hard preference constraint φ 0 = (Accomod. ≥ 10, 1)

-Soft preference constraints -φ 1 = (Animal, α 1 ) -φ 2 = (1 ≤ Sea ≤ 20, α 2 ) -φ 3 = (¬(Sea > 20) ∨ T ennis ≤ 4, α 3 ) -φ 4 = (¬(Sea > 20) ∨ ¬(T ennis ≤ 4) ∨ P ool ≤ 5, α 4 )

Handling Preference Queries

What makes the possibilistic logic setting particularly appealing for the representation of preferences is not only the fact that the language incorporates priority levels explicitly, but the existence of different representation formats [START_REF] Benferhat | Towards a possibilistic logic handling of preferences[END_REF][START_REF] Dubois | Representing preferences in the possibilistic setting[END_REF], equally expressive [START_REF] Benferhat | Bridging logical, comparative, and graphical possibilistic representation frameworks[END_REF][START_REF] Benferhat | Graphical readings of possibilisitc logic bases[END_REF], even if more or less natural or suitable for expressing preferences. Namely, preferences can be represented as prioritized goals, i.e. possibilistic formulas, or in terms of conditionals (i.e. statements of the form if p is true then having q true is preferred to having it false), or even as a Bayesian-like networks, since a possibilistic logic base can be encoded either as a qualitative or a quantitative possibilistic network and vice-versa [START_REF] Benferhat | On the transformation between possibilistic logic bases and possibilistic causal networks[END_REF]. In the next subsection, we recall how conditional preferences are represented in possibilistic logic with symbolic weights. Then in the three next subsections, different ways of handling symbolic priorities for processing the queries are discussed.

Preference Encoding in Possibilistic Logic

The unconditional preference of the form "q is preferred to ¬q" may be understood in the possibility theory setting as the constraint Π(q) > Π(¬q), which expresses that at least one model of q is preferred to any interpretation that makes q false. More generally, the possibilistic encoding of conditional preferences of the form "in context p, q is preferred to ¬q" is a constraint of the form Π(p ∧ q) > Π(p ∧ ¬q). This includes the previous case where p is a tautology. Using conditioning, this constraint is still equivalent to ∃α s. t. N (q|p) ≥ α > 0, where

N (q|p) = 1 -Π(¬q|p), such that Π(r|p) = 1 if Π(p ∧ r) ≥ Π(p ∧ ¬r) and Π(r|p) = Π(p ∧ r) otherwise.
This constraint can be encoded by the possibilistic formula (¬p ∨ q, α), which expresses the requirement N (¬p ∨ q) ≥ α, which is itself equivalent here to the above constraint on the conditional necessity measure N (q|p) ≥ α (see, e.g., [START_REF] Dubois | Possibilistic logic: a retrospective and prospective view[END_REF]).

More generally, if we need to consider more than two mutually exclusive alternatives, this can be encoded by means of several possibilistic formulas. For instance, the two weighted formulas {(¬p ∨ q ∨ r, 1), (¬p ∨ q, α)} state that if p is true, it is imperative to have q ∨ r, and that q is preferred to r ∧ ¬q since α > 0. This extends to n alternatives. For instance, {(¬p ∨ q ∨ r ∨ s, 1), (¬p ∨ q ∨ r, α), (¬p ∨ q, β)} with β < α < 1 says that in context p, one wants to have q true, or at least r true, or at least s true; see [START_REF] Bosc | A possibilistic logic view of preference queries to an uncertain database[END_REF] for further discussions.

In the next subsections, we shall exhibit different methods to rank-order outcomes based on a possibilistic logic base encoding preferences, but we first discuss the direct exploitation of constraints of the form Π(p ∧ q) > Π(p ∧ ¬q).

Weak Comparative Preferences

The handling of a set of possibilistic constraints φ i of the form Π(p i ∧ q j ) > Π(p i ∧ ¬q j ) amounts here to looking for the largest possibility distribution π compatible with these constraints applying the minimum specificity principle, see, e.g., [START_REF] Benferhat | Towards a possibilistic logic handling of preferences[END_REF]. The largest solution π, which always exists if the set of constraints is consistent, can be computed using Algorithm 1 below, and represents a preference profile that rank-orders interpretations, in agreement with the preference requirements. The minimal specificity principle ensures that all the constraints are satisfied, but only these constraints are (in other words, no extra preferences are introduced). In the algorithm, the possibility distribution π is represented as a well-ordered partition (E 1 , ..., E m ) of Ω, associated with the ordering

≻ W CP such that: ∀ω, ω ′ ∈ Ω, ω ≻ W CP ω ′ iff ω ∈ E i , ω ′ ∈ E j and i < j.
The well-ordered partition given in Algorithm 1 satisfies the minimum specificity principle. The most satisfactory set E 1 is made of the interpretations that satisfy some L(φ i ), and do not satisfy any R(φ j ). Then the set of constraints whose left part is satisfied by an interpretation of E 1 are deleted, and the procedure is iterated on the remaining constraints as long as there are some. This procedure yields a possibility distribution

Algorithm 1. Minimal specificity ranking algorithm

Require: Φ a set of constraints φi of the form:

Π(L(φi)) > Π(R(φi))
Ei whose number of values is at most n + 1 where n is the number of constraints. Indeed, it is clear that at least one constraint is deleted at each iteration step.

a

Proposition 1. Let a query Q composed of n preference constraints. The number of elements of the well-ordered partition {E

1 , • • • , E m } produced by Algorithm 1 is at most m = n + 1.
Example 2. Let 4 preference constraints be given as follows (L(φ i ),R(φ i ) are replaced by sets of interpretations): φ 1 = ({t 1 , t 2 , t 3 }, {t 4 , t 5 , t 6 , t 7 , t 8 }); φ 2 = ({t 4 , t 5 }, {t 6 , t 7 , t 8 }); φ 3 = ({t 6 }, {t 7 }); φ 4 = ({t 7 }, {t 8 }). Applying Algorithm 1 gives 5 preference levels:

E 1 = {t 1 , t 2 , t 3 }, E 2 = {t 4 , t 5 }, E 3 = {t 6 }, E 4 = {t 7 } and E 5 = {t 8 }.
Example 1 (continued). The imperative preference constraint (φ 1 ) restricts the list to 15 houses. Considering the preference constraints in the running example the result of applying Algorithm 1 to constraints of the form Π(φ i ) > Π(¬φ i ), i = 1, . . . , 4 is given in Table 1 where m = 2 and E 1 = {539}. As there is no conflict detected by the algorithm, there are only two classes of outcomes.

Lexicographic Comparaison

We now consider a possibilistic logic encoding of the preference requirements, i.e., a possibilistic logic base Σ. For each interpretation ω, we can build a vector ω(Σ) in the following way, for each preference constraint φ i for i = 1, • • • , n:

Id φ0 φ1 φ2 φ3 φ4 Rank 539 1 1 1 1 1 1 191 1 1 1-α2 1 1 2 320 1 1 1-α2 1 1 2 530 1 1 1-α2 1 1 2 119 1 1-α1 1-α2 1 1 3 261 1 1 1-α2 1-α3 1 3 339 1 1 1-α2 1 1-α4 3 366 1 1-α1 1-α2 1 1 3 434 1 1-α1 1-α2 1 1 3 435 1 1 1-α2 1-α3 1 3 507 1 1 1-α2 1-α3 1 3 519 1 1-α1 1-α2 1 1 3 536 1 1-α1 1-α2 1 1 3
-if ω satisfies φ i we put '1' in the i th component of the vector; -otherwise, we put 1α i (α i is the weight associated to preference constraint φ i ).

in agreement with the minimally specific possibility distribution π associated with Σ (see Section 2). Indeed, since we are dealing with symbolic weights, we cannot compute the result of the min operator aggregation of the vector components. So, we keep the vectors as they are, and order them using the classical lexicographic ordering, see, e.g., [START_REF] Dubois | Possibilistic logic: a retrospective and prospective view[END_REF], thus defining an order denoted ≻ leximin between vectors.

In the standard case of a totally ordered scale, the leximin order is defined by first reordering the vectors in an increasing way, and then applying the min order to the subparts of the reordered vectors without identical components. Since we deal with a partial order over the priority weights (at least, we know that 1 > 1α i , ∀i, and 1α i ≥ min(1α i , 1α j ) and so on), the reordering of vectors is no longer unique, and we have to generalize the definition in the following way: Definition 1 (leximin). Let v and v ′ be two vectors having the same number of components. First, delete all pairs (v i , v ′ j ) such that v i = v ′ j in v and v ′ (each deleted component can be used only one time in the deletion process). Thus, we get two non overlapping sets r(v) and r(v ′ ) of remaining components, namely r

(v) ∩ r(v ′ ) = ∅. Then, v ≻ leximin v ′ iff min(r(v) ∪ r(v ′ )) ⊆ r(v ′ ) (

where min here returns the set of minimal elements of the partial order between the priority weights).

Example 1 (continued). When applying the possibilistic logic semantics to query evaluation, we deal not only with interpretations, but also with items (several items may correspond to the same interpretation of the requirement). Thus, considering the house with id 339, its associated vector is v(339) = (1, 1, 1α 2 , 1, 1α 4 ) (see Table 2). The house satisfies the two first preference constraints (number of people accommodated and animals allowance) and also satisfies the 5th preference concerning the distance to a swimming pool. But it falsifies the preference about distance to the sea (it is 10 km far), and it falsifies the preference about the distance to a tennis court. Now let us compare this house with the house with id 292 and vector v(292) = (1, 1, 1α 2 , 1, 1), applying the leximin order. Then, the reduced associated vectors have one component here: r(292) = (1) and r(339) = (1α 4 ). Then, we have min(r(292) ∪ r(339)) = {1α 4 } ⊆ r(339). So, v(292) ≻ leximin v(339), and by extension, we write house 292 ≻ leximin house 339 .

Considering all the items in the running example, the result of the lexicographic comparison over the 15 houses is given in Table 2.

One can observe that ≻ leximin may induce up to n + 1 layers, since an item may violate 0, 1, • • • , or n preference constraints. Indeed, items are ranked according to the number of preferences violated.

Proposition 2. If a query Q is composed of n preference constraints, then the maximal number of levels generated by

≻ leximin is n + 1.
Contrary to what Tables 1 and2 suggest, ≻ leximin does not refine ≻ W CP as the latter generally introduces constraints between weights that are not present in the method of this section. However in the running example, the W CP is equivalent to applying classical logic, ending up in two classes of interpretations only. In that special case, ≻ leximin trivially refines ≻ W CP , since then the latter separates outcomes ω that satisfy all constraints from those that violate at least one of them, while ≻ leximin always classifies outcomes in terms of the number of violated constraints. However, ≻ leximin does not use priorities induced by the W CP approach (Algorithm 1). Of course it is also possible to refine the ordering of outcomes induced by WCP using ≻ leximin , or equivalently to refine the ≻ leximin with symbolic weights, by exploiting the priorities found by Algorithm 1.

Adding Constraints between Symbolic Weights

In the previous subsection, the partial order between priority weights, underlying the use of the lexicographic comparison, was not requiring any information on the relative values of the symbolic weights associated with the preference requirements. It should be clear that the lexicographic ordering between vectors (and thus between interpretations, and between items) will be refined by the knowledge of some additional information on the relative importance of requirements. For instance, if being not too far from a tennis court is less important than being somewhat close to the sea, then we can enforce in comparisons that α i > α j , where α i , α j are the respective weights associated to the tennis and sea requirements. However, it is important to keep in mind that when we consider two possibilistic logic formulas (ϕ, α) and (ψ, β) such that ϕ ψ then we should have β ≥ α. This is in agreement with the fact that if one requires ϕ = ¬p ∨ q and ψ = ¬p∨q ∨r (i.e. in context p, q must be true, or at least r), satisfying ϕ cannot be more important than satisfying ψ if we do not want to trivialize the latter requirement ψ (since satisfying ϕ entails satisfying ψ). To ensure this kind of coherence property, one may compute the degree to which each requirement is entailed by the other ones (which may result in attaching to formulas symbolic expressions involving max and min of other symbolic weights).

If no extra information is available between priorities, one may apply some general principle for introducing inequalities between symbolic weights. In the following we discuss two options that enable us to obtain a more refined leximin-based ordering. The first option is inspired from the CP-net representation of preferences [START_REF] Boutilier | CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF], and the second one from its refinement in terms of CP-theories [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF].

Constraints between Weights in CP-net Style

This method is inspired from CP-nets, a well-known framework for representing preferences in AI [START_REF] Boutilier | CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF]. It is a graphical representation that exploits conditional preferential independence in structuring the preferences provided by a user. These preferences take the form u : x i > ¬x i , i.e., x is preferred to ¬x in context u, (u can be tautological). CP-nets are underlain by a ceteris paribus principle that amounts to giving priority to preferences attached to parent nodes over preferences attached to children nodes in the CP-net structure. Besides, it has been noticed that a CP-net ordering can be approximated by a possibilistic logic representation with symbolic weights [START_REF] Dubois | Conditional preference nets and possibilistic logic[END_REF][START_REF] Hadjali | Database preference queries -A possibilistic logic approach with symbolic priorities[END_REF]. The priority in favor of father nodes carries over to the possibilistic setting in the following way. For each pair of formulas of the form (¬u ∨ x i , α i ) and (¬u ∨ ¬x i ∨ x j , α j ), x i plays the role of the father of x j in a CP-net. Indeed, the first formula expresses a preference in favor of having x i true (in context u), while in the second formula the context is refined from u to u ∧ x i , which establishes a particular type of links between the two formulas where the second formula is in some sense a descendant of the first one. Then, the following constraint between the corresponding weights is applied α i > α j , in a CP-net spirit. These constraints between symbolic weights can be obtained systematically by Algorithm 2, which computes the partial order between symbolic weights from a possibilistic logic base. Applying this procedure allows us to add constraints among symbolic weights and to get a more refined ranking of items, as we notice in the following example. 435, and 507 since 1α 4 > 1α 3 . Houses 119, 366, 434, 519, 536 are clearly not as good as houses 539, 191, 320, and 530; moreover they can be compared with neither house 339, nor with houses 261, 435, and 507 (since α 1 cannot be compared with α 4 or α 3 ); this is why houses 119, 366, 434, 519, 536 are put in the highest possible layer: i.e., below the lowest one where houses are preferred to them and in the highest one where there is an incomparable item.

Constraints between Weights in CP-Theories Style

CP-theories as introduced in [START_REF] Wilson | Computational techniques for a simple theory of conditional preferences[END_REF], are a generalization of CP-nets. Also based on a graphical representation, CP-theories offer a more expressive language where preference priority can be made explicit between the preference constraints. Thus, such constraints have the same form as in CP-nets u : x > ¬x [W ]; in addition we have the set of variables (attributes) W for which it is known that the preference associated to x does not depend on any value assignment of an attribute in W (i.e., the preference attached to the concerned attribute holds irrespective of values of attributes in W ). It has been suggested that possibilistic logic is able to approximate this representation by adding more priority constraints over the symbolic weights [START_REF] Dubois | Handling partially ordered preferences in possibilistic logic[END_REF]. Formally, a possibilistic preference constraint of the form u : x > ¬x [W ], with an irrespective requirement w. r. t. variables in W is encoded by a possibilistic preference statement (¬u ∨ x, α i ), to which we shall add the constraint α i > α j for any α j over symbolic weights, such that (¬u ∨ w, α j ) is a possibilistic preference statement, with the same context u, over one variable (or more) w ∈ W . These constraints over weights can be obtained by Algorithm 3. Example 1 (continued). We consider the preference constraints in the running example. In addition, it is natural to assume the preference for animals allowance holds irrespectively of the preference concerning the distance to the sea (⊤ : Animals > ¬Animals [Sea]). Then, Algorithm 3 yields α 1 > α 2 > α 3 > α 4 and the result of applying lexicographic comparison over the 15 houses, is given in Table 4, which leads here to an even more refined ranking. We can establish that the different ranking procedures discussed so far agree on the best selected items. Besides, we can show that the maximal number of layers induced by the lexicographic ordering may be greatly increased by the presence of additional constraints: Proposition 3. Let E 1 denote the set of non dominated models of a consistent possibilistic base. This set remains unchanged under the weak comparative preference ordering and the lexicographic ordering (in the presence of additional constraints or not).

E 1 ≻W CP = E 1 ≻ leximin
Proof of Proposition 3: Let E 1 ≻W CP be the set of non dominated interpretations obtained by the weak comparative preferences method. We know that ω ∈ E

Hybridizing Weak Comparative Preferences and Lexicographic Methods

As shown in the previous subsections, the above three leximin-based methods lead to different, but compatible rankings of items, with increasing discrimination. The respective complexities of the comparative preferences and lexicographic methods are P olynomial and Π P 2complete [START_REF] Benferhat | Complexity and cautiousness results for reasoning from partially preordered belief bases[END_REF][START_REF] Yahi-Mechouche | Raisonnement en présence d'incohérence: de la compilation de bases de croyances stratifiées à l'inférence à partir de bases de croyances partiellement préordonnées[END_REF]. Indeed, it can be observed in practice that the lexicographic method is more costly from a computational point of view: Proposition 4. Let Q be a query made of n preference constraints, then the maximal number of levels generated by ≻ leximin with additional constraints over weights is 2 n . Indeed, this number of layers is obtained by refining the ordering of items violating the same number of preferences in case of a total ordering of the weights. Since the [START_REF] Fagin | Optimal aggregation algorithms for middleware[END_REF] Fuzzy logic [START_REF] De Calmès | Flexibility and fuzzy case-based evaluation in querying: An illustration in an experimental setting[END_REF] Symbolic weight possibilistic logic lexicographic method leads to a more refined rank-ordering, one may think of first using the weak comparative preferences method to stratify items, and then, each layer (except the top one because of Proposition 3) may be refined by one of the lexicographic methods by considering each level as a new intermediate database. This hybrid method may be of interest for computing a rank-ordering for top k items (when k is larger than |E 1 | !). However, for refining the ranking of items inside a layer, we need to process it as a whole, even if it leads to considering more than k items in the ranking.

Related Work

Different types of approaches for handling preference queries have been proposed in the literature. Table 5 (whose evaluation criteria are taken from [START_REF] Stefanidis | A survey on representation, composition and application of preferences in database systems[END_REF]) provides a comparative assessment of the possibilistic approach along with a representative subset of other approaches.

As for other qualitative methods, the approach presented is capable of expressing preference between attribute values or between tuples of attribute values, since we use general logical formulas (e.g., considering only the two attributes 'Price' and 'Distance to sea' with values low, medium and high for a house to let, a query may express that one prefers low price and low distance, or at least low price and medium distance or at least medium price and medium distance). As can be noticed, only the Kießling approach [START_REF] Kiessling | Foundations of preferences in database systems[END_REF] can express both qualitative and quantitative preferences. Besides, only the possibilistic and the Chomicki [START_REF] Chomicki | Preference formulas in relational queries[END_REF] approaches can deal with conditional preferences. It can be seen that the advantages of this approach and of the fuzzy logic one [START_REF] Bosc | Fuzzy Preference Queries to Relational Databases[END_REF] are complementary, which suggests to try and hybridize them in the future. To this end, it would be necessary to compare vectors including both symbolic and numerical weights.

Conclusion

The interest for preference representation in the possibilistic logic framework first stems from the logical nature of the representation. Moreover, the possibilistic representation can express preferences of the form "or at least", or "and if possible"(see [START_REF] Dubois | Handling partially ordered preferences in possibilistic logic[END_REF] for an introductory survey), and can handle partial orders thanks to the use of symbolic weights, without enforcing implicit preferences (as it is the case for father node preferences in CP nets). We have proposed three types of methods in order to rank-order items, which are characterized by an increasing refinement power with manageable complexity, especially using the hybrid method explained in Subsection 4.3. Still, much remains to be done. First, the use of symbolic weights is really advantageous but we still miss some properties of numerical weights. One may think of combining these two formats to be as much expressive as possible. Moreover, this approach should be able to deal with null values, which create specific difficulties in preference queries.

  set of interpretations classified at the i th rank Ω the set of all interpretations m=1;

	ment of Em
	m=m+1;
	end if
	end while
	return {E1, • • • , Em}

while Φ = ∅ do Put in Em any interpretation ω l that satisfies some L(φi), and does not satisfy any R(φj

) if Em = ∅ then

The preference base is inconsistent else Delete Em from Ω Delete all pairs (L(φi),R(φi)) from Φ such that L(φi) is satisfied by at least one ele-

Table 1 .

 1 Weak comparison preference ranking

	Id	Sea	Animal Tennis Rank
	539	4.00	1	3.00	1
	119	100	0	0.50	2
	191	100	1	0.60	2
	261	83.00	1	4.50	2
	320	23.00	1	1.50	2
	339	100	1	8.50	2
	366	100	0	0.50	2
	434	100	0	3.50	2
	435	89.00	1	6.50	2
	507	83.00	1	4.00	2
	519	58.00	0	1.50	2
	530	100	1	0.50	2
	536	83.00	0	1.50	2

Table 2 .

 2 Lexicographic ranking

end if end for end if end for return CBW

  1 ≻W CP if only if ω satisfies all preference constraints. Let ω(Σ)(1, • • • , 1) be the vector associated to ω. It is clear that any item that has an associated vector only made of '1' components is preferred to any other vector containing at least one component ='1' according to leximin order. So ω ∈ E 1 ≻ leximin .

✷ Algorithm 3. Relative importance between possibilistic formulas in a CP-theories spirit Require: C a set of constraints of the form (Pi, αi) for ci ∈ C a preference constraint associated with an irrespective requirement do if Wi=∅ then CBW ← CBW ∪ Algorithm 2 else for cj in C do if cj is of the form (¬ui ∨ ¬xi ∨ v, αj ) or (¬ui ∨ z, αj)/z ∈ Wi, v ∈ {V -U } then CBW ← CBW ∪ (αi > αj )

Table 5 .

 5 Comparative Table of different approaches dealing with preference queries

	Formulation	Context	Ranking
	Qualitat. Quantitat. Uncond. req. Cond. req. Skyli. Top-k
	Lacroix Lavency [24]
	Chomicki 2002 [4]
	Kießling 2002 [5]
	Fagin et al 2001

Algorithm 2. Relative importance between possibilistic formulas in a CP-net spirit

Require: C a set of constraints of the form (pi, αi)

CBW=∅: the set of constraints between weights for cj in C do if cj is of the form (ui, αj

Example 1 (continued). Considering the preference constraints in the running example, the result of the lexicographic comparison of vectors adding the CP-nets-like constraints between weights, namely here α 2 > α 3 and α 3 > α 4 , is given in Table 3, where a more refined ranking is obtained. In particular, house 339 is preferred to house 261,