Cours pour les Master I Les BDAs (Les bases de données réparties)
Preview:
Citation preview
- Page 1
- Cours pour les Master I Les BDAs (Les bases de donnes
rparties)
- Page 2
- Bibliographie Pr. Ladjel Bellatreche Bases de donnes rparties,
Pr. Ladjel Bellatreche (Ensma) Principles of Distributed Database
Systems,Edition- M. Tamer zsu & Patrick Valduriez 2
- Page 3
- MotivationMotivation Relation employ E (#,nom,loc,sal,) 3 Deux
sites : S a, S b
- Page 4
- Bases de donnes rparties (BDR) Diffrents niveaux de rpartition
Donnes Donnes Schmascatalogues Schmas ou catalogues de la BD SGBD
SGBD Traitement (requtes, transactions) Traitement (requtes,
transactions) Composants matriels: Composants matriels: mmoires,
disques, 4
- Page 5
- BDR = BD + Rseau BD rpartie (distributed database) Ensemble de
BDs gres par des sites diffrents et qui apparaissent lutilisateur
comme une base unique To the user, a distributed system should look
exactly like a non distributed system (Chris. Date, Introduction to
Database Systems) SGBD Rparti (SGBDR) Logiciel qui gre une BDR et
qui rend la rpartition transparente Client de SGBDR Application qui
accde aux informations distribues par les interfaces du SGBDR
5
- Page 6
- ApplicationsApplications Cas de grosses entreprises ou
organismes ayant des agences gographiquement distribues: Banques
Fabrication Mdicales (BD biologiques) Militaires Systmes de
rservation de compagnies ariennes WEB 6
- Page 7
- ApplicationsApplications 7 Relation employ E
(#,nom,loc,sal,)
- Page 8
- Objectifs des BDR 8 Autonomie locale Autonomie locale
Transparence Performance amliore Fiabilit et disponibilit accrues
Partage accru de donnes et ressources Expansion graduelle
- Page 9
- Nouveaux dfis (1) 9 Conception dune BDR Conception dune BDR
Fragmentation Allocation Rplication (totale ou partielle)
Transparence la rpartition Transparence la rpartition Extension de
la notion dindpendance logique et physique des donnes Extension de
la notion dindpendance logique et physique des donnes Localisation
(rplication, fragmentation) Localisation (rplication,
fragmentation) Aucune spcification de la localisation des donnes
Aucune spcification de la localisation des donnes
- Page 10
- Nouveaux dfis (2) 10 Optimisation de requtes rparties
Optimisation de requtes rparties Choix de la copie en lecture Choix
de la copie en lecture Mise jour de toutes les copies Mise jour de
toutes les copies Plan d'excution rparti Transactions rparties
Transactions rparties Maintien des proprits ACID des transactions
Maintien des proprits ACID des transactions Utilisateur aura
formuler ses transactions de la mme manire que dans un
environnement centralis Utilisateur aura formuler ses transactions
de la mme manire que dans un environnement centralis
- Page 11
- Types de BDR 11
- Page 12
- BDR Homogne 12 Obtenue en divisant une BD en un ensemble de BD
locales, chacune tant gre par le mme SGBD Obtenue en divisant une
BD en un ensemble de BD locales, chacune tant gre par le mme SGBD
Mme modle de donnes Mme modle de donnes Mme langage de requtes Mme
langage de requtes Exemple: DB2, ORACLE (SQL) Exemple: DB2, ORACLE
(SQL) Donnes de la base sont rparties sur plusieurs sites Donnes de
la base sont rparties sur plusieurs sites
- Page 13
- ExempleExemple 13 BD Clients BD Clients dOran BD Clients dAlger
BD Clients de Constantine Processus de Rpartition
- Page 14
- BDR Htrognes 14 Deux niveaux dhtrognit: Deux niveaux dhtrognit:
Les BD ont le mme modle (relationnel) mais sont gres par des SGBD
diffrents (Oracle, SQL server, .) Les BD ont le mme modle
(relationnel) mais sont gres par des SGBD diffrents (Oracle, SQL
server, .) Les BD ont des modles diffrents (relationnel, objet) et
gres par des SGBD diffrents (Oracle, O2) Les BD ont des modles
diffrents (relationnel, objet) et gres par des SGBD diffrents
(Oracle, O2) BDR htrogne BDR htrogne BD rpartie obtenue en intgrant
dans une BD unique un ensemble de BD locales gres par des SGBD
diffrents. BD rpartie obtenue en intgrant dans une BD unique un
ensemble de BD locales gres par des SGBD diffrents.
- Page 15
- ExempleExemple 15
- Page 16
- Dfinition dune BDR 16 Site local Site local Site de naissance
(ne change pas) Site de naissance (ne change pas) Site de stockage
(peut changer) Site de stockage (peut changer) Site de lusager Site
de lusager ALI de site S1 cre une relation R et la stocke dans S2
ALI de site S1 cre une relation R et la stocke dans S2 CREATE TABLE
ALGER(NA, Type, Poids, Gare, Etat) ON S2 S1 = site de naissance
(ALGER @ S1) S1 = site de naissance (ALGER @ S1) S2 = site de
stockage S2 = site de stockage ALI de S1 dplace la relation de S2
vers S3 ALI de S1 dplace la relation de S2 vers S3 MIGRATE TABLE
ALGER@S1 TO S3
- Page 17
- Architecture des schmas dune BDR 17
- Page 18
- Conception des BDR 18 Approche descendante Approche descendante
Environnement homogne Environnement homogne Conception partir de
zro Conception partir de zro Nouvelles tapes avant la conception
physique Nouvelles tapes avant la conception physique Localisation
des donnes Localisation des donnes Schmas locaux Schmas locaux
Approche ascendante Approche ascendante On part de BD existantes
(souvent htrognes) On part de BD existantes (souvent htrognes)
- Page 19
- Approche descendante 19 BD BD1BD1BD2BD2BD3BD3
ECLATEMENTECLATEMENT Conception dune BD rpartie Conception dune BD
rpartie Matrise de la complexit de la rpartition (fragmentation,
duplication, placement) Matrise de la complexit de la rpartition
(fragmentation, duplication, placement) Dfinition des schmas locaux
partir du schma global Dfinition des schmas locaux partir du schma
global
- Page 20
- Approche ascendante 20 BDR BD fdre BD1BD1BD2BD2BD3BD3
INTEGRATIONINTEGRATION Intgration/fdration de BD existantes
Intgration/fdration de BD existantes Matrise de lhtrognit smantique
(BD) et syntaxique (SGBD, communications,....) Matrise de lhtrognit
smantique (BD) et syntaxique (SGBD, communications,....) Matrise de
lintgration des schmas locaux pour crer un schma global Matrise de
lintgration des schmas locaux pour crer un schma global
- Page 21
- Ascendante / Descendante (dune autre perspective) 21
- Page 22
- Approche ascendante 22 Intgration des BD locales existantes
dans une seule base Intgration des BD locales existantes dans une
seule base La distribution des donnes est prexistante La
distribution des donnes est prexistante Smantique des schmas
participants Smantique des schmas participants
- Page 23
- Approche descendante 23 La distribution des donnes est bien
prsente La distribution des donnes est bien prsente Les tables du
schma global sont fragmentes ( processus de fragmentation ) Les
tables du schma global sont fragmentes ( processus de fragmentation
) Fragment Fragment Sous-table obtenue par slection de lignes et de
colonnes partir dune table globale Sous-table obtenue par slection
de lignes et de colonnes partir dune table globale Les fragments
sont donc placs sur des sites ( processus dallocation ) Les
fragments sont donc placs sur des sites ( processus dallocation
)
- Page 24
- Objectifs de la dcomposition 24
- Page 25
- Techniques de fragmentation 25 Problme de fragmentation:
Problme de fragmentation: Entre: une relation dun schma global
Entre: une relation dun schma global Sortie: un schma de
fragmentation (ensemble de fragments) Sortie: un schma de
fragmentation (ensemble de fragments) Diffrents types de
fragmentation Diffrents types de fragmentation Horizontale
Horizontale Verticale Verticale Mixte Mixte
- Page 26
- Fragmentation Horizontale 26 Dcomposition de la table en
groupes de lignes Dcomposition de la table en groupes de lignes
Deux types de fragmentation horizontale: Deux types de
fragmentation horizontale: Primaire Primaire Drive Drive
- Page 27
- Fragmentation Horizontale Primaire 27 Obtention des fragments
horizontaux: Obtention des fragments horizontaux: Fragmentation
horizontale est dfinie par lopration de slection Fragmentation
horizontale est dfinie par lopration de slection Exemple Exemple
Client(NClient, Nom, Ville) peut tre fragmente : Client(NClient,
Nom, Ville) peut tre fragmente : Client1= SELECT * FROM Client
WHERE Ville = Paris Client1= SELECT * FROM Client WHERE Ville =
Paris Client2= SELECT * FROM Client WHERE Ville Paris Client2=
SELECT * FROM Client WHERE Ville Paris Reconstruction de la
relation initiale: Reconstruction de la relation initiale: Client =
Client1 Client2 Client = Client1 Client2
- Page 28
- Fragmentation Horizontale Drive(1) 28 Fragmentation dune table
en fonction des fragments horizontaux dune autre table.
Fragmentation dune table en fonction des fragments horizontaux dune
autre table.
- Page 29
- Fragmentation Horizontale Drive(2) 29 Obtention des fragments
horizontaux drivs. Obtention des fragments horizontaux drivs.
Fragments drivs sont obtenus par lopration de semi-jointure
Fragments drivs sont obtenus par lopration de semi-jointure Exemple
Exemple Commande(NClient, NProduit, Date, Qte, NReprsentant)
Commande(NClient, NProduit, Date, Qte, NReprsentant) Commande1=
SELECT * FROM Commande Commande1= SELECT * FROM Commande WHERE
Nclient IN ( SELECT NClient FROM CLIENT1) Commande2= SELECT * FROM
Commande Commande2= SELECT * FROM Commande WHERE NClient IN (
SELECT NClient FROM CLIENT2) Reconstruction de la relation
initiale: Reconstruction de la relation initiale: Commande =
Commande1 Commande2 Commande = Commande1 Commande2
- Page 30
- Fragmentation Verticale (1) 30 Dcomposition de la table en
groupes de colonnes. Dcomposition de la table en groupes de
colonnes.
- Page 31
- Fragmentation Verticale (2) 31 Obtention des fragments
verticaux: Obtention des fragments verticaux: Fragmentation
verticale est dfinie par lopration de projection Fragmentation
verticale est dfinie par lopration de projection Exemple Exemple
Client(NClient, Nom, Sexe,Ville) peut tre fragmente :
Client(NClient, Nom, Sexe,Ville) peut tre fragmente : Client 1 =
SELECT NClient, Nom FROM Client Client 1 = SELECT NClient, Nom FROM
Client Client 2 = SELECT NClient, Sexe, Ville FROM Client Client 2
= SELECT NClient, Sexe, Ville FROM Client Reconstruction de la
relation initiale: Reconstruction de la relation initiale: Client =
Client 1 join Client 2 Client = Client 1 join Client 2 Pourquoi le
NClient est dupliqu dans les deux fragments?
- Page 32
- Fragmentation Mixte 32 Obtention des fragments mixtes:
Obtention des fragments mixtes: Fragmentation mixte rsulte de
lapplication successive doprations de fragmentation horizontale et
de fragmentation verticale Fragmentation mixte rsulte de
lapplication successive doprations de fragmentation horizontale et
de fragmentation verticale
- Page 33
- Avantages et inconvnients de la fragmentation 33 + Rduction des
accs non pertinents + Paralllisme intra-requte + Combine avec
dautres techniques doptimisation (index, vues matrialises, etc.)
gnration des fragments disjoints est un problme difficile gnration
des fragments disjoints est un problme difficile Accs multiples aux
fragments ncessitent des oprations de jointure et dunion Accs
multiples aux fragments ncessitent des oprations de jointure et
dunion La migration des donnes (consquence dune mauvaise
fragmentation horizontale) La migration des donnes (consquence dune
mauvaise fragmentation horizontale)
- Page 34
- Rgles de correction 34 Compltude Compltude Assure que tous les
tuples dune relation sont associs au moins un fragment
(fragmentation verticale) Assure que tous les tuples dune relation
sont associs au moins un fragment (fragmentation verticale)
Reconstruction Reconstruction Assure quune relation peut tre
reconstruite partir de ses fragments Assure quune relation peut tre
reconstruite partir de ses fragments Disjonction Disjonction Assure
que les fragments dune relation sont disjoints deux deux Assure que
les fragments dune relation sont disjoints deux deux
- Page 35
- Comment Fragmenter? 35
- Page 36
- Fragmentation dirige par des requtes 36 Optimiser les requtes
les plus frquentes: Optimiser les requtes les plus frquentes: Rgle
20/80; Rgle 20/80; Connaissance pralable des requtes; Connaissance
pralable des requtes; Frquences daccs des requtes. Frquences daccs
des requtes. Travail de ladministrateur de la BD Travail de
ladministrateur de la BD Changement de requtes peut entraner une
re-fragmentation Changement de requtes peut entraner une
re-fragmentation Tuning de la base de donnes Tuning de la base de
donnes
- Page 37
- Procdure de fragmentation (1) 37 Informations sur la base de
donnes : Informations sur la base de donnes : Prdicats simples :
Prdicats simples : Exemple Exemple p1: Ville =Alger p1: Ville
=Alger p2: Salaire 70 000 p2: Salaire 70 000 tant donne une
relation R(A 1, A 2,..., A n ) Un prdicat simple p j dfini sur R
est dfini: p j : A i valeur avec: {=,,,, }; et valeur domaine(D i )
tant donne une relation R(A 1, A 2,..., A n ) Un prdicat simple p j
dfini sur R est dfini: p j : A i valeur avec: {=,,,, }; et valeur
domaine(D i )
- Page 38
- Procdure de fragmentation (2) 38 Soit P r = {p 1, p 2,..., p m
} un ensemble de prdicats simples dfinis sur la relation R i,
lensemble de minterms M= {m 1, m 2,..., m z } est dfini comme suit:
Soit P r = {p 1, p 2,..., p m } un ensemble de prdicats simples
dfinis sur la relation R i, lensemble de minterms M= {m 1, m 2,...,
m z } est dfini comme suit: Exemple Exemple m 1 : (Ville =Poitiers)
(Salaire 10 000) m 1 : (Ville =Poitiers) (Salaire 10 000) m 2 :
NOT(Ville=Poitiers) (Salaire 10 000) m 2 : NOT(Ville=Poitiers)
(Salaire 10 000) m 3 : (Ville =Poitiers) NOT(Salaire 10 000) m 3 :
(Ville =Poitiers) NOT(Salaire 10 000) m 4 : NOT(Ville =Poitiers)
NOT(Salaire 10 000) m 4 : NOT(Ville =Poitiers) NOT(Salaire 10 000)
M = {m i | m i = P j P r p* j }, 1 i z, 1 j z; where p* j = p j or
p j M = {m i | m i = P j P r p* j }, 1 i z, 1 j z; where p* j = p j
or p j
- Page 39
- Informations sur la BD 39 Slectivit dun minterm : sel (m i )
Slectivit dun minterm : sel (m i ) Le nombre de tuples de la
relation satisfaisant la clause du minterm Le nombre de tuples de
la relation satisfaisant la clause du minterm Frquence daccs dune
requte : acc (q i ) Frquence daccs dune requte : acc (q i ) Ce sont
des informations permettant de dcider que si le fragment gnr par le
minterm vaut la peine dtre fragmenter et migrer sur un site part
!
- Page 40
- Minterm predicates (1) 40
- Page 41
- Minterm predicates (2) 41
- Page 42
- Fragments finaux 42
- Page 43
- Prise en considration de la smantique 43 limination des
fragments contradictoires dpend de la smantique des applications
limination des fragments contradictoires dpend de la smantique des
applications Exemple Exemple Si LOC est SA, SB, alors on ajoute les
fragments suivants: Si LOC est SA, SB, alors on ajoute les
fragments suivants:
- Page 44
- (Architectures)(Architectures) 44 Partie Complmentaire
- Page 45
- Client/Serveur (1) 45 Modle d'architecture applicative o les
programmes sont rpartis entre processus clients et serveurs
communiquant par des requtes avec rponses. Modle d'architecture
applicative o les programmes sont rpartis entre processus clients
et serveurs communiquant par des requtes avec rponses. Une
rpartition hirarchique des fonctions Une rpartition hirarchique des
fonctions Donnes sur le serveur partages entre N clients Donnes sur
le serveur partages entre N clients Interfaces graphiques sur la
station de travail personnelle Interfaces graphiques sur la station
de travail personnelle Communication par des protocoles standardiss
Communication par des protocoles standardiss Distribution des
programmes applicatifs afin de minimiser les cots Distribution des
programmes applicatifs afin de minimiser les cots
- Page 46
- Client/Serveur (2) 46
- Page 47
- Collaborating Servers 47 Client Query
- Page 48
- Peer-to-peer (P2P) 48 Aucune diffrence entre le client et le
serveur Aucune diffrence entre le client et le serveur Le client
peut jouer le rle de serveur et vice versa Le client peut jouer le
rle de serveur et vice versa Chaque machine a sa propre base de
donnes (+SGBD) Chaque machine a sa propre base de donnes (+SGBD)
Les BDR dans le contexte P2P reste un sujet de recherche!! Les BDR
dans le contexte P2P reste un sujet de recherche!!
- Page 49
- Architecture GAV et LAV 49 GAV : Global as View GAV : Global as
View Schma global dfini comme une vue intgrante sur schmas locaux
Schma global dfini comme une vue intgrante sur schmas locaux
Approche ascendante depuis les sources vers le mdiateur Approche
ascendante depuis les sources vers le mdiateur Difficult pour
ajouter une source Difficult pour ajouter une source LAV : Local As
View LAV : Local As View Chaque source locale est dfinie comme une
vue locale du schma global Chaque source locale est dfinie comme
une vue locale du schma global Approche descendante depuis le
mdiateur vers les sources Approche descendante depuis le mdiateur
vers les sources Difficult pour rconcilier source et vue locale
Difficult pour rconcilier source et vue locale
- Page 50
- 50 Ce qui na pas t entam dans cette partie Processus
dallocation des fragments Processus dallocation des fragments
Optimisation de Requtes (Contexte rparti) Optimisation de Requtes
(Contexte rparti) valuation des requtes dans un environnement
rparti valuation des requtes dans un environnement rparti Bases de
donnes htrognes Bases de donnes htrognes Architecture de mdiation
Architecture de mdiation Adaptateur (Wrapper) Adaptateur (Wrapper)
Mdiateur Mdiateur