Extraction d’un bloc de donnes (Dice)

Extraction d’un bloc de donnes (Dice)

Les vues matérialisées

Introduction

Une vue matérialisée constitue un objet physique de la base de données. Elle contient les donnes rsultat d’une requête qui peut être une requête nomme (une vue). La matrialisation des vues est considre comme une technique tr`es utile : • Pour minimiser le temps de rponse des requêtes dcisionnelles dans les entrepôts de donnes (pr-calcul des jointures). • Pour viter les couˆts de transfert des donnes sur le rseau dans une architecture distribue d’entrepôt de donnes (dupliques les donnes sur chaque site de l’architecture). • Pour contrôler l’acc`es aux donnes (c.-a`-d. seules les donnes autorises sont mises a` la disposition des utilisateurs a` travers des vues matrialises).Cependant, la slection des vues a` matrialiser sous contrainte de maintenance (l’espace de stockage, le temps de maintenance total des vues matrialises) constitue un probl`eme majeure. Gupta and Mumick (1999) ont dﬁni le probl`eme de slection de vues matrialises comme suit : tant donne (i) un ensemble de n requêtes frquentes interrogeant un ensemble de tables, (ii) un ensemble de m vues, et (iii) une contrainte de maintenance (soit un espace de stockage ES, soit un temps de maintenance TM), le probl`eme de slection de vues matrialises consiste a` slectionner parmi les m vues un sous ensemble de k vues `a matrialiser de sorte que le temps de rponses des n requêtes soit minimis sous la contrainte que l’espace de stockage totale des k vues matrialises ne dpasse pas ES ou le temps de maintenance des k vues matrialises ne dpasse pas TM. Dans ce contexte, plusieurs travaux dans les entrepôts de donnes ont propos divers algorithmes pour rsoudre le probl`eme de slection des vues matrialises. Parmi ces travaux, nous citons ceux proposs dans (Gupta and Mumick, 1999; Zhixiang and Dongjin, CCA 2014; Gosain and Heena, 2016; Goswami et al., 2016; Sohrabi and Ghods, 2016).

Travaux sur la matérialisation des vues

La matrialisation (le pr-calcul et le stockage) de toutes les vues est impossible, due : (i) a` leur grand nombre qui croit exponentiellement en fonction des attributs des dimensions utiliss par les requêtes interrogeant l’entrepôt de donnes, et (ii) a` la contrainte de disponibilit de l’espace de stockage. De ce fait, la slection d’une conﬁguration optimale de vues matrialises constitue une solution importante d’un côt et un probl`eme assez complexe de l’autre côt (Baralis et al., 1997). Dans cette optique, plusieurs techniques ont t proposes pour rsoudre le probl`eme de slection de vues matrialises. Leur objectif principal est l’optimisation de performances des requêtes tout en respectant une contrainte de limite d’espace de stockage ou/et la contrainte de temps de maintenance. Harinarayan et al. (1996) ont introduit la structure de treillis compose de nœuds reprsentant toutes les vues pouvant être crs a` partir des dimensions de l’entrepôt de donnes par des agrgations a` des niveaux diﬀrents. Ainsi pour n dimensions, le treillis sera compos de 2n vues (nœuds). Un chemin existe entre deux nœuds ni et nj s’il existe une relation de dpendance note ni ≤ nj, qui signiﬁe que si le rsultat d’une requête q peut être obtenu a` partir de ni alors le même rsultat de q peut être aussi obtenu a` partir de nj. Matrialiser toutes les vues du treillis permet aux requêtes d’avoir les meilleurs temps des rponses. Malheureusement, pour une importante valeur de n, cette matrialisation ncessitera un grand espace de stockage. Wagner and Agrawal (2013) ont propos une slection de vues matrialises pondres (PSVM-pondr). La pondration consiste a` attribuer un poids `a chaque vue, qui est en fonction de la frquence d’acc`es et/ou de l’importance de la requête accdant a` la vue. Les auteurs ont propos une approche base sur un algorithme volutif pour dterminer l’ensemble de vues `a matrialiser de tel sorte que le nombre maximum de page disque soit minimis. `A partir : (i) d’un entrepôt de donnes, (ii) une liste de vues organise sous forme de treillis, (iii) un poids associ a` chaque vue, (iv) le nombre de pages occupes par chaque vue, (v) le nombre maximum de page disque pouvant être occupes par la matrialisation de vues, ils ont procédé de la fa¸con suivante :
1. Une population de solutions candidates est cre alatoirement. Selon la formulation du PSVM-pondr, la population des solutions candidates est composée de plusieurs ensembles de vues construit a` partir du treillis des vues possibles. Chaque ensemble doit respecter les contraintes suivantes : (i) la vue racine est incluse dans chaque ensemble, (ii) aucune vue n’est duplique dans l’ensemble, et (iii) le nombre de vues dans un ensemble doit être entre 2 et n, ou` n est le nombre de vues pouvant être matérialisées,
2. Chaque solution est classe en fonction de la valeur Z reprsentant le nombre maximal pondéré de pages qui doivent être rcupres pour obtenir les vues dans la solution,
3. Les solutions pertinentes ayant des valeurs Z petites sont slectionnes pour eﬀectuer les opérations génétiques (slection, croisement, mutation). Si deux solutions ont la même valeur Z, alors celle contenant un minimum de vues est favorise,
4. Des oprations de croisement et/ou de mutation sont appliques `a la nouvelle population obtenue précédemment. Ces opérations sont répétées pour un certain nombre d’itrations ou jusqu’a` ce que aucune amlioration dans la qualit de la solution n’est remarquée,
5. La solution ﬁnale, est celle ayant le plus haut classement dans la derni`ere population générée.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

1 Introduction
1.1 Introduction
1.2 Contributions
1.3 Organisation de la thèse
2 Entrepôt de données : Concepts de base
2.1 Introduction
2.2 Dﬁnition d’un entrepôt de données
2.3 Caractristiques des entrepôts de donnes
2.4 Modlisation multidimensionnelle d’un entrepôt de données
2.4.1 Le schéma étoile
2.4.2 Le schma en ﬂocon
2.5 Les implmentation OLAP
2.5.1 ROLAP (Relational On-Line Analytical Processing)
2.5.2 MOLAP (Multidimensional On-Line Analytical Processing)
2.6 Requêtes et oprations OLAP
2.6.1 Structure des requêtes OLAP
2.6.2 Les Oprations OLAP
2.6.2.1 Forage vers le bas (Drill-down)
2.6.2.2 Forage vers le haut (Roll-up)
2.6.2.3 Tranchage (Slice)
2.6.2.4 Extraction d’un bloc de donnes (Dice)
2.7 Conclusion
3 Techniques d’optimisation de performances dans les entrepôts de donnes
3.1 Introduction
3.2 Techniques et travaux d’optimisation
3.2.1 L’indexation des donnes
3.2.1.1 Dﬁnition
TABLE DES MATIERES
3.2.1.2 Types d’index
3.2.1.3 Travaux sur l’indexation de donnes
3.2.2 Les vues matrialisées
3.2.2.1 Introduction
3.2.2.2 Travaux sur la matrialisation des vues
3.2.3 La fragmentation de donnes
3.2.3.1 La fragmentation verticale
3.2.3.2 La fragmentation horizontale
3.2.3.3 La fragmentation mixte
3.2.3.4 Travaux sur la fragmentation
3.3 Avantages et inconvnients des techniques d’optimisation
3.4 Conclusion
4 Etude des techniques de fragmentation horizontale dans les entrepôts de donnes
4.1 Introduction
4.2 Travaux sur la fragmentation horizontale dans les entrepôts de donnes
4.3 Rsum des travaux de fragmentation
4.4 Conclusion
5 Problème d’optimisation de performances par la fragmentation horizontale : nouvelle formalisation
5.1 Introduction
5.2 Inconvnients des techniques de fragmentation horizontale existantes
5.2.1 L’explosion du nombre de fragments horizontaux
5.2.2 La non prise en compte des requêtes non bnﬁciant de la fragmentation
5.2.3 Le nombre de fragments ncessaires au traitement des requêtes bnﬁciant de la fragmentation
5.2.4 L’eﬀet des mtaheuristiques sur la slection du schma de fragmentation
5.3 Nouvelle formulation du probl`eme d’optimisation de performances par la fragmentation horizontale
5.4 Conditions de quasi-optimalit du schma de fragmentation horizontale
5.5 Satisfaction des conditions de quasi-optimalit du schma de fragmentation horizontale
5.6 Conclusion
6 Nouvelle approche de fragmentation horizontale dans les entrepôts de données
6.1 Introduction
6.2 Fragmentation horizontale de la table de faits
6.2.1 tape 1 : Extraction des prdicats et construction de la matrice d’usage

6.2.2 tape 2 : Identiﬁcation des prdicats de fragmentation
6.2.3 tape 3 : Gnration des fragments horizontaux
6.3 Exemple de fragmentation horizontale de la table de faits
6.3.1 tape 1 : Extraction des prdicats et construction de la matrice d’usage
6.3.2 tape 2 : Identiﬁcation des prdicats de fragmentation
6.4 Validation de la fragmentation horizontale de la table de faits
6.4.1 La disjonction entre les fragments horizontaux
6.4.2 La complétude
6.4.3 La reconstruction
6.5 Stratgie de rcriture et de traitement des requêtes sur l’entrepôt fragmenté
6.6 Conclusion
7 Etudes expérimentales et validation
7.1 Introduction
7.2 Environnement exprimental
7.2.1 Cration et alimentation de l’entrepôt de donnes
7.2.2 Architecture de notre implmentation
7.3 tudes exprimentales et validation
7.3.1 Exprience 1 : Test initial de performances des requêtes
7.3.2 Exprience 2 : Impact de la taille de la table de faits sur les performances
7.3.3 Exprience 3 : Impact du nombre de requêtes et du nombre de prdicats de slection sur les performance
8.1 Conclusion
8.2 Perspectives
9 Annexes
9.1 Annexe A
9.1.1 Scripts SQL du schma de l’entrepôt de donnes du Benchmark APB-1
9.1.2 Charge de requêtes
9.1.3 Réécriture des requêtes après la fragmentation horizontale : Exemple
9.2 Annexe B
9.2.1 Scripts SQL des fragments horizontaux
9.2.1.1 Fragments horizontaux générés par les prédicats de fragmentation
9.2.1.2 Fragment horizontal des tuples dupliqués FHD
9.2.1.3 Fragment horizontal complmentaire FHC
9.2.2 Schma de fragmentation horizontale