OLAP : Intégration des informations - Examen corrige

OLAP : Intégration des informations
N. Spyratos
Université Paris-Sud Le besoin : collecter des informations à partir des plusieurs sources dans
le but d'exploiter leur synthèse Le problème : les sources peuvent être autonomes et hétérogènes
autorisations nécessaires pour l'extraction
utilisation de plusieurs langages pour la définition de l'information
à extraire
La solution : utiliser un schéma fédérateur, avec ou sans données, que les
utilisateurs manipulent comme s'il s'agissait d'une base de données
habituelle
- avec données courantes provenant d'une seule source (vues matérialisées)
ou de plusieurs sources autonomes et éventuellement hétérogènes (base de
données intégrée)
(besoin d'outils pour la conception du schéma, transformation/chargement de
données et
propagation de changements
- avec données historiques (entrepôt de données, données en avance), c'est
notre cas
(besoin d'outils pour la conception du schéma, transformation/chargement
de données,
propagation de changements et rafraîchissement périodique
- sans données, au sein d'une seule source (vues virtuelles) ou lié à
plusieurs sources autonomes et éventuellement hétérogènes (médiateurs,
données à la demande)
(besoin d'outils pour la récriture/évaluation des requêtes et la fusion
des résultats
dans tous les cas, l'accès aux données se fait presque exclusivement en
lecture Constitution d'un entrepôt de données Architecture à trois niveaux : sources - entrepôt - data mart (voir figure
1)
( data mart : 'petit' entrepôt orienté sujet, dont les données sont
dérivées de l'entrepôt Extraction, Transformation, Chargement de données ( outils ETL
Extracteur :
- traduction vers le langage source, évaluation, traduction vers le langage
de l'entrepôt
- détection de changements aux sources
Intégrateur :
- réconciliation /correction d'erreurs/filtrage/estampillage pour conformer
au schéma de
l'entrepôt
- chargement de données, rafraîchissement Caractéristiques principales des entrepôts de données Un entrepôt de données est l'endroit où les données intégrées sont stockées
et exploitées à l'aide d'un système de gestion de bases de données. Par
conséquent, un entrepôt de données est avant tout une base de données,
même si les caractéristiques suivantes le distinguent clairement des bases
de données transactionnelles habituelles : Utilisation :
les utilisateurs principaux sont les décideurs de l'entreprise
( besoin des schémas faciles a lire (pas de schémas normalisés) ( schéma
dimensionnel
(voir Figure 2)
Mode d'accès :
souvent à travers un data mart, en lecture uniquement
( des index qui ne sont pas efficaces pour le transactionnel le deviennent
pour les entrepôts Volume :
de l'ordre de tera octets
( besoin d'algorithmes efficaces pour le chargement de données et
l'évaluation des requêtes Maintenance :
les mises à jour sont propagées des sources vers l'entrepôt
- immédiatement ou périodiquement (suivant la nature de l'application)
- par reconstruction ou de manière incrémentale Rafraîchissement :
les données qui deviennent 'obsolètes' sont supprimées Metadonnées :
Les métadonnées d'un entrepôt sont plus complexes et plus volumineuses que
celles d'une base de données transactionnelle, et sont souvent gérées en
dehors de l'entrepôt Utilisation d'un entrepôt de données - OLAP : Online Analytic Processing
( résumés/agrégations selon plusieurs critères et sur plusieurs
dimensions
- Génération de rapports
- Extraction de connaissances à partir de données (Fouille de données,
'Data Mining') Plan du cours : algèbre fonctionnel
( définition, opérations, propriétés le modèle fonctionnel pour l'analyse dimensionnelle de données
( schéma dimensionnel et base de données dimensionnelle
langage de chemins et langage OLAP, schémas arborescents analyse dimensionnelle en relationnel (ROLAP) :
( représentation du modèle fonctionnel en relationnel, extensions du SQL,
génération de
rapports, mécanisme de vues et algorithmes incrémentaux de maintenance
aspects physiques :
( index bitmap, index de jointure exemples d'extraction de connaissances à partir de données :
( règles d'association et algorithme A-priori, classification
supervisée/non supervisée Supports : Polycopié + Article (en anglais) Contrôle de connaissances : Examen écrit (documents autorisés) + projet
TD-1 : Algèbre fonctionnelle Rappelons d'abord qu'une fonction est désignée par f : X(Y, où f est le nom
de la fonction, X son ensemble de départ et Y son ensemble d'arrivée. Nous
noterons def(f) l'ensemble des éléments de X pour lesquels f est définie et
range(f) l'ensemble des valeurs prises par f. Une fonction f est appelée :
fonction totale (ou application) si def(f)= X (sinon, f est appelée
fonction partielle)
fonction injective (ou injection) si x(x' implique f(x)(f(x'), pour tous
x,x' dans def(f)
fonction surjective (ou surjection) si range(f)= Y
fonction bijective si elle est à la fois injective et surjective. Dans la suite, nous nous intéresserons uniquement aux fonctions totales, et
l'algèbre fonctionnelle dont nous aurons besoin comportera quatre
opérations : Composition : prend en argument deux fonctions, f et g, telles que
range(f)?def(g), et renvoie une fonction gof : def(f)(range(g) définie par
gof (x)= g(f(x)), x(def(f)
Couplage : prend en argument deux fonctions, f et g, telles que
def(f)=def(g), et renvoie une fonction f(g : def(f)(range(f)(range(g)
définie par f(g(x)= , x(def(f)
Projection : l'opération habituelle sur le produit de deux ou plusieurs
ensembles
Restriction : prend en argument une fonction f : X(Y et un ensemble
E?def(f), et renvoie une fonction f/E : E(Y définie par f/E(x)= f(x) pour
tout x dans E Proposition (cf figure 2)
Soit deux fonctions f : X(Y et g : X(Z, alors f= (Y o(f(g) et g= (Z o(f(g)
((Y et (Z sont des projections sur Y(Z) Propriétés des inverses
Rappelons d'abord que l'inverse (ou réciproque) d'une fonction f : X(Y,
noté f-1, est définie comme suit : f-1(y)= {x / f(x)= y} ; il associe
chaque élément y de range(f) à l'ensemble des éléments x de def(f) ayant y
comme image (et donc chaque élément y n'appartenant pas a range(f) à
l'ensemble vide). Voici quelques propriétés des inverses :
composition : (gof)-1(z)= ({f-1(y) / y(g-1(z)}, pour tout z(range(gof)
couplage : (f(g)-1((y, z))= f-1(y)( g-1(z)
restriction : (f/E)-1 (y) = E(f-1(y), pour tout y(range(f/E) Exercice : Pour les fonctions données en table 1, donner les résultats de
calculs suivants :
1/ g2og1, g1og, g2o(g1og), (g2og1)og
2/ f(g, g(h, (f(g)((g(h), f((g(h), (f(g)(h, (g1og)((h1oh),
f((g2og1og)((h2oh), g(g
3/ vérifier si g= (Store o(g(h) et h= (Product o(g(h)
4/ g/E, h/F, (g/E)((h/F), où E= {1, 2, 4, 5, 7, 8} et F= {2, 3, 4, 6,
7, 9}
5/ g-1, (g1og)-1, ((g2og1)og) -1¸ (g(h)-1, ((g1og)((h1oh))-1,
(g/E)-1, (h/F)-1
Quelles conclusions en tirez-vous concernant les propriétés des opérations
de l'algèbre?
TD-2 : Expressions de chemin et langage OLAP Schéma dimensionnel (voir figure 2) Un schéma dimensionnel est un graphe connexe, orienté, acyclique, étiqueté
tel que :
une seule racine, appelé l'origine et notée O
un sommet distingué, appelé l'unité et noté (
chaque sommet A est associé à un domaine, noté dom(A) ; dom(() est
singleton
il n'y a aucune flèche avec ( comme source
les étiquettes de toutes les flèches sont distinctes
les flèches de source O sont d'un de deux types, dimension ou mesure
il y a une dimension de source O et de cible (, appelée dimension unité et
notée ( : O ( (
il n'y a pas de flèche entre les cibles de deux flèches de dimension
Terminologie : la notation f : X( Y indiquera une flèche avec étiquette f,
source X et cible Y dans le schéma; de même, on parlera de la source et de
la cible d'un chemin dans le schéma chaque sommet autre que l'origine est appelé attribut
les valeurs du domaine de O sont appelées des objets
la distinction entre dimensions et mesures est faite par le concepteur
tout schéma dimensionnel doit contenir au moins une mesure
chemin dimensionnel : tout chemin de source O commençant par une dimension
( tout attribut d'un tel chemin est appelé un niveau d'agrégation
chemin de mesure : tout chemin de source O commençant par une mesure
( tout attribut d'un tel chemin est appelé un niveau de mesure
la figure 2 montre un schéma dimensionnel où f, g, h sont les dimensions et
m est la mesure Base de données dimensionnelle (bdd) Etant donné un schéma dimensionnel S, une bdd sur S est une fonction ( qui
associe chaque sommet A de S à un sous-ensemble fini ((A) du domaine de A,
la flèche ( à une fonction constante et chaque autre flèche f : X(Y de S à
une fonction totale ((f): ((X)(((Y) - les fonctions d'une bdd peuvent être données de manière explicite ou
implicite
- dans la suite, nous omettrons le symbole (, le contexte indiquant s'il
s'agit d'une flèche ou d'une fonction
- le fait que les fonctions d'une bdd soient totales entraîne la contrainte
suivante :
contrainte référentielle : range(f)?def(g) pour toutes fonctions f :
X(Y et g : Y(Z
- le passage à un niveau supérieur induit un regroupement ou «agrégation»
au niveau inférieur Expression de chemin

Etant donné un schéma dimensionnel S, une expression de chemin sur S est
une expression bien formée dont les opérandes sont des flèches de S et dont
les opérateurs sont ceux de l'algèbre fonctionnelle. De manière plus
formelle, une expression de chemin e sur S est définie par la grammaire
suivante, où le symbole '::=' signifie 'peut être' et où p, q, e1,... , ej
désignent des expressions de chemin : e ::= f, où f : X(Y est une flèche de S ; source(e)= X et target(e)= Y
qop, où target(p)= source(q) ; source(e)= source(p) et target(e)=
target(q)
p(q, où source(p)=source(q) ; source(e)= source(p) et target(e)=
target(p)(target(q)
p/E, où E?source(p) ; source(e)= E et target(e)= targ