Projet : BADINS - Évaluation de requêtes floues

<BODY bgcolor="#ffffff" text="#000000" link="#9944EE" vlink="#0000ff" alink="#00ff00"> <H2><A NAME="SECTION00066000000000000000"> Évaluation de requêtes floues</A> </H2>  <A NAME="BADINS_resultats_resultats6"></A> <P> <BR> <BR><SPAN CLASS="textbf">Participants : </SPAN> Patrick Bosc, Ludovic Liétard, Olivier Pivert. <BR> <BR> <P> <p> <strong> Mots clés : </strong><i> évaluation de requêtes, heuristiques, quantificateurs linguistiques, partitionnement .</i><p> <P> <H3>Résumé :</H3> <DIV CLASS="ABSTRACT"><I> Des stratégies d'évaluation de requêtes flexibles impliquant des quantificateurs linguistiques ont été définies. Des heuristiques sont proposées afin d'abaisser, autant que possible, le temps de traitement. </I></DIV> <P> <P> Afin d'aborder la mise en oeuvre et les aspects liés à la faisabilité d'un système de gestion de bases de données autorisant les requêtes flexibles, nous avons proposé des algorithmes pour évaluer des requêtes flexibles. Il est supposé que ces requêtes sont munies d'un seuil entre 0 et 1 exprimant un calibrage qualitatif des réponses (on ne retient que les réponses satisfaisant la requête à un degré supérieur au seuil). <P> Dans un premier temps, on s'intéresse aux requêtes impliquant un quantificateur linguistique (requêtes quantifiées) et faisant appel à un partitionnement. Dans ce cadre, la requête quantifiée se ramène à une proposition quantifiée de type "Q X sont A" ("la plupart des éléments de X sont jeunes") où Q est un quantificateur linguistique (la plupart), A une condition vague (être jeune) et où l'ensemble X est successivement instancié aux ensembles résultant du partitionnement. Basiquement l'algorithme d'évaluation détermine, pour chaque ensemble X, si l'évaluation de la proposition quantifiée "Q X sont A" est supérieure au seuil d'exigibilité. Notre objectif est de réduire le temps de traitement en limitant les accès aux éléments. Des heuristiques sont prises en compte pour déterminer, avant les accès à tous les éléments de X si l'évaluation est en dessous du seuil minimal. Une telle heuristique basée sur la définition du quantificateur (et sur le seuil) a été mise en évidence [<A HREF="bibliographie_ct.html#Bosc20e" TARGET="contents">15</A>]. Elle ne peut apporter de bénéfice qu'après un nombre déterminé d'accès (calculé d'après le quantificateur). Plus la valeur de ce nombre est faible et plus le bénéfice attendu peut être conséquent. En outre, cette heuristique nécessite de connaître la cardinalité de chaque ensemble, information pouvant être fournie par le système de gestion de bases de données via un mécanisme d'index amélioré. Dans le cas où cette cardinalité n'est pas connue (on en connaît cependant un majorant) nous avons montré que l'heuristique peut être utilisée mais avec une perte de son efficacité proportionnelle à la perte de précision sur la cardinalité. Une heuristique de succès (qui détermine si l'évaluation est en dessus du seuil) peut également être envisagée mais son emploi reste très particulier. En effet, une fois cette heuristique utilisée, on sait être en dessus du seuil minimal, mais on ne connaît cependant pas le degré exact de l'évaluation ce qui est en général inacceptable (ou inutile). <P> <HR>