Lourdes Martinez - Optimisation des requêtes distribuées par apprentissage

Les systèmes de gestion de données distribuées deviennent de plus en plus complexes. Ils interagissent avec des réseaux de dispositifs fixes et/ou mobiles, tels que des smartphones ou des tablettes, dispositifs hétérogènes, autonomes et possédant des limitations physiques. Ces dispositifs exécutent des applications permettant l’interaction des usagers (i.e. jeux virtuels, réseaux sociaux). Ces applications produisent et consomment des données à tout moment voire même en continu. Les caractéristiques de ces systèmes ajoutent des dimensions au problème de l’optimisation de requêtes, telles que la variabilité des objectifs d’optimisation, l’absence d’information sur les données (métadonnées) ou le manque d’une vision globale du système.

Les techniques traditionnelles d’optimisation des requêtes n’abordent pas (ou très peu) les systèmes autonomes. Elles se basent sur les métadonnées et font des hypothèses très fortes sur le comportement du système. En plus, la majorité de ces techniques d’optimisation ciblent uniquement l’optimisation du temps d’exécution. La difficulté d’évaluation des requêtes dans les applications modernes incite à revisiter les techniques traditionnelles d’optimisation.

Cette thèse fait face aux défis décrits précédemment par l’adaptation du paradigme du Raisonnement à partir de cas (CBR pour Case-Based Reasoning) au problème de l’optimisation des requêtes. Cette adaptation, associée à une exploration pseudo-aléatoire de l’espace de solutions fournit un moyen pour optimiser des requêtes dans les contextes possédant très peu voire aucune information sur les données. Cette approche se concentre sur l’optimisation de requêtes en utilisant les cas générés précédemment dans l’évaluation de requêtes similaires. Un cas de requête et composé par : (i) la requête (le problème), (ii) le plan d’exécution (la solution) et (iii) les mesures de ressources utilisés par l’exécution du plan (l’évaluation de la solution). Cette thèse aborde également la façon que le processus CBR interagit avec le processus de génération de plan d’exécution de la requête qui doit permettre d’explorer l’espace des solutions. Ce processus utilise les heuristiques classiques et prennent des décisions de façon aléatoire lorsque les métadonnées viennent à manquer (e.g. pour l’ordre des jointures, la sélection des algorithmes, voire même le choix des protocoles d’acheminement de messages). Ce processus exploite également le CBR pour générer des plans pour des sous-requêtes, accélérant ainsi l’apprentissage de nouveaux cas. Les propositions de cette thèse ont été validées à l’aide du prototype CoBRA développé dans le contexte du projet UBIQUEST ANR-09-BLAN-0131-01.