Cours pour les Master I Les BDAs (Les bases de données réparties)

Cours pour les Master I Les BDAs (Les bases de donnes rparties)

Bibliographie Pr. Ladjel Bellatreche Bases de donnes rparties, Pr. Ladjel Bellatreche (Ensma) Principles of Distributed Database Systems,Edition- M. Tamer zsu & Patrick Valduriez 2

MotivationMotivation Relation employ E (#,nom,loc,sal,) 3 Deux sites : S a, S b

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

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

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

ApplicationsApplications 7 Relation employ E (#,nom,loc,sal,)

Objectifs des BDR 8 Autonomie locale Autonomie locale Transparence Performance amliore Fiabilit et disponibilit accrues Partage accru de donnes et ressources Expansion graduelle

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

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

Types de BDR 11

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

ExempleExemple 13 BD Clients BD Clients dOran BD Clients dAlger BD Clients de Constantine Processus de Rpartition

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.

ExempleExemple 15

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

Architecture des schmas dune BDR 17

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)

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

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

Ascendante / Descendante (dune autre perspective) 21

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

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 )

Objectifs de la dcomposition 24

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

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

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

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.

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

Fragmentation Verticale (1) 30 Dcomposition de la table en groupes de colonnes. Dcomposition de la table en groupes de colonnes.

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?

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

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)

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

Comment Fragmenter? 35

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

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 )

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

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 !

Minterm predicates (1) 40

Minterm predicates (2) 41

Fragments finaux 42

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:

(Architectures)(Architectures) 44 Partie Complmentaire

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

Client/Serveur (2) 46

Collaborating Servers 47 Client Query

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!!

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

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

Documents

Cours pour les Master I Les BDAs (Les bases de données réparties)