Projet IDAPA

Accueil > Bases de données relationnelles et indexation du contenu > Rapport - Partie 2b

Rapport - Partie 2b

Etude des difficultés techniques

vendredi 6 février 2009, par Yoann Moreau

4. Les difficultés techniques

Que ce soit pour le stockage ou la restitution, la taille très importante de l’entrepôt de données est une contrainte majeure. Plusieurs méthodes sont utilisables pour répondre aux problèmes et l’étude de ces solutions a été une part importante du projet.

4.1 Le stockage des données

Le principal défaut de l’entrepôt de données et de regrouper de nombreuses données issues de bases de données différentes (par exemples différents services d’une entreprise), ces données sont associées à un client ou un dossier spécifique et se regroupent donc par id (voir 3.2), cependant chaque id n’a généralement pas de valeurs pour chaque base intégrée dans l’entrepôt, ce qui crée de nombreuses valeurs nulles. L’espace occupé par ces valeurs inutiles peut alors prendre une dimension problématique étant donné la taille de l’entrepôt de données.
D’un point de vue mathématique, l’entrepôt est une matrice creuse.

Une solution efficace pour ce problème est la technique des méta-données. Cette technique change radicalement la manière de stocker les données et le concept des tables. Les attributs (colonnes) sont définis dans une table indépendante qui n’a pas de limite (chaque attribut est un tuple (ligne) de cette table), les types d’attributs sont également stockés dans une autre table. Ainsi la table contenant les données ne sera pas constituées d’autant de colonnes que d’attributs mais d’autant de lignes que de valeurs pour chaque attribut. Chaque ligne contient une valeur et une référence indiquant à quel attribut la valeur correspond.

Bien sûr il est possible de mieux détailler aussi bien la table des attributs que la table des valeurs, en ajoutant par exemple un nom en chaîne de caractères aux attributs, d’ajouter une colonne d’id dans la table des données pour indiquer à quelle ligne appartenait la valeur dans le modèle classique.

L’avantage de cette technique est que les valeurs sont stockées en colonne et non pas en matrice, ce qui évite toute valeur nulle. L’inconvénient est qu’il faut stocker toutes les valeurs dans une même colonne et qu’il est donc impossible de typer directement les valeurs si les attributs ont des types différents. L’accès en lecture peut paraître moins efficace car il y a beaucoup plus de lignes à parcourir mais la création d’index compense ce problème et peut même permettre de meilleures performances qu’un modèle classique.

La solution retenue pour le stockage des données dans l’entrepôt se rapproche de l’idée de méta-données. Les valeurs seront stockées dans une colonne unique (sous forme de texte), à chaque valeur sera associée l’attribut correspondant ainsi que l’id correspondant (une personne, un dossier etc) également sous forme de chaînes de caractères mais de tailles fixes. On a donc les mêmes informations que dans une table classique avec les attributs en colonne et les valeurs en ligne. La valeur est unique pour chaque couple id/attribut. Cette structure peut être implémentée par une table de base de données ou par un fichier texte où les colonnes sont séparées par des tabulations et les lignes par des sauts de ligne.

4.2 Les points sensibles de la restitution

4.2.1 L’indexation des valeurs

La projection qui ne consiste qu’à parcourir les données et sélectionner certaines lignes n’est pas une opération de complexité exponentielle. La coupe par contre nécessite un test sur les valeurs pour sélectionner les id à conserver, puis un parcours des données pour récupérer toutes les valeurs associées à ces id. Les valeurs étant éparpillées il faudra au minimum un parcours total des données, ou beaucoup plus si les conditions utilisent plusieurs attributs.

L’indexation des attributs (indexation classique) permet de ne parcourir que les valeurs correspondant aux attributs des conditions puis de les tester, mais dans le cas de très nombreuses valeurs ce parcours reste conséquent. L’indexation des valeurs (indexation fulltext) permet à l’inverse de parcourir uniquement les valeurs correspondant aux conditions, mais cela comprend également les valeurs qui seraient associées à un autre attribut que celui de la condition. Il faut donc non pas tester la valeur mais l’attribut.

L’efficacité de la recherche par attribut ou par valeur (impliquant l’indexation de l’une ou l’autre des colonnes) dépend du ratio : A par rapport à V avec A le nombre de lignes pour l’attribut et V le nombre de valeurs correspondant à la condition . Si A est supérieur à V alors rechercher par les valeurs est plus efficace, sinon rechercher par les attributs est plus efficace.

4.2.2 Les jointures

Dans la pratique il faudra souvent effectuer plusieurs projections puis les joindre en une seule table ayant pour clé l’id et pour colonnes les attributs des projections. Ces jointures s’appliqueront sur des sous cubes de taille importante et doivent donc être optimisées. Pour cela il faudra indexer la colonne des id (avec un index classique) pour pouvoir associer les lignes des différentes projections en évitant un parcours total.

Une alternative utilisant directement des fichiers tabulés des résultats des projections serait de concaténer les fichiers puis de trier sur la colonne des id pour regrouper les valeurs. Cela implique un tri et un parcours séquentiel.