rchitecture et modélisation des entrepôts de données

Architecture et modélisation des entrepôts de données

Architecture d’un entrepôt de données

Selon Bill Inmon, l’un des premiers fondateurs des entrepôts des données, « un entrepôt de données est une collection de données thématiques, intégrées, non volatiles et historiées pour la prise de décisions. »[15]. L’intégration des sources de données hétérogènes ayant des structures différentes est le principal objectif de la naissance des entrepôts de données. Cependant, l’entrepôt de données joue un rôle stratégique dans la vie d’une entreprise. Il stocke des données pertinentes aux besoins de prise de décision en provenance des systèmes opérationnels de l’entreprise et d’autres sources externes. A la différence d’une base de données classique supportant des requêtes transactionnelles de type OLTP (On-Line Transaction Processing), un entrepôt de données est conçu pour supporter des requêtes de type OLAP (On-Line Analytical Processing). L’interrogation est l’opération la plus utilisée dans le contexte d’entrepôt de données où la mise à jour consiste seulement à alimenter l’entrepôt. Le tableau I.1 montre la différence entre un système opérationnel doté d’une base de données classique et un entrepôt de données [12].

Modélisation d’un entrepôt de données

Les données manipulées dans le contexte d’entrepôts de données sont représentées sous forme multidimensionnelle qui est mieux adaptée pour le support des processus d’analyse [16]. Ce modèle permet d’observer les données selon plusieurs perspectives ou axes d’analyse et facilite l’accès aux données. Deux concepts fondamentaux caractérisent le modèle multidimensionnel : faits et dimensions. Un fait représente le sujet analysé, il est formé de mesures correspondant aux informations de l’activité étudiée. Ces mesures sont calculables à partir d’un grand nombre d’enregistrements en appliquant les opérations d’addition, de calcul du minimum ou de la moyenne, etc. [17]. Par exemple pour la gestion des commandes client, les mesures peuvent être la quantité de produits commandés, le montant de la commande, etc. La dimension représente l’axe d’analyse de l’activité. Elle regroupe des paramètres et des informations qui peuvent influencer sur les mesures d’activités du fait. Si on considère l’analyse de la quantité de produits vendus, il est évident que cette quantité varie selon la nature des données présentes dans la dimension produite. C’est ainsi que les dimensions doivent fournir des règles de calculs pour chaque mesure. L’implémentation du modèle multidimensionnel sur un SGBD réel peut se faire selon deux modèles : MOLAP (Multidimensional On-Line Analytical Processing) et ROLAP (Relational On-Line Analytical Processing). Nous décrivons ces deux implémentations dans la section suivante.

MOLAP

Les systèmes de type MOLAP constituent une approche qui permet de représenter les données de l’entrepôt sous la forme d’un tableau multidimensionnel à n dimensions, où chaque dimension de ce tableau est associée à une dimension de l’hyper cube de données. La figure I.3 représente un tableau multidimensionnel pré-calculant le volume de ventes effectuées par type de produit (dimension Produit), trimestre (dimension Temps) et ville (dimension Client). Les systèmes MOLAP nécessitent un pré-calcul de toutes les agrégations possibles afin de les matérialiser dans les cellules du tableau multidimensionnel. L’avantage principal de cette implémentation est le gain considérable en temps d’exécution des requêtes, vu que l’accès aux données est direct. Par contre, les opérations de mise à jour sont difficiles à effectuer compte tenu que les valeurs des cellules du tableau multidimensionnel doivent être recalculées après chaque opération de mise à jour.

Les motifs fréquents

L’extraction de connaissances dans les bases de données (ECBD) est « le processus non trivial d’extraction d’informations valides, implicites, potentiellement utiles et ultimement compréhensibles à partir de grandes bases de données » [35]. De nombreuses applications dans divers domaines ont bénéficié des techniques de l’ECBD et de nombreux travaux ont été menés sur ce sujet. Un des grands problèmes traités par ECBD, et l’extraction des motifs fréquents. La découverte des motifs fréquents consiste à trouver des groupements d’items apparaissant ensemble avec une fréquence significative. La découverte de ces motifs fréquents constitue l’étape principale de résolution de certain nombre de problèmes de l’ECBD [11] comme le problème de motifs fermés [10] et de motifs tolérants [1]. Dans le cadre de conception physique des entrepôts des données, il existe deux travaux qui se basent sur l’utilisation d’une méthode d’extraction des motifs fréquents dans leurs méthodes d’optimisation utilisé (plus précisément les IJBs). Nous inspirons de ces deux travaux, notre travail d’optimisation des entrepôts des données qui est base sur l’utilisation de l’une de ses algorithmes (Motif à base tolérance de faute). A ce point, Nous abordons dans ce chapitre les différents concepts de cette méthode et une présentation des deux algorithmes (Close et Charm) utilises dans les travaux précédents [28][29].

L’algorithme CLOSE pour la recherche des motifs fréquents La génération des motifs fréquents est une tâche compliquée, car le nombre de motifs fréquents peut exploser lorsque le nombre de motifs initial est important. Pour réduire cette complexité, l’algorithme CLOSE génère les motifs fréquents fermés, ils se basent sur la propriété de Galois [10]. L’ensemble des motifs fréquents peut être généré directement à partir de l’ensemble des motifs fréquents fermés. L’algorithme se base sur les étapes suivantes : L’algorithme CLOSE parcourt l’ensemble des générateurs des motifs fermés fréquents par niveaux. À l’étape k = 1, l’ensemble des 1-générateurs est initialisé aux 1- itemsets. À chaque itération, l’algorithme considère un ensemble de k-itemsets générateurs. Il construit un ensemble de motifs fermés candidats qui sont les fermetures de ces k-générateurs et détermine ensuite parmi ces candidats les motifs fermés fréquents selon le seuil minimal du support minsup. Finalement, il crée les (k + 1)-générateurs qui seront utilisés lors de l’itération suivante afin de construire l’ensemble des motifs fermés candidats qui sont les fermetures des (k + 1)-générateurs. Un balayage du contexte d’extraction est nécessaire durant chaque itération, afin de déterminer les fermetures des k-générateurs et calculer leurs supports. Si l’ensemble de k-générateurs fréquents est vide, l’algorithme s’arrête. Sinon, ce nouvel ensemble de (k +1)-générateurs est utilisé à l’itération suivante stocke un ensemble FFk contenant les k-générateurs fréquents, leur fermeture qui est des itemsets fermés fréquents et leurs supports. Exemple 2.2 La figure II.2 Présente le résultat d’application l’algorithme Close sur la base transactionnelle D définit dans l’exemple 3, avec un minsup =3.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport gratuit propose le téléchargement des modèles gratuits de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Chapitre I : les entrepôts de données
I.1) Architecture et modélisation des entrepôts de données
I.1.1) Architecture d’un entrepôt de données
I.1.2) Modélisation d’un entrepôt de données
I.1.2.1) MOLAP
I.1.2.2) ROLAP
I.1.3) les structures d’optimisation des entrepôts de données
I.1.3.1) Les techniques redondantes
I.1.3.2) Les techniques non redondantes
Chapitre II : les motifs fréquents
II.1) Extraction des motifs fréquents
II.1.1) Motifs fréquents
II.1.2) Algorithmes A-priori
II.2) Extraction des motifs fermes
II.2.1) Les motifs fréquents fermes
II.2.2) L’algorithme CLOSE pour la recherche des motifs fréquents
II.3) Itemsets fréquent au Faute tolérant
II.3.1) Notation
II.3.2) Définitions
II.3.2.1) Relaxation transaction
II.3.2.2) Relaxation item
II.3.2.3) Relaxation motif
II.3.2.4) L’approche d’extraction des motifs faute tolérants
II.3.3) Algorithme d’Adrian et al
II.3.3.1) Problématique
II.3.3.2) Structure et Algorithme
II.3.3.3) La complexité globale
II.4) Evaluation des 3 Algorithmes
Chapitre III : les index de jointures binaire
III.1) La techniques d’optimisation redondantes : les index
III.1.1) Index B-arbre
III.1.2) Index de hachage
III.1.3) Index binaire (bitmap index
III.1.4) Index de jointure
III.1.5) Index de jointure binaire
III.1.5.1) La construction de l’index de jointure binaire IJB
III.1.5.2) Stratégie d’exécution en présence des IJB
III.2) Problème de sélection des index de jointure binaires
III.2.1) Formalisation
III.2.2) Complexité
III.2.3) Travaux de sélection d’une configuration index
III.2.3.1) travaux de Aouiche
III.2.3.2) l’approche de Bellatreche et al
III.3) Modèle de coût
III.3.1) les types de modèle de cout utilisé
III.3.2) principe de modèle de cout théorique
III.3.2.1) Paramètres utilisés dans le modèle de coût
III.3.2.2) Coût de stockage d’un IJB
III.3.2.3) Coût d’exécution
III.3.3) Les Scénarios de cout d’exécution
III.3.3.1) Scénario 1
III.3.3.2) Scénario 2
III.3.3.3) Scénario 3
Chapitre IV : sélection configuration index à base tolérance de faute
IV.1) Motivation
IV.2) Démarche de sélection automatique d’index
IV.2.1) Analyse de la charge
IV.2.2) Construction du contexte d’extraction
IV.2.3) Application de l’approche MFFT
IV.2.4) Construction de l’ensemble d’index candidats
IV.2.4.1) Application de la fonction fitness
IV.2.4.2) Purification des motifs fréquents _
IV.2.5) la sélection de la configuration finale
IV.5) Des études expérimentales
IV.5.1) L’entrepôt de données
IV.5.2) Charge de requêtes
IV.5.3) Evaluation
IV.4) L’application de validation