Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE MINISTERE DE L’ENSEIGNEMENT SUP

REPUBLIQUE ALGERIENNE DEMOCRATIQUE ET POPULAIRE MINISTERE DE L’ENSEIGNEMENT SUPERIEUR ET DE LA RECHERCHE SCIENTIFIQUE UNIVERSITE MOHAMED BOUDIAF - M’SILA FACULTE DES MATHEMATIQUES ET DE L’INFORMATIQUE DÉPARTEMENT D’INFORMATIQUE MEMOIRE de fin d’étude Présenté pour l’obtention du diplôme de MASTER Domaine : Mathématiques et Informatique Filière : Informatique Spécialité : Systèmes d’Informations Avancés Par: BARKA Ahlem SUJET Méthodes bio-inspirées pour la fragmentation d’entrepôt de données : Etude et évaluation Soutenu publiquement le : 01 / 06/2016 devant le jury composé de : Dr. H. Belouadeh Université de M’sila Président Dr. C. Lamiche Université de M’sila Rapporteur A. Guerna Université de M’sila Examinateur Promotion : 2015/2016 Remerciements Mes remerciements sont d’abord destinés à mon promoteur Dr. C. Lamiche, enseignant au département d’informatique de l’Université de M’sila, pour avoir accepté d’encadrer ce travail. Je tiens également à remercier tous les Membres du jury, qui ont accepté D’examiner ce travail. Je remercie tous les enseignant qui Nous ont orientés pendant tout Notre parcours. A tous les gens qui ont aidés du pré et du loin pour réaliser ce modeste travail. Merci à tous et à toutes Table des matières -Liste des figures………………………………………………………………i -Liste des Tables………………………………………………………………iii -Liste des Algorithmes ……………………………………………………… iv -Introduction générale ………………………………………………………………… 1 CHAPITRE I : Entrepôts de données : Concepts Fondamentaux. 1. Introduction……………………………………………………………………….… 2 2. L’entrepôt de donnée (ED)……………………………………………………….… 2 2.1.Définition………………………………………………………………………. 2 2.2.Caractéristiques………………………………………………………………… 2 2.3.Les types de données…………………………………………………...……...… 3 2.4.L’architecture d’entrepôt de données………………………………………… 4 2.4.1. Sources de données…………………………………………………….. 5 2.4.2. Processus Extract, Tranform, Load (ETL)…………………….……….. 5 2.4.3. Les magasine…………………………………………………..………..… 5 2.4.4. Les applications clients………………….…………………………………6 3. Les modèles des entrepôts de données……………………………….…………..….7 3.1.La modélisation conceptuelle……………………………………..………………. 7 3.1.1. Concept de fait, de dimension et de hiérarchie………….…………………7 3.1.2. Modèles en étoile, en flocon et en constellation….………...………….. 7 3.1.2.1. Modèle en étoile……………………….…………………..…………..7 3.1.2.2. Modèle en flocons………………….…………………..………………8 3.1.2.3. Modèle en constellation………….………………….…………………9 3.2.Modélisation logique……………………..………………..…………………….. 9 3.2.1. les modèles multidimensionnels…...…………………….………….. 9 3.2.1.1. Modèle R-OLAP………...……………………..……………………...10 3.2.1.2. Modèle M-OLAP……………………………………………………. 11 3.2.1.3. Model H-OLAP……………………………………………………… 11 3.3.La conception physique des entrepôts de données…….………………………… 11 4. Choix des techniques d’optimisation……………………………………..………. 11 4.1.Les techniques redondantes…………………………………………………….. 12 4.1.1. Les indexe………………………………………………...……………. 12 4.1.1.1. Index Bitmap……………………………………………………….. 12 4.1.1.2. Index B-Arbre………………………………………..……………. 13 4.1.1.3. Les index de jointure binaires….………………………………….. 14 4.1.2. La Fragmentation verticale……………….…………………………… 14 4.1.3. Les vues matérialisés………………………..………………………….. 15 4.2.Les techniques non redondantes……………………..……………………….. 16 4.2.1. La fragmentation horizontale……………….…………………………. 16 4.2.2. La fragmentation mixte……………………..………………………….. 17 5. Conclusion…….……………………………………………………….. CHAPITRE II : La fragmentation horizontale dans les entrepôts de données 1. Introduction……………………………………………………………………….18 2. La fragmentation horizontale FH…………………………………………………... 18 2.1.Fragmentation primaire…………………………………………………………. 18 2.2.Fragmentation dérivée………………………………………………………….. 19 2.3.Les avantages de la fragmentation horizontale……………………………….. 20 3. Méthodologie de fragmentation horizontale dans les entrepôts de données…… 20 4. Le Procédure de FH……………………..……..……………………….……….… 21 4.1.Module de gestion des requêtes …..…………………………………….………..22 4.2.Règles de correction de la fragmentation horizontale………..……………...……22 5. Le problème de sélection d’un schéma de fragmentation……………………… 22 5.1.Travaux de recherche sur le problème de fragmentation……….…...………........23 5.1.1. Travaux de DATTA et AL. (1999)…………………….………………. 23 5.1.2. Travaux de Wu et Buchmaan (1997)………………………………….. 23 5.1.3. Travaux de NOAMAN & BARKER (1999)……………………………. 23 5.1.4. Travaux de Bellatreche (2000)…………………………………………. 23 6. Algorithmes de sélection d’un schéma de FH…………………………………….. 23 6.1.Algorithmes basées sur les prédicats…………………………………………… 24 6.2.Algorithmes basés sur l’affinité…….….……………………………………… 24 6.3.Algorithmes à base de modèle de coût………………………………………… 27 7. Conclusion……………….……………………………………………………….. 28 CHAPITRE III : Métaheuristiques et fragmentation d’entrepôt de données. 1. Introduction…………………………………………………………………………. 29 2. Description du problème…………………………………………………………… 29 3. Les Algorithmes génétiques………………………………………………………. 30 3.1. Définition des algorithmes génétique………...……………………...……… 30 3.2. Principe de base…………………………………………………………….. 30 3.2.1. Le codage des individus………………………………………………… 32 3.2.2. L’évaluation d’un individu…………………………………………...... 32 3.2.3. Les opérateurs génétiques……………………………………………… 33 3.2.3.1. L'opérateur de sélection…………………………………….…….33 3.2.3.2. L'opérateur de croisement ou crossover………..………………...34 3.2.3.3. L'opérateur de mutation……………………………..…….……...35 4. Les recuits simulés…………………………………………………………………. 35 5. Application de GA au Problème de sélection de schéma de FH………………... 36 5.1. Processus génétique de la fragmentation horizontale………….……………… 36 5.1.1. Codage adopté…………………..…………………………………….36 5.1.2. Génération de la population initiale…………………………………. 37 5.1.3. Sélection des individus……….…………………….…………………37 5.1.4. Croisements de individus……………………………...………………37 5.1.5. Mutation……………………………………………………………... 38 5.1.6. Fonction d’évaluation : fitness………………………………………. 38 5.1.7. Critère d’arrêt………………………………………………………… 38 6. L’application de recuit simulé RS sur la solution de GA……………….…….…. 40 7. Conclusion………………………………………………………………………….. 41 CHAPITRE IV : Réalisation et expérimentation 1. Introduction…………………………………………………………………….…. 42 2. Les outils de développement…………………….…………………………………. 42 2.1 Microsoft Visual Studio………………………………………………………… 42 2.1.1 Microsoft Visual Studio 2012…………………………………………… 42 2.1.2 Langage de programmation C# ………………………………………... 43 2.2 Oracle…………………………………………………………………………… .43 2.2.1 Oracle Développer………………………………………………………..44 3. Implémentation ……………………………………………………………………. 44 3.1 L’entrepôt de données (Entrepôt de banc d’essai Benchmark)………………... 44 3.1.1. Types de requêtes prises en compte …………………………………… 45 3.1.2. Vecteur de sélectivité …………………………………………………….46 3.2. Implémentation de solution …………………...…………………………………46 3.2.1. Procédure de solution ................................................................................46 3.2.2. L’architecture de l’application………………………………………...….47 3.2.3. les cas d’utilisation de l’interface ……………………...…………………47 4. Présentation graphique ……………………………………………………………… 48 5. Résultats obtenus……………………………………………………………………… 49 5.1 Analyse des résultats……...…………………………………………………..…… 51 6. Conclusion…………………………………………………………………………….. 51 -Conclusion général…………………………………………………………………….. 52 - Bibliographique ....……..………………………………………………………… 53 -Annexes………………………………………………………………………………… 58 i Liste des figures Figure I.1 : Architecture d’un entrepôt de données. Figure I.2 : Magasins de données (datamarts). Figure I.3 : Schémas en étoile. Figure I.4 : Schémas en flocons. Figure I.5 : exemple d’un cube de données. Figure I.6 : Table multidimensionnelle (Visualisation d’une ‘tranche’ du cube). Figure I.7 : Classification des techniques d’optimisation. Figure I.8: Index Bitmap. Figure I.9: Index B-Arbre. Figure I.10 : Fragmentation verticale. Figure I.11 : Le processus de sélection des vues matérialisées. Figure I.12: Fragmentation Horizontale. Figure I.13 : fragmentation mixte. Figure II.1 : Exemple d’une fragmentation primaire et dérivée. Figure II.2 : Approche basée sur les prédicats. Figure II.3 : Approche basée sur les affinités. Figure II.4 : Approche basée sur un modèle de coût. Figure III.1 : Les cinq niveaux d’organisation d’un algorithme génétique. Figure III.2 : Exemple de croisement à un point. Figure III.3 : Exemple de croisement à deux points. Figure III.4 : Exemple une mutation. Figure III.5 : Exemple de codage. Figure III.6 : Exemple de croisement Figure III.7: Exemple de Mutation. Figure IV.1 : Visual Studio 2012. Figure IV.2 : Oracle. Figure IV.3 : Oracle Développer. Figure IV.4 : Schéma de l’entrepôt utilisé APB benchmark Figure IV.5 : Procédure de travail. Figure IV.6 : Architecture de l’application Figure IV.7 : Diagramme de cas d’utilisation. ii Figure IV.8 : Visualisation d’entrepôt de données. Figure IV.9 : Analyse des requêtes. Figure IV.10 : Fenêtre d’application de GA et GA+RS. Figure IV.11 : Exemple d’application de l’AG et l’AG+RS. Figure IV.12 : Évaluation de coûts d’exécutions en fonction de nombre d’itérations. Figure IV.13 : Évaluation de taux d’amélioration en fonction de nombre d’itérations. iii Liste des Tables Table I.1 : Base de données vs Entrepôt de données. Table I.2 : Comparaison entre OLTP et OLAP. Table II.1 : Matrice d'usage des sous-domaines de l'attribut Ville. Table II.2 : Matrice d'affinité des sous-domaines de l'attribut Ville. Table IV.1 : Taille des tables. Table IV.2 : Résultats d’exécutions d’AG et AG + RS avec le taux d’amélioration. iv Liste des Algorithmes Algorithme III.1 : Algorithme génétique générique. Algorithme III.2 : Algorithme génétique Recuit Simulé. Algorithme III.3 : Algorithme génétique pour la sélection d’un schéma de FH. Algorithme III.4 : Algorithme Recuit Simulé. Introduction générale 1 Introduction générale De nos jours, les entrepôts décisionnels d’entreprise constituent des ressources critiques. Avec l’évolution des exigences métiers, ils doivent gérer des volumes et des vitesses de données sans cesse grandissants. Les entrepôts sont construits autour d’une table de faits, souvent très volumineuse, qui peut atteindre plusieurs téraoctets, entourée de plusieurs tables de dimensions qui contiennent les axes d’analyse relativement aux indicateurs ou mesures contenus dans la table des faits. Ces derniers sont accédés par des requêtes décisionnelles complexes caractérisées par de multiples opérations de sélection, de jointure et d’agrégation. Pour optimiser ces requêtes, l’administrateur est amené à effectuer une tâche importante dans la conception physique, durant cette phase l’administrateur choisit un ensemble de techniques d’optimisation à sélectionner. La fragmentation horizontale est une structure non redondante d'optimisation de requêtes OLAP. Dans le cadre de ce mémoire, nous formalisons d'abord le problème de sélection d'un schéma de fragmentation pour un entrepôt de données relationnel comme un problème d'optimisation. Nous proposons ensuite une méthode hybride combinant un algorithme génétique AG et un algorithme de recuit simulé RS. Ce mémoire est organisé de la manière suivante : Chapitre 01 est consacré aux définitions des concepts fondamentaux d’entrepôt de données, aussi aux techniques d’optimisations des requêtes. Le deuxième chapitre présente d’une façon détaillée la technique d’optimisation Fragmentation Horizontale FH dans les entrepôts de données. Et concerne le troisième chapitre nous avons spécifié le problème générale qui on vas le traité, et après l’application des algorithmes génétique et des recuit simulé sur ce problème, Nous présentons aussi dans ce chapitre le modèle de coût utilisé. Dans le quatrième chapitre, nous avons présenté nos résultats de validation sur un banc d’essai APB-1 et un ensemble de 8 requêtes. Enfin, une conclusion rappelle la problématique étudiée ainsi que les résultats obtenus. Cette conclusion nous a permis de lister quelques perspectives de prolongement de nos travaux. CHAPITRE I Entrepôts de données : Concepts Fondamentaux Chapitre I : Entrepôts de données : Concepts Fondamentaux 2 1 Introduction L’entrepôt est le lieu de stockage centralisé d’un extrait des sources. Il historie les données utiles pour la décision. Son organisation doit faciliter la gestion efficace des données et la conservation des évolutions. uploads/Science et Technologie/barka-ahlem.pdf