Integration Donnees - Construction Raffraichissement - 30p Guerrero
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Integration Donnees - Construction Raffraichissement - 30p Guerrero as PDF for free.
More details
- Words: 10,186
- Pages: 29
RAPPORT DE RECHERCHE Entrep^ots de Donnees : Synthese et Analyse Edgard Bentez-Guerrero, Christine Collet, Michel Adiba
RR 1017-I-LSR 8
Mai 1999
Entrep^ots de Donnees : Synthese et Analyse Edgard Bentez-Guerrero, Christine Collet, Michel Adiba Laboratoire Logiciels, Systemes, Reseaux - IMAG BP 72, 38402 Saint Martin d'Heres Cedex e-mail : fEdgard.Benitez, Christine.Collet, [email protected] Resume Nous presentons les principaux aspects autour de la notion (( entrep^ot de donnees )) dans le domaine des bases de donnees. Tout d'abord, nous introduisons les caracteristiques d'un entrep^ot et les comparons avec celles presentees par une base de donnees traditionnelle. Nous decrivons ensuite le modele conceptuel et le modele logique utilises pour concevoir un entrep^ot. Nous abordons le processus de construction et les techniques de rafra^chissement periodique d'un entrep^ot avant de discuter les aspects relatifs a son stockage et sa gestion. Nous parlons aussi des techniques d'analyse (l'OLAP, l'orpaillage et la visualisation) qui peuvent ^etre appliquees sur l'entrep^ot. En n, nous identi ons un ensemble de perspectives de recherche dans ce domaine.
Mots clef : Entrep^ot de Donnees, Cube de Donnees, Schema en Etoile, Rafra^-
chissement Periodique, SGBD Multidimensionnel, Vues Materialisees, OLAP, Orpaillage, Visualisation.
1 Introduction Les Entrep^ots de Donnees sont indispensables a la prise de decisions et, pour cette raison, ils sont devenus des elements strategiques pour les entreprises. Le marche estime pour les produits et les services autour des technologies des entrep^ots de donnees a eu une croissance enorme: il est passe de 2 milliards de dollars en 1994 a 8 milliards de dollars en 1998 CD97]. Une etude realisee en 1996 par le Data Warehousing Institute DWI98], une organisation americaine de professionnels, indique que sur les 6000 entreprises enqu^etees, plus de 40% ont debute la mise en place d'un entrep^ot et plus de 30% ont prevu de le faire dans les 3 ans Fra97]. De plus, des entrep^ots ont ete mis en place avec succes dans plusieurs industries telles que la fabrication, le commerce, les services nanciers, le transport, les telecommunications, la medecine CD97] et dans les universites HGML+ 95]. Le theme des entrep^ots de donnees a donc donne lieu a de nombreux travaux de developpement et de recherche sur une periode de temps tres courte MH98] Gre98]. De nombreux concepts ont ete proposes et il est parfois dicile de s'y retrouver. Cet article tente de synthetiser les principaux concepts associes aux entrep^ots de donnees. Il est organise de la maniere suivante : la section 2 presente la denition et la structure des entrep^ots et la section 3 decrit le modele d'organisation des donnees d'un entrep^ot. La construction et le rafra^chissemen d'un entrep^ot sont introduits dans la section 4. Le stockage et la gestion des donnees d'un entrep^ot sont presentes dans 1
Entrep^ots de Donnees : Synthese et Analyse
2 Caracteristique Donnees Usage Unite de travail Nombre de donnees accedees Mode d'acces
Base de Donnees Courantes Support de l'operation de l'entreprise Transaction Dizaines Lecture/E criture
Type d'utilisateur Employe Nombre d'utilisateurs Mille Tab.
Entrep^ots de Donnees Historiques Support de l'analyse de l'entreprise Requ^ete Millions Lecture (principalement) Decideur Cent
1 { Bases de Donnees vs Entrep^ots de Donnees
la section 5. Les systemes OLAP, l'orpaillage et la visualisation sont abordes dans la section 6 et nalement la section 7 conclut cet article.
2 Entrep^ots de Donnees et Bases de Donnees Le concept Entrep^ot de Donnees surgit a partir des besoins d'analyse des donnees d'une entreprise pour chercher des avantages competitives sur la concurrence. Les bases de donnees des systemes existants de type On-Line Transaction Processing (OLTP) ne sont pas appropiees comme support de ces analyses parce qu'elles ont ete con cues pour des fonctions speciques realises dans l'entreprise. Donc, les donnees pertinentes pour faire des analyses se trouvent disseminees entre plusieurs bases. De plus, leur conception vise a ameliorer les performances des systemes OLTP par rapport au traitement d'un grand nombre de transactions (courtes et frequentes) de mise-ajour, ce qui complique l'interrogation. Un entrep^ot de donnees, par contre, o re des donnees integrees, consolidees et historisees pour faire des analyses. Il s'agit d'une collection de donnees pour le support d'un processus d'aide a la decision Inm92] Inm95]. Les donnees d'un entrep^ot possedent les caracteristiques suivantes : { Orientation sujet. Les donnees d'un entrep^ot s'organisent par sujets ou themes. Cette organisation permet de rassembler toutes les donnees, pertinentes a un sujet et necessaires aux besoins d'analyse, qui se trouvent repandues a travers les structures fonctionnelles d'un entreprise. { Integration. Les donnees d'un entrep^ot sont le resultat de l'integration de donnees en provenance de multiples sources ainsi, tous les donnees necessaires pour realiser une analyse particuliere se trouvent dans l'entrep^ot. L'integration est le resultat d'un processus qui peut devenir tres complexe du a l'heterogeneite des sources. { Histoire. Les donnees d'un entrep^ot representent l'activite d'un entreprise pendant une longue periode ou il est important de gerer les di erentes valeurs qu'une donnee prises au cours du temps. Cette caracteristique donne la possibilite de suivre une donnee dans le temps pour analyser ses variations.
Bentez-Guerrero, Collet, Adiba
3
{ Non-volatilite. Les donnees chargees dans l'entrep^ot sont surtout utilisees en interrogation et ne peuvent pas ^etre modiees, sauf dans certains cas de rafra^chissement. Construction Rafraîchissement Bases de Données Sources Externes
Fig.
Extraction Epuration Chargement
Stockage
Entrepôt de Données
Analyse
OLAP Orpaillage Visualisation
Systèmes Decisionnels
1 { L'Entrep^ot de Donnees est la base des systemes decisionnels
L'entrep^ot de donnees (ED) joue un r^ole strategique dans une entreprise comme le montre la gure 1. Il stocke des donnees interessantes en provenance des systemes OLTP de l'entreprise et d'autres sources externes. Avant d'^etre chargees dans l'entrep^ot, les donnees selectionnees doivent ^etre extraites des sources et soigneusement epurees, pour eliminer des erreurs et reconcilier les di erences semantiques. A partir des donnees d'un ED de nombreuses analyses peuvent avoir lieu pour cela, il faut associer aux systemes decisionnels des techniques d'analyse tels que celles de type On-Line Analytical Processing (OLAP), d'orpaillage et de visualisation. L'information et la connaissance obtenues par l'exploitation d'un entrep^ot sont directement traduisibles en beneces pour l'entreprise (augmentation des ventes au travers d'un marketing mieux cible, amelioration des taux de rotation des stocks, etc.) Fra97]. Comme exemple, considerons une cha^ne de magasins repartis geographiquement dans plusieurs pays, comme la France et le Mexique. L'analyse globale de la cha^ne est une t^ache tres compliquee, mais un entrep^ot de donnees fournit le cadre ideal pour l'e ectuer. L'entrep^ot s'organise autour des sujets les plus importants pour la cha^ne, c'est a dire, les produits qui ont ete vendus dans les magasins au cours du temps. Les donnees necesaires pour e ectuer des analyses sont extraites de di erents bases de donnees et chiers (utilises par chaque magasin pour supporter ses activites quotidiennes de ventes) et integrees dans l'entrep^ot. A partir de cet entrep^ot, le gestionnaire de la cha^ne peut e ectuer des analyses et prendre des decisions qui a ecteront les activites futures de l'entreprise. Les donnees d'un entrep^ot se structurent selon deux axes : synthetique et historique (cf. gure 2) Fra97]. L'axe synthetique etablit une hierarchie d'agregation et comprend les donnees detaillees (qui representent les evenements les plus recents au bas de la hierarchie), les donnees agregees (qui synthetisent les donnees detaillees) et les donnees fortement agregees (qui synthetisent a un niveau superieur les donnees agregees). L'axe historique comprend les donnees detaillees historisees, qui representent des evenements passes. Les meta donnees contiennent des informations concernant les donnees dans l'entrep^ot, telle que leur provenance et leur structure, ainsi que les methodes utilisees pour faire l'agregation. L'entrep^ot de donnees se trouve souvent stocke et gere par un systeme de gestion de bases de donnees (SGBD) dans un ordinateur non lie aux systemes OLTP de l'entreprise. La principale raison pour e ectuer cette separation est la degradation eventuelle des performances des systemes OLTP provoque par l'execution des
Entrep^ots de Donnees : Synthese et Analyse
4
Données fortement agregées M e t a
Axe synthétique
D o n n é e s
Données agregées
Données detaillées
Données detaillées historisées
Axe historique
Fig.
2 { La structure d'un Entrep^ot de Donnees
processus d'analyse sur les donnees de l'entrep^ot Gup97b]. La haute performance du traitement des transactions et les courts temps de reponse sont tres importants dans un systeme OLTP. Cependant ces caracteristiques ne sont pas critiques pour les processus d'analyse de l'entrep^ot, ou les chemins d'acces aux donnees sont diciles a denir a priori et le temps de reponse n'est pas rigide. Pour construire un entrep^ot, il faut adopter des techniques de conception et de mise en oeuvre totalement di erentes de celles utilisees pour construire un systeme OLTP. Dans la section suivante, nous abordons la problematique de la modelisation d'un entrep^ot.
3 Modelisation de l'Entrep^ot La conception d'un entrep^ot de donnees est tres di erente de celle des bases de donnees des systemes OLTP, parce qu'il faut penser en termes de concepts plus ouverts et plus diciles a denir. De plus, les besoins des utilisateurs de l'entrep^ot ne sont pas aussi clairs que ceux des utilisateurs des systemes OLTP. Dans la suite de cette section, nous expliquons le modele conceptuel des entrep^ots de donnees : le modele multidimensionnel de donnees.
3.1 Modele Multidimensionnel de Donnees
La conception des bases de donnees est en general basee sur le modele EntiteRelation (E-R). Ce modele permet de faire la description des relations entre donnees elementaires (entites) en cherchant l'elimination des redondances, ce qui provoque
Bentez-Guerrero, Collet, Adiba
5
l'introduction d'un nombre important de nouvelles entites. Ainsi, l'acces aux donnees devient complique et le diagramme genere devient dicile a comprendre pour une personne. Pour cette raison, l'utilisation de la modelisation E-R pour la conception d'un ED n'est pas appropriee Col96b]. Le modele multidimensionnel de donnees (MMD) est une alternative mieux adaptee aux besoins de l'analyse des donnees d'un entrep^ot Kim96]. Ce modele permet d'observer les donnees selon plusieurs perspectives ou axes d'analyse, facilite l'acces aux donnees et en plus est facile a comprendre y compris pour les personnes qui ne sont pas expertes en informatique. Pour cette raison, ce modele a ete adopte par les praticiens Kim97] Inm92] et par les chercheurs des bases de donnees AGS95] TDV97] pour organiser les donnees d'un entrep^ot.
P1
PRODUIT
1000
P2
1996 TEMPS 1995
P3 1994 Lyon
Grenoble
Annecy
MAGASIN
Fig.
3 { Un exemple de Cube de Donnees
3.1.1 Le Cube de Donnees
Le constructeur fondamental du modele multidimensionnel est le Cube de Donnees (ou simplement cube 1 ) TDV97]. Un cube organise les donnees en une ou plusieurs dimensions qui determinent une mesure d'inter^et. Une dimension specie la maniere dont on regarde les donnees pour les analyser, alors qu'une mesure est un objet d'analyse. Chaque dimension est formee par un ensemble d'attributs et chaque attribut peut prendre di erentes valeurs. Les dimensions possedent en general des hierarchies associees qui organisent les attributs a di erents niveaux pour observer les donnees a di erentes granularites. Une dimension peut avoir plusieurs hierarchies associees, chacune speciant di erentes relations d'ordre entre ses attributs. Considerons un modele multidimensionnel pour la cha^ne de magasins. Dans ce cas, la mesure d'inter^et est la Quantite d'un PRODUIT vendu dans un MAGASIN (represente par la ville auquel il appartient) a un instant du TEMPS. La gure 3 presente le cube VENTES, qui montre que 1000 unites du produit P1 ont ete vendus en 1994 dans le magasin situe a Annecy. 1. En geometrie, un cube designe un corps solide a six faces carrees de taille egale dans le modele multidimensionnel, un cube est une maniere d'organiser des donnees et, en realite, ce n'est pas un cube. Cependant, ce terme est utile pour comprendrele modele en utilisant une metaphoregraphique. Pour cette raison, dans cet article nous continuerons a utiliser ce terme.
Entrep^ots de Donnees : Synthese et Analyse
6
Les donnees multidimensionnelles sont de nature eparse car il est possible que seulement un nombre tres faible des cellules d'un cube aient une valeur. Par exemple, les produits ne sont pas tous vendus dans tous le magasins pendant les m^emes periodes de temps. Si l'on considere que la cha^ne de magasins possede 50 magasins, vend 1000 produits et a opere pendant 3 annees (1095 jours), alors il y a plus de 5 millions de combinaisons possibles (au niveau jour), chacune avec une vente potentielle. Si l'on suppose que les donnees sont disponibles pour seulement 1% de ventes (plus de 5000), on peut dire qu'il y a une dispersion de 99%.
P R
P1
100
80
M
91
D
200
1000
100
Grenoble
220
800
80
Annecy
300
500
91
G P2
1000
800
500
A
U I
Lyon A
O
S P3
200
220
300
T
1994 Lyon
Grenoble
1996 1995 TEMPS
I
1996 1995
N
1994 P3
Annecy
P2
TEMPS
P1
PRODUIT
MAGASIN
Fig.
4 { Data Slice
E tant donnee la representation sous forme de Cube d'un entrep^ot, plusieurs operations ont ete proposees Sah95]: { Slice ou Rotation { Dice { Roll-Up et Drill-Down
P1
P1 PRODUIT
PRODUIT
P2
1996
P3 1994 P3 1994 Lyon
Grenoble
1996 1995 TEMPS
Annecy
MAGASIN
Fig.
5 { Data Dice
Lyon
Annecy
MAGASIN
TEMPS
Bentez-Guerrero, Collet, Adiba
7
La Rotation ou Slice permet d'avoir acces aux di erentes vues de donnees sans les reordonner physiquement. Pour un cube a 3 dimensions il existe six vues possibles et pour 4 dimensions, 12. En general, un cube de n dimensions a n (n ; 1) vues possibles. On denote l'operateur Slice par Slicedimension (CUBE ). La gure 4 presente le resultat de l'application de l'operateur Slice sur le cube VENTES selon la dimension MAGASIN et qui est denotee par : SliceMAGASIN (V ENTES ). L'operateur Dice permet de restreindre les valeurs dans une ou plusieurs dimensions. On va denoter cet operateur par Dicerestriction (CUBE ). Ainsi, la gure 5 presente le resultat de l'application de Dice sur les cube VENTES pour selectionner les ventes des produits P1 et P3 dans les magasins de Lyon et de Annecy pendant les annees de 1994 et de 1996 et qui est denotee par : DicePRODUIT 6=P 2^MAGASIN 6=Grenoble^TEMPS 6=1995 (V ENTES )
ROLL-UP DRILL-DOWN
1998 1997 TEMPS 1996 1995 1994 P1 P R O D U I T
1998 1997 1996 1995 1994
1998 1997 1996 1995 1994
TEMPS
TEMPS
P1
P1 P R O D U I T
P2 P3 P4 P5
P R O D U I T
P2 P3 P4
MAGASIN
Rhône Alpes Lyon
ville
Grenoble
Ile de France
Annecy
Rhône Alpes
région
P3 P4 P5
P5
Lyon Grenoble Annecy Paris Creteil
P2
France
Paris
Creteil
Ile de France
France
pays
Fig.
6 { Roll Up et Drill Down
Les operateurs Roll-Up et Drill-Down autorisent l'analyse de donnees a di erents niveaux d'agregation en utilisant des hierarchies associees a chaque dimension. L'operateur Roll-Up e ectue l'agregation des mesures allant d'un niveau particulier vers un general, alors que Drill-Down realise l'operation inverse. On denote l'operateur Rollsuperieur Up par RollUpniveau niveau inferieur (CUBE ), alors que l'operateur Drill-Down est denote inferieur par DrillDownniveau niveau superieur (CUBE ). La gure 6 montre l'application des operateurs Roll-Up et Drill-Down sur la dimension MAGASIN, qui a associee la hierarchie \ville!region!pays". Cette hierarchie determine les relations qui existent entre villes et regions, et entre regions et pays. La gure montre aussi une instance possible de cette hierarchie, qui regroupe les villes
Entrep^ots de Donnees : Synthese et Analyse
8 Formalisme
Introduction Operateurs des hierarchies Hypercube Fonctions Pull, Push, Destroy Dimension, (Agrawal et. al., 1995) Restriction, Merge, Join Cube Relations Add Dimension, Transfer, RC-Join Multidimensionnel Construct, Cube Aggregation, (Li et Wang, 1996) Union Table Fonctions Unfold, Fold, Selection N-Dimensionnelle Projection, Renaming, Union (Gyssens et Intersection, Di erence, Lakshmanan, 1997) Sumarization, Classication Cube Ordre partiel Pull, Push, Partition (Thomas et. al., 1997) entre attributs Aggregation, Cartesian Product, Join, Union, Di erence F-table Ordre partiel Roll-Up (Cabibbo entre attributs et Torlone,1998) Tab.
2 { Formalismes proposes
de Paris et Creteil dans la region Ile-de-France et les regions Rh^one-Alpes et Ile-deFrance dans le pays France. Pour determiner le total de ventes au niveau region, il faut appliquer l'operateur Roll-up sur la dimension MAGASIN, en sommant les totaux de chaque ville: RollUpregion ville (V ENTES ) Le m^eme mecanisme s'applique si on veut calculer le total de ventes au niveau Pays, en sommant les ventes totales de chaque region. L'operateur Drill-Down e ectue les operations inverses : DrillDownville region (V ENTES )
3.1.2 Quelques Formalismes Proposes
Le modele multidimensionnel de donnees a attire l'attention de la communaute industrielle et maintenant de nombreux produits bases sur ce modele se trouvent sur le marche ( Ken97], App98], AS98], par exemple). Les services proposes par ces produits visent a couvrir les besoins des utilisateurs et chaque produit fournit sa propre vision du modele et des operations associees. Donc il n'existe pas (i) un formalisme independant de la mise en oeuvre qui autorise la denition de dimensions structurees avec hierarchies multiples et mesures complexes, et (ii) un langage d'interrogation sous-jacent qui facilite l'ecriture de requ^etes complexes dont les agregations ad hoc soient autorisees AGS95] BSHD98]. Pour pallier cette situation, la communaute de recherche a propose plusieurs formalismes (cf. table 2).
Hypercube Agrawal et al. AGS95] proposent un modele base sur la notion d'hypercube. Un hypercube est determine par k dimensions et ses elements (cellules) sont denies par une fonction qui associe a une combinaison de valeurs des dimensions (i)
Bentez-Guerrero, Collet, Adiba
9
la valeur 0, si la combinaison n'existe pas dans la base de donnees, (ii) la valeur 1, si la combinaison existe, ou (iii) un n-uplet, s'il existe de l'information supplementaire associee aux elements la description des composants d'un n-uplet est stockee comme une meta donnee. Ce modele utilise des fonctions pour la denition de hierarchies multiples et d'agregations ad-hoc.
<1000, ...>
P1 P R O D U I T
P2
1
P1
<1000, ...><1000, ...> <2000, ...> 1996 TEMPS 1995
P3
P R O D U I T
P2
1
1 1 3000 QUANTITE 2000
P3
1994 Lyon
Grenoble MAGASIN
(a)
Annecy
1000 Lyon
Grenoble
Annecy
MAGASIN
(b)
7 { L'HyperCube de Agrawal et al. Les elements de l'hypercube (a) prennent des n-uplets ou 0 comme valeur alors que ceux de (b) prennent les valeurs 1 ou 0 Fig.
Les operateurs (cf. table 2) ont une semantique bien denie et forment un ensemble minimal (un operateur ne peut pas ^etre elimine sans perte des fonctionnalites) bien que leur denition soit complexe a cause de l'introduction des fonctions pour representer les hierarchies. Les operateurs proposes peuvent ^etre composes pour construire d'autres operateurs de type relationnel tels que la Projection, l'Union, l'Intersection et la Di erence, ainsi que l'agregation comme Roll-Up et Drill-Down. Cette approche vise une mise en oeuvre sur un SGBD Relationnel et semble plut^ot pragmatique. La gure 7(a) presente l'hypercube VENTES dont les dimensions sont PRODUIT, MAGASIN et TEMPS, et ses elements sont des n-uplets (par exemple < 1000 : : : > pour l'element qui correspond a PRODUIT = P 2, MAGASIN = Lyon et TEMPS = 1994) ou la valeur 0 (pour les elements non representes dans la gure). La meta donnee de description des elements est une annotation de l'hypercube (dans ce cas le n-uplet < Quantite : : : >). La gure 7(b) presente un autre hypercube avec les dimensions PRODUIT, MAGASIN et QUANTITE et ses elements prennent la valeur 1 (par exemple, l'element qui correspond a PRODUIT = P 2, MAGASIN = Lyon et QUANTITE = 1000) ou bien la valeur 0.
Cube Multidimensionnel Pour Li et Wang LW96] une base de donnees multi-
dimensionnelle est un ensemble ni de Cubes Multidimensionnels et un ensemble ni de relations. Un Cube Multidimensionnel consiste en un certain nombre de relations (les dimensions) et pour chaque combinaison de n-uplets, un n-uplet pour chaque dimension, il existe une valeur associee (une mesure). Dans ce modele, les mesures ne peuvent ^etre que des valeurs numeriques. Les auteurs introduisent la notion de relations de regroupement comme moyen pour representer des hierarchies. Les operateurs (cf. table 2) prennent des cubes et relations en entree et produisent des cubes en sortie. Ils peuvent ^etre composes pour exprimer des requ^etes complexes.
Entrep^ots de Donnees : Synthese et Analyse
10
La gure 8(a) montre le cube multidimensionnel VENTES forme par les relations PRODUIT, MAGASIN et TEMPS. Pour les n-uplets MAGASIN =< Grenoble >, PRODUIT = < P 1 10 Noir > et TEMPS = < 15 Mai 1996 >, il existe la valeur associee 100. La partie (b) de la gure 8 montre la relation qui regroupe les villes de Grenoble, Lyon et Annecy dans la region Rh^one-Alpes et les villes de Creteil et Paris dans la region Ile-de-France. PRODUIT
MAGASIN
TEMPS
Nom
Poids
Couleur
Grenoble
P1
10
Noir
15
Mai
1996
100
Grenoble
P2
10
Noir
15
Mai
1996
80
Annecy
P1
20
Noir
15
Mai
1996
80
Lyon
P2
20
Blanc
15
Mai
1996
60
Creteil
P1
10
Blanc
15
Mai
1996
110
Paris
P2
10
Blanc
15
Mai
1996
150
(a)
Jour Mois Année
Quantité
Ville
Region
MAGASIN.Ville
Rhône-Alpes Rhône-Alpes Rhône-Alpes Ile-de-France Ile-de-France
Grenoble Annecy Lyon Creteil Paris
(b)
8 { Le Cube Multidimensionnel de Li et Wang. (a) Cube Multidimensionnel. (b) Relation de regroupement Fig.
Tables N-dimensionnelles Gyssens et Lakshmanan proposent dans GL97] un
formalisme autour de la notion de table n-dimensionnelle. Une instance de ce type de table est un ensemble de relations, une pour chaque dimension et une autre pour les cles de dimension et les mesures respectives. Les hierarchies ne sont pas explicitement mentionnees et elles sont incorporees en denissant des fonctions. Les operateurs proposes (cf. table 2) prennent en entree un cube et produisent en sortie un autre cube. Les auteurs montrent qu'une table n-dimensionnelle peut ^etre representee par une relation classique et vice-versa et c'est a partir de ce resultat qu'ils developpent la semantique des operateurs. En fait, chaque operateur convertit la table structuree ndimensionnelle en une relation classique, e ectue les operations necessaires et convertit cette relation en une table n-dimensionnelle. Les operateurs proposes peuvent ^etre composes pour en exprimer d'autres, comme Roll-Up. La gure 9(a) presente la table bi-dimensionnelle VENTES avec les dimensions PRODUIT et TEMPS, et la mesure VENTES. Les attributs Nom et Poids sont associes a PRODUIT, alors que les attributs Mois et Annee sont associes a TEMPS. On peut voir dans cette gure que 100 unites du produit P1 ont ete vendus au mois de Janvier 1996. La partie (b) de la m^eme gure presente une instance de VENTES, qui est formee par les relations rPRODUIT, rTEMPS et rm. Chaque n-uplet des relations rPRODUIT et rTEMPS est vue comme une \coordonnee" dans les dimensions PRODUIT et TEMPS respectivement, alors qu'un n-uplet de rm represente la valeur associee a une combinaison de coordonnees, une coordonnee pour chaque dimension.
Cube Pour Thomas et. al. TDV97] une base de donnees multidimensionnelle est
un ensemble de cubes, denis en termes de dimensions, mesures, attributs et fonctions qui associent les attributs aux dimensions. Il est possible de denir des schemas
Bentez-Guerrero, Collet, Adiba
VENTES
P R O D U I T
Nom P1 P2
11
Poids
Année
1996
Mois
Jan
1997 Fev
....
Jan
Fev
80 120 .... 50 70 ....
100 160 .... 60 75 ....
....
Vente 100 80 .... 50 60 ....
10 20 .... 10 20 ....
VENTES rTEMPS
rPRODUIT
TEMPS
80 100 .... 60 80 ....
Tid
Nom
Poids
Tid
Année
Mois
t1 t2 t3 t4 ....
P1 P1 P2 P2 ....
10 20 10 20 ....
t1 t2 t3 t4 ....
1996 1996 1997 1997 ....
Jan Fev Jan Fev ....
rm P.Tid
T.Tid
Quantité
t1 t2 .... t1 t2
t1 t1 .... t2 t2
100 80 .... 80 100
(b)
(a)
9 { Table N-Dimensionnelle de Gyssens et Lakshmanan. (a) Table bi-dimensionnelle (b) Instance de la table bi-dimensionnelle Fig.
de cubes, qui specient de maniere abstraite la structure d'un cube. A partir d'un schema, des instances peuvent ^etre creees. Les hierarchies ne sont pas explicitement representees et elles doivent ^etre denies a priori comme un ordre partiel entre les attributs d'une dimension. Les operateurs de l'algebre proposee (cf. table 2) prennent en entree un cube et produisent en sortie un cube. Le modele fournit des denitions simples des operateurs algebriques, ou chaque operateur execute une fonction unique. Les operateurs peuvent ^etre composes pour denir d'autres operateurs comme Roll-Up et Drill-Down.
<1000>
P1 a1 = Nom P2 D1 = PRODUIT
1996 1995
P3 1994 Lyon
Grenoble
a3 = Année
D3 = TEMPS
Annecy
a1 = Ville D2 = MAGASIN
Fig.
10 { Le Cube de Thomas et al. Cette gure montre un cube et ses composants
La gure 10 montre le cube (instance de cube) VENTES deni par les dimensions D1 (PRODUIT), D2 (MAGASIN) et D3 (TEMPS). L'attribut a1 de la dimension PRODUIT est \nom", l'attribut a1 de la dimension MAGASIN est \ville" et l'attribut a3 de la dimension TEMPS est \annee".
Entrep^ots de Donnees : Synthese et Analyse
12
F-tables Cabibbo et Torlone CT98] proposent une formalisme autour de la notion
de f-table, qui est une fonction des coordonnees des dimensions aux mesures. Il est possible de specier le schema d'une f-table et de denir, a partir de ce schema, un ensemble d'instances. Ce formalisme autorise la structuration complexe des hierarchies dans une dimension, en denisant des ordres partiels entre ses attributs. Le langage d'interrogation CT97] est base sur la logique du premier ordre et donc autorise l'ecriture de requ^etes de fa con declarative. Ce langage permet l'incorporation des fonctions d'agregation mieux adaptes aux besoins du domaine d'application.
VENTES [v : ville <MAGASIN>, p : nom, j : jour ] : quantité
(a) Fig.
v
p
Grenoble
P1
15
Mai
j 1996
100
Grenoble
P2
15
Mai
1996
80
Annecy
P1
15
Mai
1996
80
Lyon
P2
15
Mai
1996
60
Creteil
P1
15
Mai
1996
110
Paris
P2
15
Mai
1996
150
VENTES
(b)
11 { Les f-tables de Cabbibo et Torlone. (a) Schema (b) Instance
On peut voir dans la partie (a) de la gure 11 le schema de la f-table qui represente les ventes de la cha^ne de magasins, mesurees en termes de la quantite vendue de produits. Les attributs \v", \p" et \j" de ce schema representent, respectivement, la dimension MAGASIN au niveau ville, la dimension PRODUIT au niveau nom et la dimension TEMPS au niveau jour. La partie (b) de la gure 11 montre une instance de ce schema. Malgre l'absence d'un formalisme conceptuel communement accepte, la communaute industrielle a developpe des modeles logiques ad hoc pour faire face aux pressions du marche et a la forte concurrence. Dans la section suivante, nous abordons les modeles logiques les plus utilises.
3.2 Modele Logique
Le modele multidimensionnel de donnees decrit dans la section precedente est implante directement par des systemes specialises, appeles SGBD Multidimensionnels, presentes dans la section 5. Cependant, la mise en oeuvre du modele du cube n'est pas restreinte a ce type de SGBD. La representation de donnees en relations en troisieme forme normale n'est plus appropriee pour un entrep^ot a cause du grand nombre de jointures et de restrictions pour un nombre eleve de relations KS95b]. Pour eviter ces desavantages, les schemas sous forme d'etoile, de "ocon de neige et de constellation de faits ont ete proposes.
3.2.1 Schema en etoile
Dans le schema en etoile Kim96], les mesures sont representees par une relation de faits et chaque dimension par une relation de dimension. La relation de faits reference
Bentez-Guerrero, Collet, Adiba
13
DIMENSION RELATION DE FAITS
Magasin
Ventes Produit
DIMENSION
Magasin
Produit
Magasin Ville Region Pays
Temps Produit
Quantité
Nom Poids Couleur
DIMENSION
Temps Temps Jour Mois Année
Fig.
12 { Schema en Etoile
les relations de dimension en utilisant une cle etrangere pour chacune et stocke les valeurs des mesures pour la combinaison des cles. Autour de cette relation gurent les relations de dimension qui regroupent les caracteristiques des dimensions. La relation de faits est normalisee et peut atteindre une taille importante par rapport au nombre de n-uplets par contre, les tables de dimension sont denormalisees (c'est a dire, des dependences fonctionnelles peuvent ^etre trouvees entre les attributs) et sont en general d'une faible taille. La gure 12 montre le schema en etoile pour le cube VENTES ou la relation de faits stocke la quantite de produits vendus et les relations correspondant a PRODUIT, a MAGASIN et a TEMPS comportent les informations interessantes sur ces dimensions.
3.2.2 Schema en forme de Flocon de Neige
Le schema en etoile ne re"ete pas les hierarchies associees a une dimension. Pour resoudre ce probleme, le schema en forme de "ocon de neige a ete propose. Ce schema normalise les dimensions, reduisant la taille de chacune des relations et permettant ainsi de formaliser la notion de hierarchie au sein d'une dimension Fra97]. La gure 13 montre les relations necessaires pour representer un niveau des hierarchies des dimensions MAGASIN et TEMPS.
3.2.3 Constellation de faits
Il est possible d'avoir plusieurs relations de faits pour representer les situations dans lesquelles les faits (mesures) ne sont pas determines par exactement le m^eme ensemble de dimensions. Dans ce cas, les relations de faits forment une famille KS95b] qui partage plusieurs relations de dimension mais ou chaque membre possede ses dimensions propres. Bien entendu, si les relations de faits partagent une dimension, il faut verier que cette dimension est exactement la m^eme. Le schema resultant s'appelle constellation de faits CD97]. Les schemas relationnels adaptes aux besoins du modele multidimensionnel possedent une serie d'avantages par rapport aux schemas en troisieme forme normale. L'etoile, le "ocon et la constellation autorisent l'expression des mesures, des dimensions et des hierarchies, d'une maniere simple qui permet de les distinguer clairement
Entrep^ots de Donnees : Synthese et Analyse
14
DIMENSION RELATION DE FAITS
Magasin
Region
Ventes Produit
DIMENSION
Magasin
Produit
Magasin Ville Region
Region Pays
Temps Produit
Quantité
Nom Poids Couleur
DIMENSION
Temps Temps Jour Mois
Fig.
Mois Mois Année
13 { Schema en Flocon de Neige
et donc ils sont faciles a comprendre. Ces schemas facilitent egalement l'acces aux mesures, m^eme si la taille d'un relation de faits est souvent importante, parce que le nombre de jointures est plus petit.
4 Construction et Rafra^chissement de l'Entrep^ot 4.1 Construction
Les donnees integrees dans un entrep^ot ont une grande valeur pour une entreprise. Or leur integration n'est pas une t^ache facile, parce qu'en general les donnees se trouvent disseminees dans de multiples sources qui possedent leurs propres structures, formats et denitions. En plus, ces sources peuvent contenir des erreurs, comme des valeurs manquantes, des valeurs illegales ou des contradictions, des valeurs incoherentes et des relations invalides Mos98]. Pour ces raisons, les donnees en provenance de sources heterogenes doivent ^etre traitees avant d'^etre chargees dans un entrep^ot Boh97]. Ce traitement se compose de trois phases : 1. Extraction des donnees a partir de leurs sources et conversion dans une representation intermediaire. 2. E puration par des mecanismes qui assurent leur qualite. 3. Chargement des donnees dans l'entrep^ot. Des estimations indiquent que la plupart du temps (80% en moyenne) de la construction d'un entrep^ot est dedie a ces t^aches Inm92]. Cependant, la plupart des entreprises sous-estiment la complexite de ce processus, m^eme s'il peut ^etre determinant pour le succes de l'entrep^ot et pour la qualite des analyses CM95].
4.2 Rafra^chissement Periodique
Le processus de detection de changements dans les sources et leur propagation vers l'entrep^ot est connu sous le nom de rafra^chissement WB97]. Ce processus se realise periodiquement et la periode depend des besoins des utilisateurs et de la charge
Bentez-Guerrero, Collet, Adiba
15
d'acces a l'entrep^ot. Les techniques de rafra^chissement peuvent ^etre classees dans deux categories : statiques et incrementielles BT98]. Les techniques statiques prennent une photographie des donnees sources a un instant particulier dans le temps. Dans cette categorie se trouvent la technique statique, celle basee sur des timestamps et celle basee sur la comparaison de chiers. La premiere est la technique la plus simple et consiste a prendre une photographie des sources et a reconstruire l'entrep^ot en utilisant celle-ci. La capture basee sur des timestamps utilise une information supplementaire (nommee timestamp) associee aux donnees et qui indique le temps de sa mise a jour la plus recente pour e ectuer la photographie des donnees dont la date du timestamp est posterieure a celle du dernier rafra^chissement. Finalement, la capture basee sur la comparaison de chiers consiste a comparer l'etat courant d'un chier avec l'etat anterieur pour trouver les di erences et les integrer dans l'entrep^ot. Les techniques incrementielles de rafra^chissement capturent les changements dans les sources au moment ou ils arrivent. Les techniques de capture assiste par l'application, par triggers et par le journal se trouvent dans cette categorie. La capture assistee par l'application requiert de la part des applications qui traitent les donnees sources d'identier les changements dans les donnees et de stocker ces changements dans une zone temporaire pour les utiliser an de rafra^chir l'entrep^ot. La capture assistee par triggers est tres semblable a la technique precedente mais la detection des changements et les diverses operations sont realisees par triggers dans la base de donnees. Finalement, la capture par le journal utilise cette information propre au SGBD pour chercher les changements interessants.
5 Stockage et Gestion Dans cette section, nous decrivons les techniques les plus importantes pour e ectuer le stockage et la gestion de donnees multidimensionnelles.
5.1 SGBD Multidimensionnel
Un SGBD Multidimensionnel (SGBDMD) est un SGBD capable de stocker et de traiter des donnees multidimensionnelles. Actuellement, il n'existe pas de cadre technologique commun pour le developpement des SGBDMD car chaque produit sur le marche (Essbase d'ArborSoft, Holos de Seagate, etc.) utilise sa propre version du modele multidimensionnel et ses propres strategies de stockage et de gestion. Il est possible cependant de distinguer la technique de array linearisation comme celle la plus utilisee pour le stockage des donnees multidimensionnelles Sho97]. Dans cette technique, un nombre est associe a chaque valeur possible d'une dimension. La position d'une cellule dans un vecteur multidimensionnel est la combinaison des nombres associes aux valeurs des dimensions qui determinent la cellule. Cette technique est appropriee lorsque l'espace multidimensionnelest dense dans le cas contraire, des techniques de compression doivent s'appliquer pour reduire l'espace de stockage. Les techniques d'indexation sont une solution alternative pour traiter la nature eparse des donnees. La plupart des SGBDMD utilisent une strategie a deux niveaux dans laquelle les dimensions denses sont indexees par une structure qui stocke les combinaisons de valeurs des dimensions eparses DSHB98]. Colliat Col96b] presente une generalisation a n niveaux de cette technique de base, ou un arbre B+ est construit
Entrep^ots de Donnees : Synthese et Analyse
16
a partir des combinaisons possibles des valeurs de dimensions eparses et dont les feuilles contiennent des pointeurs vers les blocs des dimensions denses.
5.2 SGBD Relationnel
Les systemes de gestion de bases de donnees relationnelles (SGBDR) representent environ 80% du marche des systemes de gestion de bases de donnees. De ce fait, la plupart des e orts qui visent a la construction d'un entrep^ot de donnees considerent ce type de systemes. Cependant, les SGBDR doivent ^etre adaptes parce qu'ils ne possedent pas les caracteristiques adequates pour repondre aux besoins des entrep^ots. Dans cette section, nous abordons ces adaptations.
5.2.1 Extensions du langage SQL
Le langage d'interrogation standard des SGBDR est SQL. Ce langage autorise l'expression de requ^etes pour les donnees relationnelles et fournit un ensemble de fonctions primitives pour les analyser. Cependant, les analyses les plus simples sont diciles voire impossibles a exprimer KS95a]. Pour faciliter l'expression des requ^etes pour analyser un entrep^ot, les communautes industrielle et de recherche ont propose des extensions a SQL. Dans la suite de cette section, nous abordons ces extensions. Le langage SQL fournit un ensemble de fonctions d'agregation telles que COUNT, SUM et AVG. Ces fonctions sont utiles mais insusantes pour analyser les donn ees d'un entrep^ot, ou les comparaisons (les ventes de cette annee comparees aux ventes de l'annee derniere) et le traitement sequentiel des donnees resultat d'une requ^ete (qui permet de conna^tre les 5 produits les plus vendus) sont necessaires. A ce propos, des fonctions comme RANK, PERCENTILE et d'autres de type nancier ont ete incorporees dans l'extension RISQL du SGBDR RedBrick RBS96]. Par exemple, la requ^ete suivante ordonne les produits par la quantite vendue et ache seulement les cinq les plus vendus : select from when
RANK (quantite) ventes RANK(quantite) <= 5
L'operateur cube propose par Gray et al. GCB+ 97] est la generalisation en n dimensions de l'operateur group-by. Cet operateur calcule les group-by pour tous les sous-ensembles possibles des n attributs (dimensions) et est equivalent a l'union de plusieurs operations group-by. L'operateur cube est base sur une representation relationnelle des donnees et utilise la valeur \ALL" pour denoter l'ensemble sur lequel est calculee chaque agregation. La requ^ete suivante calcule le cube pour les attributs de la relation ventes : select from group by cube
Produit, Magasin, Temps, SUM(quantite) ventes Produit, Magasin, Temps
La mise en oeuvre ecace de cet operateur a attire l'attention des chercheurs. Agarwal et al. AAD+ 96] modelisent les calculs e ectues par cube comme une hie-
Bentez-Guerrero, Collet, Adiba
17
rarchie d'operations de type group-by et proposent des algorithmes qui combinent des operations communes entre plusieurs group-by et qui utilisent des calculs deja e ectues pour en calculer d'autres. L'evaluation empirique montre que e ectivement l'utilisation de ces algorithmes ameliore les performances du calcul. D'autres extensions a SQL ont ete proposees. Par exemple, Gingras et Lakshmanan GL98] proposent, dans un contexte de federation de bases de donnees, le langage nDSQL. Ce langage elimine les di erences semantiques entre plusieurs bases de donnees relationnelles avec des schemas heterogenes et supporte des operateurs d'agregation comme cube.
5.2.2 Vues materialisees Une vue est une specication pour deriver une nouvelle relation a partir d'un ensemble de relations alors qu'une vue materialisee est l'extension (les donnees m^emes) d'une vue Rou97]. Dans un entrep^ot de donnees, les vues materialisees sont utilisees pour representer les agregations des relations d'un schema en etoile. Les requ^etes peuvent utiliser ces donnees pre-agregees et on peut ainsi augmenter les performances du systeme. PMT
PT
PM
MT
P
M
T
aucune Fig.
14 { Treillis de vues
Une vue materialisee peut aider a en construire d'autres et ainsi de suite. Un probleme important est la selection d'un ensemble minimal a partir duquel on pourrait deriver les autres vues. Il existe trois approches pour la selection de cet ensemble Ull96] : la materialisation de toutes les vues, la materialisation d'aucune vue ou la materialisation selective de quelques vues. Tandis que la premiere approche est infaisable d^u a la quantite d'espace necessaire pour materialiser toutes les vues possibles, la deuxieme ne fournit aucun avantage pour les performances du systeme. Ainsi, la seule solution plausible est la materialisation selective. Il existe des travaux qui abordent le probleme de la selection de vues a materialiser. Gupta presente dans Gup97a] un cadre theorique de travail pour le probleme de selection de vues a materialiser et propose un algorithme general avec plusieurs heuristiques. Par ailleurs, Harinarayan et al. HRU96] modelisent le probleme sous la forme d'un treillis de vues, ou toutes les vues ont la m^eme probabilite d'^etre demandees dans une requ^ete et ont un co^ut determine par leur nombre de n-uplets. La gure 14
18
Entrep^ots de Donnees : Synthese et Analyse
montre le treillis des vues possibles a partir des dimensions PRODUIT (representee par P), MAGASIN (representee par M) et TEMPS (representee par T). L'algorithme propose fait la selection des vues (a materialiser) a partir de ce treillis et restreint la recherche a une nombre xe de vues a materialiser, en minimisant le temps moyen d'evaluation de chacune d'entre elles. Les auteurs montrent que cet algorithme presente des performances tres proche de l'optimal cependant, il parcourt l'espace des solutions possibles a un niveau eleve de granularite et il peut, eventuellement, perdre des bonnes solutions. En plus, son temps d'execution peut devenir tres important dans la pratique. Pour pallier ces situations, Shukla et al. SDN98] proposent l'algorithme PBS qui essaie d'eviter ces desavantages. Les techniques proposees pour la selection de vues a materialiser considerent que l'entrep^ot possede un nombre faible de dimensions, et pour cette raison, les performances de ces techniques se degradent a mesure que le nombre et la complexite des dimensions augmentent. Cette situation a ete identiee par Baralis et al. BPT97] qui proposent une technique qui reduit l'espace des solutions, en considerant seulement les elements pertinents du treillis multidimensionnel par rapport aux besoins des utilisateurs. Une fois materialisees, trouver les vues les plus appropriees pour repondre a une requ^ete n'est pas evident, surtout si l'on considere que l'utilisateur exprime une requ^ete en termes des relations de base. Ce probleme est identie dans LMSS95] par Levy et al. qui considerent le probleme de la reecriture des requ^etes en utilisant seulement les vues materialisees disponibles.
5.2.3 Indexation Binaire
Dans une relation, un index associe, pour chaque valeur possible d'un attribut (ou d'un groupe d'attributs), la liste des n-uplets qui contiennent cette valeur. Un index binaire OG95] utilise un vecteur de bits pour representer une telle liste. Dans ce vecteur, chaque n-uplet d'une relation est associee a un bit qui prend la valeur 1 si le n-uplet associee est membre de la liste ou 0 dans le cas contraire. Un index binaire est une structure de taille reduite qui peut ^etre geree en memoire, ce qui ameliore les performances du SGBDR. De plus, il est possible d'executer des operations logiques (par exemple les operateurs logiques ET, OU) de maniere performante OQ97]. Cette technique d'indexation est appropriee lorsque le nombre de valeurs possibles d'un attribut est faible. E videment, le co^ut de maintenance peut ^etre eleve car tous les index doivent ^etre actualises a chaque nouvelle insertion d'un n-uplet et l'espace de stockage augmente en presence de dimensions de grande cardinalite, parce qu'il faut gerer une quantite importante de vecteurs eparses qui contiennent presque dans leur totalite des bits avec la valeur 0. Pour eviter ces problemes, des techniques de compression de donnees, comme le run-length encoding, sont utilisees. Dans cette technique, une sequence de bits de la m^eme valeur est representee de maniere compacte par une paire dont le premier element est la valeur des bits et le deuxieme est le nombre de bits dans la sequence. L'utilisation de ce type de methode degrade les performances du SGBDR a cause de la compression et la decompression des index.
6 Analyse de l'Entrep^ot 6.1 Systemes OLAP
Les techniques de type On-Line Analytical Processing (OLAP) Cod93] e ectuent la synthese, l'analyse et la consolidation dynamique des donnees multidimension-
Bentez-Guerrero, Collet, Adiba
19
Bases de Données Integration
OLAP
Sources Externes
Sources de Données
SGBD Multidimensionnel Fig.
Interface OLAP
15 { MOLAP
nelles. Ces techniques sont apparues pour la premiere fois au niveau recherche au debut des annees 70 mais elles ont ete developpees dans l'industrie pendant cette decennie PC98] OC98]. Les techniques OLAP sont la maniere la plus naturelle d'exploiter un entrep^ot a cause de son organisation multidimensionnelle. La combinaison d'un entrep^ot et des techniques OLAP associees pour l'exploiter s'appelle systeme OLAP DMT98]. Les systemes OLAP transforment les donnees d'un entrep^ot en information de valeur. Un systeme OLAP aide le decideur a e ectuer des analyses, lui autorisant l'acces aux donnees de l'entrep^ot et lui fournissant de puissants mecanismes d'interrogation Pil98]. Ces mecanismes comprennent des requ^etes qui impliquent des agregations, des classements et des previsions. Les systemes OLAP sont souvent classes par rapport au systeme de gestion utilise pour le stockage et la gestion des donnees ainsi, il en existe fondamentalement trois types : Multidimensionnel, Relationnel et Hybride.
6.1.1 Systemes MOLAP Les systemes de type OLAP Multidimensionnel (MOLAP) stockent les donnees dans un SGBDMD (cf. gure 15). Ces systemes presentent un temps de reponse faible aux calculs complexes parce qu'ils e ectuent la pre-agregation et le pre-calcul des donnees sur tous les niveaux des hierarchies du modele de l'entrep^ot. Cela genere de grands volumes de donnees, en provoquant eventuellement la degradation des performances du systeme. En plus, les techniques incrementielles de rafra^chissement n'ont pas ete susamment developpees et il faut reconstruire l'entrep^ot de maniere periodique. Les systemes MOLAP fournissent une solution acceptable pour le stockage et l'analyse d'un entrep^ot lorsque la quantite estimee pour les donnees d'un entrep^ot ne depasse pas quelques gigaoctects et lorsque le modele multidimensionnel ne change pas beaucoup Rad95]. Les produits Essbase d'Arbor Software Co. AS98], Pilot de Pilot Software Pil98] et TM1 d'Applix App98] appartiennent a cette famille de systemes.
6.1.2 Systemes ROLAP Les systemes de type OLAP Relationnel (ROLAP) utilisent un SGBD Relationnel pour stocker l'entrep^ot (cf. gure 16). Le moteur OLAP est un element supplementaire qui fournit une vision multidimensionnelle de l'entrep^ot (organise sous forme d'etoile ou de "ocon de neige), des calculs de donnees derives et des agregations a di erents
Entrep^ots de Donnees : Synthese et Analyse
20
Bases de Données
Requête
Integration
OLAP
Sources Externes
Sources de Données
Reponse
SGBD Relationnel
Fig.
Moteur OLAP
Interface OLAP
16 { ROLAP
niveaux. Il est aussi le responsable de la generation des requ^etes SQL mieux adaptees au schema relationnel de l'entrep^ot et qui protent des vues materialisees existantes (cf. section 5.2.2). En fait, l'ecacite des requ^etes SQL generees par le moteur OLAP est le facteur principal pour mesurer les performances et le passage a echelle d'un systeme ROLAP DSHB98]. Les systemes ROLAP peuvent stocker de grands volumes de donnees, mais ils peuvent presenter un temps de reponse eleve et sont incapables d'e ectuer des calculs complexes. Les exemples de produits de cette famille de systemes OLAP sont DSS Agent de MicroStrategy Mic98] et MetaCube d'Informix Inf98].
6.1.3 Systemes HOLAP
Les systemes hybrides (HOLAP) essaient d'eviter les problemes des systemes MOLAP et ROLAP, en stockant les donnees agregees d'un entrep^ot dans un SGBDMD et les donnees detaillees dans un SGBDR. Ainsi, il est possible de gerer une grande quantite de donnees et, en m^eme temps, d'avoir un temps de reponse acceptable. Les produits Express d'Oracle Corp. Ora98], Media/MR de Speedware Corp. Spe97] et Holos de Seagate Technology Inc. Sea98] sont des exemples de cette famille de systemes OLAP. Dans les systemes OLAP, l'initiative d'analyse appartient a l'utilisateur qui dirige la recherche vers des zones interessantes dans l'espace multidimensionnel. Cependant, l'espace a analyser peut ^etre d'une grande taille et l'utilisateur n'est pas capable de l'explorer. Dans la suite, nous abordons des mecanismes plus puissants et \intelligents" qui automatisent une partie du processus d'analyse et qui sont connus sous le nom d'orpaillage.
6.2 Orpaillage
L'orpaillage ou Data Mining est la recherche de la connaissance, sous forme de modeles de comportement, cachee dans les donnees Fra91]. L'orpaillage est un domaine jeune qui se trouve a l'intersection des domaines tels que l'Intelligence Articielle, la Statistique, et les Bases de Donnees. Actuellement, il existe un nombre important de techniques d'orpaillage telles que la regression lineaire, l'induction d'arbres de decision, les algorithmes genetiques, les reseaux de neurones et les algorithmes de formation de groupes. La gure 17 montre l'application d'une technique d'orpaillage a un ensemble de donnees. Dans ce cas, il s'agit d'induire, a partir des n-uplets en entree, un modele de classication sous la forme d'une arbre de decision. L'algorithme applique a construit
Bentez-Guerrero, Collet, Adiba
PRODUIT
21
MAGASIN
TEMPS
Vente
TV
Grenoble
1996
Haute
Radio
Grenoble
1996
Basse
TV
Lyon
1996
Haute
TV
Annecy
1996
Haute
Radio
Creteil
1996
Basse
Radio
Paris
1996
Haute
Fig.
PRODUIT TV
Orpaillage
Radio
Haute
MAGASIN
Grenoble
Basse
Creteil
Basse
Paris
Haute
17 { Application d'une technique d'orpaillage
un arbre dont l'attribut le plus important pour distinguer un n-uplet d'un autre est PRODUIT et dans un deuxieme niveau, MAGASIN. Dans la gure 17, il est possible d'observer que, quelque soit la localisation du magasin et l'annee, la vente des TV est elevee. En revanche, la vente de radios depend de la localisation du magasin. Plusieurs techniques d'orpaillage ont ete utilisees pour plus d'une decennie dans des outils statistiques specialises pour l'analyse de quantites reduites de donnees aujourd'hui, ces techniques sont en train d'evoluer pour s'integrer avec les entrep^ots. La synergie entre l'orpaillage et les entrep^ots a ete reconnue jusqu'a recemment Inm96]. D'un cote, les techniques d'orpaillage sont plus performantes lorsqu'elles sont utilisees pour analyser les donnees d'un entrep^ot, parce que les donnees de qualite qu'il integre evitent que l'outil passe du temps a faire des t^aches prealables, telle que l'epuration de donnees. De l'autre cote, la capacite d'analyse unique que ces outils fournissent aux utilisateurs de l'entrep^ot provoque une augmentation de sa valeur strategique.
6.3 Visualisation
La visualisation des donnees doit faciliter leur analyse et leur interpretation. Les techniques de visualisation convertissent des donnees complexes en images, graphiques en 2 ou 3 dimensions et en animations qui peuvent ^etre analysees en cherchant des interrelations entre donnees. Les outils de visualisation autorisent que l'utilisateur explore de maniere interactive de grandes quantites de donnees AVS98]. Les techniques de visualisation ont ete utilises aussi dans des outils specialises pendant plusieurs annees. L'integration de celles-ci dans le contexte des entrep^ots a commence recemment. Cette collaboration a des avantages pour les deux domaines Bro97]: d'une part, les donnees de qualite d'un entrep^ot evitent qu'une technique de visualisation realise des t^aches d'epuration des donnees et ainsi son ecacite augmente d'autre part, la visualisation aide a l'utilisateur a mieux comprendre les caracteristiques des donnees de l'entrep^ot.
7 Conclusion Un Entrep^ot de Donnees rassemble, dans une base de donnees logiquement centralisee et non liee aux environnements operationnels d'une entreprise, des donnees selectionnees et integrees en provenance de multiples sources heterogenes. Les donnees d'un entrep^ot sont organisees pour ^etre facilement accessibles et analysables. Cette
22
Entrep^ots de Donnees : Synthese et Analyse
caracteristique est exploitee par les systemes d'aide a la decision qui utilisent les techniques d'analyse OLAP, d'orpaillage et de visualisation. La construction d'un Entrep^ot de Donnees n'est pas un processus simple, parce qu'il faut tenir compte de facteurs de di erentes natures. Il faut considerer des facteurs techniques (l'integration des donnees heterogenes et leur modelisation, ainsi que la conception des systemes d'aide a la decision). Il faut considerer aussi des facteurs economiques (l'achat d'equipements, de logiciels ou de services) et les caracteristiques des analyses a venir. Nous avons realise un etat de l'art des entrep^ots de donnees. La conclusion generale est que le domaine est tres jeune et qu'il n'est pas encore stable. M^eme si l'industrie a stimule son developpement pratique, en m^eme temps, elle a provoque un etat de confusion du a l'introduction des termes utilises pour chaque concurrent sur le marche pour se distinguer l'un de l'autre et au debat de la suprematie des systemes ROLAP sur les systemes MOLAP. Par ailleurs, la recherche a commencee a jouer un r^ole important jusqu'a recemment, avec par exemple l'importation de techniques connues de materialisation de vues dans ce nouveau contexte. Cependant, il faut encore developper de nouvelles solutions car les solutions traditionnelles ne sont plus appropriees, comme dans le cas des techniques d'indexation. En plus, la conception des entrep^ots est tres in"uencee par le modele relationnel et par les nombreux SGBD de ce type qui sont operationnels. Cette in"uence de la technologie dominante des bases de donnes emp^eche d'avoir une approche rigoureuse au probleme de la modelisation des donnes multidimensionnelles. Les entrep^ots de donnees sont un terrain fertile pour des nouveaux developpements, citons par exemple: { Le rafra^chissement periodique d'un entrep^ot est un probleme ouvert si l'on veut le realiser ecacement. Des nouvelles techniques liees aux bases de donnees actives Col96a] peuvent ^etre envisagees pour cela. { Les entrep^ots de donnees se pr^etent bien a l'utilisation des techniques de partition de donnees pour le traitement parallele entre plusieurs processeurs DMT98]. On pourrait ainsi ameliorer les temps de reponse pour des requ^etes complexes sur de grandes quantites de donnees. { L'utilisation de l'Internet et de l'intranet pour l'acces aux entrep^ots provoquera l'incorporation de mecanismes complexes de securite. { L'analyse et la critique des modeles existantes pour les donnees multidimensionnelles nous indiquent qu'il faut tirer parti de tout le travail lie aux objets complexes et multimedia AC93]. Ceci ouvrira la porte pour des nouveaux entrep^ots, comme ceux d'images satellite ou cliniques et de donnees geographiques. { La dimension temps est tres importante dans un entrep^ot. Il faut etudier les liens avec les bases de donnees temporelles FCS97]. { L'exploration des nouvelles techniques d'indexation. Dans le domaine des Bases de Donnees Spatiales, plusieurs techniques d'indexation ont ete proposees, comme par exemple, les arbres R BS96]. Ce type de techniques pourraient ^etre utiles pour l'indexation des donnees multidimensionnelles Sar97]. Tout cela constitue un domaine de recherche vaste qui est actuellement encore mal explore. Il est clair que les donnees generees aujourd'hui sont de plus en plus nombreuses, volumineuses, heterogenes et reparties. Les integrer dans des entrep^ots,
Bentez-Guerrero, Collet, Adiba
23
les organiser, les gerer, les rafra^chir et les analyser ecacement constituent les principaux des pour construire les entrep^ots de donnees et les systemes decisionnels du futur.
References
AAD+ 96] Agarwal (Sameet), Agrawal (Rakesh), Deshpande (Prasad), Gupta (Ashish), Naughton (Je re), Ramakrishnan (Raghu) et Sarawagi (Sunita). { On the computation of multidimensional aggregates. In : Proceedings of the 22nd VLDB Conference. { Bombay, India, 1996. AC93] Adiba (Michel) et Collet (Christine). { Objets et bases de donnees : le SGBD 02. { Paris, France, Hermes, 1993. AGS95] Agrawal (Rakesh), Gupta (Ashish) et Sarawagi (Sunita). { Modeling Multidimensional Databases. { Rapport technique, 650 Harry Road, San Jose, CA 95120, USA, IBM Almaden Research Center, September 1995. App98] Applix. { TM1 Technology. { Rapport technique, Applix Inc., 1998. http://www.applix.com/tm1/tm tech.htm. AS98] Arbor-Software, 1998. http://www.arborsoft.com. AVS98] AVS. { Gaining Insight Through Data Visualisation. { Rapport technique, Advanced Visual Systems Inc., 1998. Boh97] Bohn (Kathy). { Converting data for warehouses. DBMS On-Line, June 1997. { http://www.dbmsmag.com/9706d15.html. BPT97] Baralis (Elena), Paraboschi (Stefano) et Teniente (Ernest). { Materialized view selection in a multidimensional database. In : Proceedings of the 23rd VLDB Conference. { Athenes, Greece, 1997. Bro97] Brooks (Peter). { Visualizing data. DBMS On-Line, August 1997. { http://www.dbmsmag.com/9708d13.html. BS96] Bontempo (Charles) et Saracco (C.). { Accelerating indexed searching. Database Programming and Design, July 1996. BSHD98] Blaschka (Markus), Sapia (Carsten), H$o"ing (Gabriele) et Dinter (Barbara). { Finding your way through multidimensional data models. In : Proceedings of International Workshop on Data Warehouse Design and OLAP Technology (DWDOT), pp. 198{203. { Vienna, Autrich, August
BT98]
CD97]
1998. Bokun (Michele) et Taglienti (Carmen). { Incremental data warehouse updates: Approaches and strategies for capturing changed data. Data Management Review, May 1998. { http://www.dmreview.com/issues/1998/may/articles/may98 60.htm. Chauduri (Surajit) et Dayal (Umeshwar). { An overview of data warehousing and olap technology. SIGMOD Record, no1, 1997, pp. 65{74.
24
Entrep^ots de Donnees : Synthese et Analyse
CM95]
Celko (Joe) et McDonald (Jackie). { Don't warehouse dirty data. Datamation, October 1995. { http://www.datamation.com/PlugIn/issues/1995/oct15/10bsw100.html. Cod93] Codd (E.). { Providing OLAP (On-Line Analytical Processing) to UsersAnalysts: An IT Mandate. { Rapport technique, E.F. Codd and Associates, 1993. Col96a] Collet (Christine). { Bases de donnees actives : des systemes relationnels aux systemes a objets. { Rapport technique, Grenoble, France, Institut d'Informatique et Mathematiques Appliquees de Grenoble, 1996. Col96b] Colliat (George). { Olap, relational, and multidimensional database systems. SIGMOD Record, no3, 1996, pp. 64{69. CT97] Cabibbo (Luca) et Torlone (Riccardo). { Querying multidimensional databases. In : Proceedings of 6th Internation Workshop on Database Programming Languages. { Estes Park, Colorado, U.S.A., August 1997. CT98] Cabibbo (Luca) et Torlone (Riccardo). { A logical approach to multidimensional databases. In : Proceedings of 6th Internation Workshop on Extending Database Technology, EDBT '98. { Valencia, Spain, March 1998. DMT98] Datta (Anindy), Moon (Bongki) et Thomas (Helen). { A case for parallelism in data warehousing and olap. IEEE, February 1998. DSHB98] Dinter (Barbara), Sapia (Carsten), H$o"ing (Gabriele) et Blaschka (Markus). { The olap market: State of the art and research issues. In : Proc.of First International Workshop on Data Warehousing and OLAP (DOLAP, in connection with CIKM'98). { Washington, D.C., U.S.A., No-
vember 1998. DWI98] DWI. { Data warehouse institute, 1998. http://www.dw-institute.com. FCS97] Fauvet (M-C.), Canavaggio (J-F.) et Scholl (P-C.). { Tempos: un modele d'historiques pour un sgbd temporel a objets. In : Actes de 13e jounees de Bases de Donnees Avancees. { Grenoble, France, 1997. Fra91] Frawley (William). { Knowledge discovery in databases: an overview. In : Knowledge Discovery in Databases, pp. 1{30. { U.S.A., The AAAI Press, 1991. Fra97] Franco (Jean-Michel). { Le Data Warehouse. { France, Eyrolles, 1997. GCB+ 97] Gray (Jim), Chaudhuri (Surajit), Bosworth (Adam), Layman (Andrew), Reichart (Don), Venkatrao (Murali), Pellow (Frank) et Pirahesh (Hamid). { Data cube: A relational aggregation operator generalizing groupby, cross-tab, ans sub-totals. Data Mining and Knowledge Discovery, 1997, pp. 29{53. GL97] Gyssens (Marc) et Lakshmanan (Laks). { A foundation for multidimensional databases. In : Proceedings of the 23rd VLDB Conference. { Athenes, Greece, 1997.
Bentez-Guerrero, Collet, Adiba GL98]
25
Gingras (Frederic) et Lakshmanan (Laks). { nd-sql: A multi-dimensional language for interoperability and olap. In : Proceedings of the 24th VLDB Conference. { New York, U.S.A., 1998. Gre98] Greeneld (Larry). { The data warehousing information center, 1998. http://pwp.starnetinc.com/larryg/index.html. Gup97a] Gupta (Himanshu). { Selection of views to materialize in a data warehouse. In : Proceedings of the 6th International Conference on Database Theory, pp. 98{112. { Delphi, Greece, January 1997. Gup97b] Gupta (Vivek). { An Introduction to Data Warehousing. { Rapport technique, System Services Corporation, 1997. HGML+ 95] Hammer (J.), Garcia-Molina (H.), Labio (W.), Widom (J.) et Zhuge (Y.). { The stanford data warehousing project. IEEE Data Engineering Bulletin, no18, 1995, pp. 41{48. HRU96] Harinarayan (V.), Rajaraman (A.) et Ullman (J.). { Implementing data cubes eciently. In : Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 205{227. Inf98] Informix. { Data Warehouse Administrator's Guide. { Rapport technique, Informix, 1998. http://www.informix.com. Inm92] Inmon (W.). { Building the Data Warehouse. { Wellesley, Massachusetts, U.S.A., QED Technical Publishing Group, 1992. Inm95] Inmon (W.). { What is a Data Warehouse? { Rapport technique, Prism Solutions, 1995. http://www.cait.wustl.edu/cait/papers/prism/vol11 no1/. Inm96] Inmon (W.). { The data warehouse and data mining. Communications of ACM, no11, 1996, pp. 49{50. Ken97] Kenan (Sahin). { Multidimensional Database Technology and Data Warehousing. { Rapport technique, Kenan Systems Corporation, 1997. Kim96] Kimball (Ralph). { The Data Warehouse Toolkit. { U.S.A., John Wiley, 1996. Kim97] Kimball (Ralph). { A dimensional modeling manifesto. DBMS On-Line, 1997. { http://www.dbmsmag.com/. KS95a] Kimball (Ralph) et Strehlo (Kevin). { Sql is our language, x it now. SIGMOD Record, no3, 1995. KS95b] Kimball (Ralph) et Strehlo (Kevin). { Why decision support fails and how to x it. SIGMOD Record, no3, 1995. LMSS95] Levy (A.), Mendelzon (A.), Sagiv (Y.) et Srivastava (D.). { Answering queries using views. In : Proceedings of the 14th ACM Symposium on Principles of Database Systems, pp. 95{104. { San Jose, CA, U.S.A., March 1995.
26 LW96] MH98] Mic98] Mos98] OC98] OG95] OQ97]
Ora98] PC98] Pil98] Rad95] RBS96] Rou97] Sah95] Sar97] SDN98]
Entrep^ots de Donnees : Synthese et Analyse Li (Chang) et Wang (X.Sean). { A data model for supporting on-line analytical processing. In : Proceedings Conference on Information and Knowledge Management. { Baltimore, MD, U.S.A., November 1996. Mendelzon (Alberto) et Hurtado (Carlos). { Data warehousing and olap: A research-oriented bibliography, 1998. http://www.cs.toronto.edu/ mendel/dwbib.html. MicroStrategy. { The Case for Relational OLAP. { Rapport technique, MicroStrategy, 1998. http://www.microstrategy.com. Moss (Larissa). { Data cleansing: A dichotomy of data warehousing? Data Management Review, February 1998. { http://www.dmreview.com/issues/1998/feb/articles/feb98 46.htm. OLAP-Council. { The olap council, 1998. http://www.olapcouncil.com. O'Neil (Patrick) et Graefe (Goetz). { Multi-table joins through bitmapped join indices. SIGMOD Record, no3, 1995, pp. 8{11. O'Neil (Patrick) et Quass (Dallan). { Improved query performance with variant indexes. In : Proceedings of the ACM SIGMOD International Conference on Management of Data. { Tucson, Arizona, U.S.A., May 1997. Oracle. { Oracle Warehouse: Unleash the Power of Information. { Rapport technique, Oracle Corporation, November 1998. http://www.oracle.com/tools/datawarehouse. Pendse (Nigel) et Creeth (Richard). { The OLAP Report. { U.S.A., Business Intelligence Inc., 1998. http://www.olapreport.com. PilotSoftware. { An Introduction to OLAP: Multidimensional Terminology and Technology. { Rapport technique, Pilot Software, 1998. http://www.pilotsw.com/olap/olap.html. Raden (Neil). { Data, data everywhere. Information Week, October 1995. { http://members.aol.com/nraden/iw mct01.htm. Red-Brick-Systems. { Decision-Makers, Business Data and RISQL. { Rapport technique, Red Brick Systems, 1996. Roussopoulos (Nick). { Materialized views and data warehouses. In : Proceedings of the 4th KRDB Workshop. { Athenes, Greece, 1997. Sahin (Kenan). { An Introduction to Multidimensional Database Technology. { Rapport technique, Kenan Systems Corporation, 1995. Sarawagi (Sunita). { Indexing olap data. Bulletin of the Technical Committee on Data Engineering, 1997, pp. 36{43. Shukla (Amit), Deshpande (Prasad) et Naughton (Je rey). { Materialized view selection for multidimensional datasets. In : Proceedings of the 24th VLDB Conference. { New York, U.S.A., 1998.
Bentez-Guerrero, Collet, Adiba Sea98] Sho97]
Spe97] TDV97] Ull96]
WB97]
27
Seagate. { Seagate holos : In depth analysis, 1998. http://www.seagatesoftware.com/holos/homepage/indepth.asp. Shoshani (Arie). { Olap and statistical databases: Similarities and di erences. In : Proceedings of the 16th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 185{196. { Tucson, Arizona, U.S.A., May 1997. Speedware. { Media/MR: The Hybrid OLAP Technology for the Enterprise. { Rapport technique, Speedware Corporation Inc., November 1997. http://www.speedware.com/pubs/datashet/mediamr.pdf. Thomas (Helen), Datta (Anindya) et Viguier (Igor). { A Conceptual Model and Algebra for On-Line Analytical Processing in Decision Support Databases. { Rapport technique, University of Arizona, 1997.
Ullman (Je rey). { Ecient implementation of data cubes via materialized views. In : Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96), pp. 386{388. { Portland, Oregon, U.S.A., 1996. Wu (Ming-Chuan) et Buchmann (Alejandro). { Research issues in data warehousing. In : GI-Fachtagung Datenbanken in Buro, Technik und Wissenschaft (BTW'97). { Ulm, Germany, March 1997.
RR 1017-I-LSR 8
Mai 1999
Entrep^ots de Donnees : Synthese et Analyse Edgard Bentez-Guerrero, Christine Collet, Michel Adiba Laboratoire Logiciels, Systemes, Reseaux - IMAG BP 72, 38402 Saint Martin d'Heres Cedex e-mail : fEdgard.Benitez, Christine.Collet, [email protected] Resume Nous presentons les principaux aspects autour de la notion (( entrep^ot de donnees )) dans le domaine des bases de donnees. Tout d'abord, nous introduisons les caracteristiques d'un entrep^ot et les comparons avec celles presentees par une base de donnees traditionnelle. Nous decrivons ensuite le modele conceptuel et le modele logique utilises pour concevoir un entrep^ot. Nous abordons le processus de construction et les techniques de rafra^chissement periodique d'un entrep^ot avant de discuter les aspects relatifs a son stockage et sa gestion. Nous parlons aussi des techniques d'analyse (l'OLAP, l'orpaillage et la visualisation) qui peuvent ^etre appliquees sur l'entrep^ot. En n, nous identi ons un ensemble de perspectives de recherche dans ce domaine.
Mots clef : Entrep^ot de Donnees, Cube de Donnees, Schema en Etoile, Rafra^-
chissement Periodique, SGBD Multidimensionnel, Vues Materialisees, OLAP, Orpaillage, Visualisation.
1 Introduction Les Entrep^ots de Donnees sont indispensables a la prise de decisions et, pour cette raison, ils sont devenus des elements strategiques pour les entreprises. Le marche estime pour les produits et les services autour des technologies des entrep^ots de donnees a eu une croissance enorme: il est passe de 2 milliards de dollars en 1994 a 8 milliards de dollars en 1998 CD97]. Une etude realisee en 1996 par le Data Warehousing Institute DWI98], une organisation americaine de professionnels, indique que sur les 6000 entreprises enqu^etees, plus de 40% ont debute la mise en place d'un entrep^ot et plus de 30% ont prevu de le faire dans les 3 ans Fra97]. De plus, des entrep^ots ont ete mis en place avec succes dans plusieurs industries telles que la fabrication, le commerce, les services nanciers, le transport, les telecommunications, la medecine CD97] et dans les universites HGML+ 95]. Le theme des entrep^ots de donnees a donc donne lieu a de nombreux travaux de developpement et de recherche sur une periode de temps tres courte MH98] Gre98]. De nombreux concepts ont ete proposes et il est parfois dicile de s'y retrouver. Cet article tente de synthetiser les principaux concepts associes aux entrep^ots de donnees. Il est organise de la maniere suivante : la section 2 presente la denition et la structure des entrep^ots et la section 3 decrit le modele d'organisation des donnees d'un entrep^ot. La construction et le rafra^chissemen d'un entrep^ot sont introduits dans la section 4. Le stockage et la gestion des donnees d'un entrep^ot sont presentes dans 1
Entrep^ots de Donnees : Synthese et Analyse
2 Caracteristique Donnees Usage Unite de travail Nombre de donnees accedees Mode d'acces
Base de Donnees Courantes Support de l'operation de l'entreprise Transaction Dizaines Lecture/E criture
Type d'utilisateur Employe Nombre d'utilisateurs Mille Tab.
Entrep^ots de Donnees Historiques Support de l'analyse de l'entreprise Requ^ete Millions Lecture (principalement) Decideur Cent
1 { Bases de Donnees vs Entrep^ots de Donnees
la section 5. Les systemes OLAP, l'orpaillage et la visualisation sont abordes dans la section 6 et nalement la section 7 conclut cet article.
2 Entrep^ots de Donnees et Bases de Donnees Le concept Entrep^ot de Donnees surgit a partir des besoins d'analyse des donnees d'une entreprise pour chercher des avantages competitives sur la concurrence. Les bases de donnees des systemes existants de type On-Line Transaction Processing (OLTP) ne sont pas appropiees comme support de ces analyses parce qu'elles ont ete con cues pour des fonctions speciques realises dans l'entreprise. Donc, les donnees pertinentes pour faire des analyses se trouvent disseminees entre plusieurs bases. De plus, leur conception vise a ameliorer les performances des systemes OLTP par rapport au traitement d'un grand nombre de transactions (courtes et frequentes) de mise-ajour, ce qui complique l'interrogation. Un entrep^ot de donnees, par contre, o re des donnees integrees, consolidees et historisees pour faire des analyses. Il s'agit d'une collection de donnees pour le support d'un processus d'aide a la decision Inm92] Inm95]. Les donnees d'un entrep^ot possedent les caracteristiques suivantes : { Orientation sujet. Les donnees d'un entrep^ot s'organisent par sujets ou themes. Cette organisation permet de rassembler toutes les donnees, pertinentes a un sujet et necessaires aux besoins d'analyse, qui se trouvent repandues a travers les structures fonctionnelles d'un entreprise. { Integration. Les donnees d'un entrep^ot sont le resultat de l'integration de donnees en provenance de multiples sources ainsi, tous les donnees necessaires pour realiser une analyse particuliere se trouvent dans l'entrep^ot. L'integration est le resultat d'un processus qui peut devenir tres complexe du a l'heterogeneite des sources. { Histoire. Les donnees d'un entrep^ot representent l'activite d'un entreprise pendant une longue periode ou il est important de gerer les di erentes valeurs qu'une donnee prises au cours du temps. Cette caracteristique donne la possibilite de suivre une donnee dans le temps pour analyser ses variations.
Bentez-Guerrero, Collet, Adiba
3
{ Non-volatilite. Les donnees chargees dans l'entrep^ot sont surtout utilisees en interrogation et ne peuvent pas ^etre modiees, sauf dans certains cas de rafra^chissement. Construction Rafraîchissement Bases de Données Sources Externes
Fig.
Extraction Epuration Chargement
Stockage
Entrepôt de Données
Analyse
OLAP Orpaillage Visualisation
Systèmes Decisionnels
1 { L'Entrep^ot de Donnees est la base des systemes decisionnels
L'entrep^ot de donnees (ED) joue un r^ole strategique dans une entreprise comme le montre la gure 1. Il stocke des donnees interessantes en provenance des systemes OLTP de l'entreprise et d'autres sources externes. Avant d'^etre chargees dans l'entrep^ot, les donnees selectionnees doivent ^etre extraites des sources et soigneusement epurees, pour eliminer des erreurs et reconcilier les di erences semantiques. A partir des donnees d'un ED de nombreuses analyses peuvent avoir lieu pour cela, il faut associer aux systemes decisionnels des techniques d'analyse tels que celles de type On-Line Analytical Processing (OLAP), d'orpaillage et de visualisation. L'information et la connaissance obtenues par l'exploitation d'un entrep^ot sont directement traduisibles en beneces pour l'entreprise (augmentation des ventes au travers d'un marketing mieux cible, amelioration des taux de rotation des stocks, etc.) Fra97]. Comme exemple, considerons une cha^ne de magasins repartis geographiquement dans plusieurs pays, comme la France et le Mexique. L'analyse globale de la cha^ne est une t^ache tres compliquee, mais un entrep^ot de donnees fournit le cadre ideal pour l'e ectuer. L'entrep^ot s'organise autour des sujets les plus importants pour la cha^ne, c'est a dire, les produits qui ont ete vendus dans les magasins au cours du temps. Les donnees necesaires pour e ectuer des analyses sont extraites de di erents bases de donnees et chiers (utilises par chaque magasin pour supporter ses activites quotidiennes de ventes) et integrees dans l'entrep^ot. A partir de cet entrep^ot, le gestionnaire de la cha^ne peut e ectuer des analyses et prendre des decisions qui a ecteront les activites futures de l'entreprise. Les donnees d'un entrep^ot se structurent selon deux axes : synthetique et historique (cf. gure 2) Fra97]. L'axe synthetique etablit une hierarchie d'agregation et comprend les donnees detaillees (qui representent les evenements les plus recents au bas de la hierarchie), les donnees agregees (qui synthetisent les donnees detaillees) et les donnees fortement agregees (qui synthetisent a un niveau superieur les donnees agregees). L'axe historique comprend les donnees detaillees historisees, qui representent des evenements passes. Les meta donnees contiennent des informations concernant les donnees dans l'entrep^ot, telle que leur provenance et leur structure, ainsi que les methodes utilisees pour faire l'agregation. L'entrep^ot de donnees se trouve souvent stocke et gere par un systeme de gestion de bases de donnees (SGBD) dans un ordinateur non lie aux systemes OLTP de l'entreprise. La principale raison pour e ectuer cette separation est la degradation eventuelle des performances des systemes OLTP provoque par l'execution des
Entrep^ots de Donnees : Synthese et Analyse
4
Données fortement agregées M e t a
Axe synthétique
D o n n é e s
Données agregées
Données detaillées
Données detaillées historisées
Axe historique
Fig.
2 { La structure d'un Entrep^ot de Donnees
processus d'analyse sur les donnees de l'entrep^ot Gup97b]. La haute performance du traitement des transactions et les courts temps de reponse sont tres importants dans un systeme OLTP. Cependant ces caracteristiques ne sont pas critiques pour les processus d'analyse de l'entrep^ot, ou les chemins d'acces aux donnees sont diciles a denir a priori et le temps de reponse n'est pas rigide. Pour construire un entrep^ot, il faut adopter des techniques de conception et de mise en oeuvre totalement di erentes de celles utilisees pour construire un systeme OLTP. Dans la section suivante, nous abordons la problematique de la modelisation d'un entrep^ot.
3 Modelisation de l'Entrep^ot La conception d'un entrep^ot de donnees est tres di erente de celle des bases de donnees des systemes OLTP, parce qu'il faut penser en termes de concepts plus ouverts et plus diciles a denir. De plus, les besoins des utilisateurs de l'entrep^ot ne sont pas aussi clairs que ceux des utilisateurs des systemes OLTP. Dans la suite de cette section, nous expliquons le modele conceptuel des entrep^ots de donnees : le modele multidimensionnel de donnees.
3.1 Modele Multidimensionnel de Donnees
La conception des bases de donnees est en general basee sur le modele EntiteRelation (E-R). Ce modele permet de faire la description des relations entre donnees elementaires (entites) en cherchant l'elimination des redondances, ce qui provoque
Bentez-Guerrero, Collet, Adiba
5
l'introduction d'un nombre important de nouvelles entites. Ainsi, l'acces aux donnees devient complique et le diagramme genere devient dicile a comprendre pour une personne. Pour cette raison, l'utilisation de la modelisation E-R pour la conception d'un ED n'est pas appropriee Col96b]. Le modele multidimensionnel de donnees (MMD) est une alternative mieux adaptee aux besoins de l'analyse des donnees d'un entrep^ot Kim96]. Ce modele permet d'observer les donnees selon plusieurs perspectives ou axes d'analyse, facilite l'acces aux donnees et en plus est facile a comprendre y compris pour les personnes qui ne sont pas expertes en informatique. Pour cette raison, ce modele a ete adopte par les praticiens Kim97] Inm92] et par les chercheurs des bases de donnees AGS95] TDV97] pour organiser les donnees d'un entrep^ot.
P1
PRODUIT
1000
P2
1996 TEMPS 1995
P3 1994 Lyon
Grenoble
Annecy
MAGASIN
Fig.
3 { Un exemple de Cube de Donnees
3.1.1 Le Cube de Donnees
Le constructeur fondamental du modele multidimensionnel est le Cube de Donnees (ou simplement cube 1 ) TDV97]. Un cube organise les donnees en une ou plusieurs dimensions qui determinent une mesure d'inter^et. Une dimension specie la maniere dont on regarde les donnees pour les analyser, alors qu'une mesure est un objet d'analyse. Chaque dimension est formee par un ensemble d'attributs et chaque attribut peut prendre di erentes valeurs. Les dimensions possedent en general des hierarchies associees qui organisent les attributs a di erents niveaux pour observer les donnees a di erentes granularites. Une dimension peut avoir plusieurs hierarchies associees, chacune speciant di erentes relations d'ordre entre ses attributs. Considerons un modele multidimensionnel pour la cha^ne de magasins. Dans ce cas, la mesure d'inter^et est la Quantite d'un PRODUIT vendu dans un MAGASIN (represente par la ville auquel il appartient) a un instant du TEMPS. La gure 3 presente le cube VENTES, qui montre que 1000 unites du produit P1 ont ete vendus en 1994 dans le magasin situe a Annecy. 1. En geometrie, un cube designe un corps solide a six faces carrees de taille egale dans le modele multidimensionnel, un cube est une maniere d'organiser des donnees et, en realite, ce n'est pas un cube. Cependant, ce terme est utile pour comprendrele modele en utilisant une metaphoregraphique. Pour cette raison, dans cet article nous continuerons a utiliser ce terme.
Entrep^ots de Donnees : Synthese et Analyse
6
Les donnees multidimensionnelles sont de nature eparse car il est possible que seulement un nombre tres faible des cellules d'un cube aient une valeur. Par exemple, les produits ne sont pas tous vendus dans tous le magasins pendant les m^emes periodes de temps. Si l'on considere que la cha^ne de magasins possede 50 magasins, vend 1000 produits et a opere pendant 3 annees (1095 jours), alors il y a plus de 5 millions de combinaisons possibles (au niveau jour), chacune avec une vente potentielle. Si l'on suppose que les donnees sont disponibles pour seulement 1% de ventes (plus de 5000), on peut dire qu'il y a une dispersion de 99%.
P R
P1
100
80
M
91
D
200
1000
100
Grenoble
220
800
80
Annecy
300
500
91
G P2
1000
800
500
A
U I
Lyon A
O
S P3
200
220
300
T
1994 Lyon
Grenoble
1996 1995 TEMPS
I
1996 1995
N
1994 P3
Annecy
P2
TEMPS
P1
PRODUIT
MAGASIN
Fig.
4 { Data Slice
E tant donnee la representation sous forme de Cube d'un entrep^ot, plusieurs operations ont ete proposees Sah95]: { Slice ou Rotation { Dice { Roll-Up et Drill-Down
P1
P1 PRODUIT
PRODUIT
P2
1996
P3 1994 P3 1994 Lyon
Grenoble
1996 1995 TEMPS
Annecy
MAGASIN
Fig.
5 { Data Dice
Lyon
Annecy
MAGASIN
TEMPS
Bentez-Guerrero, Collet, Adiba
7
La Rotation ou Slice permet d'avoir acces aux di erentes vues de donnees sans les reordonner physiquement. Pour un cube a 3 dimensions il existe six vues possibles et pour 4 dimensions, 12. En general, un cube de n dimensions a n (n ; 1) vues possibles. On denote l'operateur Slice par Slicedimension (CUBE ). La gure 4 presente le resultat de l'application de l'operateur Slice sur le cube VENTES selon la dimension MAGASIN et qui est denotee par : SliceMAGASIN (V ENTES ). L'operateur Dice permet de restreindre les valeurs dans une ou plusieurs dimensions. On va denoter cet operateur par Dicerestriction (CUBE ). Ainsi, la gure 5 presente le resultat de l'application de Dice sur les cube VENTES pour selectionner les ventes des produits P1 et P3 dans les magasins de Lyon et de Annecy pendant les annees de 1994 et de 1996 et qui est denotee par : DicePRODUIT 6=P 2^MAGASIN 6=Grenoble^TEMPS 6=1995 (V ENTES )
ROLL-UP DRILL-DOWN
1998 1997 TEMPS 1996 1995 1994 P1 P R O D U I T
1998 1997 1996 1995 1994
1998 1997 1996 1995 1994
TEMPS
TEMPS
P1
P1 P R O D U I T
P2 P3 P4 P5
P R O D U I T
P2 P3 P4
MAGASIN
Rhône Alpes Lyon
ville
Grenoble
Ile de France
Annecy
Rhône Alpes
région
P3 P4 P5
P5
Lyon Grenoble Annecy Paris Creteil
P2
France
Paris
Creteil
Ile de France
France
pays
Fig.
6 { Roll Up et Drill Down
Les operateurs Roll-Up et Drill-Down autorisent l'analyse de donnees a di erents niveaux d'agregation en utilisant des hierarchies associees a chaque dimension. L'operateur Roll-Up e ectue l'agregation des mesures allant d'un niveau particulier vers un general, alors que Drill-Down realise l'operation inverse. On denote l'operateur Rollsuperieur Up par RollUpniveau niveau inferieur (CUBE ), alors que l'operateur Drill-Down est denote inferieur par DrillDownniveau niveau superieur (CUBE ). La gure 6 montre l'application des operateurs Roll-Up et Drill-Down sur la dimension MAGASIN, qui a associee la hierarchie \ville!region!pays". Cette hierarchie determine les relations qui existent entre villes et regions, et entre regions et pays. La gure montre aussi une instance possible de cette hierarchie, qui regroupe les villes
Entrep^ots de Donnees : Synthese et Analyse
8 Formalisme
Introduction Operateurs des hierarchies Hypercube Fonctions Pull, Push, Destroy Dimension, (Agrawal et. al., 1995) Restriction, Merge, Join Cube Relations Add Dimension, Transfer, RC-Join Multidimensionnel Construct, Cube Aggregation, (Li et Wang, 1996) Union Table Fonctions Unfold, Fold, Selection N-Dimensionnelle Projection, Renaming, Union (Gyssens et Intersection, Di erence, Lakshmanan, 1997) Sumarization, Classication Cube Ordre partiel Pull, Push, Partition (Thomas et. al., 1997) entre attributs Aggregation, Cartesian Product, Join, Union, Di erence F-table Ordre partiel Roll-Up (Cabibbo entre attributs et Torlone,1998) Tab.
2 { Formalismes proposes
de Paris et Creteil dans la region Ile-de-France et les regions Rh^one-Alpes et Ile-deFrance dans le pays France. Pour determiner le total de ventes au niveau region, il faut appliquer l'operateur Roll-up sur la dimension MAGASIN, en sommant les totaux de chaque ville: RollUpregion ville (V ENTES ) Le m^eme mecanisme s'applique si on veut calculer le total de ventes au niveau Pays, en sommant les ventes totales de chaque region. L'operateur Drill-Down e ectue les operations inverses : DrillDownville region (V ENTES )
3.1.2 Quelques Formalismes Proposes
Le modele multidimensionnel de donnees a attire l'attention de la communaute industrielle et maintenant de nombreux produits bases sur ce modele se trouvent sur le marche ( Ken97], App98], AS98], par exemple). Les services proposes par ces produits visent a couvrir les besoins des utilisateurs et chaque produit fournit sa propre vision du modele et des operations associees. Donc il n'existe pas (i) un formalisme independant de la mise en oeuvre qui autorise la denition de dimensions structurees avec hierarchies multiples et mesures complexes, et (ii) un langage d'interrogation sous-jacent qui facilite l'ecriture de requ^etes complexes dont les agregations ad hoc soient autorisees AGS95] BSHD98]. Pour pallier cette situation, la communaute de recherche a propose plusieurs formalismes (cf. table 2).
Hypercube Agrawal et al. AGS95] proposent un modele base sur la notion d'hypercube. Un hypercube est determine par k dimensions et ses elements (cellules) sont denies par une fonction qui associe a une combinaison de valeurs des dimensions (i)
Bentez-Guerrero, Collet, Adiba
9
la valeur 0, si la combinaison n'existe pas dans la base de donnees, (ii) la valeur 1, si la combinaison existe, ou (iii) un n-uplet, s'il existe de l'information supplementaire associee aux elements la description des composants d'un n-uplet est stockee comme une meta donnee. Ce modele utilise des fonctions pour la denition de hierarchies multiples et d'agregations ad-hoc.
<1000, ...>
P1 P R O D U I T
P2
1
P1
<1000, ...><1000, ...> <2000, ...> 1996 TEMPS 1995
P3
P R O D U I T
P2
1
1 1 3000 QUANTITE 2000
P3
1994 Lyon
Grenoble MAGASIN
(a)
Annecy
1000 Lyon
Grenoble
Annecy
MAGASIN
(b)
7 { L'HyperCube de Agrawal et al. Les elements de l'hypercube (a) prennent des n-uplets ou 0 comme valeur alors que ceux de (b) prennent les valeurs 1 ou 0 Fig.
Les operateurs (cf. table 2) ont une semantique bien denie et forment un ensemble minimal (un operateur ne peut pas ^etre elimine sans perte des fonctionnalites) bien que leur denition soit complexe a cause de l'introduction des fonctions pour representer les hierarchies. Les operateurs proposes peuvent ^etre composes pour construire d'autres operateurs de type relationnel tels que la Projection, l'Union, l'Intersection et la Di erence, ainsi que l'agregation comme Roll-Up et Drill-Down. Cette approche vise une mise en oeuvre sur un SGBD Relationnel et semble plut^ot pragmatique. La gure 7(a) presente l'hypercube VENTES dont les dimensions sont PRODUIT, MAGASIN et TEMPS, et ses elements sont des n-uplets (par exemple < 1000 : : : > pour l'element qui correspond a PRODUIT = P 2, MAGASIN = Lyon et TEMPS = 1994) ou la valeur 0 (pour les elements non representes dans la gure). La meta donnee de description des elements est une annotation de l'hypercube (dans ce cas le n-uplet < Quantite : : : >). La gure 7(b) presente un autre hypercube avec les dimensions PRODUIT, MAGASIN et QUANTITE et ses elements prennent la valeur 1 (par exemple, l'element qui correspond a PRODUIT = P 2, MAGASIN = Lyon et QUANTITE = 1000) ou bien la valeur 0.
Cube Multidimensionnel Pour Li et Wang LW96] une base de donnees multi-
dimensionnelle est un ensemble ni de Cubes Multidimensionnels et un ensemble ni de relations. Un Cube Multidimensionnel consiste en un certain nombre de relations (les dimensions) et pour chaque combinaison de n-uplets, un n-uplet pour chaque dimension, il existe une valeur associee (une mesure). Dans ce modele, les mesures ne peuvent ^etre que des valeurs numeriques. Les auteurs introduisent la notion de relations de regroupement comme moyen pour representer des hierarchies. Les operateurs (cf. table 2) prennent des cubes et relations en entree et produisent des cubes en sortie. Ils peuvent ^etre composes pour exprimer des requ^etes complexes.
Entrep^ots de Donnees : Synthese et Analyse
10
La gure 8(a) montre le cube multidimensionnel VENTES forme par les relations PRODUIT, MAGASIN et TEMPS. Pour les n-uplets MAGASIN =< Grenoble >, PRODUIT = < P 1 10 Noir > et TEMPS = < 15 Mai 1996 >, il existe la valeur associee 100. La partie (b) de la gure 8 montre la relation qui regroupe les villes de Grenoble, Lyon et Annecy dans la region Rh^one-Alpes et les villes de Creteil et Paris dans la region Ile-de-France. PRODUIT
MAGASIN
TEMPS
Nom
Poids
Couleur
Grenoble
P1
10
Noir
15
Mai
1996
100
Grenoble
P2
10
Noir
15
Mai
1996
80
Annecy
P1
20
Noir
15
Mai
1996
80
Lyon
P2
20
Blanc
15
Mai
1996
60
Creteil
P1
10
Blanc
15
Mai
1996
110
Paris
P2
10
Blanc
15
Mai
1996
150
(a)
Jour Mois Année
Quantité
Ville
Region
MAGASIN.Ville
Rhône-Alpes Rhône-Alpes Rhône-Alpes Ile-de-France Ile-de-France
Grenoble Annecy Lyon Creteil Paris
(b)
8 { Le Cube Multidimensionnel de Li et Wang. (a) Cube Multidimensionnel. (b) Relation de regroupement Fig.
Tables N-dimensionnelles Gyssens et Lakshmanan proposent dans GL97] un
formalisme autour de la notion de table n-dimensionnelle. Une instance de ce type de table est un ensemble de relations, une pour chaque dimension et une autre pour les cles de dimension et les mesures respectives. Les hierarchies ne sont pas explicitement mentionnees et elles sont incorporees en denissant des fonctions. Les operateurs proposes (cf. table 2) prennent en entree un cube et produisent en sortie un autre cube. Les auteurs montrent qu'une table n-dimensionnelle peut ^etre representee par une relation classique et vice-versa et c'est a partir de ce resultat qu'ils developpent la semantique des operateurs. En fait, chaque operateur convertit la table structuree ndimensionnelle en une relation classique, e ectue les operations necessaires et convertit cette relation en une table n-dimensionnelle. Les operateurs proposes peuvent ^etre composes pour en exprimer d'autres, comme Roll-Up. La gure 9(a) presente la table bi-dimensionnelle VENTES avec les dimensions PRODUIT et TEMPS, et la mesure VENTES. Les attributs Nom et Poids sont associes a PRODUIT, alors que les attributs Mois et Annee sont associes a TEMPS. On peut voir dans cette gure que 100 unites du produit P1 ont ete vendus au mois de Janvier 1996. La partie (b) de la m^eme gure presente une instance de VENTES, qui est formee par les relations rPRODUIT, rTEMPS et rm. Chaque n-uplet des relations rPRODUIT et rTEMPS est vue comme une \coordonnee" dans les dimensions PRODUIT et TEMPS respectivement, alors qu'un n-uplet de rm represente la valeur associee a une combinaison de coordonnees, une coordonnee pour chaque dimension.
Cube Pour Thomas et. al. TDV97] une base de donnees multidimensionnelle est
un ensemble de cubes, denis en termes de dimensions, mesures, attributs et fonctions qui associent les attributs aux dimensions. Il est possible de denir des schemas
Bentez-Guerrero, Collet, Adiba
VENTES
P R O D U I T
Nom P1 P2
11
Poids
Année
1996
Mois
Jan
1997 Fev
....
Jan
Fev
80 120 .... 50 70 ....
100 160 .... 60 75 ....
....
Vente 100 80 .... 50 60 ....
10 20 .... 10 20 ....
VENTES rTEMPS
rPRODUIT
TEMPS
80 100 .... 60 80 ....
Tid
Nom
Poids
Tid
Année
Mois
t1 t2 t3 t4 ....
P1 P1 P2 P2 ....
10 20 10 20 ....
t1 t2 t3 t4 ....
1996 1996 1997 1997 ....
Jan Fev Jan Fev ....
rm P.Tid
T.Tid
Quantité
t1 t2 .... t1 t2
t1 t1 .... t2 t2
100 80 .... 80 100
(b)
(a)
9 { Table N-Dimensionnelle de Gyssens et Lakshmanan. (a) Table bi-dimensionnelle (b) Instance de la table bi-dimensionnelle Fig.
de cubes, qui specient de maniere abstraite la structure d'un cube. A partir d'un schema, des instances peuvent ^etre creees. Les hierarchies ne sont pas explicitement representees et elles doivent ^etre denies a priori comme un ordre partiel entre les attributs d'une dimension. Les operateurs de l'algebre proposee (cf. table 2) prennent en entree un cube et produisent en sortie un cube. Le modele fournit des denitions simples des operateurs algebriques, ou chaque operateur execute une fonction unique. Les operateurs peuvent ^etre composes pour denir d'autres operateurs comme Roll-Up et Drill-Down.
<1000>
P1 a1 = Nom P2 D1 = PRODUIT
1996 1995
P3 1994 Lyon
Grenoble
a3 = Année
D3 = TEMPS
Annecy
a1 = Ville D2 = MAGASIN
Fig.
10 { Le Cube de Thomas et al. Cette gure montre un cube et ses composants
La gure 10 montre le cube (instance de cube) VENTES deni par les dimensions D1 (PRODUIT), D2 (MAGASIN) et D3 (TEMPS). L'attribut a1 de la dimension PRODUIT est \nom", l'attribut a1 de la dimension MAGASIN est \ville" et l'attribut a3 de la dimension TEMPS est \annee".
Entrep^ots de Donnees : Synthese et Analyse
12
F-tables Cabibbo et Torlone CT98] proposent une formalisme autour de la notion
de f-table, qui est une fonction des coordonnees des dimensions aux mesures. Il est possible de specier le schema d'une f-table et de denir, a partir de ce schema, un ensemble d'instances. Ce formalisme autorise la structuration complexe des hierarchies dans une dimension, en denisant des ordres partiels entre ses attributs. Le langage d'interrogation CT97] est base sur la logique du premier ordre et donc autorise l'ecriture de requ^etes de fa con declarative. Ce langage permet l'incorporation des fonctions d'agregation mieux adaptes aux besoins du domaine d'application.
VENTES [v : ville <MAGASIN>, p : nom
(a) Fig.
v
p
Grenoble
P1
15
Mai
j 1996
100
Grenoble
P2
15
Mai
1996
80
Annecy
P1
15
Mai
1996
80
Lyon
P2
15
Mai
1996
60
Creteil
P1
15
Mai
1996
110
Paris
P2
15
Mai
1996
150
VENTES
(b)
11 { Les f-tables de Cabbibo et Torlone. (a) Schema (b) Instance
On peut voir dans la partie (a) de la gure 11 le schema de la f-table qui represente les ventes de la cha^ne de magasins, mesurees en termes de la quantite vendue de produits. Les attributs \v", \p" et \j" de ce schema representent, respectivement, la dimension MAGASIN au niveau ville, la dimension PRODUIT au niveau nom et la dimension TEMPS au niveau jour. La partie (b) de la gure 11 montre une instance de ce schema. Malgre l'absence d'un formalisme conceptuel communement accepte, la communaute industrielle a developpe des modeles logiques ad hoc pour faire face aux pressions du marche et a la forte concurrence. Dans la section suivante, nous abordons les modeles logiques les plus utilises.
3.2 Modele Logique
Le modele multidimensionnel de donnees decrit dans la section precedente est implante directement par des systemes specialises, appeles SGBD Multidimensionnels, presentes dans la section 5. Cependant, la mise en oeuvre du modele du cube n'est pas restreinte a ce type de SGBD. La representation de donnees en relations en troisieme forme normale n'est plus appropriee pour un entrep^ot a cause du grand nombre de jointures et de restrictions pour un nombre eleve de relations KS95b]. Pour eviter ces desavantages, les schemas sous forme d'etoile, de "ocon de neige et de constellation de faits ont ete proposes.
3.2.1 Schema en etoile
Dans le schema en etoile Kim96], les mesures sont representees par une relation de faits et chaque dimension par une relation de dimension. La relation de faits reference
Bentez-Guerrero, Collet, Adiba
13
DIMENSION RELATION DE FAITS
Magasin
Ventes Produit
DIMENSION
Magasin
Produit
Magasin Ville Region Pays
Temps Produit
Quantité
Nom Poids Couleur
DIMENSION
Temps Temps Jour Mois Année
Fig.
12 { Schema en Etoile
les relations de dimension en utilisant une cle etrangere pour chacune et stocke les valeurs des mesures pour la combinaison des cles. Autour de cette relation gurent les relations de dimension qui regroupent les caracteristiques des dimensions. La relation de faits est normalisee et peut atteindre une taille importante par rapport au nombre de n-uplets par contre, les tables de dimension sont denormalisees (c'est a dire, des dependences fonctionnelles peuvent ^etre trouvees entre les attributs) et sont en general d'une faible taille. La gure 12 montre le schema en etoile pour le cube VENTES ou la relation de faits stocke la quantite de produits vendus et les relations correspondant a PRODUIT, a MAGASIN et a TEMPS comportent les informations interessantes sur ces dimensions.
3.2.2 Schema en forme de Flocon de Neige
Le schema en etoile ne re"ete pas les hierarchies associees a une dimension. Pour resoudre ce probleme, le schema en forme de "ocon de neige a ete propose. Ce schema normalise les dimensions, reduisant la taille de chacune des relations et permettant ainsi de formaliser la notion de hierarchie au sein d'une dimension Fra97]. La gure 13 montre les relations necessaires pour representer un niveau des hierarchies des dimensions MAGASIN et TEMPS.
3.2.3 Constellation de faits
Il est possible d'avoir plusieurs relations de faits pour representer les situations dans lesquelles les faits (mesures) ne sont pas determines par exactement le m^eme ensemble de dimensions. Dans ce cas, les relations de faits forment une famille KS95b] qui partage plusieurs relations de dimension mais ou chaque membre possede ses dimensions propres. Bien entendu, si les relations de faits partagent une dimension, il faut verier que cette dimension est exactement la m^eme. Le schema resultant s'appelle constellation de faits CD97]. Les schemas relationnels adaptes aux besoins du modele multidimensionnel possedent une serie d'avantages par rapport aux schemas en troisieme forme normale. L'etoile, le "ocon et la constellation autorisent l'expression des mesures, des dimensions et des hierarchies, d'une maniere simple qui permet de les distinguer clairement
Entrep^ots de Donnees : Synthese et Analyse
14
DIMENSION RELATION DE FAITS
Magasin
Region
Ventes Produit
DIMENSION
Magasin
Produit
Magasin Ville Region
Region Pays
Temps Produit
Quantité
Nom Poids Couleur
DIMENSION
Temps Temps Jour Mois
Fig.
Mois Mois Année
13 { Schema en Flocon de Neige
et donc ils sont faciles a comprendre. Ces schemas facilitent egalement l'acces aux mesures, m^eme si la taille d'un relation de faits est souvent importante, parce que le nombre de jointures est plus petit.
4 Construction et Rafra^chissement de l'Entrep^ot 4.1 Construction
Les donnees integrees dans un entrep^ot ont une grande valeur pour une entreprise. Or leur integration n'est pas une t^ache facile, parce qu'en general les donnees se trouvent disseminees dans de multiples sources qui possedent leurs propres structures, formats et denitions. En plus, ces sources peuvent contenir des erreurs, comme des valeurs manquantes, des valeurs illegales ou des contradictions, des valeurs incoherentes et des relations invalides Mos98]. Pour ces raisons, les donnees en provenance de sources heterogenes doivent ^etre traitees avant d'^etre chargees dans un entrep^ot Boh97]. Ce traitement se compose de trois phases : 1. Extraction des donnees a partir de leurs sources et conversion dans une representation intermediaire. 2. E puration par des mecanismes qui assurent leur qualite. 3. Chargement des donnees dans l'entrep^ot. Des estimations indiquent que la plupart du temps (80% en moyenne) de la construction d'un entrep^ot est dedie a ces t^aches Inm92]. Cependant, la plupart des entreprises sous-estiment la complexite de ce processus, m^eme s'il peut ^etre determinant pour le succes de l'entrep^ot et pour la qualite des analyses CM95].
4.2 Rafra^chissement Periodique
Le processus de detection de changements dans les sources et leur propagation vers l'entrep^ot est connu sous le nom de rafra^chissement WB97]. Ce processus se realise periodiquement et la periode depend des besoins des utilisateurs et de la charge
Bentez-Guerrero, Collet, Adiba
15
d'acces a l'entrep^ot. Les techniques de rafra^chissement peuvent ^etre classees dans deux categories : statiques et incrementielles BT98]. Les techniques statiques prennent une photographie des donnees sources a un instant particulier dans le temps. Dans cette categorie se trouvent la technique statique, celle basee sur des timestamps et celle basee sur la comparaison de chiers. La premiere est la technique la plus simple et consiste a prendre une photographie des sources et a reconstruire l'entrep^ot en utilisant celle-ci. La capture basee sur des timestamps utilise une information supplementaire (nommee timestamp) associee aux donnees et qui indique le temps de sa mise a jour la plus recente pour e ectuer la photographie des donnees dont la date du timestamp est posterieure a celle du dernier rafra^chissement. Finalement, la capture basee sur la comparaison de chiers consiste a comparer l'etat courant d'un chier avec l'etat anterieur pour trouver les di erences et les integrer dans l'entrep^ot. Les techniques incrementielles de rafra^chissement capturent les changements dans les sources au moment ou ils arrivent. Les techniques de capture assiste par l'application, par triggers et par le journal se trouvent dans cette categorie. La capture assistee par l'application requiert de la part des applications qui traitent les donnees sources d'identier les changements dans les donnees et de stocker ces changements dans une zone temporaire pour les utiliser an de rafra^chir l'entrep^ot. La capture assistee par triggers est tres semblable a la technique precedente mais la detection des changements et les diverses operations sont realisees par triggers dans la base de donnees. Finalement, la capture par le journal utilise cette information propre au SGBD pour chercher les changements interessants.
5 Stockage et Gestion Dans cette section, nous decrivons les techniques les plus importantes pour e ectuer le stockage et la gestion de donnees multidimensionnelles.
5.1 SGBD Multidimensionnel
Un SGBD Multidimensionnel (SGBDMD) est un SGBD capable de stocker et de traiter des donnees multidimensionnelles. Actuellement, il n'existe pas de cadre technologique commun pour le developpement des SGBDMD car chaque produit sur le marche (Essbase d'ArborSoft, Holos de Seagate, etc.) utilise sa propre version du modele multidimensionnel et ses propres strategies de stockage et de gestion. Il est possible cependant de distinguer la technique de array linearisation comme celle la plus utilisee pour le stockage des donnees multidimensionnelles Sho97]. Dans cette technique, un nombre est associe a chaque valeur possible d'une dimension. La position d'une cellule dans un vecteur multidimensionnel est la combinaison des nombres associes aux valeurs des dimensions qui determinent la cellule. Cette technique est appropriee lorsque l'espace multidimensionnelest dense dans le cas contraire, des techniques de compression doivent s'appliquer pour reduire l'espace de stockage. Les techniques d'indexation sont une solution alternative pour traiter la nature eparse des donnees. La plupart des SGBDMD utilisent une strategie a deux niveaux dans laquelle les dimensions denses sont indexees par une structure qui stocke les combinaisons de valeurs des dimensions eparses DSHB98]. Colliat Col96b] presente une generalisation a n niveaux de cette technique de base, ou un arbre B+ est construit
Entrep^ots de Donnees : Synthese et Analyse
16
a partir des combinaisons possibles des valeurs de dimensions eparses et dont les feuilles contiennent des pointeurs vers les blocs des dimensions denses.
5.2 SGBD Relationnel
Les systemes de gestion de bases de donnees relationnelles (SGBDR) representent environ 80% du marche des systemes de gestion de bases de donnees. De ce fait, la plupart des e orts qui visent a la construction d'un entrep^ot de donnees considerent ce type de systemes. Cependant, les SGBDR doivent ^etre adaptes parce qu'ils ne possedent pas les caracteristiques adequates pour repondre aux besoins des entrep^ots. Dans cette section, nous abordons ces adaptations.
5.2.1 Extensions du langage SQL
Le langage d'interrogation standard des SGBDR est SQL. Ce langage autorise l'expression de requ^etes pour les donnees relationnelles et fournit un ensemble de fonctions primitives pour les analyser. Cependant, les analyses les plus simples sont diciles voire impossibles a exprimer KS95a]. Pour faciliter l'expression des requ^etes pour analyser un entrep^ot, les communautes industrielle et de recherche ont propose des extensions a SQL. Dans la suite de cette section, nous abordons ces extensions. Le langage SQL fournit un ensemble de fonctions d'agregation telles que COUNT, SUM et AVG. Ces fonctions sont utiles mais insusantes pour analyser les donn ees d'un entrep^ot, ou les comparaisons (les ventes de cette annee comparees aux ventes de l'annee derniere) et le traitement sequentiel des donnees resultat d'une requ^ete (qui permet de conna^tre les 5 produits les plus vendus) sont necessaires. A ce propos, des fonctions comme RANK, PERCENTILE et d'autres de type nancier ont ete incorporees dans l'extension RISQL du SGBDR RedBrick RBS96]. Par exemple, la requ^ete suivante ordonne les produits par la quantite vendue et ache seulement les cinq les plus vendus : select from when
RANK (quantite) ventes RANK(quantite) <= 5
L'operateur cube propose par Gray et al. GCB+ 97] est la generalisation en n dimensions de l'operateur group-by. Cet operateur calcule les group-by pour tous les sous-ensembles possibles des n attributs (dimensions) et est equivalent a l'union de plusieurs operations group-by. L'operateur cube est base sur une representation relationnelle des donnees et utilise la valeur \ALL" pour denoter l'ensemble sur lequel est calculee chaque agregation. La requ^ete suivante calcule le cube pour les attributs de la relation ventes : select from group by cube
Produit, Magasin, Temps, SUM(quantite) ventes Produit, Magasin, Temps
La mise en oeuvre ecace de cet operateur a attire l'attention des chercheurs. Agarwal et al. AAD+ 96] modelisent les calculs e ectues par cube comme une hie-
Bentez-Guerrero, Collet, Adiba
17
rarchie d'operations de type group-by et proposent des algorithmes qui combinent des operations communes entre plusieurs group-by et qui utilisent des calculs deja e ectues pour en calculer d'autres. L'evaluation empirique montre que e ectivement l'utilisation de ces algorithmes ameliore les performances du calcul. D'autres extensions a SQL ont ete proposees. Par exemple, Gingras et Lakshmanan GL98] proposent, dans un contexte de federation de bases de donnees, le langage nDSQL. Ce langage elimine les di erences semantiques entre plusieurs bases de donnees relationnelles avec des schemas heterogenes et supporte des operateurs d'agregation comme cube.
5.2.2 Vues materialisees Une vue est une specication pour deriver une nouvelle relation a partir d'un ensemble de relations alors qu'une vue materialisee est l'extension (les donnees m^emes) d'une vue Rou97]. Dans un entrep^ot de donnees, les vues materialisees sont utilisees pour representer les agregations des relations d'un schema en etoile. Les requ^etes peuvent utiliser ces donnees pre-agregees et on peut ainsi augmenter les performances du systeme. PMT
PT
PM
MT
P
M
T
aucune Fig.
14 { Treillis de vues
Une vue materialisee peut aider a en construire d'autres et ainsi de suite. Un probleme important est la selection d'un ensemble minimal a partir duquel on pourrait deriver les autres vues. Il existe trois approches pour la selection de cet ensemble Ull96] : la materialisation de toutes les vues, la materialisation d'aucune vue ou la materialisation selective de quelques vues. Tandis que la premiere approche est infaisable d^u a la quantite d'espace necessaire pour materialiser toutes les vues possibles, la deuxieme ne fournit aucun avantage pour les performances du systeme. Ainsi, la seule solution plausible est la materialisation selective. Il existe des travaux qui abordent le probleme de la selection de vues a materialiser. Gupta presente dans Gup97a] un cadre theorique de travail pour le probleme de selection de vues a materialiser et propose un algorithme general avec plusieurs heuristiques. Par ailleurs, Harinarayan et al. HRU96] modelisent le probleme sous la forme d'un treillis de vues, ou toutes les vues ont la m^eme probabilite d'^etre demandees dans une requ^ete et ont un co^ut determine par leur nombre de n-uplets. La gure 14
18
Entrep^ots de Donnees : Synthese et Analyse
montre le treillis des vues possibles a partir des dimensions PRODUIT (representee par P), MAGASIN (representee par M) et TEMPS (representee par T). L'algorithme propose fait la selection des vues (a materialiser) a partir de ce treillis et restreint la recherche a une nombre xe de vues a materialiser, en minimisant le temps moyen d'evaluation de chacune d'entre elles. Les auteurs montrent que cet algorithme presente des performances tres proche de l'optimal cependant, il parcourt l'espace des solutions possibles a un niveau eleve de granularite et il peut, eventuellement, perdre des bonnes solutions. En plus, son temps d'execution peut devenir tres important dans la pratique. Pour pallier ces situations, Shukla et al. SDN98] proposent l'algorithme PBS qui essaie d'eviter ces desavantages. Les techniques proposees pour la selection de vues a materialiser considerent que l'entrep^ot possede un nombre faible de dimensions, et pour cette raison, les performances de ces techniques se degradent a mesure que le nombre et la complexite des dimensions augmentent. Cette situation a ete identiee par Baralis et al. BPT97] qui proposent une technique qui reduit l'espace des solutions, en considerant seulement les elements pertinents du treillis multidimensionnel par rapport aux besoins des utilisateurs. Une fois materialisees, trouver les vues les plus appropriees pour repondre a une requ^ete n'est pas evident, surtout si l'on considere que l'utilisateur exprime une requ^ete en termes des relations de base. Ce probleme est identie dans LMSS95] par Levy et al. qui considerent le probleme de la reecriture des requ^etes en utilisant seulement les vues materialisees disponibles.
5.2.3 Indexation Binaire
Dans une relation, un index associe, pour chaque valeur possible d'un attribut (ou d'un groupe d'attributs), la liste des n-uplets qui contiennent cette valeur. Un index binaire OG95] utilise un vecteur de bits pour representer une telle liste. Dans ce vecteur, chaque n-uplet d'une relation est associee a un bit qui prend la valeur 1 si le n-uplet associee est membre de la liste ou 0 dans le cas contraire. Un index binaire est une structure de taille reduite qui peut ^etre geree en memoire, ce qui ameliore les performances du SGBDR. De plus, il est possible d'executer des operations logiques (par exemple les operateurs logiques ET, OU) de maniere performante OQ97]. Cette technique d'indexation est appropriee lorsque le nombre de valeurs possibles d'un attribut est faible. E videment, le co^ut de maintenance peut ^etre eleve car tous les index doivent ^etre actualises a chaque nouvelle insertion d'un n-uplet et l'espace de stockage augmente en presence de dimensions de grande cardinalite, parce qu'il faut gerer une quantite importante de vecteurs eparses qui contiennent presque dans leur totalite des bits avec la valeur 0. Pour eviter ces problemes, des techniques de compression de donnees, comme le run-length encoding, sont utilisees. Dans cette technique, une sequence de bits de la m^eme valeur est representee de maniere compacte par une paire dont le premier element est la valeur des bits et le deuxieme est le nombre de bits dans la sequence. L'utilisation de ce type de methode degrade les performances du SGBDR a cause de la compression et la decompression des index.
6 Analyse de l'Entrep^ot 6.1 Systemes OLAP
Les techniques de type On-Line Analytical Processing (OLAP) Cod93] e ectuent la synthese, l'analyse et la consolidation dynamique des donnees multidimension-
Bentez-Guerrero, Collet, Adiba
19
Bases de Données Integration
OLAP
Sources Externes
Sources de Données
SGBD Multidimensionnel Fig.
Interface OLAP
15 { MOLAP
nelles. Ces techniques sont apparues pour la premiere fois au niveau recherche au debut des annees 70 mais elles ont ete developpees dans l'industrie pendant cette decennie PC98] OC98]. Les techniques OLAP sont la maniere la plus naturelle d'exploiter un entrep^ot a cause de son organisation multidimensionnelle. La combinaison d'un entrep^ot et des techniques OLAP associees pour l'exploiter s'appelle systeme OLAP DMT98]. Les systemes OLAP transforment les donnees d'un entrep^ot en information de valeur. Un systeme OLAP aide le decideur a e ectuer des analyses, lui autorisant l'acces aux donnees de l'entrep^ot et lui fournissant de puissants mecanismes d'interrogation Pil98]. Ces mecanismes comprennent des requ^etes qui impliquent des agregations, des classements et des previsions. Les systemes OLAP sont souvent classes par rapport au systeme de gestion utilise pour le stockage et la gestion des donnees ainsi, il en existe fondamentalement trois types : Multidimensionnel, Relationnel et Hybride.
6.1.1 Systemes MOLAP Les systemes de type OLAP Multidimensionnel (MOLAP) stockent les donnees dans un SGBDMD (cf. gure 15). Ces systemes presentent un temps de reponse faible aux calculs complexes parce qu'ils e ectuent la pre-agregation et le pre-calcul des donnees sur tous les niveaux des hierarchies du modele de l'entrep^ot. Cela genere de grands volumes de donnees, en provoquant eventuellement la degradation des performances du systeme. En plus, les techniques incrementielles de rafra^chissement n'ont pas ete susamment developpees et il faut reconstruire l'entrep^ot de maniere periodique. Les systemes MOLAP fournissent une solution acceptable pour le stockage et l'analyse d'un entrep^ot lorsque la quantite estimee pour les donnees d'un entrep^ot ne depasse pas quelques gigaoctects et lorsque le modele multidimensionnel ne change pas beaucoup Rad95]. Les produits Essbase d'Arbor Software Co. AS98], Pilot de Pilot Software Pil98] et TM1 d'Applix App98] appartiennent a cette famille de systemes.
6.1.2 Systemes ROLAP Les systemes de type OLAP Relationnel (ROLAP) utilisent un SGBD Relationnel pour stocker l'entrep^ot (cf. gure 16). Le moteur OLAP est un element supplementaire qui fournit une vision multidimensionnelle de l'entrep^ot (organise sous forme d'etoile ou de "ocon de neige), des calculs de donnees derives et des agregations a di erents
Entrep^ots de Donnees : Synthese et Analyse
20
Bases de Données
Requête
Integration
OLAP
Sources Externes
Sources de Données
Reponse
SGBD Relationnel
Fig.
Moteur OLAP
Interface OLAP
16 { ROLAP
niveaux. Il est aussi le responsable de la generation des requ^etes SQL mieux adaptees au schema relationnel de l'entrep^ot et qui protent des vues materialisees existantes (cf. section 5.2.2). En fait, l'ecacite des requ^etes SQL generees par le moteur OLAP est le facteur principal pour mesurer les performances et le passage a echelle d'un systeme ROLAP DSHB98]. Les systemes ROLAP peuvent stocker de grands volumes de donnees, mais ils peuvent presenter un temps de reponse eleve et sont incapables d'e ectuer des calculs complexes. Les exemples de produits de cette famille de systemes OLAP sont DSS Agent de MicroStrategy Mic98] et MetaCube d'Informix Inf98].
6.1.3 Systemes HOLAP
Les systemes hybrides (HOLAP) essaient d'eviter les problemes des systemes MOLAP et ROLAP, en stockant les donnees agregees d'un entrep^ot dans un SGBDMD et les donnees detaillees dans un SGBDR. Ainsi, il est possible de gerer une grande quantite de donnees et, en m^eme temps, d'avoir un temps de reponse acceptable. Les produits Express d'Oracle Corp. Ora98], Media/MR de Speedware Corp. Spe97] et Holos de Seagate Technology Inc. Sea98] sont des exemples de cette famille de systemes OLAP. Dans les systemes OLAP, l'initiative d'analyse appartient a l'utilisateur qui dirige la recherche vers des zones interessantes dans l'espace multidimensionnel. Cependant, l'espace a analyser peut ^etre d'une grande taille et l'utilisateur n'est pas capable de l'explorer. Dans la suite, nous abordons des mecanismes plus puissants et \intelligents" qui automatisent une partie du processus d'analyse et qui sont connus sous le nom d'orpaillage.
6.2 Orpaillage
L'orpaillage ou Data Mining est la recherche de la connaissance, sous forme de modeles de comportement, cachee dans les donnees Fra91]. L'orpaillage est un domaine jeune qui se trouve a l'intersection des domaines tels que l'Intelligence Articielle, la Statistique, et les Bases de Donnees. Actuellement, il existe un nombre important de techniques d'orpaillage telles que la regression lineaire, l'induction d'arbres de decision, les algorithmes genetiques, les reseaux de neurones et les algorithmes de formation de groupes. La gure 17 montre l'application d'une technique d'orpaillage a un ensemble de donnees. Dans ce cas, il s'agit d'induire, a partir des n-uplets en entree, un modele de classication sous la forme d'une arbre de decision. L'algorithme applique a construit
Bentez-Guerrero, Collet, Adiba
PRODUIT
21
MAGASIN
TEMPS
Vente
TV
Grenoble
1996
Haute
Radio
Grenoble
1996
Basse
TV
Lyon
1996
Haute
TV
Annecy
1996
Haute
Radio
Creteil
1996
Basse
Radio
Paris
1996
Haute
Fig.
PRODUIT TV
Orpaillage
Radio
Haute
MAGASIN
Grenoble
Basse
Creteil
Basse
Paris
Haute
17 { Application d'une technique d'orpaillage
un arbre dont l'attribut le plus important pour distinguer un n-uplet d'un autre est PRODUIT et dans un deuxieme niveau, MAGASIN. Dans la gure 17, il est possible d'observer que, quelque soit la localisation du magasin et l'annee, la vente des TV est elevee. En revanche, la vente de radios depend de la localisation du magasin. Plusieurs techniques d'orpaillage ont ete utilisees pour plus d'une decennie dans des outils statistiques specialises pour l'analyse de quantites reduites de donnees aujourd'hui, ces techniques sont en train d'evoluer pour s'integrer avec les entrep^ots. La synergie entre l'orpaillage et les entrep^ots a ete reconnue jusqu'a recemment Inm96]. D'un cote, les techniques d'orpaillage sont plus performantes lorsqu'elles sont utilisees pour analyser les donnees d'un entrep^ot, parce que les donnees de qualite qu'il integre evitent que l'outil passe du temps a faire des t^aches prealables, telle que l'epuration de donnees. De l'autre cote, la capacite d'analyse unique que ces outils fournissent aux utilisateurs de l'entrep^ot provoque une augmentation de sa valeur strategique.
6.3 Visualisation
La visualisation des donnees doit faciliter leur analyse et leur interpretation. Les techniques de visualisation convertissent des donnees complexes en images, graphiques en 2 ou 3 dimensions et en animations qui peuvent ^etre analysees en cherchant des interrelations entre donnees. Les outils de visualisation autorisent que l'utilisateur explore de maniere interactive de grandes quantites de donnees AVS98]. Les techniques de visualisation ont ete utilises aussi dans des outils specialises pendant plusieurs annees. L'integration de celles-ci dans le contexte des entrep^ots a commence recemment. Cette collaboration a des avantages pour les deux domaines Bro97]: d'une part, les donnees de qualite d'un entrep^ot evitent qu'une technique de visualisation realise des t^aches d'epuration des donnees et ainsi son ecacite augmente d'autre part, la visualisation aide a l'utilisateur a mieux comprendre les caracteristiques des donnees de l'entrep^ot.
7 Conclusion Un Entrep^ot de Donnees rassemble, dans une base de donnees logiquement centralisee et non liee aux environnements operationnels d'une entreprise, des donnees selectionnees et integrees en provenance de multiples sources heterogenes. Les donnees d'un entrep^ot sont organisees pour ^etre facilement accessibles et analysables. Cette
22
Entrep^ots de Donnees : Synthese et Analyse
caracteristique est exploitee par les systemes d'aide a la decision qui utilisent les techniques d'analyse OLAP, d'orpaillage et de visualisation. La construction d'un Entrep^ot de Donnees n'est pas un processus simple, parce qu'il faut tenir compte de facteurs de di erentes natures. Il faut considerer des facteurs techniques (l'integration des donnees heterogenes et leur modelisation, ainsi que la conception des systemes d'aide a la decision). Il faut considerer aussi des facteurs economiques (l'achat d'equipements, de logiciels ou de services) et les caracteristiques des analyses a venir. Nous avons realise un etat de l'art des entrep^ots de donnees. La conclusion generale est que le domaine est tres jeune et qu'il n'est pas encore stable. M^eme si l'industrie a stimule son developpement pratique, en m^eme temps, elle a provoque un etat de confusion du a l'introduction des termes utilises pour chaque concurrent sur le marche pour se distinguer l'un de l'autre et au debat de la suprematie des systemes ROLAP sur les systemes MOLAP. Par ailleurs, la recherche a commencee a jouer un r^ole important jusqu'a recemment, avec par exemple l'importation de techniques connues de materialisation de vues dans ce nouveau contexte. Cependant, il faut encore developper de nouvelles solutions car les solutions traditionnelles ne sont plus appropriees, comme dans le cas des techniques d'indexation. En plus, la conception des entrep^ots est tres in"uencee par le modele relationnel et par les nombreux SGBD de ce type qui sont operationnels. Cette in"uence de la technologie dominante des bases de donnes emp^eche d'avoir une approche rigoureuse au probleme de la modelisation des donnes multidimensionnelles. Les entrep^ots de donnees sont un terrain fertile pour des nouveaux developpements, citons par exemple: { Le rafra^chissement periodique d'un entrep^ot est un probleme ouvert si l'on veut le realiser ecacement. Des nouvelles techniques liees aux bases de donnees actives Col96a] peuvent ^etre envisagees pour cela. { Les entrep^ots de donnees se pr^etent bien a l'utilisation des techniques de partition de donnees pour le traitement parallele entre plusieurs processeurs DMT98]. On pourrait ainsi ameliorer les temps de reponse pour des requ^etes complexes sur de grandes quantites de donnees. { L'utilisation de l'Internet et de l'intranet pour l'acces aux entrep^ots provoquera l'incorporation de mecanismes complexes de securite. { L'analyse et la critique des modeles existantes pour les donnees multidimensionnelles nous indiquent qu'il faut tirer parti de tout le travail lie aux objets complexes et multimedia AC93]. Ceci ouvrira la porte pour des nouveaux entrep^ots, comme ceux d'images satellite ou cliniques et de donnees geographiques. { La dimension temps est tres importante dans un entrep^ot. Il faut etudier les liens avec les bases de donnees temporelles FCS97]. { L'exploration des nouvelles techniques d'indexation. Dans le domaine des Bases de Donnees Spatiales, plusieurs techniques d'indexation ont ete proposees, comme par exemple, les arbres R BS96]. Ce type de techniques pourraient ^etre utiles pour l'indexation des donnees multidimensionnelles Sar97]. Tout cela constitue un domaine de recherche vaste qui est actuellement encore mal explore. Il est clair que les donnees generees aujourd'hui sont de plus en plus nombreuses, volumineuses, heterogenes et reparties. Les integrer dans des entrep^ots,
Bentez-Guerrero, Collet, Adiba
23
les organiser, les gerer, les rafra^chir et les analyser ecacement constituent les principaux des pour construire les entrep^ots de donnees et les systemes decisionnels du futur.
References
AAD+ 96] Agarwal (Sameet), Agrawal (Rakesh), Deshpande (Prasad), Gupta (Ashish), Naughton (Je re), Ramakrishnan (Raghu) et Sarawagi (Sunita). { On the computation of multidimensional aggregates. In : Proceedings of the 22nd VLDB Conference. { Bombay, India, 1996. AC93] Adiba (Michel) et Collet (Christine). { Objets et bases de donnees : le SGBD 02. { Paris, France, Hermes, 1993. AGS95] Agrawal (Rakesh), Gupta (Ashish) et Sarawagi (Sunita). { Modeling Multidimensional Databases. { Rapport technique, 650 Harry Road, San Jose, CA 95120, USA, IBM Almaden Research Center, September 1995. App98] Applix. { TM1 Technology. { Rapport technique, Applix Inc., 1998. http://www.applix.com/tm1/tm tech.htm. AS98] Arbor-Software, 1998. http://www.arborsoft.com. AVS98] AVS. { Gaining Insight Through Data Visualisation. { Rapport technique, Advanced Visual Systems Inc., 1998. Boh97] Bohn (Kathy). { Converting data for warehouses. DBMS On-Line, June 1997. { http://www.dbmsmag.com/9706d15.html. BPT97] Baralis (Elena), Paraboschi (Stefano) et Teniente (Ernest). { Materialized view selection in a multidimensional database. In : Proceedings of the 23rd VLDB Conference. { Athenes, Greece, 1997. Bro97] Brooks (Peter). { Visualizing data. DBMS On-Line, August 1997. { http://www.dbmsmag.com/9708d13.html. BS96] Bontempo (Charles) et Saracco (C.). { Accelerating indexed searching. Database Programming and Design, July 1996. BSHD98] Blaschka (Markus), Sapia (Carsten), H$o"ing (Gabriele) et Dinter (Barbara). { Finding your way through multidimensional data models. In : Proceedings of International Workshop on Data Warehouse Design and OLAP Technology (DWDOT), pp. 198{203. { Vienna, Autrich, August
BT98]
CD97]
1998. Bokun (Michele) et Taglienti (Carmen). { Incremental data warehouse updates: Approaches and strategies for capturing changed data. Data Management Review, May 1998. { http://www.dmreview.com/issues/1998/may/articles/may98 60.htm. Chauduri (Surajit) et Dayal (Umeshwar). { An overview of data warehousing and olap technology. SIGMOD Record, no1, 1997, pp. 65{74.
24
Entrep^ots de Donnees : Synthese et Analyse
CM95]
Celko (Joe) et McDonald (Jackie). { Don't warehouse dirty data. Datamation, October 1995. { http://www.datamation.com/PlugIn/issues/1995/oct15/10bsw100.html. Cod93] Codd (E.). { Providing OLAP (On-Line Analytical Processing) to UsersAnalysts: An IT Mandate. { Rapport technique, E.F. Codd and Associates, 1993. Col96a] Collet (Christine). { Bases de donnees actives : des systemes relationnels aux systemes a objets. { Rapport technique, Grenoble, France, Institut d'Informatique et Mathematiques Appliquees de Grenoble, 1996. Col96b] Colliat (George). { Olap, relational, and multidimensional database systems. SIGMOD Record, no3, 1996, pp. 64{69. CT97] Cabibbo (Luca) et Torlone (Riccardo). { Querying multidimensional databases. In : Proceedings of 6th Internation Workshop on Database Programming Languages. { Estes Park, Colorado, U.S.A., August 1997. CT98] Cabibbo (Luca) et Torlone (Riccardo). { A logical approach to multidimensional databases. In : Proceedings of 6th Internation Workshop on Extending Database Technology, EDBT '98. { Valencia, Spain, March 1998. DMT98] Datta (Anindy), Moon (Bongki) et Thomas (Helen). { A case for parallelism in data warehousing and olap. IEEE, February 1998. DSHB98] Dinter (Barbara), Sapia (Carsten), H$o"ing (Gabriele) et Blaschka (Markus). { The olap market: State of the art and research issues. In : Proc.of First International Workshop on Data Warehousing and OLAP (DOLAP, in connection with CIKM'98). { Washington, D.C., U.S.A., No-
vember 1998. DWI98] DWI. { Data warehouse institute, 1998. http://www.dw-institute.com. FCS97] Fauvet (M-C.), Canavaggio (J-F.) et Scholl (P-C.). { Tempos: un modele d'historiques pour un sgbd temporel a objets. In : Actes de 13e jounees de Bases de Donnees Avancees. { Grenoble, France, 1997. Fra91] Frawley (William). { Knowledge discovery in databases: an overview. In : Knowledge Discovery in Databases, pp. 1{30. { U.S.A., The AAAI Press, 1991. Fra97] Franco (Jean-Michel). { Le Data Warehouse. { France, Eyrolles, 1997. GCB+ 97] Gray (Jim), Chaudhuri (Surajit), Bosworth (Adam), Layman (Andrew), Reichart (Don), Venkatrao (Murali), Pellow (Frank) et Pirahesh (Hamid). { Data cube: A relational aggregation operator generalizing groupby, cross-tab, ans sub-totals. Data Mining and Knowledge Discovery, 1997, pp. 29{53. GL97] Gyssens (Marc) et Lakshmanan (Laks). { A foundation for multidimensional databases. In : Proceedings of the 23rd VLDB Conference. { Athenes, Greece, 1997.
Bentez-Guerrero, Collet, Adiba GL98]
25
Gingras (Frederic) et Lakshmanan (Laks). { nd-sql: A multi-dimensional language for interoperability and olap. In : Proceedings of the 24th VLDB Conference. { New York, U.S.A., 1998. Gre98] Greeneld (Larry). { The data warehousing information center, 1998. http://pwp.starnetinc.com/larryg/index.html. Gup97a] Gupta (Himanshu). { Selection of views to materialize in a data warehouse. In : Proceedings of the 6th International Conference on Database Theory, pp. 98{112. { Delphi, Greece, January 1997. Gup97b] Gupta (Vivek). { An Introduction to Data Warehousing. { Rapport technique, System Services Corporation, 1997. HGML+ 95] Hammer (J.), Garcia-Molina (H.), Labio (W.), Widom (J.) et Zhuge (Y.). { The stanford data warehousing project. IEEE Data Engineering Bulletin, no18, 1995, pp. 41{48. HRU96] Harinarayan (V.), Rajaraman (A.) et Ullman (J.). { Implementing data cubes eciently. In : Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 205{227. Inf98] Informix. { Data Warehouse Administrator's Guide. { Rapport technique, Informix, 1998. http://www.informix.com. Inm92] Inmon (W.). { Building the Data Warehouse. { Wellesley, Massachusetts, U.S.A., QED Technical Publishing Group, 1992. Inm95] Inmon (W.). { What is a Data Warehouse? { Rapport technique, Prism Solutions, 1995. http://www.cait.wustl.edu/cait/papers/prism/vol11 no1/. Inm96] Inmon (W.). { The data warehouse and data mining. Communications of ACM, no11, 1996, pp. 49{50. Ken97] Kenan (Sahin). { Multidimensional Database Technology and Data Warehousing. { Rapport technique, Kenan Systems Corporation, 1997. Kim96] Kimball (Ralph). { The Data Warehouse Toolkit. { U.S.A., John Wiley, 1996. Kim97] Kimball (Ralph). { A dimensional modeling manifesto. DBMS On-Line, 1997. { http://www.dbmsmag.com/. KS95a] Kimball (Ralph) et Strehlo (Kevin). { Sql is our language, x it now. SIGMOD Record, no3, 1995. KS95b] Kimball (Ralph) et Strehlo (Kevin). { Why decision support fails and how to x it. SIGMOD Record, no3, 1995. LMSS95] Levy (A.), Mendelzon (A.), Sagiv (Y.) et Srivastava (D.). { Answering queries using views. In : Proceedings of the 14th ACM Symposium on Principles of Database Systems, pp. 95{104. { San Jose, CA, U.S.A., March 1995.
26 LW96] MH98] Mic98] Mos98] OC98] OG95] OQ97]
Ora98] PC98] Pil98] Rad95] RBS96] Rou97] Sah95] Sar97] SDN98]
Entrep^ots de Donnees : Synthese et Analyse Li (Chang) et Wang (X.Sean). { A data model for supporting on-line analytical processing. In : Proceedings Conference on Information and Knowledge Management. { Baltimore, MD, U.S.A., November 1996. Mendelzon (Alberto) et Hurtado (Carlos). { Data warehousing and olap: A research-oriented bibliography, 1998. http://www.cs.toronto.edu/ mendel/dwbib.html. MicroStrategy. { The Case for Relational OLAP. { Rapport technique, MicroStrategy, 1998. http://www.microstrategy.com. Moss (Larissa). { Data cleansing: A dichotomy of data warehousing? Data Management Review, February 1998. { http://www.dmreview.com/issues/1998/feb/articles/feb98 46.htm. OLAP-Council. { The olap council, 1998. http://www.olapcouncil.com. O'Neil (Patrick) et Graefe (Goetz). { Multi-table joins through bitmapped join indices. SIGMOD Record, no3, 1995, pp. 8{11. O'Neil (Patrick) et Quass (Dallan). { Improved query performance with variant indexes. In : Proceedings of the ACM SIGMOD International Conference on Management of Data. { Tucson, Arizona, U.S.A., May 1997. Oracle. { Oracle Warehouse: Unleash the Power of Information. { Rapport technique, Oracle Corporation, November 1998. http://www.oracle.com/tools/datawarehouse. Pendse (Nigel) et Creeth (Richard). { The OLAP Report. { U.S.A., Business Intelligence Inc., 1998. http://www.olapreport.com. PilotSoftware. { An Introduction to OLAP: Multidimensional Terminology and Technology. { Rapport technique, Pilot Software, 1998. http://www.pilotsw.com/olap/olap.html. Raden (Neil). { Data, data everywhere. Information Week, October 1995. { http://members.aol.com/nraden/iw mct01.htm. Red-Brick-Systems. { Decision-Makers, Business Data and RISQL. { Rapport technique, Red Brick Systems, 1996. Roussopoulos (Nick). { Materialized views and data warehouses. In : Proceedings of the 4th KRDB Workshop. { Athenes, Greece, 1997. Sahin (Kenan). { An Introduction to Multidimensional Database Technology. { Rapport technique, Kenan Systems Corporation, 1995. Sarawagi (Sunita). { Indexing olap data. Bulletin of the Technical Committee on Data Engineering, 1997, pp. 36{43. Shukla (Amit), Deshpande (Prasad) et Naughton (Je rey). { Materialized view selection for multidimensional datasets. In : Proceedings of the 24th VLDB Conference. { New York, U.S.A., 1998.
Bentez-Guerrero, Collet, Adiba Sea98] Sho97]
Spe97] TDV97] Ull96]
WB97]
27
Seagate. { Seagate holos : In depth analysis, 1998. http://www.seagatesoftware.com/holos/homepage/indepth.asp. Shoshani (Arie). { Olap and statistical databases: Similarities and di erences. In : Proceedings of the 16th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 185{196. { Tucson, Arizona, U.S.A., May 1997. Speedware. { Media/MR: The Hybrid OLAP Technology for the Enterprise. { Rapport technique, Speedware Corporation Inc., November 1997. http://www.speedware.com/pubs/datashet/mediamr.pdf. Thomas (Helen), Datta (Anindya) et Viguier (Igor). { A Conceptual Model and Algebra for On-Line Analytical Processing in Decision Support Databases. { Rapport technique, University of Arizona, 1997.
Ullman (Je rey). { Ecient implementation of data cubes via materialized views. In : Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96), pp. 386{388. { Portland, Oregon, U.S.A., 1996. Wu (Ming-Chuan) et Buchmann (Alejandro). { Research issues in data warehousing. In : GI-Fachtagung Datenbanken in Buro, Technik und Wissenschaft (BTW'97). { Ulm, Germany, March 1997.
Related Documents
Integration Donnees - Construction Raffraichissement - 30p Guerrero
November 2019 17
Integration Donnees Sur Web - Tef Univ 30p
November 2019 15
Integration Donnees Dwh Xml - These Guerrero
November 2019 16
Integration Donnees - Tps Reel
November 2019 23
Integration Donnees - Approche Materialisee Virtuelle
November 2019 25