Optimisation de requêtes OLAP en entrepôts de données : Approche basée sur la fragmentation génétique

Abstract

Les systèmes décisionnels manipulent de très importants volumes de données stockées dans des entrepôts de données. Ces derniers sont alimentés par des données provenant de sources distribuées et hétérogènes. Les entrepôts de données sont très souvent modélisés par un schéma en étoile. Ce schéma est caractérisé par une table de faits de très grande taille (allant de quelques Gigaoctets à plusieurs téraoctets) liée à un ensemble de tables de dimension de plus petite taille. Les requêtes définies sur un schéma en étoile (connues par requêtes de jointure en étoile) sont caractérisées par des opérations de sélection sur les tables de dimension, suivies de jointures avec la table des faits. Toute jointure doit passer par la table des faits, ce qui rend le coût d’exécution de ces requêtes très important. Sans technique d’optimisation, leur exécution peut prendre des heures, voire des jours. Les travaux présentés dans cette thèse traitent des apports de l’algorithmique génétique à ce problème. Notre étude se focalise en premier lieu, sur les principales techniques d’optimisation utilisées qui ont été suggérés dans la littérature pour améliorer les performances des entrepôts de données. En second lieu, notre intérêt s’est porté à la mise en oeuvre de notre approche d’optimisation de requête. Elle consiste à fragmenter un schéma relationnel d’un entrepôt de données horizontalement, ensuite verticalement afin de réduire le coût d’exécution de requêtes. Nous avons formalisé le problème de sélection de schéma de fragmentation verticale comme un problème d’optimisation avec contrainte. Cette dernière représente le nombre de fragments verticaux que l’administrateur peut maintenir. Pour le résoudre, nous avons proposé un algorithme génétique qui adapte le même codage que les algorithmes proposés. Un processus de codage des schémas de fragmentation possibles est décrit. Un modèle de coût qui représente la fonction sélective a été développé afin de mesurer la qualité de la solution choisie. Nous évaluons enfin notre approche, au travers d’expérimentations réalisées à l’aide d’un banc d’essai et un ensemble de requêtes décisionnelles pour prouver l’efficacité et l’utilité de la fragmentation mixte génétique, en entrepôt de données.