Cours EDD 240328 115957

Introduction aux entrepôts
de données
Master 2 SID
Département d’Informatique
Universtié de Laghouat
Programme :
1. Contexte et problématique
2. Concepts et définitions
3. Modélisation
4. Processus ETL (Extract Transform Load)
5. Conception physique : Optimisation des
performances
Contexte : Évolution des BDDs
Évolution des BDDs

I Évolution considérable et grand déploiement des BDDs.
Évolution des BDDs

I Gros volume de données :
I Ventes,
I Médecine,
I Éducation,
I Internet,
I …etc.,
Évolution des BDDs

I Ventes,
I Médecine,
I Éducation,
I Internet,
I …etc.,
I Évolution des besoins : Comment répondre aux
demandes d’analyses historiques et prédictives ?
Évolution des BDDs

I Ventes,
I Médecine,
I Éducation,
I Internet,
I …etc.,
I Évolution des besoins : Comment répondre aux
demandes d’analyses historiques et prédictives ?
I Exemple : analyse des ventes :
I Par catégories de produits,
I Par régions,
I Par mois, semestre, année,
I Par type de clients,
I ….
Contexte : Données & Connaissances
Des organismes :
I de plus en plus riche en données,
I … mais pauvres en connaissnaces.
Des organismes :
I Données : Résultats de l’observation

I Exemple : Nombre d’unités achetées pour un produit
donné.
Des organismes :

donné.
I Informations : Résultats de l’analyse de données
I Exemple : La répartition géographique des produits
achetés.
Des organismes :

donné.
I Informations : Résultats de l’analyse de données
I Exemple : La répartition géographique des produits
achetés.
I Connaissances : Informations utiles pour la prise de
décision
I Exemple : Mauvais emplacements de certains magasins
de vente.
Question :
I Comment aller des données aux Connaissances ?
Question :
I Caractéristiques des données :

I Éparpillées : Plusieurs SI (BDD),
Question :

I Hétérogènes : SGBD et structures de données variés,

Question :

I Pas d’historisation.
Question :

I Pas d’historisation.
I Non organisées dans une perspective décisionnelle.

Problématique :
I Besoins de connaissances : Prise de décisions
stratégiques
Problématique :
stratégiques
I Exemples de connaissances recherchées :

Problématique :
stratégiques

I Quelles sont les caractéristiques de mes clients ?
Comment les conserver ?,
Problématique :
stratégiques

I Où placer un produit donné ? Quels sont les acheteurs
potontiels de ce produit ?
Problématique :
stratégiques

I Où placer un produit donné ? Quels sont les acheteurs
potontiels de ce produit ?
I Quelles sont les ventes du produit X pendant le mois M
de l’année A pour la région R ?
Il faut donc :
I Avoir une information globale (générale) sur l’activité
de l’entreprise
I Accés rapide à l’information stratégique.
Il faut donc :
I Avoir une information globale (générale) sur l’activité
de l’entreprise
I Accés rapide à l’information stratégique.
I Solution :
I Mettre en place un SI dédié aux applications
décisionnelles : Entrepôt de données (Data Warehouse)
Entrepôt de données : Définition
Entrepôt de données
Un entrepôt de données est une collection de données
orientées sujets, intégrées, non volatiles et historisées,
organisées pour un processus d’aide à la décision.
Entrepôt de données :
I Orientées sujet : Les données des entrepôts sont
organisées par sujet (thème) plutôt que par application.
Par exemple, une chaîne de magasins d’alimentation
organise les données de son entrepôt par rapport aux
ventes qui ont été réalisées par produit et par magasin,
au cours d’un certain temps.
I Orientées sujet : Les données des entrepôts sont
organisées par sujet (thème) plutôt que par application.
Par exemple, une chaîne de magasins d’alimentation
organise les données de son entrepôt par rapport aux
ventes qui ont été réalisées par produit et par magasin,
au cours d’un certain temps.
I Intégrées : Les données provenant des différentes
sources doivent être intégrées, avant leur stockage dans
l’entrepôt de données. L’intégration (mise en
correspondance des formats, par exemple), permet
d’avoir une cohérence de l’information.
I Non volatiles : Les données de l’entrepôt sont
permanentes et ne peuvent pas être modifiées. Le
rafraîchissement de l’entrepôt consiste à ajouter de
nouvelles données, sans modifier ou perdre celles qui
existent. On y intègre seulement de nouvelles données
datées qui viennent s’ajouter aux précédentes.
I Non volatiles : Les données de l’entrepôt sont
permanentes et ne peuvent pas être modifiées. Le
rafraîchissement de l’entrepôt consiste à ajouter de
nouvelles données, sans modifier ou perdre celles qui
existent. On y intègre seulement de nouvelles données
datées qui viennent s’ajouter aux précédentes.
I Historiées : La prise en compte de l’évolution des
données est essentielle pour la prise de décision. Par
exemple, on utilise des techniques de prédiction en
s’appuyant sur les évolutions passées pour prévoir les
évolutions futures.
Entrepôt de données : Objectifs
I Organisation cohérente des informations de l’entreprise
I Unification et globalisation de l’information de
l’entreprise
l’entreprise
I Accès rapide à toute l’information de l’entreprise
l’entreprise
I Extraction des connaissances (Qualité de l’information)
l’entreprise
I Extraction des connaissances (Qualité de l’information)
I Outils (applications) d’aide à la décision (Intelligence
d’affaire)
Entrepôt de données : Caractéristiques
I Volumétrie : Taille de plusieurs téra octets
I Requêtes complexes : Exigence des décideurs
I Requêtes complexes : Exigence des décideurs
I Complexité de la conception physique :
I Index
I Vues matérialisées
I Fragmentataion (Horizontale, Verticale, Hybride)
I Avantages :
I Avantages :
I Simplicité d’utilisation : 1 seul SGBD, 1 seule requête.
I Avantages :
I Qualité des données : Nettoyées, Organisées et classifiées
I Avantages :
I Données historiques : Compréhension, Exploitation.
I Avantages :
I Désavantages :
I Avantages :
I Désavantages :
I Complexité de mise en place : 6= SGBD et 6= structures de
données.
I Avantages :
I Désavantages :
I Complexité de mise en place : 6= SGBD et 6= structures de
données.
I Coûts : Réalisation, Maintenance, Formation des
utilisateurs.
Entrepôt de données : Composants
I Sources : BDD,
Files,…
I Entrepôt,
I Méta-données :
Schéma, Users, …
I Serveur OLAP : Accès
I Outils de front-end :
rapports, statistiques,
data mining
Processus ETL (Extract Transform Load)
Processus ETL :
I Extract : Extraction des données depuis les différentes
sources (6= SGBDs et 6= formats)
Processus ETL :
I Exemple de sources de données :
Processus ETL :
I Base de données relationelles (6= formats)
Processus ETL :
I Fichiers CSV, Excel
Processus ETL :
I Fichiers XML
Processus ETL :
I Fichiers XML
I Données sur papier ! !….
Processus ETL :
I Transform : trier, filtrer, agrèger, regrouper, etc.
Processus ETL :
I Exemple :
I Représentation uniforme
Processus ETL :
I Exemple :
I Nettoyage des données : sélection, suppression des
doublons,…
Processus ETL :
I Exemple :
doublons,…
I Transformation : jointure, agrégation,…
Processus ETL :
I Exemple :
doublons,…
I Load : Stockage (chargement) des résultats de
transformation dans l’entrepôt.
Processus ETL :
I Exemple :
doublons,…
I Load : Stockage (chargement) des résultats de
transformation dans l’entrepôt.
I 70% de l’effort consacré à un projet de DW est dépensé
dans l’ETL
Processus ETL :
I Quelques outils open source :
I Apache Airflow ⇒ https ://airflow.apache.org/
I CloverETL ⇒ https ://sourceforge.net/projects/cloveretl/
I Jaspersoft ETL ⇒
https ://community.jaspersoft.com/project/jaspersoft-etl
I Talend Open Studio ⇒ https ://www.talend.com/pro-
ducts/data-integration/data-integration-open-studio/
I Apatar ⇒ http ://www.apatar.com/
Exploitation de l’entrepôt : Pourquoi stocker les
données ?
Pourquoi stocker les données ?

I Outils de front-end :
I Reporting : Informations synthétiques (visualisation
graphiques diverses),
I Outils OLAP (Online Analytical Processing) : Analyser les
données à l’aide de requêtes complexes,
I Data mining : Extraction de connaissances.
Entrepôt : Modélisation Multidimensionnelle
Modélisation d’un entrepôt :

I Problématique : Analyse du montant des ventes.
Catégorie Région Montant
Burautique Alger 500
Burautique Laghouat 50
Burautique Oran 100
Electroménager Alger 1000
Electroménager Oran 9000
Informatique Alger 2000
Informatique Laghouat 500
Informatique Oran 1000
Modélisation d’un entrepôt :

I Problématique : Analyse du montant des ventes.
Catégorie Région Montant
Burautique Alger 500
Burautique Laghouat 50
Burautique Oran 100
Electroménager Alger 1000
Electroménager Oran 9000
Informatique Alger 2000
Informatique Laghouat 500
Informatique Oran 1000
I Différentes observations d’analyse du Montant :
I Selon la catégorie des produits
I Selon la région.
Concepts de fait et de dimension :

I Définir le sujet (thème) d’analyse : Faits,


I Formés de mesures correspondant aux informations de
l’activité analysée.
I Les mesures sont numériques (Moyenne, Min, Max)

I Définir les axes d’analyse : Dimensions.
I Formées des attributs permettant l’analysér des mesures.

I Exemple : Analyse de ventes

I Exemple : Analyse de ventes
I Faits : Ventes (Mesures : Quantité et Montant.)
I Dimensions : Client, Temps, Magasin.
Entrepôt de données : Schéma multidimensionnel
Schéma en étoile :
I R-OLAP : Relational OLAP
Temps Produit
(Dimension) (Dimension)
TID PID
Jour Ventes Description
Mois (Faits) Marque
Trimestre Categorie
TID
Annee
PID 300 000
1094 CID tuples
tuples MID Magasin
Quantite (Dimension)
Client
Montant
(Dimension) MID
CID 100 000 000 Nom
Nom tuples Ville
Genre Adresse
Ville
Age 10 000
tuples
1 000 000
tuples
Entrepôt de données : Optimisation des
performances
Rappels :
I BDD : Collection de données interreliées, stockées
ensemble pour servir une ou plusieurs applications de
façon optimale. Le stockage des données est
indépendant des programmes d’utilisation.
performances
Rappels :
I SGBD : Ensemble des programmes :
performances
Rappels :
I SGBD : Ensemble des programmes :
I Création, stockage, maintenance, MAJ et recherche dans
la BDD.
I Interfaces nécessaires aux différentes formes
d’utilisation de la BDD.
performances
Rappels :
I Administrateur de la BDD :.
performances
Rappels :
I Conception, Création, Maintenance.
performances
Rappels :
I Gestion des données au niveau logique (définition de
schéma conceptuel)
performances
Rappels :
schéma conceptuel)
I Gestion des données au niveau physique (tables,
stockage, organisation des données)
performances
Rappels :
schéma conceptuel)
I Optimisation des performances (choix des structures
d’optimisation : index, frgaments, vues matérialisées,
..etc)
performances
Rappels :
schéma conceptuel)
I Optimisation des performances (choix des structures
d’optimisation : index, frgaments, vues matérialisées,
..etc)
I Tuning : Réglage des structures d’optimisation.
performances
Rappels :
I Détermination des accès fréquents
performances
Rappels :
I Choix des bonnes structures physiques : Partitionnement
de tables, index, etc.
performances
Rappels :
I Choix des bonnes structures physiques : Partitionnement
de tables, index, etc.
I La modification ou l’ajout de structures physiques mieux
adaptées permet d’améliorer les performances de
traitement des requêtes
performances
Rappels :
I Objectif : Obtenir les meilleures performances :
performances
Rappels :
I Temps d’accès
performances
Rappels :
I Temps d’accès
I Espace mémoire utilisé
performances
Rappels :
I Temps d’accès
I Espace mémoire utilisé
I Espace disque occupé.
performances
Techniques d’optimisation :
Fragmentation
verticale Mono
table
Redandantes Indexes
Milti
tables
Vues
matérialisées
Techniques
d’optimisaion
Fragmentation
horizentale
Non
redandantes
Traitement
parallèl
Optimisation des performances : Pourquoi les index ?
Rappels :
I Un index sur une table va permettre au SGBD d’accéder
très rapidement aux enregistrements, selon la valeur
d’un ou plusieurs champs.
Rappels :
I Index simple : Sur une seule table (Arbre-B ou index
binaire)
Rappels :
I Index simple : Sur une seule table (Arbre-B ou index
binaire)
I Index de jointure : Sur plusieurs tables dans un schéma
en étoile (index de jointure binaire)
Rappels :
I SELECT * FROM Etud WHERE Moy >= 10
Rappels :
I Sans index sur Moy : Pour déterminer les enregistrements
vérifiant la condition Moy >= 10, le SGBD doit vérifier
cette condition pour chaque enregistrement de la table.
Rappels :
I Sans index sur Moy : Pour déterminer les enregistrements
vérifiant la condition Moy >= 10, le SGBD doit vérifier
cette condition pour chaque enregistrement de la table.
I Avec un index sur Moy : Le SGBD parcours l’index pour
les identifier les enregistrements vérifiant la condition
Moy >= 10
Optimisation des performances : Index B-Arbre
Rappels :
I BDD classique : La structure la plus courante pour les
index est l’Arbre-B (B-tree).
25 40
19 21 23 25 33 37 40 44 46
r6 r3 r4 r1 r5 r9 r2 r7 r8
Optimisation des performances : Index Binaire
(BitMap)
Rappels :
I Soit un attribut A, prenant n valeurs possibles v1 , . . . , vn
(domaine).
(BitMap)
Rappels :
(domaine).
I Création d’un index bitmap sur l’attribut A :
I On crée n vecteurs de bit, (un vecteur pour chaque valeur
vi )
(BitMap)
Rappels :
(domaine).
vi )
I Chaque vecteur contient un bit pour chaque tuple (ligne)
t de la table
(BitMap)
Rappels :
(domaine).
vi )
I Chaque vecteur contient un bit pour chaque tuple (ligne)
t de la table
I Le bit corréspondant à un tuple t est à 1 si : t.A = vi , à 0
sinon
Index Binaire (BitMap) : Exemple
Rappels :
I Enseignant(NSS, Nom, Grade, Salaire)
I Domaine(Grade)=MAB, MAA, MCB, MCA, P
RowID NSS Nom Grade Salaire
00051 :000 :0065 11111 AAAA MAA 26511
I 00019 :000 :0066 66666 BBBB MCA 30000
00071 :000 :0043 22222 CCCC MAA 26511
00024 :000 :0095 44444 DDDD P 50000
Rappels :
I SQL : CREATE INDEX BITMAP ON Enseignant(Grade) ;
Rappels :
RowID MAB MAA MCB MCA P
00051 :000 :0065 0 1 0 0 0
I
Rappels :
00051 :000 :0065 0 1 0 0 0
I 00019 :000 :0066 0 0 0 1 0
Rappels :
00051 :000 :0065 0 1 0 0 0
I 00019 :000 :0066 0 0 0 1 0
00071 :000 :0043 0 1 0 0 0
Rappels :
00051 :000 :0065 0 1 0 0 0
I 00019 :000 :0066 0 0 0 1 0
00071 :000 :0043 0 1 0 0 0
00024 :000 :0095 0 0 0 0 1
Rappels :
I Q1 :SELECT * FROM Enseignant WHERE Grade = ”P” ;
Rappels :
I On considère le vecteur de bit de la colonne P
I On garde toutes les cellules à 1
I On accède aux enregistrements par l’adresse (ROWID)
Rappels :
I Q2 :SELECT COUNT(*) FROM Enseignant WHERE Grade
= ”MAA” ;
Rappels :
= ”MAA” ;
I On compte le nombre 1 dans la colonne MAA (C’est
tout ! ! !)
Rappels :
= ”MAA” ;
tout ! ! !)
I Très efficace si le nombre de valeurs n est petit.
Rappels :
= ”MAA” ;
tout ! ! !)
I Très efficace si le nombre de valeurs n est petit.
I Si n est très grand ⇒ Compression de l’index.
Index de Jointure Binaire (Bitmap Join Index) :
définition
Problématique :
I Problème fondamental pour les EDD : Performances.
définition
Problématique :
I EDD : Données colossales + Requêtes complexes.
définition
Problématique :
I Objectif : Une réponse très rapide ou du moins dans un
délai acceptable.
définition
Problématique :
délai acceptable.
I Pour une requête q : Même resultat ∀ le schéma physique
mis en place.
définition
Problématique :
délai acceptable.
mis en place.
I Mais le temps d’exécution de q peut largement varié
pour 6= schémas physiques
définition
Problématique :
délai acceptable.
mis en place.
I Mais le temps d’exécution de q peut largement varié
pour 6= schémas physiques
I Par conséquence, le choix de la conception physique à
mettre en place a un impact important sur les
performances de l’entrepôt.
définition
Problématique :
I Les requêtes définies sur un EDD modélisé par un
schéma en étoile : Requêtes de jointures en étoile (star
join queries)
définition
Problématique :
join queries)
I Opérations de sélection sur les tables de dimension,
suivies par de multiple opérations de jointures avec la
table des faits.
définition
Problématique :
join queries)
I Opérations de sélection sur les tables de dimension,
suivies par de multiple opérations de jointures avec la
table des faits.
I De telles requêtes peuvent nécessiter des heures, voir
des jours de temps d’exécution
I Les index de jointure binaire ont été proposés pour
optimiser de telles requêtes.
définition
IJB :
I Un index de jointure binaire est défini sur la table des
faits en utilisant des attributs, non clés, appartenant à
une ou plusieurs tables de dimension.
définition
IJB :
I Soit A un attribut relatif à une table de dimension D et
ayant n valeurs distinctes v1 , v2 . . . , vn
définition
IJB :
I Supposons que la table des faits F est composée de m
tuples (enregistrements). La construction de l’index de
jointure binaire défini sur l’attribut A est réalisée de la
manière suivante :
définition
IJB :
manière suivante :
I Création de n vecteurs composés chacun de m entrées ;
définition
IJB :
manière suivante :
I Création de n vecteurs composés chacun de m entrées ;
I Le i me bit du vecteur correspondant à une valeur vk est
mis à 1 si le tuple de rang i de la table des faits est joint
avec un tuple de la table de dimension D tel que la valeur
de A de ce tuple est égale à vk . Il est mis à 0 dans le cas
contraire.
Exemple
Exemple IJB :
I Considérons un entrepôt de données constitué d’une
table de faits VENTES et deux tables de dimension
CLIENT et TEMPS (voir figure (a))
Exemple
Exemple IJB :
I Considérons un entrepôt de données constitué d’une
table de faits VENTES et deux tables de dimension
CLIENT et TEMPS (voir figure (a))
I Soit la requête q :
Select count(*)
From Ventes V, Client C, Temps T
Where V.CID = C.CID AND V.TID = T.TID
AND C.Ville = ’Alger’ AND T.Mois = ’Mar’.
Exemple
Exemple IJB :
VENTES
RID CID TID Montant
CLIENTS 1 111 11 100
2 111 22 10 TEMPS
CID Nom Ville
3 111 33 258 TID Mois Annee
111 Ali Alger
4 414 11 24 11 Jan 2010
212 Ameur Oran
5 515 22 70 22 Fev 2010
313 Youcef Alger
6 515 11 33 33 Mar 2010
414 Kamel Alger
7 515 44 101 44 Avr 2010
515 Nacer Oran
8 515 33 11
9 313 22 200
10 414 11 55
11 313 11 58
12 212 11 47
(a)
Ville Mois
RID Alger Oran Jan Fev Mar Avr AND
1 1 0 1 0 0 0 0
2 1 0 0 1 0 0 0
3 1 0 0 0 1 0 1
4 1 0 1 0 0 0 0
5 0 1 0 1 0 0 0
6 0 1 1 0 0 0 0
7 0 1 0 0 0 1 0
8 0 1 0 0 1 0 0
9 1 0 0 1 0 0 0
10 1 0 1 0 0 0 0
11 1 0 1 0 0 0 0
12 0 1 1 0 0 0 0
IJB Ville Mois
(b) (c)
Exemple
Exemple IJB :
I Afin d’optimiser le coût de q, l’administrateur crée un
index de jointure binaire sur les attributs Ville et Mois
(figure (b)).
Exemple
Exemple IJB :
I Afin d’optimiser le coût de q, l’administrateur crée un
index de jointure binaire sur les attributs Ville et Mois
(figure (b)).
I Pour répondre à q, l’optimiseur lit les vecteurs de bits
associés aux valeurs ”Alger” et ”Mar”, réalise un AND et
en fin il calcule le nombre de ’1’ dans le vecteur résultat
(Figure (c)).
Avantages
Avantages IJB :
I L’espace nécessaire au stockage des IJB est réduit,
notamment quand la cardinalité des attributs indexés est
relativement faible.
Avantages
Avantages IJB :
I Très bénéfiques pour les requêtes de type Count(*) : La
réponse à ce type de requêtes ne nécessite aucun accès
aux données dans les tables.
Avantages
Avantages IJB :
I Très bénéfiques pour les requêtes de type Count(*) : La
réponse à ce type de requêtes ne nécessite aucun accès
aux données dans les tables.
I Les opérations logiques sur les bits les rendent très
efficaces pour l’optimisation des opérations de jointures.
Problème de selection des index
PSI :
I Un système de base de données traite un ensemble de
requêtes Q = {q1 , q2 , . . . , } soumises respectivement à
des moments différents.
PSI :
I Si une requête qi est traitée par le système à un temps ti ,
il est probable qu’elle sera soumise au système à un
instant tj > ti .
PSI :
instant tj > ti .
I ⇒ les administrateurs s’intéressent à optimiser le
traitement des requêtes les plus fréquentes.
PSI :
instant tj > ti .
I En pratique les requêtes qui sont prise en compte
représentent environ seulement 20% de l’ensemble des
requêtes actives et réalisent 80% des accès aux données
PSI :
instant tj > ti .
I En pratique les requêtes qui sont prise en compte
représentent environ seulement 20% de l’ensemble des
requêtes actives et réalisent 80% des accès aux données
I L’ensemble des requêtes sélectionnées pour le processus
d’optimisation est appelé charge de travail (Workload en
Anglais).
PSI :
f f f
I Soit W = {q11 , q22 , . . . , qnn } une charge de n requêtes où
chaque requête qi est caractérisée par sa fréquence
d’utilisation fi .
PSI :
f f f
I Soit W = {q11 , q22 , . . . , qnn } une charge de n requêtes où
chaque requête qi est caractérisée par sa fréquence
d’utilisation fi .
I Une première étape très importante pour la procédure
de sélection des index est l’identification des attributs
pertinents susceptibles d’être indexés. Ces derniers sont
appelés attributs indexables.
Attribut indexable : Définition

Les attributs indexables sont ceux présents dans les prédicats
de sélection dans les clauses Where des requêtes. Un prédicat
de sélection défini sur un attribut ai d’une table T possède la
forme suivante :
T .ai θ Valeur
Où θ représente un opérateur de comparaison dans l’en-
semble {=, <, >, <=, >=} et Valeur ∈ Domaine(ai ). Domaine(ai )
étant l’ensemble des valeurs possibles de l’attribut ai .
Attribut indexable : Exemple

I Si la clause WHERE d’une requête q contient le prédicat
T .a = 10, un index sur l’attribut a peut être utilisé pour
répondre à la requête en récupérant tous les tuples
(enregistrements) de T vérifiant la condition spécifiée
dans le prédicat.
Attribut indexable : Exemple

I Si la clause WHERE d’une requête q contient le prédicat
T .a = 10, un index sur l’attribut a peut être utilisé pour
répondre à la requête en récupérant tous les tuples
(enregistrements) de T vérifiant la condition spécifiée
dans le prédicat.
I Soit AW = {a1 , a2 , . . . , ak } l’ensemble des attributs
indexables pour une charge de requêtes donnée W .
Etant donné qu’un index peut être créé sur un ou
plusieurs attributs, alors tout sous-ensemble non vide
I ⊆ AW représente un index potentiel. Si
IW = {I1 , I2 , . . . , Im } designe l’ensemble des tous les index
possibles pour la charge W , alors tout sous-ensemble
non vide C ⊆ IW est appelé configuration d’index.
PSI
I Pour une requête q ∈ W et une configuration d’index Ci ,
on note le coût d’exécution de q, exploitant Ci , par
χ(q, Ci ).
I Si S(I) désigne l’espace nécessaire pour stocker l’index I,
alors l’espace nécessaire pour stocker Ci est donné par
S(Ci ) = I∈Ci S(I).
P
PSI : Définition
f f f
Étant donnée une charge de requêtes W = {q11 , q22 , . . . , qnn } et
une limite d’espace de stockage Smax , l’objectif du problème
de sélection d’index est de trouver, parmi toutes les configu-
rations possibles, une configuration Copt qui minimise le coût
de la charge W et respecte la limite Smax :
Copt = argmin χ(q, Ci ) ∗ fi

 P

Ci q∈W



 et S(I) ≤ Smax

 P

I∈Ci
Complexité :
I Soit k le nombre des attributs indéxables pour une
charge donnée W .
Complexité :
charge donnée W .
I Nombre de possibilité pour sélectionner un seul index :
k
!
k
= 2k − 1
X
n1 =
i=1
i
Complexité :
charge donnée W .
k
!
k
= 2k − 1
X
n1 =
i=1
i
I Nombre de possibilité pour sélectionner plusieurs index

(configuration d’inde) :
k −1
2X
2k − 1
!
k −1
n2 = = 22 −1
i=1
i
Complexité :
charge donnée W .
k
!
k
= 2k − 1
X
n1 =
i=1
i
I Nombre de possibilité pour sélectionner plusieurs index

(configuration d’inde) :
k −1
2X
2k − 1
!
k −1
n2 = = 22 −1
i=1
i
I Pour k = 7 : n1 = 127 et n2 ≈ 2 × 1038 !!!,

PSI : Approche générique

f f
Données : Charge (q11 , . . . , qnn ) + Contrainte Smax .
Résultat : Configuration COpt optimisée d’index.

f f
1. Étape 1 : Identification des attributs indéxables


f f

2. Étape 2 : Élagage de l’espace de recherche (Élimination
des attributs non pertinents)

f f

3. Étape 3 : Construction d’une configuration initiale

f f

4. Étape 4 : Améliorer la configuration (Modèle de coût)

f f

4. Étape 4 : Améliorer la configuration (Modèle de coût)
5. Étape 5 : Séletionner une configuration finale.
Modèle de coût : Exemple

I Estimer la taille d’un IJB définit sur un attribut A ?

1. En lignes : ||F || (nombre de tuples dans la table des faits F )

2. En colonnes : |A| (cardinalité de l’attribut A)

2. En colonnes : |A| (cardinalité de l’attribut A)
||F ||×|A|
I SIJB(A) = 8 bytes
I Pour ||F || = 1000000000
12
10
8
Taille (Go)
0
0 20 40 60 80 100
Cardinalité

Cours EDD 240328 115957

Transféré par

Droits d'auteur :

Formats disponibles

Cours EDD 240328 115957

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours EDD 240328 115957

Transféré par

Droits d'auteur :

Formats disponibles

Introduction aux entrepôts

Évolution des BDDs

Évolution des BDDs

Évolution des BDDs

Évolution des BDDs

I Données : Résultats de l’observation

I Données : Résultats de l’observation

I Données : Résultats de l’observation

I Caractéristiques des données :

I Caractéristiques des données :

I Hétérogènes : SGBD et structures de données variés,

I Caractéristiques des données :

I Hétérogènes : SGBD et structures de données variés,

I Caractéristiques des données :

I Hétérogènes : SGBD et structures de données variés,

I Non organisées dans une perspective décisionnelle.

I Exemples de connaissances recherchées :

I Exemples de connaissances recherchées :

I Exemples de connaissances recherchées :

I Exemples de connaissances recherchées :

Pourquoi stocker les données ?

Modélisation d’un entrepôt :

Modélisation d’un entrepôt :

Concepts de fait et de dimension :

Concepts de fait et de dimension :

Concepts de fait et de dimension :

Concepts de fait et de dimension :

Concepts de fait et de dimension :

Concepts de fait et de dimension :

Attribut indexable : Définition

Attribut indexable : Exemple

Attribut indexable : Exemple

Copt = argmin χ(q, Ci ) ∗ fi

I Nombre de possibilité pour sélectionner plusieurs index

I Nombre de possibilité pour sélectionner plusieurs index

I Pour k = 7 : n1 = 127 et n2 ≈ 2 × 1038 !!!,

PSI : Approche générique

PSI : Approche générique

1. Étape 1 : Identification des attributs indéxables

PSI : Approche générique

1. Étape 1 : Identification des attributs indéxables

PSI : Approche générique

1. Étape 1 : Identification des attributs indéxables

PSI : Approche générique

1. Étape 1 : Identification des attributs indéxables

PSI : Approche générique

1. Étape 1 : Identification des attributs indéxables

Modèle de coût : Exemple

Modèle de coût : Exemple

Modèle de coût : Exemple

Modèle de coût : Exemple

I Pour ||F || = 1000000000

Vous aimerez peut-être aussi