BASES DE DONNES RPARTIES

ET PARTAGE DE DONNES LARGE CHELLE

Master 1 MIF37

Nicolas.Lumineau@liris.cnrs.fr

CM1

JUSQU PRSENT .

SQL Toto@orapeda1

N-uplets

1 base N relations que vous avez cres M requtes SQL

MIF37

MAINTENANT
Toto@orapeda2 Toto@orapeda3

SQL

N-uplets Toto@orapeda1

K bases N relations que vous avez cres ou qui ont t cres par dautres M requtes SQL

MIF37

AUTRE CONTEXTE
Htrognit des donnes

Toto@orapeda2

SQL Toto@orapeda1
Toto@orapeda3

N-uplets
MIF37

AUTRE CONTEXTE
Htrognit des sources XML
<> <> <> <>

Toto

Mdiateur

Fichier TXT --- -- -- -- - - -- -- - --- --- - -- - - -- - - --

Toto@orapeda1

MIF37

AUTRE CONTEXTE
Passage lchelle

MIF37

CONTEXTE
un ensemble de donnes stockes sur plusieurs sites (machines) communicant via un rseau.

C B

BD3

BD2

BD1

Rseau

BD4

BD5

MIF37

PROBLME

Comment offrir aux utilisateurs une vue sur lensemble des donnes en faisant abstraction de leur localisation physique ?

MIF37

CAS POSSIBLES (1)

Systme grant de manire transparente un ensemble de BD logiquement relies et rparties sur diffrents sites
Base de Donnes Rpartie
C B D

BD3

BD2

BD1

Rseau

BD4

BD5

MIF37

CAS POSSIBLES (2)

Systme grant plusieurs BD htrognes capables dinteroprer via un modle commun
Base de Donnes Fdre

C B

BD3

BD2

vue commune

BD1

BD4

Rseau
I J

BD5

MIF37

CAS POSSIBLES (3)

Systme grant plusieurs BD (htrognes ou non) capables dinteroprer sans modle commun
Multi-Base
C B D

BD3

BD2

BD1

Rseau

BD4

BD5

MIF37

REFORMULATION DU PROBLME

Comment offrir aux utilisateurs une vue sur lensemble des donnes en faisant abstraction de leur localisation physique tout en garantissant de bonnes performances de traitement des requtes?

MIF37

Temps de traitement

Passage lchelle

ORGANISATION DE CE COURS Cours / TD :

Conception des bases de donnes rparties Intgration et Mdiation de donnes htrognes Evaluation de requtes rparties Architectures P2P

TP
Conception dune BDR Intgration de donnes Traitement de requtes rparties Simulation et Prototypage dapplications P2P

MIF37

PR-REQUIS : ALGBRE RELATIONNELLE

ALGBRE RELATIONNELLE
Dfinition Une algbre relationnelle est un ensemble doprations agissant sur des relations et produisant des relations
Oprateurs :
<Oprateur><parametres> <Oprande> <Rsultat> <Oprande> <Oprateur><parametres> <Oprande> <Rsultat>

Cest un langage ferm les oprandes et les rsultats sont toujours des relations
MIF37

BREF RAPPEL (OPRATEURS ALGBRIQUES)

Pour R et S deux relations UNION R S = { t | tR ou tS} INTERSECTION

R S = { t | tR et tS}
DIFFERENCE

R S={ t | tR et tS}
PRODUIT CARTESIEN R S = {t.A1Ak1 Ak1+1Ak1+k2 | t.A1Ak1 R et t.Ak1+1Ak1+k2 S } DIVISION MIF37 R S = {Ak+1,,Ak+n| t. A1,,Ak,Ak+1,,Ak+n R et t.A1Ak S avec tous les n-uplets t tels que {t} S R

BREF RAPPEL (OPRATEURS ALGBRIQUES SPCIFIQUES)

Pour R et S deux relations
PROJECTION A1,,An(R)={t.A1 An | tR} SELECTION F(R)={t | tR et F(t) est vrai}, F une formule logique sans quantificateur JOINTURE
R
FS

= {t.A1AnB1Bm | t.A1AnR et t.B1BmS et F est vraie }

SEMI-JOINTURE R
FS

= {t.A1An | t.A1AnR et t.B1BmS et F est vraie }

MIF37

RENOMMAGE

A1/B1,An/Bn (R)={t | tR et A1 renomm en B1, An renomm en Bn }

EXERCICE
Une UFR dInformatique dispose dune base de donnes lui permettant darchiver les rsultats de ses tudiants aux examens. Le schma de cette base comprend les relations suivantes : etudiant( No, Nom, Prenom, Rue, Ville, DateNaiss) ; enseignant( No, Nom, Prenom, Rue, Ville, DateNaiss) ; module( Diplome, NomMod, ObliOp, NoResp) ; diplome( Titre, NbOpt) ; examen( Diplome, Module, Session, Annee, NoEt, Note) . Requtes :
R1 : Liste des noms des tudiants lyonnais ayant pass au moins un examen en 2010 et des enseignants lyonnais responsables dun module R2 : Liste des tudiants lyonnais (numro, nom et prnom), qui ont russi tous les examens de modules obligatoires auxquels ils se sont prsents en 2010. Pour chaque tudiant on prcisera le diplme obtenu ainsi que son nombre doptions.

MIF37

CONCEPTION DE BDR

DIFFRENTS SCNARII POSSIBLES

Des donnes jusqualors centralises doivent tre rparties sur diffrents sites
Comment dcouper logiquement ma base pour rpartir les n-uplets sur les diffrents sites?

Des donnes rparties sur diffrents sites doivent tre interrogeables depuis nimporte quel site
Comment offrir lutilisateur un moyen daccs transparents toutes ces donnes ?
MIF37

RAPPEL
Dans un contexte centralis : Analyse des besoins

Modle conceptuel de donnes

Schma E/A

Modle relationnel

Modle logique
MIF37

21

DANS UN CONTEXTE DCENTRALIS

Analyse des besoins

Modle conceptuel de donnes

Processus de conception de BD centralis

Modle logique

Migration / Dcomposition / Rplication Processus de distribution Allocation (Placement)

MIF37

22

MIGRATION
Transfre dune relation complte sur un site distant

1.copie
BD source

BD cible

2.suppression Intrt Rapprocher les donnes des besoins

MIF37

23

RPLICATION
Cration dune copie conforme dune table (ou ensemble de tuples) sur un site distant. La copie doit rester cohrente avec les donnes sources

1.copie
BD principale

BD secondaire

2. synchronisation

Intrt Avoir les mmes donnes sur diffrents sites

MIF37

24

DCOMPOSITION
BDinit
SCH
{D1}

SC1(SCH) SC2(SCH) SC3(SCH)

Donnes {D2}
{D3}

BD1

BD2

BD3

MIF37

SCH est le schma global qui permet linterrogation des donnes stockes sur BD1, BD2 et BD3 !

SCHMA GLOBAL Le schma global est constitu :

dun schma conceptuel global
Contenant la description globale et unifie de toutes les donnes de la BDR Indpendant de la rpartition des donnes

dun schma de placement (dallocation)

Contenant les rgles de correspondance avec les donnes locales indpendant la fragmentation et la rplication

Remarque :
Le schma global fait partie du dictionnaire de la BDR et peut tre conu comme une BDR (rpliqu ou fragment)
MIF37

LES OUTILS POUR DCOMPOSER LES DONNES

Les diffrentes fragmentations
Fragmentation horizontale Fragmentation horizontale drive
Un fragment est une slection dun sousensemble de tuples

Fragmentation Verticale

Un fragment est une projection sur un sous-ensemble dattributs Un fragment est une composition dune fragmentation horizontale (drive) avec une fragmentation verticale

Fragmentation Mixte

MIF37

FRAGMENTATION HORIZONTALE
Client nclient nom Dupont Martin Martin Smith ville Paris Lyon Paris Lille

Fragments dfinis par slection

Client2 =
Client1 =

ville = Paris(Client)

C1 C2 C3 C4

ville != Paris(Client)

Client1 nclient C1 C3 Client2 nom Dupont Martin ville Paris Paris

Reconstruction Client = Client1 U Client2

nclient C2 C4

nom Martin Smith

ville Lyon Lille

MIF37

FRAGMENTATION HORIZONTALE DRIVE

Fragments dfinis par jointure Cde1 = Cde Client1
nclient

Cde ncde D1 D2 D3 D4 nclient C1 C1 C2 C4 produit P1 P2 P3 P4 qt 10 20 5 10

Cde2 = Cde

nclient

Client2

Reconstruction Cde = Cde1 U Cde2

Cde1 ncde D1 D2 nclient C1 C1 produit P1 P2 qt 10 20

Cde2 ncde D3 D4 nclient C2 C4 produit P3 P4 qt 5 10

MIF37

FRAGMENTATION VERTICALE (1)

Fragments dfinis par projection
Cde

Cde1 = Cde2 =

ncde, nclient(Cde) ncde, produit, qt(Cde)

ncde D1 D2 D3 D4

nclient C1 C1 C2 C4

produit P1 P2 P3 P4

qt 10 20 5 10

Reconstruction Cde = Cde1

ncde

Cde2
Cde1 ncde D1 D2 D3 D4 nclient C1 C1 C2 C4 Cde2 ncde D1 D2 D3 D4 produit P1 P2 P3 P4 qt 10 20 MIF37 5 10

FRAGMENTATION VERTICALE (2)

Cde ncde nclient C1 C1 C2 C4 produit P1 P2 P3 P4 qt 10 20 5 10

Remarque importante : Il est important de conserver les cls dans chaque fragment vertical Sinon reconstruction impossible !
Cde1 ncde D1 D2 D3 D4

D1 D2 D3 D4

Cde2 nclient C1 C1 C2 C4 produit P1 P2 P3 P4 qt 10 20 5 10

MIF37

FRAGMENTATION MIXTEClient
nclient nom Dupont Martin Martin Smith ville Paris Lyon Paris Lille C1 C2 C3 C4

Fragments dfinis par slection et projection

Fragmentation horizontale Client1 nclient C1 C3 nom Dupont Martin ville Paris Paris Client2 nclient C2 C4 nom Martin Smith ville Lyon Lille

Fragmentation verticale Client11 nclient C1 C3 nom Dupont Martin Client12 nclient C1 C3 ville Paris Paris Client21 nclient C2 C4

Fragmentation verticale Client22 nom Martin Smith nclient C2 C4 ville

MIF37

Lyon Lille

FRAGMENTATION CORRECTE
Si R=(A1,,Ak) est la table globale initiale, la fragmentation est dite correcte si elle est : Complte
chaque lment de R doit se trouver dans un fragment

Reconstructible
on doit pouvoir recomposer R partir de ses fragments

Disjointe
chaque lment de R (hormis les cls) ne doit pas tre dupliqu

MIF37

Client

Cde nom Dupont Martin Martin Smith ville Paris Lyon Paris Lille ncde nclient C1 C1 C2 C4 produit P1 P2 P3 P4 qt

EXERCICE

nclient C1 C2 C3 C4

D1 D2 D3 D4

10 20 5 10

Les fragmentations suivantes sont-elles correctes ?

Cde1 ncde D1 D2 nclient C1 C1 produit P1 P2 qt Cde2 ncde D3 D4 nclient C2 C4 produit P3 P4 qt

10 20

5 10

Client1 nclient C1 C2 nom Dupont Martin ville Paris Lyon

Client2 nclient C2 C4 nom Martin Smith ville Lyon Paris

Client1 nclient C1 C2 C3 C4 nom Dupont Martin Martin Smith

Client2 nom Dupont Martin Martin Smith ville

MIF37
Paris Lyon Paris Lille

MTHODOLOGIES
Stratgie de fragmentation
En fonction des hypothses :
Informations sur les contraintes de placement

En fonction des besoins :

Informations sur les requtes gnralement poses

MIF37

EXEMPLE DE FRAGMENTATION (MTHODO1)

Contexte On considre une base de donnes comprenant la table:
ETUDIANT (numE, nomE, pnomE, numC) VACATAIRE (numV, nomV, pnomV) CENTRE (numC, villeC, adrC, telC, zoneC) FORMATION( numC, numF, nomF, nbHeure, numV, coutF, rentabilitF)

avec : zoneC {Nord, Est, Sud , Ouest} Sites gographiques : Paris, Lyon, Marseille, Bordeaux Hypothses
H1 : Paris gre les centres du nord de la France, Lyon les centres de la zone Est, Marseille les centres de zone sud et Bordeaux les centres de la zone Ouest. H2 : Chaque centre gre ses tudiants H3 : Les vacataires dlivrent des formations dans tous les centres H4 : Les informations sur les formations sont gres Paris, hormis les MIF37 informations lies au cot et la rentabilit qui sont stockes Lyon

EXEMPLE DE FRAGMENTATION (MTHODO1)

CENTRE (numC, villeC, adrC, telC, zoneC)

avec : zoneC {Nord, Est, Sud , Ouest}

H1 : Paris gre les centres du nord de la France, Lyon les centres de la zone Est, Marseille les centres de zone sud et Bordeaux les centres de la zone Ouest.

FRAGMENTATION HORIZONTALE de CENTRE

CentreParis = CentreLyon

zoneC = Nord(Centre)

zoneC = Est(Centre)

CentreMarseille = CentreBordeaux

zoneC = Sud(Centre)

zoneC =

Ouest(Centre)

MIF37

EXEMPLE DE FRAGMENTATION (MTHODO1)

ETUDIANT (numE, nomE, pnomE, numC)

H2 : Chaque centre gre ses tudiants FRAGMENTATION HORIZONTALE de ETUDIANT DERIVEE de CENTRE

EtudiantParis = Etudiant EtudiantLyon = Etudiant

numC

CentreParis CentreLyon

numC

EtudiantMarseille = Etudiant EtudiantBordeaux = Etudiant

numC

CentreMarseille CentreBordeaux
MIF37

numC

EXEMPLE DE FRAGMENTATION (MTHODO1)

VACATAIRE (numV, nomV, pnomV) H3 : Les vacataires dlivrent des formations dans tous les centres

REPLICATION de VACATAIRE

VacataireParis = Vacataire VacataireLyon = Vacataire VacataireMarseille = Vacataire VacataireBordeaux = Vacataire

MIF37

EXEMPLE DE FRAGMENTATION (MTHODO1)

FORMATION( numC, numF, nomF, nbHeure, numV, coutF, rentabilitF) H4 : Les informations sur les formations sont gres Paris, hormis les informations lies au cot et la rentabilit qui sont stockes Lyon

FRAGMENTATION VERTICALE de FORMATION

numC, numF, nomF, nbHeure, numV (Formation) FormationLyon = numC, numF, coutF, rentabilitF(Formation) FormationMarseille = FormationBordeaux =
FormationParis =
MIF37

EXEMPLE DE FRAGMENTATION
Requtes les plus souvent formules

(MTHODO2)

R1 : SELECT nomE, pnomE FROM ETUDIANT WHERE numC = 1 ; R2 : SELECT pnomE FROM ETUDIANT WHERE nomE LIKE '%R%' ; R3 : SELECT numE FROM ETUDIANT WHERE pnomE = "Jean" AND numC = 2 ;

Solution
On pose : A : numC = 1 B : nomE LIKE '%R%' C : pnomE = "Jean" D : numC = 2 : A Expression des clauses where des requtes en fonction de A,B,C et D : C1 : A C2 : B C3 : C D = C A

MIF37

EXEMPLE DE FRAGMENTATION (MTHODO2)

Solution (suite)
Expression des combinaisons possibles
1) 2) 3) 4) 5) 6) 7) 8)

C1C2C3 C1C2C3 C1C2C3 C1C2C3 C1C2C3 C1C2C3 C1C2C3 C1C2C3

1) Expression en fonction de A, B, C 2) 3) 4) 5) 6) 7) 8)

A B (C A) = AB A B (C A) = A B A B C A B C A B C A B C

6 fragments horizontaux

MIF37

EXEMPLE DE FRAGMENTATION (MTHODO2)

F1 : A B
numE 8 10 nomE DURALUMIN DURALEX pnomE Roberte Jean numC 1 6 1 7 DURAND DURACUIRE Aline Robert 2 2

F4 : A B C
numE nomE pnomE numC

F2 : A B
numE 1 3 4 nomE DUPONT DUBOIS DUBALAI pnomE Jean Robert Aline numC 1 1 1

F5 : A B C
numE 5 nomE DUGENOU pnomE Jean numC 2

F3 : A B C
numE 9 nomE DURDUR pnomE Jean numC 2

F6 : A B C
numE 2 nomE DUPOND pnomE Jeanne numC 2

EXEMPLE DE FRAGMENTATION (MTHODO2)

Rappel
R1 : SELECT nomE, pnomE FROM ETUDIANT WHERE numC = 1 ; R2 : SELECT pnomE FROM ETUDIANT WHERE nomE LIKE '%R%' ; R3 : SELECT numE FROM ETUDIANT WHERE pnomE = "Jean" AND numC =2;

Solution (suite)
On considre les projections suivantes : P1 = nomE, pnomE pour R1 P2 = pnomE pour R2 P3 = numE pour R3 Et leurs duals : ~P1 = numE, numC ~P2 = numE,nomE,numC ~P3 = nomE,pnomE,numC

MIF37

EXEMPLE DE FRAGMENTATION (MTHODO2)

Remarque :
Soit Pi et Pj les projections des requtes Ri et Rj Pi Pj : correspond aux attributs utiles pour Ri et Rj Pi ~Pj correspond aux attributs utiles uniquement pour Ri ~Pi Pj correspond aux attributs utiles uhniquement pour Rj ~Pi ~Pj correspond aux attributs inutiles pour Ri et Rj Pour la suite, on pose : IPk = { (Pi Pj), (Pi ~Pj), (~Pi Pj), (~Pi ~Pj) }
MIF37

EXEMPLE DE FRAGMENTATION= (MTHODO2) P1 nomE, pnomE

P2 = pnomE P3 = numE ~P1 = numE, numC ~P2 = numE,nomE,numC ~P3 = nomE,pnomE,numC Solution (suite)
Pour F1 (satisfaisant R1 et R2):
On a : IP1= {(pNomE), (nomE), (), (numE, numC) }

F11 = F12 = F13 =

numE, numE, numE, numE, numE,

pnomE (F1) nomE (F1) numC (F1) nomE,pnomE (F2) numC (F2)

Pour F2 (satisfaisant R1) :

On a : IP2= { (nomE , pnomE), (numE , numC) }

F21 = F22 =

Pour F3 (satisfaisant R2 et R3):

On a: IP3= {(), (pNomE), (numE), (numC, nomE) }

F31 = F32 = F33 =

numE,pnomE (F3) numE (F3) numE, nomE, numC

(F3)

MIF37

P1 = nomE, pnomE EXEMPLE DE FRAGMENTATION (MTHODO2) P2 = pnomE P3 = numE ~P1 = numE, numC ~P2 = numE,nomE,numC ~P3 = nomE,pnomE,numC Solution (suite)

Pour F4 (satisfaisant R2) :

On a : : IP4= {(pnomE), (numE,nomE,numC) }

F41 = F42 =

numE, pnomE (F4) numE,nomE,numC (F4)

Pour F5 (satisfaisant R3):

On a : : IP5= {(numE), (numE, nomE,pnomE,numC)]

F51 = F52 =

numE (F5) numE, nomE,pnomE,numC

(F5)

Pour F6 (satisfaisant personne) :

Ce fragment nintresse personne, il est donc inutile de le fragmenter verticalement

MIF37

RETOUR SUR LA RPLICATION

Principe
Faire des copies de tables (fragments) et les stocker sur des sites distants

Rgle :
La rplication est avantageuse sil y a plus de lectures que dcritures

Avantages
Accs simplifi, plus performant pour les lectures Rsistance aux pannes Paralllisme accru Evite des transferts

Inconvnients
Temps de traitement des mises jour Cohrence des donnes
MIF37

INCOHRENCE DES RPLIQUES

S1
BD BD

Q = Update Client

Rseau

S2
BD BD

S3
BD BD

S4
BD

MIF37

FONCTIONS D'UN RPLICATEUR

Dfinition des objets rpliqus table cible = sous-ensemble horizontal et/ou vertical d'une ou plusieurs tables Dfinition de la frquence de rafraichissement immdiat (aprs mise jour des tables primaires) intervalles rguliers (heure, jour, etc.) partir d'un vnement produit par l'application Rafraichissement complet ou partiel (propagation des modifications) push (primaire secondaires) ou pull (secondaires

primaire)
MIF37

GESTION STATIQUE DES MISES JOUR DES RPLIQUES

Seul le site primaire peut mettre jour, les sites cibles ne recevant que des copies en lecture

Diffusion
cible1 primaire cible2

Consolidation
primaire1 cible primaire2
MIF37

GESTION DYNAMIQUE DES MISES JOUR DES RPLIQUES

Le site primaire peut tre diffrent au cours du temps, en fonction d'vnements: panne d'un site, tat de la donnes, etc. l'instant t1 cible1 primaire cible2

l'instant t2 primaire cible2 cible1

MIF37

GESTION PARTAGE DES MISES JOUR DES RPLIQUES

Une donne appartient plusieurs sites, qui peuvent chacun mettre jour et diffuser aux autres sites augmente la disponibilit peut produire des conflits, qui doivent tre dtects et rsolus

primaire2 primaire1 primaire3

MIF37

DTECTION DES MODIFICATIONS

Solution 1 : utilisation du journal les transactions qui modifient crivent une marque spciale dans le journal dtection priodique en lisant le journal, indpendamment de la transaction qui a modifi modification de la gestion du journal Solution 2 : utilisation de triggers la modification d'une donne rplique dclenche un trigger mcanisme gnral et extensible la dtection fait partie de la transaction et la ralentit
MIF37

PRODUITS COMMERCIAUX
Outils pour la rplication: Data Propagator Relational (DProp R) d'IBM Informix OnLine CA-OpenIngres Replicator Oracle Sybase Replication Server Multi Server Option d'Afic Technologies

MIF37

STRATGIE DALLOCATION DE FRAGMENTS

Soit F un ensemble de fragments S un ensemble de sites Problme: Quelle est la distribution "optimale" de F sur S ? Optimum cot minimal de communication, stockage et traitement Performance = temps de rponse ou dbit Solution allouer une copie de fragment l o le bnfice est suprieur au cot
MIF37

QUELQUES COMMANDES UTILES SUR ORACLE

Cration de lien logique entre les bases
Create database link

Cration de fragments
Create table Copy from

Cration de rpliques
Create materialized view

MIF37

DATABASE LINK
Cr un lien avec une table dans une BD distante CREATE DATABASE LINK <nomLien> CONNECT TO <loginUser> IDENTIFIED BY <pwdUser> USING <nomBD> Exemple de commande excute sur la base orapeda2 pour crer un lien avec la base orapeda1 : CREATE DATABASE LINK lienora2versora1 CONNECT TO M1IFxxx IDENTIFIEDBY M1IFxx USING orapeda1;
MIF37

CREATE MATERIALIZED VIEW

Permet de crer des fragments partir dune base existante :

CREATE MATERIALIZED VIEW <nomRpl> REFRESH [on commit | on demand | start with next ] [ complete | fast | force ] AS ( SELECT FROM WHERE );

Exemple de commande excute sur la base orapeda2 pour crer une rplique sur la base orapeda1 :

CREATE MATERIALIZED VIEW joueurs REFRESH ON COMMIT FAST AS (Select nujoueur, nom, prenom, nation, annais From joueurs@lienora2versora1);
MIF37

BIBLIOGRAPHIE
T. zsu, P. Valduriez: Principles of Distributed Database Systems. 2nd Edition, Prentice Hall, 1999; 3rd edition, forthcoming in 2008. M. Wiesmann, F. Pedone, A. Schiper, B. Kemme, and G. Alonso. Understanding replication in databases and distributed systems. In Proceedings of 20 the International Conference on Distributed Computing Systems (ICDCS'2000), pages 264--274, Taipei, Taiwan, R.O.C., April 2000. IEEE Computer Society LosAlamitos California.

MIF37

MIF37

61

PEER DATA MANAGEMENT SYSTEMS (PDMS)

Solutions de gestion de donnes reposant sur des architectures Peer to Peer garantissant un fonctionnement lchelle de linternet.

MIF37

A DIMENSION HUMAINE
il est possible de connaitre et de se coordonner avec des serveurs de donnes distants
C

MIF37
G

ET MAINTENANT LARGE LCHELLE !

???

Qui interroger ? Comment linterroger ?

MIF37