Préférences et quantités dans le cadre de l’interrogation flexible : sur la prise en compte d’expressions quantifiées

Plus sur les mathématiques :

http://www.audentia-gestion.fr/MATHEMATIQUES/

 

ou juste avant la balise de fermeture -->

 

 

Préférences et quantités dans le cadre de l’interrogation flexible : sur la prise en compte d’expressions quantifiées Daniel Rocacher 1 Ludovic Liétard 2 1 IRISA/ENSSAT 2 IRISA/IUT Lannion 1 BP 447, 22305 Lannion Cédex, France, rocacher(à)enssat.fr 2 BP 150, 22302 Lannion cédex, France, ludovic.lietard(à)univ-rennes1.fr Résumé : L’interrogation flexible permet de prendre en compte des préférences de l’utilisateur dans les requêtes. Ces préférences sont exprimées au moyen de critères de sélection définis par des ensembles flous. Le traitement conjoint des notions de préférence et de cardinalité nous a conduits à définir le concept d’entier graduel ( f). Ce cadre a ensuite été étendu (en f et f) afin de pouvoir traiter des requêtes comportant des di érences et des divisions. Dans ce papier, nous étudions comment définir des relations d’ordre entre ces nombres graduels. Puis nous montrons que ces concepts appliqués au traitement d’expressions quantifiées du type Q X sont A ou Q B X sont A fournissent un nouveau cadre pour leurs interprétations. Mots-clés : Nombres graduels, relation d’ ordre, conjonction, disjonction, interrogation flexible. Abstract: Based on fuzzy set theory, flexible querying enables users to express preferences inside requirements. Quantifications and preferences on data have led us to define the notion of fuzzy integers ( f). This framework has been extended (to f and f ) in order to dealing with queries based on di erence or division operations. In this paper we study how to define fuzzy order relations between such fuzzy numbers. This approach applies to quantified statements of type “Q X are A” and “Q B X are A” and provides a new theoretical background for their interpretations. Keywords: Gradual numbers, order relation, conjonction, disjonction, flexible querying. 1 Introduction Un des objectifs de la recherche dans le domaine des bases de données est d’améliorer la capacité d’expression des langages de requêtes. Un des moyens étudiés est la prise en compte de préférences afin de faciliter l’accès à des informations pertinentes. Différentes propositions ont été faites pour introduire des préférences dans des requêtes. On peut distinguer deux approches générales selon que les valeurs de préférences associées aux attributs sont commensurables ou pas. Dans le premier cas, les valeurs de préférences peuvent être agrégées pour délivrer une valeur globale et définir un ordre total sur les réponses. Dans le second cas, lorsqu’il n’y a pas commensurabilité, seul un ordre partiel des réponses, basé sur l’ordre de Pareto, est possible et des classes incomparables de réponses sont construites. Cette approche est détaillée dans [7] et illustrée par l’opérateur Skyline [3] ou dans PreferenceSQL [14].Les préférences des utilisateurs peuvent aussi être exprimées par des critères de sélection fondés sur des ensembles flous. Les prédicats ne sont alors plus en « tout ou rien » mais peuvent être plus ou moins satisfaits. Par exemple, dans la requête « trouver les employés jeunes et bien-payés de l’ entreprise X », les critères jeune et bien-payé peuvent être plus ou moins satisfaits et leur définition doit tenir compte de préférences sur les valeurs des domaines indiquant lesquelles correspondent le mieux aux concepts décrits. Les critères jeunes et bien-payé sont définis par des ensembles flous permettant de restituer pour un âge et un salaire donnés des satisfactions définies sur une même échelle d’ interprétation, généralement l’ intervalle [0, 1]. Ces degrés de satisfaction sont donc commensurables et, en conséquence, composables. Ainsi, la théorie des ensembles flous est un cadre général permettant d’ exprimer des requêtes flexibles. Il a été montré [23] qu’ elle généralise d’ autres propositions essentiellement basée sur des distances [12][17][22]. Un ensemble flou E est défini par une fonction caractéristique m à valeur dans l’ intervalle [0, 1] de , telle que mE(x) exprime dans quelle mesure l’ élément x appartient à l’ ensemble flou E. Les prédicats dits graduels (i.e. dont le résultat est un degré de satisfaction), comme jeune et bien-payé, sont décrits au moyen d’ ensembles flous. Ces critères peuvent être combinés grâce à des opérateurs de conjonction ou de disjonction (éventuellement pondérés pour exprimer des importances relatives entre critères) ou de moyennes exprimant des effets de compensation entre critères. Les résultats d’ une requête flexible sont alors qualifiés en fonction de leur adéquation aux critères de sélection et peuvent être ordonnés. Divers travaux portant sur l’ expression et l’ interprétation de requêtes flexibles dans le contexte du modèle relationnel [6][13] et du modèle objet [8] ont vu le jour. Cette étude se place dans ce contexte de l’ interrogation flexible de bases de données usuelles (i. e. : ne contenant pas de données mal connues) et s’ intéresse plus particulièrement au traitement conjoint de préférences et de quantités sur les données manipulées. Concernant le traitement de quantités associées à des données, le concept de multi-ensemble, c’ est- à-dire de collection autorisant des occurrences multiples de ses éléments, est un support intéressant. Il trouve de nombreuses applications, en algorithmique notamment [16], mais aussi dans les bases de données [1][18]. Dans ce contexte, l’ utilisation des multi-ensembles est principalement motivée par leur capacité à gérer des quantités. On note qu’ ils facilitent également le traitement de certaines opérations en évitant la suppression des doubles. Les propriétés algébriques des multi-ensembles ont été largement étudiées, voir [2] pour une présentation complète. Nous avons montré [25][30] que l’ utilisation des multi-ensembles pour gérer des quantités et des ensembles flous pour gérer des préférences, conduit à la définition d’ une généralisation de ces structures appelée multi-ensemble flou [21][34]. Un multi-ensemble flou est un multi-ensemble dont chaque occurrence d’ un élément est associée à un degré d’ appartenance. Par exemple, un multiensemble flou peut être délivré par la requête : trouver le salaire des employés jeunes. Comme plusieurs employés peuvent avoir le même salaire, le résultat peut contenir des doubles. De plus, chaque occurrence d’ un salaire coïncide avec un employé plus ou moins jeune et est donc associée à un degré de satisfaction. Le multi-ensemble flou résultat correspond alors la distribution des salaires des employés jeunes. Dans [25] nous avons proposé une approche qui caractérise les multi-ensembles flous et permet de traiter de manière uniforme les ensembles, ensembles flous, multi-ensembles et multiensembles flous. Cette construction s’ appuie sur le concept d’ entier naturel graduel ( f) qui correspond à la cardinalité d’ un ensemble flou. Par la suite [28], nous avons défini un cadre plus général, basé sur l’ ensemble des entiers relatifs graduels ( f), dans lequel il est possible de définir des différences exactes. L’ intérêt de cette démarche est d’ offrir une base algébrique permettant la composition de calculs. Enfin, f a été prolongé en f [26][27], l’ ensemble des nombres rationnels graduels, afin de construire un système d’ opérations multiplicatives fermé et de réaliser des divisions exactes. Ces contextes permettent de traiter des requêtes flexibles complexes basées sur des calculs entre quantités graduelles ou nécessitant la manipulation de multi-ensembles flous [24]. Des requêtes de ce type sont par exemple : - calculer la moyenne des salaires des employés jeunes ; - trouver les entreprises où le nombre des employés proches de la retraite est plus grand que celui des employés jeunes ; - trouver les entreprises dont la plupart des employés jeunes sont bien-payés. Dans cet article, nous nous intéressons à l’ utilisation de ces notions pour traiter des requêtes portant sur des quantités graduelles. Ainsi, notre objectif est d’ étudier des conditions flexibles telles que : environ deux employés jeunes sont bien payés ou la plupart des employés jeunes sont bien payés qui comportent respectivement un quantificateur absolu (environ deux) et un quantificateur relatif (la plupart). Pour évaluer ces conditions il est nécessaire de définir des relations d’ ordre sur des quantités graduelles. Par la suite, en section 2, les constructions de f , f et f sont brièvement rappelées. Puis, en section 3, nous étudions comment définir des relations d’ ordre entre quantités graduelles au moyen d’ une intégrale pondérée. Nous montrons que cette notion de relation d’ ordre généralise le concept d’ implication floue définie dans le cadre de la logique multivaluée. Le cadre ainsi obtenu nous permet, en section 4, de proposer un mécanisme de base pour traiter des requêtes flexibles comportant des expressions quantifiées. 2 Quantités graduelles Dans cette section nous décrivons quelques éléments de base relatifs à la modélisation de quantités graduelles. Ceux-ci sont nécessaires à la compréhension des sections suivantes qui traitent de la comparaison de quantités graduelles et à leurs utilisations dans des expressions quantifiées. 2.1 Entiers naturels graduels Un ensemble flou, défini sur un domaine X, peut se définir par une fonction caractéristique, notée m E , telle que : mE : X ® [0, 1] x ® mE (x). La valeur mE(x) exprime dans quelle mesure l’ élément x de X appartient à l’ ensemble flou E. Quand mE(x) est nul, x n’ appartient pas du tout à E et quand il vaut 1, x est complètement dans E. Plus mE (x) est proche de 1 (resp. 0), plus (resp. moins) x appartient à E. Dans le cas d’ un ensemble flou fini E, on note généralement : { } å = = =  (  [ [  [ [  [ [ 1 1 1 m ( ) / ,...,m ( ) / m ( ) / . Un ensemble flou peut également être décrit comme une collection d’ ensembles ordinaires emboîtés grâce à la notion de coupes de niveau ou a-coupes. La coupe de niveau a de l’ ensemble flou E, notée Ea, est l’ ensemble usuel composé des éléments dont le degré d’ appartenance à E est au moins égal à a, d’ où : Ea = {x | x Î X et mE (x) ³ a}. La cardinalité floue |E| d’ un ensemble flou E est définie par un ensemble flou d’ entiers caractérisé par : " n Î , m|E|(n) = sup{a / |Ea| ³ n}. Cette définition est aussi appelée FGCount(E) par Zadeh [36]. Le degré a, associé à un entier n de |E|, évalue dans quelle mesure E contient au moins n éléments. Exemple 2.1. Soit l’ ensemble flou E = {1/x1, 1/x2, 0.5/x3, 0.2/x4}, la cardinalité de E est représentée par : |E| = {1/0, 1/1, 1/2, 0.5/3, 0.2/4}. Le degré 0.5 de |E| exprime dans quelle mesure l’ ensemble flou E contient au moins 3 éléments. ¨ La cardinalité d’ un ensemble usuel fini peut être vue comme un entier naturel n. La cardinalité floue d’ un ensemble flou fini peut être vue comme un entier que nous qualifions de graduel pour le distinguer de la notion de nombre flou au sens habituel du terme [10]. En effet, il est important de