Titre :	Vers une approche incrémentale pour la fragmentation horizontale dans les entrepôts de données relationnels
Type de document :	texte imprimé
Auteurs :	Mansouri,zakaria ; TOUMI, Lyazid, Directeur de thèse
Editeur :	Setif:UFA
Année de publication :	2016
Importance :	1 vol (96f.)
Format :	29 cm
Langues :	Français (fre)
Catégories :	Thèses & Mémoires:Informatique
Mots-clés :	Réseaux Systèmes Distribués entrepot de données conception physique fragmentation horizontal sélection incrémentale algorithme d'optimisation
Index. décimale :	004 Informatique
Résumé :	Résumé De nos jours, les entrepôts de données stockent des Zeta-octets de données. Les requêtes décisionnelles définies sur les entrepôts de données sont généralement coûteuses en temps d'exécution. Plusieurs techniques sont utilisées pour l'optimisation de ces requêtes dans les entrepôts de données, tels que les index, la fragmentation et les vues matérialisées. Ici, nous nous concentrons sur le problème de la fragmentation horizontale. Plusieurs approches ont été proposées pour résoudre le problème de fragmentation horizontale dans les entrepôts de données, y compris des algorithmes de classification et des algorithmes génétiques à l'aide d'un petit ensemble de charge de requêtes. Nous présentons une nouvelle approche basée sur la sélection incrémentale multi-objective pour résoudre le problème de fragmentation horizontale dans les entrepôts de données à l'aide d'une charge de requêtes. Tout d'abord, nous effectuons une analyse incrémentale pour l'extraction des nouveaux prédicats. Puis, nous utilisons un algorithme d’optimisation appelé Non-dominated Sorting Genetic Algorithm II (NSGAII) pour la sélection du meilleur schéma de fragmentation. Plusieurs expériences ont été réalisées pour démontrer l'efficacité de notre approche, les résultats obtenues sont comparés aux meilleures approches connues jusqu'à présent en état de l’art: l'approche basée sur la classification, l'approche basée sur l'algorithme génétique ainsi que l'approche basée sur l'algorithme génétique incrémentale. L'approche proposée est jugée plus efficace que les autres approches pour résoudre le problème de fragmentation horizontale dérivée des entrepôts de données.
Note de contenu :	Table des matières Table des figures............................................................................................................. VIII Table des tableaux .............................................................................................................IX Résumé................................................................................................................... 10 Introduction Générale....................................................................................................... 11 Chapitre 1 : Entrepôt de donnés : Architecture et Conception .................................... 12 Introduction....................................................................................................................... 13 1. Architecture de l'entrepôt de données........................................................................... 14 1.1. Pourquoi les entrepôts de données sont séparés des bases de données opérationnelles?.................................... 15 1.2. Modélisation de l'entrepôt de données ..................................................................... 15 1.2.1. Types des systèmes OLAP ................................................................................. 16 2. Conception de l'entrepôt de données............................................................................. 16 2.1. Conception logique................................................................................................... 16 2.1.1. Schéma en étoile................................................................................................ 17 2.1.2. Schéma en flocon de neige ................................................................................ 17 2.1.3. Schéma en constellation .................................................................................... 18 2.2. Conception physique ................................................................................................ 18 3. Techniques d’optimisation de la conception physique ................................................. 19 3.1. Techniques redondantes ........................................................................................... 20 3.1.1. Vues matérialisées............................................................................................. 20 3.1.2. Index .................................................................................................................. 20 3.1.3. Fragmentation verticale ..................................................................................... 21 3.2. Techniques non redondantes .................................................................................... 21 3.2.1. Fragmentation horizontale................................................................................. 21 3.2.2. Traitement parallèle........................................................................................... 22 3.3. Fragmentation mixte (hybride) ............................................................................. 23 Conclusion......................................................................................................................... 24 Chapitre 2 : Fragmentation horizontale et problème de sélection................................ 25 Introduction…………………………………………………………………………….26 1. Fragmentation horizontale ............................................................................................ 27 1.1. Avantages de la fragmentation horizontale .............................................................. 27 1.1.1. Fragmenter pour améliorer la performance ....................................................... 27 1.1.2. Fragmenter pour améliorer la disponibilité ....................................................... 27 1.1.3. Fragmenter pour faciliter la gestion................................................................... 27 1.2. Approches de la fragmentation horizontale.............................................................. 28 1.2.1. Approche basé sur les prédicats......................................................................... 28 1.2.2. Approche basé sur l’affinité .............................................................................. 28 1.2.3. Approche basé sur un modèle de coût............................................................... 28 1.2.4. Approche basé sur le data mining...................................................................... 28 1.2.5. Approche basé sur un coût avec contrainte ....................................................... 29 1.3. Fragmentation primaire et dérivée............................................................................ 29 1.4. Modes de la fragmentation horizontale .................................................................... 30 1.4.1. Mode Simple ..................................................................................................... 30 1.4.2. Mode Composé.................................................................................................. 31 1.5. Démarche de la fragmentation horizontale............................................................... 31 1.5.1. Extraction des prédicats de sélection................................................................. 32 1.5.2. Découpage du domaine de chaque attribut en sous-domaines................... 32 1.5.3. La sélection d’un schéma de fragmentation ...................................................... 32 1.5.4. La Fragmentation de l’ED................................................................................. 33 1.6. Limites de la fragmentation horizontale................................................................... 33 2. Problème de sélection d’un schéma de fragmentation.................................................. 34 Conclusion .......................................................................................... 37 Chapitre 3 : Sélection d’un schéma de fragmentation................................................... 38 Introduction....................................................................................................................... 40 1. Préparation de la sélection ............................................................................................ 40 1.1. Analyse statique........................................................................................................ 40 1.1.1. Analyse de l’ED et extraction des prédicats de la charge des requêtes............. 40 1.1.2. Codage de la solution ........................................................................................ 41 1.2. Analyse incrémentale ............................................................................................... 41 2. Modèle de coût.............................................................................................................. 42 2.1. Coût sans fragmentation ........................................................................................... 42 2.2. Coût avec fragmentation........................................................................................... 43 2.2.1. Identification des sous-schémas valides............................................................ 44 2.2.2. Exécution de la requête sur chaque sous-schéma valide ................................... 44 2.2.3. Effectuer l’union des résultats........................................................................... 46 3. Méta-heuristiquespourla sélection d’un schéma de fragmentation ................................. 46 3.1. Algorithme de classification..................................................................................... 47 3.1.1. Principe.............................................................................................................. 48 3.1.2. Codage des prédicats de sélection ..................................................................... 48 3.1.3. Classification des prédicats et génération des fragments .................................. 49 3.1.4. Évaluation des fragments avec le modèle de coût............................................. 50 3.2. Algorithme Génétique .............................................................................................. 50 3.2.1. Principe............................................................................................................... 50 3.2.2. Paramètres de dimensionnement ....................................................................... 52 3.2.3. Codage des solutions......................................................................................... 52 3.2.4. Génération de la population initiale.................................................................... 53 3.2.5. Génération de nouvelles populations................................................................. 54 3.2.6. Operateurs génétiques ....................................................................................... 54 3.2.7. Fonction objective ............................................................................................. 56 3.3. Improved Incremental Selection Based on Genetic Algorithms ............................. 56 3.3.1. Différence entre AG et IISGA........................................................................... 57 3.3.2. Nouvelle fonction de pénalité............................................................................ 57 3.4. Non-dominated Sorting Génétique Algorithm II...................................................... 58 3.4.1. Algorithmes multi-objectifs............................................................................... 58 3.4.2. Différence entre NSGAII et IISGA................................................................... 58 Conclusion......................................................................................................................... 60 Chapitre 4 : Expérimentation et validation .................................................................... 61 Introduction....................................................................................................................... 62 1. Entrepôt de données...................................................................................................... 63 2. Implémentation de l’APB-1 .......................................................................................... 64 2.1. Chargement de l’APB-1 ........................................................................................... 64 2.2. Types de requêtes prises en compte .......................................................................... 65 3. Évaluation de performance des quatre algorithmes ...................................................... 65 3.1. Coût d’exécution ...................................................................................................... 66 3.2. Temps d’exécution ................................................................................................... 69 3.3. Nombre d’évaluations .............................................................................................. 71 3.4. Coût de maintenance ................................................................................................ 73 4. Récapitulation ............................................................................................................... 75 Conclusion......................................................................................................................... 76 Conclusion et perspective.................................................................................................. 77 Bibliographie...................................................................................................................... 78 Annexe ...................................................................................................................... 81
Côte titre :	MAI/0126
En ligne :	https://drive.google.com/file/d/1nqPb-Y-tX24VCOSbejUAXhiRd3KFZE6r/view?usp=shari [...]
Format de la ressource électronique :	pdf

Vers une approche incrémentale pour la fragmentation horizontale dans les entrepôts de données relationnels [texte imprimé] / Mansouri,zakaria ; TOUMI, Lyazid, Directeur de thèse . - [S.l.] : Setif:UFA, 2016 . - 1 vol (96f.) ; 29 cm.
Langues : Français (fre)

Catégories :	Thèses & Mémoires:Informatique
Mots-clés :	Réseaux Systèmes Distribués entrepot de données conception physique fragmentation horizontal sélection incrémentale algorithme d'optimisation
Index. décimale :	004 Informatique
Résumé :	Résumé De nos jours, les entrepôts de données stockent des Zeta-octets de données. Les requêtes décisionnelles définies sur les entrepôts de données sont généralement coûteuses en temps d'exécution. Plusieurs techniques sont utilisées pour l'optimisation de ces requêtes dans les entrepôts de données, tels que les index, la fragmentation et les vues matérialisées. Ici, nous nous concentrons sur le problème de la fragmentation horizontale. Plusieurs approches ont été proposées pour résoudre le problème de fragmentation horizontale dans les entrepôts de données, y compris des algorithmes de classification et des algorithmes génétiques à l'aide d'un petit ensemble de charge de requêtes. Nous présentons une nouvelle approche basée sur la sélection incrémentale multi-objective pour résoudre le problème de fragmentation horizontale dans les entrepôts de données à l'aide d'une charge de requêtes. Tout d'abord, nous effectuons une analyse incrémentale pour l'extraction des nouveaux prédicats. Puis, nous utilisons un algorithme d’optimisation appelé Non-dominated Sorting Genetic Algorithm II (NSGAII) pour la sélection du meilleur schéma de fragmentation. Plusieurs expériences ont été réalisées pour démontrer l'efficacité de notre approche, les résultats obtenues sont comparés aux meilleures approches connues jusqu'à présent en état de l’art: l'approche basée sur la classification, l'approche basée sur l'algorithme génétique ainsi que l'approche basée sur l'algorithme génétique incrémentale. L'approche proposée est jugée plus efficace que les autres approches pour résoudre le problème de fragmentation horizontale dérivée des entrepôts de données.
Note de contenu :	Table des matières Table des figures............................................................................................................. VIII Table des tableaux .............................................................................................................IX Résumé................................................................................................................... 10 Introduction Générale....................................................................................................... 11 Chapitre 1 : Entrepôt de donnés : Architecture et Conception .................................... 12 Introduction....................................................................................................................... 13 1. Architecture de l'entrepôt de données........................................................................... 14 1.1. Pourquoi les entrepôts de données sont séparés des bases de données opérationnelles?.................................... 15 1.2. Modélisation de l'entrepôt de données ..................................................................... 15 1.2.1. Types des systèmes OLAP ................................................................................. 16 2. Conception de l'entrepôt de données............................................................................. 16 2.1. Conception logique................................................................................................... 16 2.1.1. Schéma en étoile................................................................................................ 17 2.1.2. Schéma en flocon de neige ................................................................................ 17 2.1.3. Schéma en constellation .................................................................................... 18 2.2. Conception physique ................................................................................................ 18 3. Techniques d’optimisation de la conception physique ................................................. 19 3.1. Techniques redondantes ........................................................................................... 20 3.1.1. Vues matérialisées............................................................................................. 20 3.1.2. Index .................................................................................................................. 20 3.1.3. Fragmentation verticale ..................................................................................... 21 3.2. Techniques non redondantes .................................................................................... 21 3.2.1. Fragmentation horizontale................................................................................. 21 3.2.2. Traitement parallèle........................................................................................... 22 3.3. Fragmentation mixte (hybride) ............................................................................. 23 Conclusion......................................................................................................................... 24 Chapitre 2 : Fragmentation horizontale et problème de sélection................................ 25 Introduction…………………………………………………………………………….26 1. Fragmentation horizontale ............................................................................................ 27 1.1. Avantages de la fragmentation horizontale .............................................................. 27 1.1.1. Fragmenter pour améliorer la performance ....................................................... 27 1.1.2. Fragmenter pour améliorer la disponibilité ....................................................... 27 1.1.3. Fragmenter pour faciliter la gestion................................................................... 27 1.2. Approches de la fragmentation horizontale.............................................................. 28 1.2.1. Approche basé sur les prédicats......................................................................... 28 1.2.2. Approche basé sur l’affinité .............................................................................. 28 1.2.3. Approche basé sur un modèle de coût............................................................... 28 1.2.4. Approche basé sur le data mining...................................................................... 28 1.2.5. Approche basé sur un coût avec contrainte ....................................................... 29 1.3. Fragmentation primaire et dérivée............................................................................ 29 1.4. Modes de la fragmentation horizontale .................................................................... 30 1.4.1. Mode Simple ..................................................................................................... 30 1.4.2. Mode Composé.................................................................................................. 31 1.5. Démarche de la fragmentation horizontale............................................................... 31 1.5.1. Extraction des prédicats de sélection................................................................. 32 1.5.2. Découpage du domaine de chaque attribut en sous-domaines................... 32 1.5.3. La sélection d’un schéma de fragmentation ...................................................... 32 1.5.4. La Fragmentation de l’ED................................................................................. 33 1.6. Limites de la fragmentation horizontale................................................................... 33 2. Problème de sélection d’un schéma de fragmentation.................................................. 34 Conclusion .......................................................................................... 37 Chapitre 3 : Sélection d’un schéma de fragmentation................................................... 38 Introduction....................................................................................................................... 40 1. Préparation de la sélection ............................................................................................ 40 1.1. Analyse statique........................................................................................................ 40 1.1.1. Analyse de l’ED et extraction des prédicats de la charge des requêtes............. 40 1.1.2. Codage de la solution ........................................................................................ 41 1.2. Analyse incrémentale ............................................................................................... 41 2. Modèle de coût.............................................................................................................. 42 2.1. Coût sans fragmentation ........................................................................................... 42 2.2. Coût avec fragmentation........................................................................................... 43 2.2.1. Identification des sous-schémas valides............................................................ 44 2.2.2. Exécution de la requête sur chaque sous-schéma valide ................................... 44 2.2.3. Effectuer l’union des résultats........................................................................... 46 3. Méta-heuristiquespourla sélection d’un schéma de fragmentation ................................. 46 3.1. Algorithme de classification..................................................................................... 47 3.1.1. Principe.............................................................................................................. 48 3.1.2. Codage des prédicats de sélection ..................................................................... 48 3.1.3. Classification des prédicats et génération des fragments .................................. 49 3.1.4. Évaluation des fragments avec le modèle de coût............................................. 50 3.2. Algorithme Génétique .............................................................................................. 50 3.2.1. Principe............................................................................................................... 50 3.2.2. Paramètres de dimensionnement ....................................................................... 52 3.2.3. Codage des solutions......................................................................................... 52 3.2.4. Génération de la population initiale.................................................................... 53 3.2.5. Génération de nouvelles populations................................................................. 54 3.2.6. Operateurs génétiques ....................................................................................... 54 3.2.7. Fonction objective ............................................................................................. 56 3.3. Improved Incremental Selection Based on Genetic Algorithms ............................. 56 3.3.1. Différence entre AG et IISGA........................................................................... 57 3.3.2. Nouvelle fonction de pénalité............................................................................ 57 3.4. Non-dominated Sorting Génétique Algorithm II...................................................... 58 3.4.1. Algorithmes multi-objectifs............................................................................... 58 3.4.2. Différence entre NSGAII et IISGA................................................................... 58 Conclusion......................................................................................................................... 60 Chapitre 4 : Expérimentation et validation .................................................................... 61 Introduction....................................................................................................................... 62 1. Entrepôt de données...................................................................................................... 63 2. Implémentation de l’APB-1 .......................................................................................... 64 2.1. Chargement de l’APB-1 ........................................................................................... 64 2.2. Types de requêtes prises en compte .......................................................................... 65 3. Évaluation de performance des quatre algorithmes ...................................................... 65 3.1. Coût d’exécution ...................................................................................................... 66 3.2. Temps d’exécution ................................................................................................... 69 3.3. Nombre d’évaluations .............................................................................................. 71 3.4. Coût de maintenance ................................................................................................ 73 4. Récapitulation ............................................................................................................... 75 Conclusion......................................................................................................................... 76 Conclusion et perspective.................................................................................................. 77 Bibliographie...................................................................................................................... 78 Annexe ...................................................................................................................... 81
Côte titre :	MAI/0126
En ligne :	https://drive.google.com/file/d/1nqPb-Y-tX24VCOSbejUAXhiRd3KFZE6r/view?usp=shari [...]
Format de la ressource électronique :	pdf