Nouredine Tamani
email: tamani@enssat.fr

Ludovic Liétard
email: ludovic.lietard@univ-rennes1.fr

Daniel Rocacher
email: rocacher@enssat.fr

Bipolar SQLf: a Flexible Querying Language for Relational Databases

Keywords: Flexible Querying, Fuzzy Bipolar Conditions, Fuzzy Bipolar Algebra, SQLf Language, Bipolar SQLf Language

. This language is an extension of the SQLf language [2, 1]. Basic statements (projection, selection, etc.) are firstly defined in terms of syntax, evaluation and calibration. Then, complex statements, such as bipolar queries based on nesting operators are studied in terms of expression, evaluation, query equivalence and backward compatibility with the SQLf language.

Introduction

Flexible querying of databases allows users to express preferences in their queries. Within this framework, numerous tools have been proposed such as Preference SQL [START_REF] Chomicki | Querying with intrinsic preferences[END_REF], SQLf language [START_REF] Bosc | SQLf: A relational database langage for fuzzy querying[END_REF][START_REF] Bosc | Base de données -Gradualité et imprécision dans les bases de données Ensembles flous, requêtes flexibles et interrogation de données mal connues[END_REF], Top-k queries [START_REF] Li | RankSQL: Query algebra and optimization for relational top-k queries[END_REF], the winnow operator [START_REF] Kiebling | Foundation of preferences in database systems[END_REF], etc. which are based on diverse mathematic foundations.

In the context of fuzzy querying, user preferences are expressed by fuzzy predicates (such as high, fast, expensive, etc.) which are defined by fuzzy sets [START_REF] Zadeh | Fuzzy sets[END_REF]. The SQLf language is an extension of the SQL language to fuzzy conditions, which allows expressing queries addressed to relational databases. Such queries deliver a set of tuples attached with degrees used to rank them from the most to the least preferred. In this context, it is also possible to consider fuzzy bipolar conditions to model preferences.

A bipolar condition is a compound condition made of negative and positive conditions. Several interpretations have been introduced for the evaluation of queries involving such conditions (see [START_REF] Dubois | Bipolarity in flexible querying[END_REF][START_REF] Dubois | Bipolarité dans un processus d'interrogation flexible[END_REF][START_REF] Tré | Dealing with positive and negative query criteria in fuzzy database quering bipolar satisfaction degrees[END_REF][START_REF] Zadrozny | Bipolar queries using various interpretations of logical connectives[END_REF][START_REF] Zadrozny | Bipolar queries: An approach and its various interpretations[END_REF]). In this paper, we rely on the interpretation introduced by Dubois and Prade [START_REF] Dubois | Bipolarity in flexible querying[END_REF][START_REF] Dubois | Bipolarité dans un processus d'interrogation flexible[END_REF], in which a bipolar condition is made of a constraint c and a wish w. It is noted (c, w) and means "to satisfy c and if possible to satisfy w". More precisely, for the expression of user preferences, we rely on fuzzy bipolar conditions in which the constraint and the wish are defined by fuzzy sets. Furthermore, we define a fuzzy bipolar query as a query that involves fuzzy bipolar conditions. More precisely, when querying a relation R with a fuzzy bipolar condition, each tuple t from R is then attached with a couple of grades (µ c (t), µ w (t)) that expresses the degree of its satisfaction to c and w and a so-called fuzzy bipolar relation is obtained.

In order to define a bipolar relational algebra, the algebraic operators (selection, projection, join, union, intersection) have been extended to fuzzy bipolar conditions [START_REF] Liétard | On the extension of SQL to fuzzy bipolar conditions[END_REF][START_REF] Bosc | Extending relational algebra to handle bipolarity[END_REF]. These operators allow the expression of fuzzy bipolar queries.

We are aimed in this article to define the Bipolar SQLf language which is an SQL-like language based on a bipolar relational algebra. Since fuzzy bipolar conditions generalize fuzzy conditions, we consider the enrichment to fuzzy bipolar conditions of the SQLf language [START_REF] Bosc | SQLf: A relational database langage for fuzzy querying[END_REF][START_REF] Bosc | Base de données -Gradualité et imprécision dans les bases de données Ensembles flous, requêtes flexibles et interrogation de données mal connues[END_REF] which is devoted to flexible querying with fuzzy sets. At the first step basic Bipolar SQLf queries are defined in terms of expression, evaluation and calibration. Then, complex bipolar queries based on nesting (in = , in ≈ , exists, θany) and partitioning operators are defined.

The remainder of this paper is as follows. In section 2, both fuzzy sets theory and the SQLf language are described. Section 3 introduces respectively fuzzy bipolar conditions, the bipolar relational algebra defined in [START_REF] Liétard | On the extension of SQL to fuzzy bipolar conditions[END_REF][START_REF] Bosc | Extending relational algebra to handle bipolarity[END_REF] and the basis of the Bipolar SQLf language. In section 4, the extension of advanced Bipolar SQLf statements to fuzzy bipolar conditions is studied. Section 5 sums up our contribution and draws some lines for future works.

Flexible Querying Within the SQLf Language

We introduce in this section the fuzzy sets theory and the SQLf language.

The Fuzzy Sets Theory

The fuzzy sets theory is introduced by Zadeh [START_REF] Zadeh | Fuzzy sets[END_REF] to express the gradual membership of an element to a set. Formally, a fuzzy set F is defined on a referential U by a membership function µ F : U → [0, 1] such that µ F (x) denotes the membership grade of x in F . In particular, µ F (x) = 1 denotes the full membership of x in F , µ F (x) = 0 expresses the absolute non-membership and when 0 < µ F (x) < 1, it reflects a partial membership (the closer to 1 µ F (x), the more x belongs to F ).

A fuzzy set generalizes an ordinary (crisp) set in which membership grades are in {0, 1}. If a fuzzy set is a discrete set then it is denoted F = {µ F (x 1 )/x 1 , ..., µ F (x n )/x n }, otherwise, it is characterized by its membership function, generally a trapezoidal function.

The union ∪ and the intersection ∩ operators are defined with a couple of (t-norm, t-conorm) such as (min, max). Let F , G be two fuzzy sets,

µ F ∪G (x) = max(µ F (x), µ G (x)), µ F ∩G (x) = min(µ F (x), µ G (x)), and the complement of F , noted F c , is defined by µ F c (x) = 1 -µ F (x).
The logical counterparts of ∩, ∪ and the complement are resp. ∧, ∨ and ¬. Other operators have also been defined such as fuzzy implications [START_REF] Bouchon-Meunier | Fuzzy sets in approximate reasoning and information systems[END_REF].

The SQLf Language

The SQLf language [START_REF] Bosc | SQLf: A relational database langage for fuzzy querying[END_REF][START_REF] Bosc | Base de données -Gradualité et imprécision dans les bases de données Ensembles flous, requêtes flexibles et interrogation de données mal connues[END_REF] is an extension of the SQL language to flexible querying based on fuzzy conditions. An SQLf query delivers a fuzzy relation r where the grade of membership of tuple t expresses its level of satisfaction.

The SQLf language is based on the fuzzy relational algebra, in which relational algebra operators have been extended to fuzzy predicates as follows: let r, s be two fuzzy relations such that the schema of r (resp. s) is X (resp. Y ):

Fuzzy projection: µ π(r,V ) (v) = max w µ r (vw), where V ⊆ X, v ∈ V and w ∈ (X -V ).
Fuzzy selection: µ σ(r,p) (x) = min(µ r (x), µ p (x)), where p is a fuzzy predicate. Fuzzy join: µ (r, s, θ, A, B) = min(µ r (x), µ s (y), µ θ (x.A, y.B)), where A and B are compatible sets of attributes such that A (resp. B) is a subset of X (resp. Y ) and x.A (resp. y.B) is the value of A in x (resp. B in y), and θ is either a crisp or a fuzzy binary operator (θ ∈ {=, ≈, <, >, much larger than, ...}).

The basic form of an SQLf query is a fuzzy restriction defined as follows:

Select [ distinct] [n|t|n,t]
attributes From relations Where fuzzy cond; This query returns a set of ranked tuples with their attached degree, where n specifies an n-top query and t ∈]0, 1] is a minimal threshold of satisfaction.

Example 1: Let fast be a fuzzy predicate defined on

R + → [0, 1]: µ fast (d) = 1, if d ∈ [0, 2]; -d 3 + 5 3 , if d ∈ [2, 5
] and 0, otherwise. The query "find the 2 fastest journeys from Brussels to Paris" can be expressed in SQLf by: Select 2 #journey From Journey Where source='Brussels' and destination='Paris' and fast (duration); The fuzzy condition fast delivers the fuzzy relation FastJourney, where µ FastJourney (t) = µ Fast (t.duration). Table 1 The SQLf language allows the expression of more complex statements such as partitioning, nesting and division involving fuzzy relations. For example, the query "find journeys for which most of their steps are comfortable" corresponds to a partitioning based on fuzzy quantified propositions.

Flexible Querying and Bipolarity

In this section, we introduce fuzzy bipolar conditions, a bipolar relational algebra [START_REF] Liétard | On the extension of SQL to fuzzy bipolar conditions[END_REF][START_REF] Bosc | Extending relational algebra to handle bipolarity[END_REF] and the basis of Bipolar SQLf language.

Fuzzy Bipolar Conditions

A bipolar condition is a compound condition which is made of two conditions defined on the same universe: i) a constraint c, which describes the set of acceptable elements, and ii) a wish w which defines the set of desired elements. Since it is incoherent to wish a rejected element, the property of coherence w ⊆ c holds.

It is worth mentioning that the linguistic expression of a fuzzy condition may not follows the coherence property. As an example, a user may think of "a japanese car and if possible a red car", however, such a condition should be clearly be rewritten "a japanese car, and if possible a japanese and red car".

In addition, condition c is mandatory in the sense that an element which does not satisfy it is rejected. Condition w is optional in the sense that an element which does not satisfy it is not necessarily rejected.

If c and w are boolean conditions, the satisfaction with respect to (c, w) is a couple from {0, 1} 2 . When querying a database with such a condition, tuples satisfying the constraint and the wish are returned in priority to the user. If such answers do not exist, tuples satisfying only the constraint are delivered.

If c and w are fuzzy conditions (defined on the universe U ), the property of coherence becomes: ∀u ∈ U, µ w (u) ≤ µ c (u) and the satisfaction with respect to (c, w) is a couple of degrees from [0, 1] × [0, 1]. Each element u from U is then attached with a pair of grades (µ c (u), µ w (u)) that expresses the degree of its satisfaction respectively to the constraint c and to the wish w.

In the context of bipolar relations, a tuple t is then denoted (µ c , µ w )/t. We assume that any tuple u such that µ c (u) = 0 does not belong to the fuzzy bipolar relation. In addition, tuples cannot be ranked from the most to the least preferred using an aggregation of µ c and µ w because constraints and wishes are not commensurable. However they can be ranked using the lexicographical order:

t 1 is preferred to t 2 , denoted t 1 > t 2 or (µ c (t 1 ), µ w (t 1 )) > (µ c (t 2 ), µ w (t 2 )), iif µ c (t 1 ) > µ c (t 2 ) or (µ c (t 1 ) = µ c (t 2 ) ∧ µ w (t 1 ) > µ w (t 2 ))
. Since the constraint is mandatory, its satisfaction is firstly used to discriminate among answers. The satisfaction with respect to the wish being not mandatory, it can only be used to discriminate among answers having the same evaluation with respect to the constraint. A total order is then obtained on c and w (with (1, 1) as the greatest element and (0, 0) as the least element).

Based on the lexicographical order, the lmin and lmax operators [START_REF] Liétard | On the definition of extended norms and co-norms to aggregate fuzzy bipolar conditions[END_REF][START_REF] Bosc | Extending relational algebra to handle bipolarity[END_REF] are used to define the conjunction (resp. intersection) and the disjunction (resp. union) of bipolar conditions (resp. relations).

They are defined on

([0, 1] × [0, 1]) 2 → [0, 1] × [0, 1] as follows: ((µ, η), (µ , η )) → lmin((µ, η), (µ , η )) = (µ, η) if µ < µ ∨ (µ = µ ∧ η < η ), (µ , η ) otherwise. ((µ, η), (µ , η )) → lmax((µ, η), (µ , η )) = (µ, η) if µ > µ ∨ (µ = µ ∧ η > η ), (µ , η ) otherwise.
The lmin (resp. lmax) operator is commutative, associative, idempotent and monotonic. The couple of grades (1, 1) is the neutral (resp. absorbing) element of the operator lmin (resp. lmax) and the couple (0, 0) is the absorbing (resp. neutral) element of the operator lmin (resp. lmax).

It can be noticed that a fuzzy predicate is a fuzzy bipolar predicate such that ∀x, (µ c (x) = µ w (x)), which means that a fuzzy condition is a fuzzy bipolar condition in which the wish is equal to the constraint. In other words, fuzzy bipolar conditions generalize fuzzy condition and it has been proven [START_REF] Liétard | On the definition of extended norms and co-norms to aggregate fuzzy bipolar conditions[END_REF][START_REF] Bosc | Extending relational algebra to handle bipolarity[END_REF] that lmin (resp. lmax) generalizes the t-norm min (resp. the t-conorm max).

Basis of the Bipolar Relational Algebra

We introduce the bipolar relational algebra proposed in [START_REF] Liétard | On the extension of SQL to fuzzy bipolar conditions[END_REF][START_REF] Bosc | Extending relational algebra to handle bipolarity[END_REF]. It is based on the couple (lmin, lmax). Let r and s be two fuzzy bipolar relations defined respectively by the fuzzy bipolar conditions (c 1 , w 1 ) and (c 2 , w 2 ).

The intersection: r ∩ s is a fuzzy bipolar relation defined as follows:

r ∩ s = {(µ c , µ w )/t|(µ c1 , µ w1 )/t ∈ r ∧ (µ c2 , µ w2 )/t ∈ s∧ (µ c , µ w ) = lmin((µ c1 (t), µ w1 (t)), (µ c2 (t), µ w2 (t)))}.
The union: r ∪ s is a fuzzy bipolar relation defined as follows:

r ∪ s = {(µ c , µ w )/t|(µ c1 , µ w1 )/t ∈ r ∧ (µ c2 , µ w2 )/t ∈ s∧ (µ c , µ w ) = lmax((µ c1 (t), µ w1 (t)), (µ c2 (t), µ w2 (t)))}.
The cartesian product: r ⊗ s is a fuzzy bipolar relation defined as follows:

r ⊗ s = {(µ c , µ w )/t ⊕ t |(µ c1 , µ w1 )/t ∈ r ∧ (µ c2 , µ w2 )/t ∈ s ∧(µ c , µ w ) = lmin((µ c1 (t), µ w1 (t)
), (µ c2 (t ), µ w2 (t )))}, where ⊕ is the operator of concatenation of tuples.

The projection π: the projection of distinct tuples of r on attributes a 1 , ..., a k is a fuzzy bipolar relation of tuples a 1 , ..., a k defined by: π a1,...,a k (r) = {(µ c1 , µ w1 )/ a 1 , ..., a k | (µ c1 , µ w1 ) = lmax t∈r∧t[a1,...,a k ]= a1,...,a k ((µ c1 (t), µ w1 (t))), where t[a 1 , ..., a k ] is the value of the tuple t on the attributes a 1 , ..., a k .

The selection σ: the selection of tuples from r, based on the fuzzy bipolar condition (c , w ) is defined as: σ(r, (c , w )) = {(µ c , µ w )/t|(µ c1 , µ w1 )/t ∈ r∧ (µ c , µ w ) = lmin((µ c (t), µ w (t)), (µ c1 (t), µ w1 (t)))}. The join operator : as in the SQL and SQLf languages, the join operator is defined by the bipolar selection operator applied over a bipolar cartesian product. This operator is studied in Section 4.

Bipolar SQLf Basic Statements

A Bipolar SQLf basic statement is a fuzzy bipolar selection applied over a bipolar projection operator. It has the following form:

Select [distinct] [n|t|(t 1 , t 2 )|n, t|n, (t 1 , t 2 )] attributes From
relations [as alias] Where (c, w); The parameters intended to calibration of the result are also extended to bipolarity. A bipolar top k query is obtained by positioning the optional integer n, which delivers the n best tuples attached with the n greatest couples of degrees in the sense of the lexicographical order. The qualitative calibration can be specified by either a threshold t ∈ [0, 1], which delivers tuples u such that (µ c (u), µ w (u)) ≥ (t, 0), or a couple of thresholds (t

1 , t 2 ) ∈ [0, 1] 2 , such that t 2 ≤ t 1 , which delivers tuples u such that (µ c (u), µ w (u)) ≥ (t 1 , t 2 ).
Example 2: The query "find the 2 best journeys which are fast and if possible not expensive", can be expressed in Bipolar SQLf as:

Select 2 #Journey From Journey as J Where (fast(J.duration), notexpensive(J.cost)); Due to the coherence property of fuzzy bipolar conditions, the fuzzy bipolar condition "fast and if possible and not expensive" is interpreted as "fast and if possible (fast and not expensive)".

The fuzzy predicate expensive can be defined as ∀x ∈ R + : µ Expensive (x) = x 80 , if x ∈ [0, 80]; 1, otherwise; where x expresses the cost of a journey. Its negation is defined as follows:

∀x ∈ R + , µ notExpensive (x) = 1 -µ Expensive (x).
Based on the definition of fuzzy predicates fast (example 1) and not expensive, the query is evaluated over the relation Journey and delivers the fuzzy bipolar relation Journey (Fast, notExpensive) (see Table 2). The returned tuples are ranked using the lexicographical order : (1, 0.13)/12, (0.66, 0.38)/13. The tuple #12 is the best one with regard to the constraint (total satisfaction), and tuples #13 and #10 have the same satisfaction with respect to the constraint but #13 is better than #10 on the wish. p

Extension of Complex SQLf Statements to Bipolarity

In this section, we define the bipolar join operator. Then, the extension to bipolarity of nesting operators (in = , in ≈ , exists, θany) and aggregate functions are defined in the scope of their equivalence to the bipolar join operator. Since fuzzy bipolar conditions generalize fuzzy conditions, the bipolar definition of these operators is based on the extension to bipolarity of the SQLf statements.

Extension of the Join Operator to Bipolarity

The basic form of an SQLf join query is as follows:

Q 1 : Select R.A, R .B From R, R
Where c 1 (R) and c 2 (R ) and R.att 1 = R .att 2 ; where c 1 and c 2 are two fuzzy conditions applied resp. on relations R and R . Tuples u = (a, b) delivered from Q 1 are attached with degrees processed by the following formula (1):

µ Q1 (u) = max t∈R∧t ∈R ∧t.A=a∧t .B=b min(µ R (t), µ c1 (t), µ R (t ), µ c2 (t ), µ = (t.att 1 , t .att 2 )) (1)
The formula (1) can be rewritten as follows:

µ Q1 (u) = max t∈R∧t ∈R ∧t.A=a∧t .B=b∧t.att1=t .att2 min(µ R (t), µ c1 (t), µ R (t ), µ c2 (t )) (2)
In the context of bipolarity, the basic form of a join query is as follows:

Q 2 : Select R.A, R .B From R, R Where (c 1 (R), w 1 (R)
) and (c 2 (R ), w 2 (R )) and R.att 1 = R .att 2 ; The definition of the join operator based on the formula (1) is as follows:

(µ cQ2 (u), µ wQ2 (u)) = lmax t∈R∧t ∈R ∧t.A=a∧t .B=b lmin((µ Rc (t), µ Rw (t)), (µ c1 (t), µ w1 (t)), (µ R c (t ), µ R w (t )), (µ c2 (t ), µ w2 (t )), (µ = (t .att 2 , t.att 1 ), µ = (t .att 2 , t.att 1 ))) (3)
Based on the formula (2), tuples u = (a, b) delivered from Q 2 are attached with couples of degrees processed by the following formula (4):

(µ cQ2 (u), µ wQ2 (u)) = lmax t∈R∧t ∈R ∧t.A=a∧t .B=b∧t.att1=t .att2 lmin( (µ Rc (t), µ Rw (t)), (µ c1 (t), µ w1 (t)), (µ R c (t ), µ R w (t )), (µ c2 (t ), µ w2 (t ))) (4)
It is easy to prove that formulas (4) and (3) are equivalent.

Remark: A bipolar θ-join operator, where θ is either a boolean or a fuzzy relational operator (θ ∈ {<, >, ≤, ≥, =, =, around , much greater than, ...}), can straightforwardly be defined from formula (3) by substituting (µ = (t .att 2 , t.att 1 ), µ = (t .att 2 , t.att 1 )) by (µ θ (t .att 2 , t.att 1 ), µ θ (t .att 2 , t.att 1 ).

Bipolar (θ c , θ w )-join operator

We define a new bipolar join operator denoted (θ c , θ w )-join made of two relational operators: θ c and θ w which are in {<, >, ≤, ≥, =, =, around ,greater than, ...}.This bipolar operator permits us to express queries such as "find salespersons who get a turnover much greater and if possible very much greater than 10 times their own salary". The main form of such queries is:

Q 2 : Select R.A, R .B From R, R Where (c 1 (R), w 1 (R)) and
(c 2 (R ), w 2 (R )) and (R.att 1 θ c R .att 2 , R.att 3 θ w R .att 4 ); Based on the formula (3), couples of degrees associated to tuples delivered from Q 2 are processed by the following formula ( 5 Due to the space limitation, we only describe the derived fuzzy bipolar relations: Seller (Young,veryYoung) (see Table 3) and Balance (low,veryLow) , in which we show the couples of degrees of satisfaction to the bipolar join condition (much greater(S.salary*5,MB.turnover),very much greater(S.salary*5, MB.turnover))).

The predicate low is defined on

R + → [0, 1] as: µ low (x) = 1 if x ∈ [0, 25000], µ low (x) = -x 5000 + 6 if x ∈ [25000, 30000], µ low (x) = 0 otherwise. The predicate very low is defined as ∀x ∈ R + : µ veryLow (x) = (µ low (x)) 2 .
We define the predicate much greater on (R 2 + → [0, 1]): µ muchGreater (x, y) = 1 -y

x if x > y; 0, otherwise; and the predicate very much greater is defined: ∀(x, y) ∈ R 2 + : µ vM Greater (x, y) = (µ mGreater (x, y)) 2 . The couple of degrees associated to the seller #1 is: (µ c (#1), µ w (#1)) = lmax(lmin((0.8, 0.64), (0.5, 0.25), (0.55, 0.33)), lmin((0.8, 0.64), (0.7, 0.49), (0.53, 0.28))) = lmax((0.5, 0.25), (0.53, 0.28)) = (0.53, 0.28).

For sellers #3 and #5, the couples of degrees are respectively: (µ c (#3), µ w (#3)) = (0.2, 0.04) and (µ c (#5), µ w (#5)) = (0.6, 0.36).

Sellers are delivered as follows: (0.6, 0.36)/#5, (0.53, 0.28)/#1, (0.2, 0.04)/#3. p In the SQLf language, the in = (resp. in ≈ ) operator expresses at what level a value of an attribute is equal (resp. is close) to a value from the fuzzy set delivered by the nested subquery. The main format of an in θ query, where θ ∈ {=, ≈}, in the SQLf language is:

Q 3 : Select A From R Where c 1 and att 1 in θ (Select att 2 From R Where c 2 );
The query Q 3 is equivalent to the following join query [START_REF] Bosc | SQLf: A relational database langage for fuzzy querying[END_REF]:

Q 4 : Select R.A From R, R Where R.att 1 θR .att 2 and c 1 (R) and c 2 (R );
Based on this equivalence, the evaluation of the condition v 1 such that:

v 1 = att 1 in θ (Select att 2 From R Where c 2 ) is as follows: µ v1 = max t ∈R min(µ R (t ), µ c2 (t ), µ θ (t .att 2 , t.att 1 )) (6)
This equivalence holds in the case of bipolarity. The condition v 1 is written

v 1 = att 1 in θ (Select att 2 From R Where (c 2 , w 2 )).
The evaluation of the condition v 1 is based on the extension of the formula (6) to bipolarity as follows:

(µ c v 1 , µ w v 1 ) = lmax t ∈R lmin((µ R c (t ), µ R w (t )), (µ c2 (t ), µ w2 (t )), (µ θ (t .att 2 , t.att 1 ), µ θ (t .att 2 , t.att 1 ))) [START_REF] Dubois | Bipolarité dans un processus d'interrogation flexible[END_REF] 4.4 Bipolar in (≈,=) Operator It is possible to define a bipolar in operator denoted in (≈,=) which expresses conditions v 2 of the following form: v 2 = att 1 in (≈,=) (Select att 2 From R Where (c 2 , w 2 )), which expresses at what level att 1 is close and if possible is equal to a value among those delivered from the bipolar SQLf subquery (Select att 2 From R Where (c 2 , w 2 )). From the syntactic point of view the bipolar operator in (≈,=) is expressed (approx, equal).

The evaluation of the condition v 2 is based on the following formula [START_REF] Kiebling | Foundation of preferences in database systems[END_REF], which is an extension to bipolarity in the formula ( 6):

(µ c v2 , µ w v2 ) = lmax t ∈R lmin((µ R c (t ), µ R w (t )), (µ c2 (t ), µ w2 (t )),
(µ ≈ (t .att 2 , t.att 1 ), µ = (t .att 2 , t.att 1 ))) [START_REF] Kiebling | Foundation of preferences in database systems[END_REF] It is worth noticing that a query defined with the bipolar in (≈,=) operator is equivalent to a (θ c , θ w )-join query where θ c corresponds to the ≈ operator and θ w corresponds to the = operator.

Example 4: We consider the following query "find villas which are small, and if possible not far from the downtown and having a price similar, and if possible equal to the price of apartments which are spacious, and if possible located near to the downtown". It can be expressed in the Bipolar SQLf as follows: Select #villa From Villa as V Where (small(V.surface), not far town(V.address)) and V.price (approx, equal) (Select #apart From Apartment as A Where (spacious (A.surface), near town (A.address))); p

Extension of the exists Operator to Bipolarity

In the scope of the SQLf language, the exists operator indicates a non emptiness of a fuzzy set. It is defined by the formula µ exists (E) = sup x∈support(E) µ E (x) which expresses at what extent an element belongs to the returned fuzzy set.

The main form of an exists query in the SQLf language is: Q 5 : Select A From R Where c 1 and exists (Select * From R Where c 2 and R.att 1 θR .att 2 ); where θ is a relational operator which can be either boolean or fuzzy.

This query is equivalent to the following join query:

Q 6 : Select A From R, R Where c 1 (R) and c 2 (R ) and R.att 1 θ R .att 2 ;
The condition v 3 defined by the exists operator: v 3 = exists (Select * From R Where c 2 and R.att 1 θ R .att 2 ) is evaluated by the following formula (9):

µ v3 = max t ∈R min(µ R (t ), µ c2 (t ), µ θ (t.att 1 , t .att 2 )) (9)
This interpretation preserves the equivalence between the exists operator and the in = and in ≈ operators, when θ ∈ {≈, =} and with the join operator.

In the context of bipolarity, these equivalences hold, and the condition v 3 is rewritten as v 3 = exists (Select * From R Where (c 2 , s 2 ) and R.att 1 θR .att 2 ).

The condition v 3 is evaluated by the following formula [START_REF] Liétard | On the definition of extended norms and co-norms to aggregate fuzzy bipolar conditions[END_REF]:

(µ c v 3 , µ w v 3 ) = lmax t ∈R lmin((µ R c (t ), µ R w (t )), (µ c2 (t ), µ w2 (t )),
(µ θ (t.att 1 , t .att 2 ), µ θ (t.att 1 , t .att 2 ))) [START_REF] Liétard | On the definition of extended norms and co-norms to aggregate fuzzy bipolar conditions[END_REF] From the formula (10), we can define the exist operator as the retrieval of the greatest couple of grades which satisfies the imbricated query.

The Extension of the θany Operator to Bipolarity

In the SQLf language, a query involving θany can be rewritten as a query involving the exists operator. This equivalence is also valid in the Bipolar SQLf language. As consequence, the two following queries are equivalent: Q 7 : Select A From R Where (c 1 , w 1 ) and att 1 θ any (Select att 2 From R Where (c 2 , w 2 )); Q 8 : Select A From R Where (c 1 , w 1 ) and exists (Select att 2 From R Where (c 2 , w 2 ) and R.att 1 θR .att 2 ); The evaluation of a θany query relies then on the formula (10).

Extension of Aggregate Functions Based Query to Bipolarity

Aggregate functions such as sum, count, avg, min, max are used to perform arithmetic operations over a set of tuples. The following query expresses the main form of an SQLf query based on aggregate functions: Q 9 : Select A From R Where c Group By A Having c f1 (agg 1 (att 1 )) cnt... cnt c fn (agg n (att n )); where c is a boolean condition, agg 1 , ..., agg n are aggregate functions which are applied resp. on attributes att 1 , ..., att n . The returned values are, then, used as parameters for fuzzy conditions c f1 , ..., c fn to determine their grades of satisfaction. Finally, the obtained grade are combined depending on connectors cnt.

The same principal of partitioning is used in the case of fuzzy bipolar conditions. The following query is the main form of such a partitioning: Q 9 : Select A From R Where c Group By A Having (c 1 (agg 1 (att 1 ), w 1 (agg 1 (att 1 )) cnt ... cnt (c n (agg n (att n ), w n (agg n (att n )); where cnt can be either an and or an or operator. The combination of the couples of grades returned by (c i , w i ), i = 1...n is based on lmin and/or lmax operators.

Conclusion

This article has considered the definition of an SQL-like language to express preferences defined by fuzzy bipolar conditions. Such fuzzy bipolar conditions are extension of fuzzy conditions. This language (namely Bipolar SQLf language) is an extension of the SQLf language to bipolarity. It is based on a relational bipolar algebra that defines basis operators and provides a well appropriate interpretation for each language statement. In this article, we have defined basic statements (projection, selection, join, etc.) and nesting operators such as in = , in ≈ , exists and θany.

As future works, we aim at extending the language to fuzzy bipolar quantified propositions, to be able to express queries based on linguistic quantifiers such as "find stores that have most of their sellers are young and if possible well paid", and to study queries corresponding to divisions involving fuzzy bipolar relations, such as "find students who are well scored and if possible very well scored in all difficult and if possible in all very difficult courses". An implementation of a prototype for query evaluation is in progress, and in order to provide users with personalized services, this language is intended to be integrated into a platform of flexible querying of heterogeneous and distributed information systems developed in the field of multimodal transportation networks, in which complex queries could be expressed such as: "find journeys from Lannion to Brussels which are fast and having early departures, and if possible not expensive and having steps which go through stations in which are located good restaurants which serve health foods and if possible not expensive".

is an example of the fuzzy relation fastJourney and journey #12 and either journey #13 or #10 are delivered. pTable 1 .

 1 Extension of the fuzzy relation fastJourney.

	#Journey cost ($) duration (h) ... µFastJourney
	12	70	2	...	1
	13	50	3	...	0.66
	10	50	4	...	0.66

Table 2 .

 2 Fuzzy bipolar relation Journey (Fast, notExpensive) .

	#Journey cost ($) duration (h) µFast µFast ∧µnotExpensive
	12	70	2	1	0.13
	13	50	3	0.66	0.38
	10	50	4	0.66	0.33

  R c (t ), µ R w (t )), (µ c2 (t ), µ w2 (t )), (µ θc (t .att 2 , t.att 1 ), µ θw (t .att 3 , t.att 4 ))) (5)Example 3: In order to select the best young sellers, a manager based on the monthly balance sheets can express the following query "find young and if possible very young salespersons with turnovers of their low and if possible very low monthly balance sheets, are much greater and if possible very much greater than 5 times their salary". It can be written in Bipolar SQLf as: Select #Seller From Seller as S, MonthBalance as MB Where S.#Seller = MB.#Seller and (young (S.age), very young (S.age)) and (low (MB.turnover), very low (MB.turnover)) and (much greater (S.salary*5, MB.turnover), very much greater (S.salary*5, MB.turnover));

			):
	(µ cQ 2 (u), µ wQ 2 (u)) =	lmax t∈R∧t ∈R ∧t.A=a∧t .B=b	lmin((µ Rc (t), µ Rw (t)),
	(µ c1 (t), µ w1 (t)), (µ

Table 3 .

 3 The fuzzy bipolar relation Seller (young,veryY oung) .

	#Seller salary µyoung µveryY oung
	5	2000	1	1
	1	2500 0.8	0.64
	3	2800 0.2	0.04

Table 4 .

 4 The fuzzy bipolar relation Balance (low,veryLow) . Extension of in = and in ≈ Operators to Bipolarity

	#Balance #Seller turnover µ low µveryLow µmGreater µvMGreater
	1	1	27500 0.5	0.25	0.55	0.30
	2	1	26500 0.7	0.49	0.53	0.28
	5	3	28500 0.3	0.09	0.56	0.32
	6	3	28000 0.4	0.16	0.55	0.31
	9	5	29500 0.1	0.01	0.66	0.44
	10	5	25000	1	1	0.60	0.36
	4.3

Acknowledgments

We warmly thank the Brittany region, the department of Côtes-d'Armor and the National Agency for Research (AOC Ref. ANR-08-CORD-009) for financing this work.


Nouredine Tamani
email: tamani@enssat.fr

Ludovic Liétard
email: ludovic.lietard@univ-rennes1.fr

Daniel Rocacher
email: rocacher@enssat.fr

Bipolarity and the relational division

Keywords: Relational division, fuzzy bipolar conditions, bipolar division, tolerant bipolar division

.

Introduction

The bipolarity in the domain of flexible querying is defined as the ability to express, in one single condition, positive and negative conditions, which are associated to form bipolar conditions. Several interpretations have been introduced for the combination and the evaluation of bipolar conditions (see [START_REF] Bordogna | A fuzzy query language with a linguistic hierarchical aggregator[END_REF][START_REF] Dubois | Bipolarity in flexible querying[END_REF][START_REF] Dubois | Bipolarité dans un processus d'interrogation flexible[END_REF][START_REF] Tré | Dealing with positive and negative query criteria in fuzzy database quering bipolar satisfaction degrees[END_REF][START_REF] Zadrozny | Bipolar queries using various interpretations of logical connectives[END_REF][START_REF] Zadrozny | Bipolar queries: A way to enhance the flexibility of database queries[END_REF]). In this paper, we rely on the interpretation introduced by Dubois and Prade [START_REF] Dubois | Bipolarity in flexible querying[END_REF][START_REF] Dubois | Bipolarité dans un processus d'interrogation flexible[END_REF], in which a bipolar condition is made of a constraint c, which is mandatory, and a wish w, which is optional. It is noted (c, w) and means "satisfy c and if possible satisfy w". We define then a bipolar query as a query that involves bipolar conditions. This paper is set in the general case of fuzzy bipolar conditions where c and w are fuzzy.

When querying a relation R with a fuzzy bipolar condition, each tuple t from R is then attached with a pair of grades (µ c (t), µ w (t)) that expresses the degree of its satisfaction respectively to the constraint c and the wish w, and a so-called fuzzy bipolar relation is obtained.

In order to define a bipolar relational algebra, the algebraic operators (selection, projection, join, union, intersection) have been extended to fuzzy bipolar conditions [START_REF] Liétard | On the extension of SQL to fuzzy bipolar conditions[END_REF][START_REF] Bosc | Extending relational algebra to handle bipolarity[END_REF]. These operators allow the expression of fuzzy bipolar queries over fuzzy bipolar relations.

In this paper, we are interested at the first step to the definition of a tolerant bipolar division operator, applied on boolean relations R and S, where the underlying universal quantifier all of the division oper-ator is substituted by the linguistic quantifier almost all as in the following query "Find students who got a mark which is ≥ 10 and if possible which is ≥ 15 in almost all courses", which corresponds to a tolerant bipolar division query of the bipolar relation StudentResults (≥10,≥15) by the boolean relation Courses. The interpretation of such a tolerant bipolar division is based on quantified propositions of type "Almost_all S are R".

At the second step, we study several approaches to express division queries which involve fuzzy bipolar relations, such as the query "Find students who are well scored and if possible very well scored in all difficult and if possible in all very difficult courses", which corresponds to a bipolar division of the fuzzy bipolar relation StudentResults (Well,VeryWell) by the fuzzy bipolar relation Courses (Difficult,VeryDifficult) .

The remainder of the paper is structured as follows. In section 2, a short reminder about fuzzy bipolar conditions and relations is introduced. In section 3, we recall previous works, introduced in [START_REF] Bosc | About bipolar division operators[END_REF][START_REF] Bosc | On the division of bipolar fuzzy relations[END_REF], to define a division operator applied on fuzzy bipolar relations. However, one may notice that this kind of bipolar division has not the form of an "and if possible" statement. In section 4, a tolerant division operator and its extension to bipolarity are proposed. In section 5, we introduce an interpretation of the division involving fuzzy bipolar relations, which is based on a final user's expectations. It is shown that this interpretation fits within the general model [START_REF] Bosc | About bipolar division operators[END_REF][START_REF] Bosc | On the division of bipolar fuzzy relations[END_REF]. Finally, section 6 concludes the paper and draws some lines for future works.

Fuzzy bipolar conditions

A bipolar condition is a compound condition which is made of two conditions defined on the same universe: i) a constraint c, which describes the set of acceptable elements, and ii) a wish w which defines the set of desired or wished elements. The negation of c is the set of rejected elements since it describes non-acceptable elements. Since it is not coherent to wish a rejected element, the following property of coherence holds: w ⊆ c.

In addition, condition c is mandatory since an element which does not satisfy c is rejected (¬c is the negative pole of the bipolarity). Condition w is optional since an element which does not satisfy it is not necessarily rejected (w is the positive pole of the bipolarity).

If c and w are boolean conditions, the satisfaction with respect to (c, w) is a pair from {0, 1} 2 . When querying a database with such a condition, tuples satisfying the constraint and the wish are returned in priority to the user. If such answers do not exist, tuples satisfying only the constraint are delivered.

If c and w are fuzzy conditions (defined on the universe U ), the property of coherence becomes: ∀u ∈ U, µ w (u) ≤ µ c (u) and the satisfaction with respect to (c, w) is a pair of degrees from [0, 1] × [0, 1]. Each element u from U is then attached with a pair of grades (µ c (u), µ w (u)) that expresses the degree of its satisfaction respectively to the constraint c and to the wish w. In the context of bipolar relations, a tuple t is then denoted (µ c , µ w )/t. We assume that any tuple u such that µ c (u) = 0 does not belong to the fuzzy bipolar relation.

In order to rank the delivered tuples, previous bipolar approaches [START_REF] Dubois | Bipolarity in flexible querying[END_REF][START_REF] Dubois | Bipolarité dans un processus d'interrogation flexible[END_REF][START_REF] Tré | Dealing with positive and negative query criteria in fuzzy database quering bipolar satisfaction degrees[END_REF][START_REF] Zadrozny | Bipolar queries using various interpretations of logical connectives[END_REF][START_REF] Zadrozny | Bipolar queries: A way to enhance the flexibility of database queries[END_REF] consider the aggregation of the constraint and the wish. In our case, the constraint and the wish are not commensurable and tuples cannot be ranked from the most preferred to the least preferred using an aggregation of µ c and µ w . However they can be ranked using the lexicographical order:

t 1 is preferred to t 2 , de- noted t 1 > t 2 or (µ c (t 1 ), µ w (t 1 )) > (µ c (t 2 ), µ w (t 2 )), if and only if µ c (t 1 ) > µ c (t 2 ) or (µ c (t 1 ) = µ c (t 2 ) ∧ µ w (t 1 ) > µ w (t 2 )
). These two degrees being not commensurable and since the constraint is mandatory, its satisfaction is firstly used to discriminate among answers. The satisfaction with respect to the wish being not mandatory, it can only be used to discriminate among answers having the same evaluation with respect to the constraint. A total order is then obtained on c and w (with (1, 1) as the greatest element and (0, 0) as the least element).

Based on the lexicographical order, the lmin and lmax operators [START_REF] Liétard | On the definition of extended norms and co-norms to aggregate fuzzy bipolar conditions[END_REF][START_REF] Bosc | Extending relational algebra to handle bipolarity[END_REF] are introduced in order to define the conjunction (resp. intersection) and the disjunction (resp. union) of bipolar conditions (resp. relations). They are respectively defined as follows:

([0, 1] × [0, 1]) 2 → [0, 1] × [0, 1] ((µ, η), (µ , η )) → lmin((µ, η), (µ , η )) = (µ, η) if µ < µ ∨ (µ = µ ∧ η < η ), (µ , η ) else. ([0, 1] × [0, 1]) 2 → [0, 1] × [0, 1] ((µ, η), (µ , η )) → lmax((µ, η), (µ , η )) = (µ, η) if µ > µ ∨ (µ = µ ∧ η > η ), (µ , η ) else.
The lmin (resp. lmax) operator is commutative, associative, idempotent and monotonic. The pair of grades (1, 1) is the neutral (resp. absorbing) element of the operator lmin (resp. lmax) and the pair (0, 0) is the absorbing (resp. neutral) element of the operator lmin (resp. lmax).

It can be noticed that a fuzzy relation is a fuzzy bipolar relation such that ∀x, (µ c (x) = µ w (x)), which means that a fuzzy condition is a bipolar condition in which the wish is equal to the constraint; and a regular relation corresponds to a fuzzy bipolar relation in which the pair of grades (1, 1) is associated to their tuples. It has also been proven that lmin (resp. lmax) generalizes the triangular norm min (resp. the triangular co-norm max) [START_REF] Liétard | On the definition of extended norms and co-norms to aggregate fuzzy bipolar conditions[END_REF][START_REF] Bosc | Extending relational algebra to handle bipolarity[END_REF].

Fuzzy and bipolar division operations

Two lines of extension of the relational division have been proposed by Bosc et al. in [START_REF] Bosc | About quotient and division of crisp and fuzzy relations[END_REF]. The first one concerns the operands of the division operator and the second one is about the operator itself. In this section, we are interested in the extension of the operands to fuzzy bipolar relations.

The definition of the division operator involving fuzzy bipolar relations is based on the extension of the division operator to fuzzy relations (obtained from fuzzy queries). In subsection 3.1, a short reminder of the division involving fuzzy relations is introduced and in subsection 3.2, we describe the general model [START_REF] Bosc | About bipolar division operators[END_REF][START_REF] Bosc | On the division of bipolar fuzzy relations[END_REF] for the extension of the relational division operator to fuzzy bipolar relations.

The division of fuzzy relations

We describe in what follows, the extension of the division operator to fuzzy relations proposed in [START_REF] Bosc | About quotient and division of crisp and fuzzy relations[END_REF].

Let R and S be two fuzzy relations of schema (A, X) and B respectively, where A and B are compatible sets of attributes.

The relational division of R(A, X) by S(B), denoted R[A ÷ B]S or more simply R ÷ S, defines a relation which consists of elements from R[X] which are associated to every element of S, where R[X] is the projection of R on attributes X. The grades attached to the resulting tuples are defined as follows:

µ R÷S (x) = inf a∈S µ S (a) → µ R (x, a)
, where → is a fuzzy implication. We recall that any fuzzy implication operator satisfies the following properties (which are used later):

• x ≤ z ⇒ (x → y) ≥ (z → y) • y ≤ z ⇒ (x → y) ≤ (x → z) • ∀x, (x → 1) = 1 • ∀y, (0 → y) = 1 • (1 → 0) = 0
Depending on the choice of the fuzzy implication, several meanings can be obtained for µ R÷S (x). For instance, when a Gödel fuzzy implication (a → Gö b = 1 if a ≤ b; b else) is used, the degree µ S is viewed as a threshold to be reached by µ R . In this case, µ R÷S (x) = 1 if all thresholds are reached, otherwise, µ R÷S (x) corresponds to the smallest value µ R that does not reach its threshold. and the fuzzy relation which results from the division, when Gödel fuzzy implication is used. The resulting relation states that for the student #1 all thresholds are reached, and for the student #2, thresholds are reached till 0.9. @

#Student #Course µ WellScored 1 C 1 1 1 C 2 0.6 1 C 3 0.9 2 C 1 0.9 2 C 2 0.6 2 C 3 0.8 3 C 1 0.4 3 C 3 0.8 Table 1: Example of extension of the relation R Well . #Course µ Difficult C 1 1 C 2 0.5 C 3 0.8

The division of bipolar relations

A general model for the division of bipolar relations is introduced in [START_REF] Bosc | About bipolar division operators[END_REF][START_REF] Bosc | On the division of bipolar fuzzy relations[END_REF]. It is based on the decomposition of the division operation involving fuzzy bipolar relations on two divisions involving fuzzy relations. The two obtained relations are, after that, combined to form the resulting fuzzy bipolar relation.

Let R (c,w) (A, X) and S (c ,w ) (B) be two fuzzy bipolar relations defined respectively by fuzzy bipolar conditions (c, w) and (c , w ). The fuzzy relations which can be extracted from them are:

• R c and R w of schema (A, X) which are respectively the projection of R (c,w) on the constraint c and the wish w. • S c and S w of schema B which are respectively the projection of S (c ,w ) on the constraint c and the wish w .

The fuzzy division operations which can be performed are (where S is the set made of B-values

#Student µ R Well ÷S Dif 1 1 2 0.9 Table 3: The resulting relation from R Well ÷ S Dif .
appearing in S (c ,w ) , and → is a fuzzy implication): R c ÷ S w : the degrees of satisfaction of the resulting tuples are obtained by the formula (1):

µ Rc÷S w (x) = inf a∈S (µ w (a) → µ c (x, a)) (1)
R w ÷ S c : the degrees of satisfaction of the resulting tuples are obtained by the formula (2):

µ Rw÷S c (x) = inf a∈S (µ c (a) → µ w (x, a)) (2)
R c ÷ S c : the degrees of satisfaction of the resulting tuples are obtained by the formula (3):

µ Rc÷S c (x) = inf a∈S (µ c (a) → µ c (x, a)) (3)
R w ÷ S w : the degrees of satisfaction of the resulting tuples are obtained by the formula (4):

µ Rw÷S w (x) = inf a∈S (µ w (a) → µ w (x, a)) (4)
The pair of grades of satisfaction proposed in this approach is the one composed by the extremum values µ Rc÷S w (formula (1)) and µ Rw÷S c (formula (2)), since they are the two degrees which respect the coherence property of bipolar conditions (due to the properties of fuzzy implications which ensure that ∀x,

µ Rw÷S c (x) ≤ µ Rc÷S c (x) ≤ µ Rc÷S w (x) and ∀x, µ Rw÷S c (x) ≤ µ Rw÷S w (x) ≤ µ Rc÷S w (x)),
and guarantee that the resulting fuzzy bipolar relation is a quotient [START_REF] Bosc | About bipolar division operators[END_REF][START_REF] Bosc | On the division of bipolar fuzzy relations[END_REF].

The degree µ Rc÷S w expresses at what extent a perfect element in the divisor S is related to an accepted element in the dividend R, and the degree µ Rw÷S c expresses at what extent an accepted element of S is related to a preferred element of R.

The degrees attached to each answer are established as the only possible alternative, without taking into account the bipolar aspect of the resulting relation. In other terms, this division does not take the form of an "and if possible" statement, and we think that it is a major issue. So, we propose other interpretations for the division extended to bipolarity in the next sections. Firstly, a tolerant bipolar division applied on boolean relations is studied in section 4; secondly, several forms of division involving fuzzy bipolar relations is discussed in section 5.

Tolerant bipolar division of boolean relations

This section is devoted to a tolerant division in which the underlying quantifier is the linguistic quantifier almost all. Subsection 4.1 introduces the basis of such a division. An improvement based on bipolarity is proposed in subsection 4.2.

A tolerant relational division

Let R(A, X) and S(B) be two regular (boolean) relations with (A, X) and B are their respective schemas. A tolerant division of R by S, denoted

#Student #Course #Student #Course 1 C 1 2 C 1 1 C 2 2 C 2 1 C 3 2 C 3 1 C 4 2 C 4 1 C 5 2 C 5 3 C 1 4 C 1 3 C 2 4 C 3 3 C 3 4 C 4 3 C 5 4 C 5 Table 4: Extension of the relation StudentResults ≥10 .
R ÷S, is defined as the retrieval of elements from R[X] which are related to almost all elements of S.

The interpretation of such a division is based on that of quantified propositions of the form "Q Y are Z". More precisely, R ÷S delivers elements x from R[X] where x is attached to the degree of satisfaction of the quantified proposition: "Almost all elements of S are related to x in R". Therefore, for a given value x appearing in R we get:

µ R[A ÷B]S (x) = µ Almost_all ( v n ) ( 5
)
where v is the number of elements of S which are in relationship R with x and n is the cardinality of S. This tolerant division delivers elements which would be discarded by the regular division R ÷ S. Let table 4 be an example of the relation StudentResults ≥10 and Courses is a table which contains 5 courses:

C 1 , C 2 , C 3 , C 4 and C 5 .
We define the linguistic quantifier almost all by the following membership function:

µ Almost_all : [0, 1] → [0, 1] p → µ Almost_all (p) = 0 if p ∈ [0, 0.5] 2p -1 if p ∈ [0.5, 1]
The resulting relation from this tolerant division is a fuzzy relation (table 5), in which: would be discarded by the regular division. @ A drawback of this tolerant division is that elements are ranked with respect to µ Almost_all ( v n ), which in fact reverts to rank the elements with respect to v n (as far as v n = 0). We think that it is rather a weak discrimination and the next subsection shows that bipolarity can help to provide a refinement of this tolerant division.

µ R ÷S (1) = µ R ÷S (2) = µ Almost_all ( 5 5 ) = µ Almost_all (1) = 1,

A tolerant bipolar relational division

As pointed out, the tolerant division operator applied on crisp relations R and S delivers elements x attached to degrees corresponding to portions of elements of S which are related to x in R. The obtained elements can be gathered with respect to the degrees, which leads to a weak discrimination between tuples. We show through the following example 3 that the bipolarity can improve the discrimination between the resulting tuples.

Example 3: The query of the example 2 can be extended to bipolarity as follows: "Find students who got a mark which is ≥ 10 and if possible which is ≥ 15 in almost all courses". The obtained query can be rewritten as "Find students who got a mark which is ≥ 10 in almost all courses, and if possible students who got a mark which is ≥ 15 in almost all courses".

The resulting relation is a fuzzy bipolar relation (see table 6) made of tuples from the tolerant division R ≥10 ÷S, and if possible tuples from the tolerant division R ≥15 ÷S, where R ≥10 (resp. R ≥15 ) is the projection on columns #Student and #Course of the relation StudentResults restricted to students who got marks ≥ 10 (resp. ≥ 15), and S denotes the relation Courses.

Each student is attached to two degrees, each of them being the expression of the tolerant division as previously defined ("find students who got a mark which is ≥ 10 in almost all courses" and "find stu-dents who got a mark which is ≥ 15 in almost all courses" respectively). The most important result is the one provided by the first division. The second degree may be used to discriminate between elements having the same level of satisfaction with respect to the first one. In other words, the lexicographical order can be used to rank the tuples and to provide a refinement to the order delivered by the tolerant division "find students who got a mark which is ≥ 10 in almost all courses". Students are then ranked as follows: #2 > #1 > #3 > #4. @ More formally, this type of tolerant bipolar division can be defined as (R 1 , R 2 ) ÷S where R 1 and R 2 are two boolean relations such that R 2 ⊆ R 1 , and S is a boolean relation. This kind of division expresses queries of the form "find elements from R 1 and if possible elements from R 2 which are related to almost all elements of S". This form is rewritten as: "find elements from R 1 which are related to almost all elements of S, and if possible elements from R 2 which are related to almost all elements of S". Such a query is interpreted as: for each delivered element x, "almost all elements of S are associated with x in R 1 , and if possible almost all elements of S are associated with x in R 2 ".

This type of tolerant division can be rewritten R (c,w) ÷S, where R is a bipolar relation of schema (A, X) defined by a boolean constraint c and a boolean wish w, and S is a boolean relation of schema B. In this case, the division of the bipolar relation R (c,w) by the boolean relation S delivers elements x from R c [X], which are related to almost all elements of S, and if possible, elements x from R w [X], which are related to almost all elements of S. The resulting relation is a fuzzy bipolar relation and the pair of grades (µ Rc ÷S , µ Rw ÷S ) associated to tuples is computed as follows:

µ Rc[A ÷B]S (x) = µ Almost_all ( v n ). µ Rw[A ÷B]S (x) = µ Almost_all ( v n )
, where v (resp. v ) is the number of elements of S which are in relationship R c (resp. R w ) with x, and n is the cardinality of S.

The obtained pairs of degrees satisfy the coherence property of fuzzy bipolar conditions, since

R w ⊆ R c ⇒ ∀x, v ≤ v ⇒ ∀x, Almost_all( v n ) ≤ Almost_all( v n ).
It is worth noticing that the extension of such a tolerant bipolar division to fuzzy relations is rather difficult since its interpretation amounts to evaluate a quantified proposition of the form "Almost_all Y X are Z". This kind of quantified propositions raises an issue of interpretation when the fuzzy set Y tends to an empty set. This case is not detailed because it is out of the scope of this paper.

The division of fuzzy bipolar relations

Different forms of divisions involving bipolar relations can be distinguished; they are studied in this section in terms of interpretation and evaluation.

Division of the form R ÷ S (c,w)

By definition, the division operation is a matter of quantities. The division R[A ÷ B]S delivers the R[X] elements which are related in R to all elements of S without taking into consideration the meaning of this relationship. Therefore, in the bipolarity context, the division operator can be applied to express bipolar queries involving fuzzy relations S 1 and S 2 such that S 2 ⊆ S 1 as divisors.

Such queries, which express a division, have then the following main format: "Return elements from R[X] which are related to all elements of S 2 and if possible related to all elements of S 1 ".

More formally, let R be a relation (either boolean or fuzzy) and let S 1 and S 2 such that S 2 ⊆ S 1 be two fuzzy relations involved as divisors in a fuzzy bipolar division query of the form R÷(S 1 , S 2 ). This division is interpreted as follows:

R ÷ (S 1 , S 2 ) = (R ÷ S 2 , R ÷ S 1 ), (6)
where (R ÷ S 2 , R ÷ S 1 ) denotes the fuzzy bipolar relation defined as elements which are from R ÷ S 2 and if possible elements which are from R ÷ S 1 . This type of division can be rewritten R ÷ S (c,w) , where R can be either a boolean or a fuzzy relation and S is a fuzzy bipolar relation. In this case, the division of the relation R(A, X) by the fuzzy bipolar relation S (c,w) delivers elements x from R[X], which are related to every element of S w , and if possible, elements x from R[X], which are related to every element of S c . The resulting relation is a bipolar relation and the pair of grades (µ R÷Sw , µ R÷Sc ) associated to tuples is computed as follows:

µ R÷Sw (x) = min a∈Sw (µ w (a) → µ R (a, x)), µ R÷Sc (x) = min a∈Sc (µ c (a) → µ R (a, x))
, where S c (resp. S w ) is the projection of S (c,w) on the constraint c (resp. on the wish w), and → is a fuzzy implication.

The obtained pairs of grades satisfy the coherence property of fuzzy bipolar conditions, since:

∀a ∈ S, µ w (a) ≤ µ c (a) then ∀x, µ w (a) → µ R (a, x) ≥ µ c (a) → µ R (a, x).
(R 1 , R 2 ) ÷ S = (R 1 ÷ S, R 2 ÷ S), (7)
where (R 1 ÷ S, R 2 ÷ S) is the fuzzy bipolar relation defined as elements which are from R 1 ÷ S, and if possible elements which are from R 2 ÷ S. This type of division can be rewritten R (c,w) ÷ S, where R (c,w) (A, X) is a fuzzy bipolar relation and S is either a boolean or a fuzzy relation. In this case, the division of R (c,w) by the relation S consists in the retrieval of elements x of R c [X], which are related to all elements of S, and if possible, elements x of R w [X], which are related to all elements of S.

The resulting relation is a fuzzy bipolar relation and the pair of grades (µ Rc÷S , µ Rw÷S ) associated to tuples is computed as follows:

µ Rc÷S (x) = min a∈S (µ S (a) → µ c (a, x)). µ Rw÷S (x) = min a∈S (µ S (a) → µ w (a, x)).
The obtained pairs of grades satisfy the coherence property of fuzzy bipolar conditions, since: ∀y ∈ R, µ w (y) ≤ µ c (y) then ∀y = (a, x), µ S (a) → µ w (a, x) ≤ µ S (a) → µ c (a, x).

Example 5: The following query "Find students who are well scored and if possible very well scored in all difficult courses" is rewritten as "Find students who are well scored in all difficult courses, and if possible students who are very well scored in all difficult courses". This query is processed as the division of the fuzzy bipolar relation StudentResults (WellScored,VeryWellScored) , de- 10 shows the resulting relation when the Gödel fuzzy implication is used. @

Division of the form R (c,w) ÷ S (c ,w )

Let R 1 , R 2 , S 1 and S 2 be four fuzzy relations such that R 2 ⊆ R 1 and S 2 ⊆ S 1 , which are involved in the bipolar division (R 1 , R 2 ) ÷ (S 1 , S 2 ). Firstly, we consider the dividend (R 1 , R 2 ) and we apply the formula [START_REF] Bosc | About quotient and division of crisp and fuzzy relations[END_REF]. Then, since (S 1 , S 2 ) is the divisor, the formula (6) is applied. Finally, the resulting fuzzy bipolar relation is obtained by identification.

Since R 1 and R 2 are involved in the bipolar division (R 1 , R 2 ) ÷ (S 1 , S 2 ) as dividends and by using the formula [START_REF] Bosc | About quotient and division of crisp and fuzzy relations[END_REF], this fuzzy bipolar division must deliver a fuzzy bipolar relation ρ defined by elements which are from (R 1 ÷ ∆) and if possible elements from (R 2 ÷ ∆ ): ρ = (R 1 ÷ ∆, R 2 ÷ ∆ ), where ∆ and ∆ are fuzzy relations.

Moreover, because S 1 and S 2 are involved as divisors and by using the formula (6), the bipolar division must deliver a bipolar relation ρ defined by elements which are from (∇ ÷ S 2 ) and if possible elements from (∇ ÷ S 1 ): ρ = (∇ ÷ S 2 , ∇ ÷ S 1 ), where ∇ and ∇ are fuzzy relations.

Since, the fuzzy bipolar division (R 1 , R 2 ) ÷ (S 1 , S 2 ) delivers the same fuzzy bipolar relation as result, then ρ = ρ , which means that:

(R 1 ÷ ∆, R 2 ÷ ∆ ) = (∇ ÷ S 2 , ∇ ÷ S 1 ).
By identification, we obtain straightforwardly: ∆ = S 2 and ∆ = S 1 ∇ = R 1 and ∇ = R 2 Finally, the following general form for the division that involves fuzzy bipolar relations is obtained:

#Student µ R Well ÷S VeryDif µ R VeryWell ÷S Dif 1 1 0.36 2 0.9 0.36
Table 11:

The resulting relation from R (Well,VeryWell) ÷ S (Dif ,VeryDif ) .

(R 1 , R 2 ) ÷ (S 1 , S 2 ) = (R 1 ÷ S 2 , R 2 ÷ S 1 ). This form of bipolar division can be rewritten R (c,w) ÷ S (c ,w ) , where both R (c,w) and S (c ,w ) are fuzzy bipolar relations. The division of R (c,w) of schema (A, X) by the fuzzy bipolar relation S (c ,w ) delivers elements x of R c [X] which are related to all elements of S w , and if possible, elements x of R w [X], which are related to all elements of S c . The resulting relation is a fuzzy bipolar relation and the pair of grades (µ Rc÷S w , µ Rw÷S c ) associated to tuples is computed using formulas (1) and ( 2).

This form of fuzzy bipolar division is in adequacy with the general model introduced in [START_REF] Bosc | About bipolar division operators[END_REF][START_REF] Bosc | On the division of bipolar fuzzy relations[END_REF], and pairs of grades attached to answers satisfy the coherence property of fuzzy bipolar conditions as previously stated in subsection 3.1.

Example 6:

The following query "Find students who are (well scored and if possible very well scored) in all (difficult courses and if possible in all very difficult courses)" is rewritten as "Find students who are well scored in all very difficult courses, and if possible students who are very well scored in all difficult courses". This query is the division of the fuzzy bipolar relation StudentResults (WellScored,VeryWellScored) , denoted R (Well,VeryWell) , by the fuzzy bipolar relation Courses (Difficult,VeryDifficult) , denoted S (Dif ,VeryDif ) : R (Well,VeryWell) ÷ S (Dif ,VeryDif ) = (R Well ÷ S VeryImp , R VeryWell ÷ S Dif ). 7), when the Gödel fuzzy implication is used. @

Conclusion

The extension of the relational division operator to bipolarity is tackled in this paper. Firstly, a tolerant division operator and its extension to bipolarity are introduced. Secondly, a quantity-based division operator of fuzzy bipolar relations is studied in terms of interpretations. By doing this, we have shown that the general model proposed for the bipolar division [START_REF] Bosc | About bipolar division operators[END_REF][START_REF] Bosc | On the division of bipolar fuzzy relations[END_REF] can be interpreted in terms of bipolar statements, i.e. statements based on bipolar conditions of type "and if possible".

As future work, we aim at integrating of these forms of division operation into the bipolar SQLf language, which is an extension of the SQLf language [START_REF] Bosc | SQLf: A relational database langage for fuzzy querying[END_REF][START_REF] Bosc | Base de données -Gradualité et imprécision dans les bases de données Ensembles flous, requêtes flexibles et interrogation de données mal connues[END_REF] to fuzzy bipolar conditions.

Example 2 :

 2 Let Courses(#Course) and StudentResults(#Student, #Course, Mark) be two crisp relations. The following "Find students who got a mark which is ≥ 10 in almost all courses" corresponds to the tolerant division R ÷S, where R denotes the boolean relation StudentResults ≥10 , which is a projection on columns #Student and #Course of the restriction of the relation StudentResults to elements which got a mark ≥ 10, and S is the relation Courses.

Table 2 :

 2 Example of extension of the relation S Dif .

Example 1: The following query "Find students who are well scored in every difficult courses" corresponds to the division of the fuzzy relation StudentResults Well , denoted R Well , by the fuzzy relation Courses Difficult , denoted S Dif . Tables 1, 2 and 3 display respectively examples of relations StudentResults Well , Courses Difficult

Table 5 :

 5 StudentResults 10 ÷Courses The resulting relation from a tolerant division: StudentResults 10 ÷Courses. #Student µ R 10 ÷S µ R 15 ÷S

	1	1
	2	1
	3	0.6
	4	0.6
	2	1	0.6
	1	1	0.2
	3	0.6	0.6
	4	0.6	0.2
	Table 6:	The resulting relation from:
	(R ≥10 , R ≥15 ) ÷Courses.

since 100% of elements from S got a mark ≥ 10, and µ R ÷S (3) = µ R ÷S (4) = µ Almost_all ( 4 5 ) = µ Almost_all (0.8) = 0.6, since 80% of elements from S got a mark ≥ 10.

It can be checked that this tolerant division delivers elements (such as students #3 and #4) which #Student µ

Table 7 :

 7 StudentResults Well , denoted R Well , by the fuzzy bipolar relation Courses (Difficult,VeryDifficult) , denoted S (Dif ,VeryDif ) : R Well ÷ S (Dif ,VeryDif ) = (R Well ÷ S VeryDif , R Well ÷ S Dif ). Tables 7 and 8 display respectively an example of the relation Courses (Difficult,VeryDifficult) and the #Course µ Difficult µ VeryDifficult Extension of the relation S (Dif ,VeryDif ) .

	Example 4: The following query "Find students
	who are well scored in all difficult courses and if
	possible in all very difficult courses" is interpreted
	as "Find students who are well scored in all very
	difficult courses, and if possible students who are
	well scored in all difficult courses" (all very difficult
	courses being included in all difficult courses). It
	corresponds to the bipolar division of the fuzzy re-
	lation

Table 8 :

 8 The resulting relation from R Well ÷ S (Dif ,VeryDif ) .Let R 1 and R 2 be two fuzzy relations, such that R 2 ⊆ R 1 , involved as dividends in a fuzzy bipolar division of the form (R 1 , R 2 )÷S, where S is either a boolean or a fuzzy relation, the division query delivers "elements of R 1 which are related to all elements of S and if possible elements of R 2 which are related to all elements of S". More formally, this division is interpreted as follows:

	fuzzy bipolar relation which results from the divi-
	sion of R Well (see table 1) by the fuzzy bipolar re-
	lation S (Dif ,VeryDif ) , when the Gödel fuzzy implica-tion is used. @
	5.2. Division of the form R (c,w) ÷ S

Table 9 :

 9 #Student #Course µ WellScored µ VeryWellScored Extension of the relation R (Well,VeryWell) . Well ÷S Dif µ R VeryWell ÷S Dif

	1	C 1	1	1
	1	C 2	0.6	0.36
	1	C 3	0.9	0.81
	2	C 1	0.9	0.81
	2	C 2	0.6	0.36
	2	C 3	0.8	0.64
	3	C 1	0.4	0.16
	3	C 3	0.8	0.64
	1	1	0.36
	2	0.9	0.36

#Student µ R

Table 10 :

 10 The resulting relation from R (Well,VeryWell) ÷ S Dif . noted R (Well,VeryWell) by the fuzzy relation Courses Difficult , denoted S Dif (see table 2): R (Well,VeryWell) ÷ S Dif = (R Well ÷ S Dif , R VeryWell ÷ S Dif ). An example of extension of the relation R (Well,VeryWell) is displayed in table 9. Table

  Table 11 displays the fuzzy bipolar relation which results from the division of the fuzzy bipolar relation StudentResults (WellScored,VeryWellScored) (see table 9) by the fuzzy bipolar relation Courses (Difficult,VeryDifficult) (see table

Acknowledgments

This work is funded by the Brittany region and the department of Côtes-d'Armor and is partially supported by the National Agency for Research (AOC Ref. ANR-08-CORD-009).