University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur TOUMI, Lyazid |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Une approche incrémentale pour la fragmentation horizontale des BIGS DATA WAREHOUSE / Djemouai, selma
Titre : Une approche incrémentale pour la fragmentation horizontale des BIGS DATA WAREHOUSE Type de document : texte imprimé Auteurs : Djemouai, selma ; TOUMI, Lyazid, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (97f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Ingénierie de Données
Technologies Web
Entrepôt de données
conception physique
fragmentation horizontale
sélection incrémentale
algorithme d’optimisation
optimisation Multi-objectiveIndex. 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 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 multiobjective 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 l'algorithme génétique et 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 dans les entrepôts de données.Côte titre : MAI/0198 Une approche incrémentale pour la fragmentation horizontale des BIGS DATA WAREHOUSE [texte imprimé] / Djemouai, selma ; TOUMI, Lyazid, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (97f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Ingénierie de Données
Technologies Web
Entrepôt de données
conception physique
fragmentation horizontale
sélection incrémentale
algorithme d’optimisation
optimisation Multi-objectiveIndex. 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 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 multiobjective 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 l'algorithme génétique et 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 dans les entrepôts de données.Côte titre : MAI/0198 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0198 MAI/0198 Mémoire Bibliothéque des sciences Français Disponible
DisponibleUne approche parallèle a base de GPU pour la sélection d'indexes binaires de jointures dans les entrepôts de données / Azziz, yamina
Titre : Une approche parallèle a base de GPU pour la sélection d'indexes binaires de jointures dans les entrepôts de données Type de document : texte imprimé Auteurs : Azziz, yamina ; TOUMI, Lyazid, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (81f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Ingénierie de Données
Technologies Web
GPU
indexes binairesIndex. décimale : 004 Informatique Côte titre : MAI/0199 Une approche parallèle a base de GPU pour la sélection d'indexes binaires de jointures dans les entrepôts de données [texte imprimé] / Azziz, yamina ; TOUMI, Lyazid, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (81f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Ingénierie de Données
Technologies Web
GPU
indexes binairesIndex. décimale : 004 Informatique Côte titre : MAI/0199 Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0199 MAI/0199 Mémoire Bibliothéque des sciences Français Disponible
Disponible
Titre : Health information System in shadow areas within the framework of law 1275 Type de document : texte imprimé Auteurs : Amani Ghamoud, Auteur ; Nesrine Dimane, Auteur ; TOUMI, Lyazid, Directeur de thèse Année de publication : 2023 Importance : 1 vol (54 f .) Format : 29cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Doctors
patientsIndex. décimale : 004 Informatique Résumé : In our country, many rural and poorly served areas face difficulties accessing medical
care. Often, we neglect our health and have trouble keeping track of our well-being.
Fortunately, health apps have become essential tools for monitoring our health and
taking preventive measures. It is in this context that we present SIHATI, a mobile
and web platform that aims to improve access to quality care in disadvantaged regions.
Patients can use this app to search for and make appointments with specialists available
in major cities, while doctors have the opportunity to offer their services and plan their
visits to specific areas. Through a grouping function based on patient preferences,
SIHATI optimizes the impact of physicians on patients, thus contributing to reducing
health disparities. Our main goal is to promote equity in access to healthcare through
technology.Côte titre : MAI/0702 En ligne : https://drive.google.com/file/d/1ADgzfOIuzpEUwIoSTXLa0ofHIUVTVjcw/view?usp=drive [...] Format de la ressource électronique : Health information System in shadow areas within the framework of law 1275 [texte imprimé] / Amani Ghamoud, Auteur ; Nesrine Dimane, Auteur ; TOUMI, Lyazid, Directeur de thèse . - 2023 . - 1 vol (54 f .) ; 29cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Doctors
patientsIndex. décimale : 004 Informatique Résumé : In our country, many rural and poorly served areas face difficulties accessing medical
care. Often, we neglect our health and have trouble keeping track of our well-being.
Fortunately, health apps have become essential tools for monitoring our health and
taking preventive measures. It is in this context that we present SIHATI, a mobile
and web platform that aims to improve access to quality care in disadvantaged regions.
Patients can use this app to search for and make appointments with specialists available
in major cities, while doctors have the opportunity to offer their services and plan their
visits to specific areas. Through a grouping function based on patient preferences,
SIHATI optimizes the impact of physicians on patients, thus contributing to reducing
health disparities. Our main goal is to promote equity in access to healthcare through
technology.Côte titre : MAI/0702 En ligne : https://drive.google.com/file/d/1ADgzfOIuzpEUwIoSTXLa0ofHIUVTVjcw/view?usp=drive [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0702 MAI/0702 Mémoire Bibliothéque des sciences Anglais Disponible
DisponibleOptimisation des performances par administration et tuning d’entrepôt de données / TOUMI, Lyazid
Titre : Optimisation des performances par administration et tuning d’entrepôt de données Type de document : texte imprimé Auteurs : TOUMI, Lyazid, Auteur ; Abdelouahab Moussaoui, Directeur de thèse Editeur : Setif:UFA Année de publication : 2015 Importance : 1 vol (134 f .) Format : 29 cm Catégories : Informatique Mots-clés : Entrepôts de données, auto-administration et tuning, conception physique des entrepôts
de données, optimisation, programmation linéaire, fouille de données, fragmentation
horizontale, sélection d’indexes binaires de jointures.Résumé : Résumé :
Cette thèse présente un travail sur l’administration et tuning d’entrepôts de données, précisément
aborde le problème de sélection d’indexes binaires de jointure (PSIJB) et le problème de la
fragmentation horizontale dérivé (PFHD). La thèse propose trois contributions à la recherche, la
première contribution utilise les essaims de particule pour résoudre le PSIJB. La deuxième permet de
modéliser le PSIJB en utilisant la programmation linéaire en nombre entier. Dans la troisième
contribution, nous avons proposé une nouvelle méthodologie pour résoudre le PFHD. Toutes les
approches proposées ont été validées par des tests sous un entrepôt de données utilisant des classes de
problèmes. Ces tests ont montré l’efficacité des approches proposées en terme de temps, de qualité
ainsi que d’exactitudes.
Note de contenu : TABLE OF CONTENTS
Page
List of Tables ix
List of Figures xi
1 Introduction 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Thesis goals and results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Academic publication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
I Backgrounds and state of art 7
2 Data warehouses architecture and design 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Data warehouses architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 The Data Cube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Data warehouse physical design . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 Data warehouse tuning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.6 DBMS tuning tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Indexes selection problem in data warehouses 17
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Indexation techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.1 B-tree index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.2 Projection index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.3 Hash index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.4 Bitmap Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.5 Join index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.6 Star join index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.7 Bitmap join index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Bitmap join indexes selection problem in data warehouses . . . . . . . . . . 22
3.3.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.2 Cost models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.2.1 Data access cost in presence of useful SBJIs (IndexCost) . 24
3.3.2.2 Data access cost in absence of useful SBJIs(JoinCost) . . . 24
3.3.2.3 Size of SBJI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4 Background of indexes selection problem . . . . . . . . . . . . . . . . . . . . . 25
3.4.1 Frank et al. approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4.2 Choenni’s approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4.3 Gundem’s approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.4 Golfarelli’s approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.5 Data mining based approach . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4.5.1 Mining closed frequent pattern . . . . . . . . . . . . . . . . 29
3.4.5.2 General schema of the data mining approach . . . . . . . . 30
3.4.6 Extended data mining based approach . . . . . . . . . . . . . . . . . . 31
3.4.7 Genetic algorithm based approach . . . . . . . . . . . . . . . . . . . . 32
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Horizontal partitioning in data warehouses 37
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Horizontal partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3 Horizontal partitioning example . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.5 Horizontal partitioning advantages . . . . . . . . . . . . . . . . . . . . . . . . 40
4.5.1 Horizontal Partitioning for databases administration . . . . . . . . . 40
4.5.2 Partitioning for performance optimization . . . . . . . . . . . . . . . 40
4.5.3 Partitioning for the availability . . . . . . . . . . . . . . . . . . . . . . 40
4.6 Horizontal partitioning modes . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.6.1 Range partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.6.2 Hach partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.6.3 List partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.6.4 Composite partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . 44
4.6.5 Multicolumn partitioning mode . . . . . . . . . . . . . . . . . . . . . . 46
4.6.6 Reference partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . 47
4.6.7 Virtual column partitioning . . . . . . . . . . . . . . . . . . . . . . . . 48
4.7 Horizontal partitioning problem in data warehouses . . . . . . . . . . . . . . 49
4.7.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.7.2 Cost model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.8 Background of approaches for the horizontal partitioning Problem . . . . . 50
4.8.1 Workload-based approach . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.8.2 Attribute affinity based approach . . . . . . . . . . . . . . . . . . . . . 51
4.8.3 Cost based approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.8.4 Data mining based approach . . . . . . . . . . . . . . . . . . . . . . . . 52
4.8.5 Constrained cost based approach . . . . . . . . . . . . . . . . . . . . . 53
4.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
II Contributions 57
5 Particle swarm optimization for solving SBJISP 59
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2 Particle Swarm Optimization (PSO) . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2.1 The PSO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2.2 Binary particle swarm optimization (BPSO) . . . . . . . . . . . . . . . 61
5.2.3 Inertia weight considerations for BPSO . . . . . . . . . . . . . . . . . 62
5.3 BPSO for the SBJI selection problem . . . . . . . . . . . . . . . . . . . . . . . 62
5.3.1 Query workload parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3.2 Solution coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3.3 Fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4.2 Preview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.4.3 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.4.3.1 The smaller size problem set CSP results . . . . . . . . . . 69
5.4.3.2 The moderate size problem set CMP results . . . . . . . . 72
5.4.3.3 The larger size problem set CLP results . . . . . . . . . . . 74
5.4.4 Performance Scalability Study . . . . . . . . . . . . . . . . . . . . . . . 76
5.4.4.1 Scalability results for the smaller size problem set CSP. . 76
5.4.4.2 Scalability results for the moderate size problem set CMP. 79
5.4.4.3 Scalability results for the larger size problem set CLP. . . 82
5.4.5 Performance results for the classes CSP, CMP and CLP using Oracle
DBMS cost models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6 Mixed-Integer linear programming for SBJISP 91
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2 Linear programming definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2.1 Linear program solution time . . . . . . . . . . . . . . . . . . . . . . . 92
6.2.2 Mixed Integer Programming . . . . . . . . . . . . . . . . . . . . . . . . 92
6.3 Mathematical formulation of SBJI selection problem . . . . . . . . . . . . . . 92
6.3.1 SBJISP constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.3.2 SBJISP objective Function . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.2 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.2.1 The smaller size problem set CSP results . . . . . . . . . . 98
6.4.2.2 The moderate size problem set CMP results . . . . . . . . 98
6.4.2.3 The larger size problem set CLP results . . . . . . . . . . . 101
6.4.3 Performance Scalability Study . . . . . . . . . . . . . . . . . . . . . . . 101
6.4.3.1 Scalability results for the smaller size problem set CSP. . 101
6.4.3.2 Scalability results for the moderate size problem set CMP. 102
6.4.3.3 Scalability results for the larger size problem set CLP. . . 105
6.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7 Efficient methodology for Reference Horizontal partitioning in data warehouses 109
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.2 The proposed methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.2.1 Predicates attraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.2.2 Clustering of Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.2.3 Determining the number of clusters . . . . . . . . . . . . . . . . . . . 113
7.2.3.1 Solution coding . . . . . . . . . . . . . . . . . . . . . . . . . . 113
7.2.4 Discrete particle swarm optimization for selecting horizontal partitioning schema . . . . . . . . . . . . . 114
7.2.4.1 Fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3.2 Preview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7.3.3 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7.3.3.1 The smaller size problem set CSP results . . . . . . . . . . 117
7.3.3.2 The moderate size problem set CMP results . . . . . . . . 120
7.3.3.3 The larger size problem set CLP results . . . . . . . . . . . 122
7.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
8 Conclusions 125
8.1 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
8.2 Future research directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
Bibliography 127Côte titre : DI/0022 En ligne : https://drive.google.com/file/d/1qaEXnuqod_wfImnJx2cU1N0-S8Fil2eT/view?usp=shari [...] Format de la ressource électronique : Optimisation des performances par administration et tuning d’entrepôt de données [texte imprimé] / TOUMI, Lyazid, Auteur ; Abdelouahab Moussaoui, Directeur de thèse . - [S.l.] : Setif:UFA, 2015 . - 1 vol (134 f .) ; 29 cm.
Catégories : Informatique Mots-clés : Entrepôts de données, auto-administration et tuning, conception physique des entrepôts
de données, optimisation, programmation linéaire, fouille de données, fragmentation
horizontale, sélection d’indexes binaires de jointures.Résumé : Résumé :
Cette thèse présente un travail sur l’administration et tuning d’entrepôts de données, précisément
aborde le problème de sélection d’indexes binaires de jointure (PSIJB) et le problème de la
fragmentation horizontale dérivé (PFHD). La thèse propose trois contributions à la recherche, la
première contribution utilise les essaims de particule pour résoudre le PSIJB. La deuxième permet de
modéliser le PSIJB en utilisant la programmation linéaire en nombre entier. Dans la troisième
contribution, nous avons proposé une nouvelle méthodologie pour résoudre le PFHD. Toutes les
approches proposées ont été validées par des tests sous un entrepôt de données utilisant des classes de
problèmes. Ces tests ont montré l’efficacité des approches proposées en terme de temps, de qualité
ainsi que d’exactitudes.
Note de contenu : TABLE OF CONTENTS
Page
List of Tables ix
List of Figures xi
1 Introduction 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Thesis goals and results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Academic publication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
I Backgrounds and state of art 7
2 Data warehouses architecture and design 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Data warehouses architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 The Data Cube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Data warehouse physical design . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5 Data warehouse tuning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.6 DBMS tuning tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Indexes selection problem in data warehouses 17
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Indexation techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.1 B-tree index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.2 Projection index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.3 Hash index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.4 Bitmap Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.5 Join index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.6 Star join index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.7 Bitmap join index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Bitmap join indexes selection problem in data warehouses . . . . . . . . . . 22
3.3.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.2 Cost models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.2.1 Data access cost in presence of useful SBJIs (IndexCost) . 24
3.3.2.2 Data access cost in absence of useful SBJIs(JoinCost) . . . 24
3.3.2.3 Size of SBJI . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4 Background of indexes selection problem . . . . . . . . . . . . . . . . . . . . . 25
3.4.1 Frank et al. approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4.2 Choenni’s approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4.3 Gundem’s approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.4 Golfarelli’s approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.5 Data mining based approach . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4.5.1 Mining closed frequent pattern . . . . . . . . . . . . . . . . 29
3.4.5.2 General schema of the data mining approach . . . . . . . . 30
3.4.6 Extended data mining based approach . . . . . . . . . . . . . . . . . . 31
3.4.7 Genetic algorithm based approach . . . . . . . . . . . . . . . . . . . . 32
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Horizontal partitioning in data warehouses 37
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Horizontal partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.3 Horizontal partitioning example . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.5 Horizontal partitioning advantages . . . . . . . . . . . . . . . . . . . . . . . . 40
4.5.1 Horizontal Partitioning for databases administration . . . . . . . . . 40
4.5.2 Partitioning for performance optimization . . . . . . . . . . . . . . . 40
4.5.3 Partitioning for the availability . . . . . . . . . . . . . . . . . . . . . . 40
4.6 Horizontal partitioning modes . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.6.1 Range partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.6.2 Hach partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.6.3 List partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.6.4 Composite partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . 44
4.6.5 Multicolumn partitioning mode . . . . . . . . . . . . . . . . . . . . . . 46
4.6.6 Reference partitioning mode . . . . . . . . . . . . . . . . . . . . . . . . 47
4.6.7 Virtual column partitioning . . . . . . . . . . . . . . . . . . . . . . . . 48
4.7 Horizontal partitioning problem in data warehouses . . . . . . . . . . . . . . 49
4.7.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.7.2 Cost model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.8 Background of approaches for the horizontal partitioning Problem . . . . . 50
4.8.1 Workload-based approach . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.8.2 Attribute affinity based approach . . . . . . . . . . . . . . . . . . . . . 51
4.8.3 Cost based approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.8.4 Data mining based approach . . . . . . . . . . . . . . . . . . . . . . . . 52
4.8.5 Constrained cost based approach . . . . . . . . . . . . . . . . . . . . . 53
4.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
II Contributions 57
5 Particle swarm optimization for solving SBJISP 59
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2 Particle Swarm Optimization (PSO) . . . . . . . . . . . . . . . . . . . . . . . . 59
5.2.1 The PSO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2.2 Binary particle swarm optimization (BPSO) . . . . . . . . . . . . . . . 61
5.2.3 Inertia weight considerations for BPSO . . . . . . . . . . . . . . . . . 62
5.3 BPSO for the SBJI selection problem . . . . . . . . . . . . . . . . . . . . . . . 62
5.3.1 Query workload parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3.2 Solution coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.3.3 Fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4.2 Preview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.4.3 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.4.3.1 The smaller size problem set CSP results . . . . . . . . . . 69
5.4.3.2 The moderate size problem set CMP results . . . . . . . . 72
5.4.3.3 The larger size problem set CLP results . . . . . . . . . . . 74
5.4.4 Performance Scalability Study . . . . . . . . . . . . . . . . . . . . . . . 76
5.4.4.1 Scalability results for the smaller size problem set CSP. . 76
5.4.4.2 Scalability results for the moderate size problem set CMP. 79
5.4.4.3 Scalability results for the larger size problem set CLP. . . 82
5.4.5 Performance results for the classes CSP, CMP and CLP using Oracle
DBMS cost models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6 Mixed-Integer linear programming for SBJISP 91
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2 Linear programming definition . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2.1 Linear program solution time . . . . . . . . . . . . . . . . . . . . . . . 92
6.2.2 Mixed Integer Programming . . . . . . . . . . . . . . . . . . . . . . . . 92
6.3 Mathematical formulation of SBJI selection problem . . . . . . . . . . . . . . 92
6.3.1 SBJISP constraints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.3.2 SBJISP objective Function . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.2 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.2.1 The smaller size problem set CSP results . . . . . . . . . . 98
6.4.2.2 The moderate size problem set CMP results . . . . . . . . 98
6.4.2.3 The larger size problem set CLP results . . . . . . . . . . . 101
6.4.3 Performance Scalability Study . . . . . . . . . . . . . . . . . . . . . . . 101
6.4.3.1 Scalability results for the smaller size problem set CSP. . 101
6.4.3.2 Scalability results for the moderate size problem set CMP. 102
6.4.3.3 Scalability results for the larger size problem set CLP. . . 105
6.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7 Efficient methodology for Reference Horizontal partitioning in data warehouses 109
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.2 The proposed methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.2.1 Predicates attraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
7.2.2 Clustering of Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
7.2.3 Determining the number of clusters . . . . . . . . . . . . . . . . . . . 113
7.2.3.1 Solution coding . . . . . . . . . . . . . . . . . . . . . . . . . . 113
7.2.4 Discrete particle swarm optimization for selecting horizontal partitioning schema . . . . . . . . . . . . . 114
7.2.4.1 Fitness function . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3.1 Problem instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
7.3.2 Preview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7.3.3 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7.3.3.1 The smaller size problem set CSP results . . . . . . . . . . 117
7.3.3.2 The moderate size problem set CMP results . . . . . . . . 120
7.3.3.3 The larger size problem set CLP results . . . . . . . . . . . 122
7.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
8 Conclusions 125
8.1 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
8.2 Future research directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
Bibliography 127Côte titre : DI/0022 En ligne : https://drive.google.com/file/d/1qaEXnuqod_wfImnJx2cU1N0-S8Fil2eT/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité DI/0022 DI/0022 Thèse Bibliothéque des sciences Français Disponible
Disponible
Titre : Optimisation physique des Entrepôt de Données : Cas des Structures redondantes Type de document : texte imprimé Auteurs : MEKIDECHE, MANEL ; TOUMI, Lyazid, Directeur de thèse Editeur : Setif:UFA Année de publication : 2012 Importance : 1 vol (54f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Génie logiciel
optimisation physique
Entrepôt de Donnée
Structures redondantesIndex. décimale : 004 Informatique Résumé : Conclusion générale
Dans ce travail nous avons concentré sur les techniques d’optimisation des requêtes dans les entrepôts de données et plus précisément sur les problèmes de sélection d’index binaire de jointure, où nous avons proposé une nouvelle heuristique à base des essaims de particules pour résoudre le problème de sélection d’une configuration d’index binaire de jointure et d'autre part nous avons étudier ce qui a été déjà proposé comme approches. A la fin nous avons validé notre approche, où une comparaison a été faite avec l’approche Dynaclose. Du point de vue empirique nous avons implémenté ces algorithmes, qui nous y a permis de calculé les couts d’E/S des requêtes en présence des configurations d’index sélectionnés par les deux approches BPSO et Dynaclose afin d’arriver a tiré des conclusions sur les performances de chacune des approches. A la fin nous avons déduit que notre approche a prouvé son efficacité quand à l’optimisation des performances des entrepôts de données. L’idée de proposer une nouvelle approche pour sélectionner une configuration d’index de jointure binaire est très originale et prometteuse.
D’après les efforts que nous avons fournis durant toute l’année, nous estimons que les objectifs fixés au départ de ce travail sont achevé à un taux élevé de 90%, où nous avons proposé une nouvelle approche et nous avons validé avec des approches déjà proposé et nous avons arrivé à apprendre beaucoup de choses intéressantes et motivantes tels que, les problèmes et les technique de résolutions de problèmes, les entrepôts de données (conception et administration) et les techniques de fouille de données (Close et Charm). Comme perspectives de ce travail, nous jugions nécessaire de faire d’autres types expérimentations, ainsi d’ajouter d’autres paramètres dans le model de coût tel que le Buffer et de proposer les BPSO pour la sélection des index binaire de jointure multi-attributs.Côte titre : MAI/0025 En ligne : https://drive.google.com/file/d/12_fxPIsIWTWj06iVwDAWXkJCu3V0b9cM/view?usp=shari [...] Format de la ressource électronique : Optimisation physique des Entrepôt de Données : Cas des Structures redondantes [texte imprimé] / MEKIDECHE, MANEL ; TOUMI, Lyazid, Directeur de thèse . - [S.l.] : Setif:UFA, 2012 . - 1 vol (54f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Génie logiciel
optimisation physique
Entrepôt de Donnée
Structures redondantesIndex. décimale : 004 Informatique Résumé : Conclusion générale
Dans ce travail nous avons concentré sur les techniques d’optimisation des requêtes dans les entrepôts de données et plus précisément sur les problèmes de sélection d’index binaire de jointure, où nous avons proposé une nouvelle heuristique à base des essaims de particules pour résoudre le problème de sélection d’une configuration d’index binaire de jointure et d'autre part nous avons étudier ce qui a été déjà proposé comme approches. A la fin nous avons validé notre approche, où une comparaison a été faite avec l’approche Dynaclose. Du point de vue empirique nous avons implémenté ces algorithmes, qui nous y a permis de calculé les couts d’E/S des requêtes en présence des configurations d’index sélectionnés par les deux approches BPSO et Dynaclose afin d’arriver a tiré des conclusions sur les performances de chacune des approches. A la fin nous avons déduit que notre approche a prouvé son efficacité quand à l’optimisation des performances des entrepôts de données. L’idée de proposer une nouvelle approche pour sélectionner une configuration d’index de jointure binaire est très originale et prometteuse.
D’après les efforts que nous avons fournis durant toute l’année, nous estimons que les objectifs fixés au départ de ce travail sont achevé à un taux élevé de 90%, où nous avons proposé une nouvelle approche et nous avons validé avec des approches déjà proposé et nous avons arrivé à apprendre beaucoup de choses intéressantes et motivantes tels que, les problèmes et les technique de résolutions de problèmes, les entrepôts de données (conception et administration) et les techniques de fouille de données (Close et Charm). Comme perspectives de ce travail, nous jugions nécessaire de faire d’autres types expérimentations, ainsi d’ajouter d’autres paramètres dans le model de coût tel que le Buffer et de proposer les BPSO pour la sélection des index binaire de jointure multi-attributs.Côte titre : MAI/0025 En ligne : https://drive.google.com/file/d/12_fxPIsIWTWj06iVwDAWXkJCu3V0b9cM/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0025 MAI/0025 Mémoire Bibliothéque des sciences Français Disponible
DisponibleVers une approche incrémentale pour la fragmentation horizontale dans les entrepôts de données relationnels / Mansouri,zakaria
Permalink