Étude de la relaxation de requêtes dans un contexte flexible

Abstract

L'une des priorités lors de la conception de systèmes de gestion de bases de données est de rendre la conversation avec la machine plus abordable pour l'utilisateur profane. L'un des problèmes majeurs qu'il peut rencontrer est celui des réponses vides, dont le traitement s'inscrit dans un domaine qui étudie les subtilités des échanges conversationnels : celui des réponses coopératives. L'accès aux données distantes étant souvent incomplet, il semble pertinent de traiter ce problème en agissant sur la requête, en atténuant l'exigence de ses critères. Sa relaxation pourra permettre de récupérer des réponses qui bien que proches de ces conditions avaient été écartées car elles ne les satisfont pas strictement, le but étant d'obtenir un ensemble nonvide de réponses.Notre travail s'inscrit dans le cadre de l'étude des requêtes flexibles, à prédicats graduels et représentés par des ensembles flous. Les tuples sélectionnés ne satisfont pas obligatoirement pleinement les conditions comme avec les requêtes classiques, et sont ordonnés selon leur degré de satisfaction à ces conditions, ce qui revient à les discriminer selon les préférences de l'utilisateur.L'aspect coopératif est introduit par une technique de relaxation basée sur la proximité relative. Les éléments qui ne satisfont pas (du tout) la condition d'un prédicat mais sont dans un voisinage proche pourront être récoltés grâce à cette relation de tolérance. Ainsi, les prédicats constituant la requête infructueuse sont transformés un par un de manière itérative afin d'aboutir à une requête qui renvoie un ensemble non vide de réponses sans trop s'éloigner de la requête initiale.Les combinaisons de transformations successives constituent un treillis de requêtes relaxées. Afin d'optimiser son parcours, ce treillis pourra être élagué en utilisant la notion des MFS (Minimally Failing Subqueries). La meilleure des requêtes à réponse non vide obtenues après ce parcours sera ensuite choisie grâce à la mesure de la distance de Hausdorff, employée pour comparer ses prédicats flous avec ceux de la requête initiale.La mise en oeuvre de l'approche présentée a été effectuée à travers un prototype écrit en Java. Son interface permet de tester des requêtes flexibles et de réaliser des expérimentations pour estimer l'efficacité de l'approche étudiée sur des bases de données du monde réel.