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 127 |
Côte titre : |
DI/0022 |
En ligne : |
https://drive.google.com/file/d/1qaEXnuqod_wfImnJx2cU1N0-S8Fil2eT/view?usp=shari [...] |
Format de la ressource électronique : |
pdf |
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 127 |
Côte titre : |
DI/0022 |
En ligne : |
https://drive.google.com/file/d/1qaEXnuqod_wfImnJx2cU1N0-S8Fil2eT/view?usp=shari [...] |
Format de la ressource électronique : |
pdf |
|