Titre :	Un algorithme évolutionnaire pour la sélection des vues matérialisées dans l’entrepôt de données
Type de document :	texte imprimé
Auteurs :	KARA, Sara ; SEMCHEDINE, FOUZI, Directeur de thèse
Importance :	1 vol (51f.)
Format :	29 cm
Langues :	Français (fre)
Catégories :	Thèses & Mémoires:Informatique
Mots-clés :	vue matérialisée, entrepôt de données, les algorithmes d’optimisation, méta-heuristiques, requête OLAP.
Index. décimale :	004 Informatique
Résumé :	Résumé L’importance du volume des entrepôts de données rend les requêtes très lourdes. Des améliorations sur les techniques d’optimisation des requêtes ont été exigés afin d’accélérer l’exécution de ces requêtes. Parmi ces techniques : les vues matérialisées. Cette technique a connu un important problème d’optimisation ; il s’agit du problème de sélection des vues. La matérialisation de tous les vues accélère l’exécution de n’importe quelle requête mais nécessite un coût considérable pour les maintenir. Par contre, la maintenance des vues rend les résultats des requêtes plus bénéfiques pour les décideurs. Ces contraintes rendent la sélection des vues un problème Non Polynomial-difficile. Ce type de problème n’a pas une solution exacte, ce qui fait appel à des heuristiques pour le résoudre. Nous avons proposé dans ce mémoire une solution par l’adaptation de la recherche taboue pour résoudre le problème de sélection des vues afin de satisfaire les différentes contraintes d’optimisation des requêtes.
Note de contenu :	Table des matières Introduction générale 1 Contexte du travail 1 Plan du mémoire 2 Chapitre 1 : Les entrepôts de données et les systèmes décisionnels 1. Introduction 3 2. Définition d’un entrepôt de données 3 3. Caractéristiques 3 4. Les systèmes OLTP versus les systèmes OLAP 4 5. Les entrepôts de données et les systèmes décisionnels 5 5.1. Extraction 5 5.2. Transformation 6 5.3. Chargement 6 6. L’architecture d’un entrepôt de données 7 6.1. Données de détail courantes 7 6.2. Données de détail anciennes 7 6.3. Données agrégés 7 6.4. Métadonnées 7 7. La modélisation multidimensionnelle 8 7.1. Les concepts de base 9 7.1.1. Les faits 9 7.1.2. Les dimensions 9 7.1.3. La hiérarchie 9 7.2. Les schémas relationnels 9 7.2.1. Le modèle en étoile 9 7.2.2. Le modèle en flocon de neige 10 7.2.3. Le modèle en constellation 11 7.3. Le schéma multidimensionnel 12 8. La modélisation logique 12 8.1. ROLAP 13 8.2. MOLAP 13 9. La manipulation des données multidimensionnelles 14 9.1. Opérations classiques 14 9.2. Opérations agissant sur la structure 14 9.2.1. La rotation 14 9.2.2. La permutation 14 9.2.3. La division 15 9.2.4. L’emboitement 15 9.3. Opérations agissant sur la granularité 15 9.3.1. Le forage vers le haut 15 9.3.2. Le forage vers le bas 15 10. Conclusion 15 Chapitre 2 : La sélection des vues matérialisées dans l’entrepôt de 1. Introduction 16 2. Les vues matérialisées 16 2.1. Le problème de sélection des vues matérialisées PSV 17 2.1.1. Matérialiser toutes les vues 17 2.1.2. Ne matérialiser aucune vue 17 2.1.3. Matérialiser une partie de cube de données 17 2.2. La maintenance des vues matérialisées 18 3. Le modèle de coût 19 3.1. Le coût d’évaluation des requêtes 19 3.2. Le coût de maintenance des vues 19 3.3. Le coût opérationnel 19 4. Les contraintes 20 4.1. Les contraintes orientées systèmes 20 4.1.1. La contrainte d’espace 20 4.1.2. La contrainte de temps de maintenance 20 4.2. Les contraintes orientées utilisateurs 20 4.2.1. La contrainte d’exactitude de données de réponse 20 4.2.2. La contrainte de temps de réponse à la requête 21 5. La représentation de l’espace de recherche 21 5.1. L’algèbre relationnel 21 5.2. Le graphe orienté acyclique 22 5.3. Le graphe AND/OR 22 5.4. Le treillis 23 6. Les algorithmes pour la résolution du problème PSV 24 6.1. Les algorithmes sans contraintes 24 6.1.1. L’algorithme de Yang et al. 24 6.1.2. L’algorithme de Hrong et al. 25 6.1.3. L’algorithme de Dhote et al. 27 6.2. Les algorithmes avec contraintes 27 6.2.1. L’algorithme de Panos et al. 27 6.2.2. L’algorithme de Yang.Jal. 28 6.2.3. L’algorithme d’Ashedevi et al. 29 6.2.4. L’algorithme de Zhou et al. 29 6.2.5. L’algorithme de Choudhari et al. 30 6.2.6. L’algorithme d’Ashedevi et al. 29 7. Conclusion 32 Chapitre 3 : Proposition et conception d’une solution pour la sélection des vues matérialisées 1. Introduction 34 2. La recherche tabou 34 2.1. Notion de voisinage 34 2.2. L’optimum local 35 2.3. L’optimum global 35 2.4. Fonctionnement de l’algorithme tabou 35 2.5. Les améliorations possibles 37 2.5.1. L’intensification 37 2.5.2. La diversification 37 3. L’optimisationmultiobjectif 38 3.1. Formalisation du problème d’optimisation multiobjectif 38 3.2. Notion de dominance de Pareto (optimalité) 38 3.3. Métaheuristiques pour les problèmes multiobjectif 39 4. Conception de la solution 40 4.1. L’entrepôt de données multidimensionnels 40 4.2. Le treillis multidimensionnel 41 4.3. Le modèle de cout 41 4.4. La résolution avec la recherche tabou 42 4.4.1. La génération du treillis 42 4.4.2. La solution initiale 42 4.4.3. La génération de l’ensemble de voisinage 43 5. Conclusion 43 Chapitre 4 : Validation de la solution proposée 1. Introduction 44 2. Description de l’outil de simulation 44 3. Le modèle TPC-D benchmark 44 4. La résolution du problème de sélection des vues matérialisées 47 4.1. La résolution par l’algorithme BPUS 47 4.2. La résolution par la méthode de recherche taboue 47 4.3. Résultat de la simulation 48 5. Conclusion 49 Conclusion générale 50
Côte titre :	MAI/0084

Un algorithme évolutionnaire pour la sélection des vues matérialisées dans l’entrepôt de données [texte imprimé] / KARA, Sara ; SEMCHEDINE, FOUZI, Directeur de thèse . - [s.d.] . - 1 vol (51f.) ; 29 cm.
Langues : Français (fre)

Catégories :	Thèses & Mémoires:Informatique
Mots-clés :	vue matérialisée, entrepôt de données, les algorithmes d’optimisation, méta-heuristiques, requête OLAP.
Index. décimale :	004 Informatique
Résumé :	Résumé L’importance du volume des entrepôts de données rend les requêtes très lourdes. Des améliorations sur les techniques d’optimisation des requêtes ont été exigés afin d’accélérer l’exécution de ces requêtes. Parmi ces techniques : les vues matérialisées. Cette technique a connu un important problème d’optimisation ; il s’agit du problème de sélection des vues. La matérialisation de tous les vues accélère l’exécution de n’importe quelle requête mais nécessite un coût considérable pour les maintenir. Par contre, la maintenance des vues rend les résultats des requêtes plus bénéfiques pour les décideurs. Ces contraintes rendent la sélection des vues un problème Non Polynomial-difficile. Ce type de problème n’a pas une solution exacte, ce qui fait appel à des heuristiques pour le résoudre. Nous avons proposé dans ce mémoire une solution par l’adaptation de la recherche taboue pour résoudre le problème de sélection des vues afin de satisfaire les différentes contraintes d’optimisation des requêtes.
Note de contenu :	Table des matières Introduction générale 1 Contexte du travail 1 Plan du mémoire 2 Chapitre 1 : Les entrepôts de données et les systèmes décisionnels 1. Introduction 3 2. Définition d’un entrepôt de données 3 3. Caractéristiques 3 4. Les systèmes OLTP versus les systèmes OLAP 4 5. Les entrepôts de données et les systèmes décisionnels 5 5.1. Extraction 5 5.2. Transformation 6 5.3. Chargement 6 6. L’architecture d’un entrepôt de données 7 6.1. Données de détail courantes 7 6.2. Données de détail anciennes 7 6.3. Données agrégés 7 6.4. Métadonnées 7 7. La modélisation multidimensionnelle 8 7.1. Les concepts de base 9 7.1.1. Les faits 9 7.1.2. Les dimensions 9 7.1.3. La hiérarchie 9 7.2. Les schémas relationnels 9 7.2.1. Le modèle en étoile 9 7.2.2. Le modèle en flocon de neige 10 7.2.3. Le modèle en constellation 11 7.3. Le schéma multidimensionnel 12 8. La modélisation logique 12 8.1. ROLAP 13 8.2. MOLAP 13 9. La manipulation des données multidimensionnelles 14 9.1. Opérations classiques 14 9.2. Opérations agissant sur la structure 14 9.2.1. La rotation 14 9.2.2. La permutation 14 9.2.3. La division 15 9.2.4. L’emboitement 15 9.3. Opérations agissant sur la granularité 15 9.3.1. Le forage vers le haut 15 9.3.2. Le forage vers le bas 15 10. Conclusion 15 Chapitre 2 : La sélection des vues matérialisées dans l’entrepôt de 1. Introduction 16 2. Les vues matérialisées 16 2.1. Le problème de sélection des vues matérialisées PSV 17 2.1.1. Matérialiser toutes les vues 17 2.1.2. Ne matérialiser aucune vue 17 2.1.3. Matérialiser une partie de cube de données 17 2.2. La maintenance des vues matérialisées 18 3. Le modèle de coût 19 3.1. Le coût d’évaluation des requêtes 19 3.2. Le coût de maintenance des vues 19 3.3. Le coût opérationnel 19 4. Les contraintes 20 4.1. Les contraintes orientées systèmes 20 4.1.1. La contrainte d’espace 20 4.1.2. La contrainte de temps de maintenance 20 4.2. Les contraintes orientées utilisateurs 20 4.2.1. La contrainte d’exactitude de données de réponse 20 4.2.2. La contrainte de temps de réponse à la requête 21 5. La représentation de l’espace de recherche 21 5.1. L’algèbre relationnel 21 5.2. Le graphe orienté acyclique 22 5.3. Le graphe AND/OR 22 5.4. Le treillis 23 6. Les algorithmes pour la résolution du problème PSV 24 6.1. Les algorithmes sans contraintes 24 6.1.1. L’algorithme de Yang et al. 24 6.1.2. L’algorithme de Hrong et al. 25 6.1.3. L’algorithme de Dhote et al. 27 6.2. Les algorithmes avec contraintes 27 6.2.1. L’algorithme de Panos et al. 27 6.2.2. L’algorithme de Yang.Jal. 28 6.2.3. L’algorithme d’Ashedevi et al. 29 6.2.4. L’algorithme de Zhou et al. 29 6.2.5. L’algorithme de Choudhari et al. 30 6.2.6. L’algorithme d’Ashedevi et al. 29 7. Conclusion 32 Chapitre 3 : Proposition et conception d’une solution pour la sélection des vues matérialisées 1. Introduction 34 2. La recherche tabou 34 2.1. Notion de voisinage 34 2.2. L’optimum local 35 2.3. L’optimum global 35 2.4. Fonctionnement de l’algorithme tabou 35 2.5. Les améliorations possibles 37 2.5.1. L’intensification 37 2.5.2. La diversification 37 3. L’optimisationmultiobjectif 38 3.1. Formalisation du problème d’optimisation multiobjectif 38 3.2. Notion de dominance de Pareto (optimalité) 38 3.3. Métaheuristiques pour les problèmes multiobjectif 39 4. Conception de la solution 40 4.1. L’entrepôt de données multidimensionnels 40 4.2. Le treillis multidimensionnel 41 4.3. Le modèle de cout 41 4.4. La résolution avec la recherche tabou 42 4.4.1. La génération du treillis 42 4.4.2. La solution initiale 42 4.4.3. La génération de l’ensemble de voisinage 43 5. Conclusion 43 Chapitre 4 : Validation de la solution proposée 1. Introduction 44 2. Description de l’outil de simulation 44 3. Le modèle TPC-D benchmark 44 4. La résolution du problème de sélection des vues matérialisées 47 4.1. La résolution par l’algorithme BPUS 47 4.2. La résolution par la méthode de recherche taboue 47 4.3. Résultat de la simulation 48 5. Conclusion 49 Conclusion générale 50
Côte titre :	MAI/0084