Cours Bases de données réparties

Déroulement de l’année

!

!

! Planning :

–  28/09 : Cours, Fragmentation-Transactions (C.Labbé)

–  5/10 : TD, Fragmentation (F.Jouanot)

–  12/10 : Cours-TD, Transactions (C.Labbé-J.Jouanot)

–  19/10,26/10,2/11,9/11,16/11: Cours-TP, Admin Oracle (G.Forestier)

–  23/11,30/11: Cours-TD, Relationel-objet/semi-structuré (C.Labbé-

J.Jouanot)

2

Pourquoi une Base de Données Distribuée

! Limiter le transfert d’information (nombre et volume)

! Répartition de charge

! Augmenter la fiabilité (duplication)

! Fusionner des systèmes d’informations

! Def : Une base de données distribuée est une base de données dont les différentes parties sont stockées sur des sites (géographiquement distants), reliés par un réseau. La réunion de ces parties forme la base de données distribuée.

                                                                                                   C. L. Roncancio,- C. Labbé  notes de cours        ³

Approches de conception d’une Base de Données Distribuée

! Approche descendante (décomposition)

–  Conception du schéma conceptuel global

–  Distribution pour obtenir des schémas conceptuels locaux

–  Fragmentation

BDD :Schéma global – Affectation aux sites - Allocation

! Approche ascendante

–  Intégration de bases de données existantes

–  Hétérogénéité

Exemple

! Relation Employé (nss, nom, loc, ...)

! Relation Taux (pays, valeur, ...)

! 12 bureaux d’environ la même taille

–  6 à Paris, 4 à Marseille et 2 à Lyon

! 80% des requêtes dans une ville portent sur les employés de la ville

! 10% des requêtes dans une ville portent sur Taux

C. L. Roncancio,- C. Labbé  notes de cours       ⁵

Exemple - suite

! Créer 3 bases de données : P, M, L

! Sur chaque base : les employés de la ville et une copie de Taux.

! Si trop cher :

–  fusionner M et L

–  ou maintenir Taux à M.

6

Conception d’une BDD

! De la conception en centralisé :

–  schéma conceptuel global

•  Attributs, Domaines, Tables, Vue,…

–  schéma physique • Stockage, index, pages,…

! Nouveau en distribué :

–  Définition des fragments

•  Unité de distribution logique

–  Conception « physique » : placement des fragments, stockage, chemins d’accès.

C. L. Roncancio,- C. Labbé  notes de cours       ⁷

Pour quoi fragmenter ?

! Pas de vraie raison d’un point de vue  « distribution de données ».

! Avantages de la distribution : performances, disponibilité, tolérance aux pannes, localité...

! Grain : une relation entière est une unité de distribution trop grande

–  cas des vues, faible concurrence,

8

Comment fragmenter ?

! Grain / degré de fragmentation

–  Trop peu de fragments - faible concurrence

–  Trop de fragments - surcoût dans la reconstruction des relations

! Possibilités de fragmentation d’une relation

–  Horizontale - basée sur des sélections

–  Verticale - basée sur des projections

                                       C. L. Roncancio,- C. Labbé  notes de cours       ⁹

Comment fragmenter (2) ?

0

Et le placement des fragments ?

! Chaque fragment sur un seul site

–  copie unique, BD partitionnée

! Duplication de fragments

(+) performances des requêtes et disponibilité

(-) coût des mises à jour et contrôle de concurrence plus complexe

! Fréquemment : duplication partielle

! Applications pour la duplication totale

C. L. Roncancio,- C. Labbé  notes de cours       ¹

1

Objectifs généraux

! Fragmentation

–  Favoriser les accès locaux

–  Équilibrer la charge de travail entre les sites

! Duplication

–  Favoriser les accès locaux

–  Augmenter la disponibilité des données

1

2

Informations utile...

! BD : taille des relations, CI, etc.

! Applications : FAQ et où

! Sites : capacités de stockage / traitement.

! Réseaux et système

! Les deux dernières servent essentiellement dans l’allocation

C. L. Roncancio,- C. Labbé  notes de cours       ¹

3

Fragmentation Horizontale

! Fragments définis par sélection

Ex : Clients( NClient, Nom, Ville)

Client1 = ! Ville = Paris (Client)

Client2 = ! Ville != Paris (Client)

! Reconstruction par union des fragments

Ex : Client = Client1 U Client2

1

4

Fragmentation Horizontale – Exemple

Relation Client

NoClient	Nom	Ville
C1	Dupont	Paris
C2	Martin	Grenoble
C3	Martin	Paris
C4	Talon	Lille

C. L. Roncancio,- C. Labbé  notes de cours       ¹

5

Fragmentation Horizontale - Suite exemple

NoClient	Nom	Ville
C1	Dupont	Paris
C3	Martin	Paris

Client1

NoClient	Nom	Ville
C4	Talon	Lille
C2	Martin	Grenoble

Client2

1

6

Fragmentation Horizontale Dérivée

! Fragments définis par (semi) jointure

! Ex : Commande( NC, NClient, Produit,Qté)

Commande1 = Commande " Client1

Commande2 = Commande " Client2

! Reconstruction par union des fragments

Ex : Commande = Commande1 U Commande2

C. L. Roncancio,- C. Labbé  notes de cours       ¹

7

Fragmentation Horizontale Dérivée Exemple

Relation Commande

NC	NClient	Produit	Qte
Co1	C1	P1	10
Co2	C1	P2	200
Co3	C2	P3	30
Co4	C4	P4	5

1

8

Fragmentation Horizontale Dérivée – Suite exemple

Relation Commande1

NC	NClient	Produit	Qte
Co1	C1	P1	10
Co2	C1	P2	200

Relation Commande2

NC	NClient	Produit	Qte
Co3	C2	P3	30
Co4	C4	P4	5

C. L. Roncancio,- C. Labbé  notes de cours       ¹

9

Fragmentation Verticale

! Fragments définis par projection ! Ex : Commande( NC, NClient, Produit,Qté) CommandeA = #_{NC, NClient} (Commande)

CommandeB = # NC, Produit, Qté(Commande)

! Reconstruction par jointure

Ex : Commande = CommandeA * CommandeB

! Utile si forte affinité des attributs

2

0

Fragmentation Verticale - Exemple

Relation Commande

NC	NClient	Produit	Qte
Co1	C1	P1	10
Co2	C1	P2	200
Co3	C2	P3	30
Co4	C4	P4	5

C. L. Roncancio,- C. Labbé  notes de cours       ²

1

Fragmentation Verticale – Suite Exemple

NC	NClient
Co1	C1
Co2	C1
Co3	C2
Co4	C4

NC	Produit	Qte
Co1	P1	10
Co2	P2	200
Co3	P3	30
Co4	P4	5

Relation CommandeA

Relation CommandeB

2

2

Propriétés de la fragmentation

! Reconstruction

–  Possible avec les opérateurs de l’algèbre relationnelle

–  Critères de fragmentation horizontale simples ou complexes

! Complétude

–  Horizontale : chaque n-uplet de R est dans un fragment

–  Verticale : chaque attribut est dans un fragment

–  Pas de perte d’information

–  Similaire à la normalisation

C. L. Roncancio,- C. Labbé  notes de cours       ²

3

Exemple perte d’information (1)

! RA      a  b  c

               1  2  3

               4  5  6

! RA1    a  b                RA2    b c

               1 2                            2 3

               4 5                            5 6

2

4

Exemple perte d’information (2)

! RA      a  b  c        RA1 * RA2  =  a  b  c

               1  2 3                                 1  2  3

               4  5  6                                 4  5  6

! RA1    a  b                RA2    b c

               1 2                            2 3

               4 5                            5 6

C. L. Roncancio,- C. Labbé  notes de cours       ²

5

Exemple perte d’information (3)

! RA      a  b  c

               1  2  3

               4  5  6

               7  2  8

! RA1    a  b                RA2    b c

               1 2                            2  3

               4 5                            5  6

               7 2                            2  8

2

6

Exemple perte d’information (4)

! RA      a  b  c                  ! RA1 * RA2           a  b  c

               1  2  3 1  2  3

               4  5  6 1  2  8

               7  2  8 4  5  6

! RA1    a  b                RA2                    b c        7  2  3

               1 2                            2 3                    7  2  8

               4 5                            5  6

               7 2                            2  8

C. L. Roncancio,- C. Labbé  notes de cours       ²

7

Propriétés de la fragmentation (2)

! Fragments disjoints

–      Une « entité » est dans un seul fragment ! Exemple FAQ : !s_{al < 30} ( R) et !s_{al >20} ( R)

! Fragments candidats : !s_{al < 30} ( R) et !s_{al > 20} ( R)

–      Non disjoint

! Alternative / disjoint :

!sal <= 20 ( R)  et  !20 < sal < 30 ( R)  et !sal >= 30 ( R)

2

8

Disjoint vs. Non Disjoint

! Disjoint

 Bonne propriété, facilite les mises à jour

! Non Disjoint

Forme de duplication, accélère certaines requêtes

C. L. Roncancio,- C. Labbé  notes de cours       ²

9

Comment ???

Comment obtenir des fragments disjoints et assurer la reconstruction ?

! Génération automatique

! Souvent « manuelle » par l ’administrateur.

! Différentes méthodologies selon le type de fragmentation.

3

0

Analyse fragmentation horizontale

! Commencer avec les conditions de sélection  fréquentes

(FAQ)

! Règle de  Wiederhold : 80 / 20

! Extraire des requêtes les conditions de sélections :

– A < 10, A > 5, Ville = Paris, Ville = Lyon

! On obtient un ensemble : C={c1, c2,}  des conditions élémentaires (ce).

C. L. Roncancio,- C. Labbé  notes de cours       ³

1

Fragmentation horizon

! Construire l’ensemble des conjonctions de ce (cc) suivant :

CC ={" C_i^*         ou C_i^*est soit c_isoit¬c_i}

i=1,n

CC =??

! Simplifier chaque cc

! Supprimer les cc tjr fausses

3

2

Exemple

A < 10,  A > 5, Ville = Paris, Ville = Lyon

A < 10, A > 5, Ville = Paris, Ville != Lyon

A < 10, A > 5, Ville != Paris, Ville = Lyon

A < 10, A > 5, Ville != Paris, Ville != Lyon

A < 10, A <= 5, Ville = Paris, Ville = Lyon

A < 10, A <= 5, Ville = Paris, Ville != Lyon

A < 10, A <= 5, Ville != Paris, Ville = Lyon

A < 10, A <= 5, Ville != Paris, Ville != Lyon

A >= 10, A > 5, Ville = Paris, Ville = Lyon

A >=10, A > 5, Ville = Paris, Ville != Lyon

A >= 10, A > 5, Ville != Paris, Ville = Lyon

A >= 10, A > 5, Ville != Paris, Ville !=Lyon

A >= 10, A <= 5, Ville = Paris, Ville =Lyon

A >=10, A <= 5, Ville = Paris, Ville !=Lyon A >= 10, A <= 5, Ville != Paris, Ville = Lyon

                                           A >= 10, A <= 5, Ville != Paris, Ville != LyonC. L. Roncancio,- C. Labbé  notes de cours           ₃

3

Éliminer les inutiles ...

•   Conditions non satisfiables

•   Connaissance des contraintes d’intégrité, e.g; ville soit Paris, soit Lyon.

A < 10, A > 5, Ville = Paris, Ville != Lyon

A < 10, A > 5, Ville != Paris, Ville = Lyon

A < 10, A <= 5, Ville = Paris, Ville != Lyon

A < 10, A <= 5, Ville != Paris, Ville = Lyon

A >=10, A > 5, Ville = Paris, Ville != Lyon

A >= 10, A > 5, Ville != Paris, Ville = Lyon

3

4

Fragments finaux

!Regrouper les conditions sur un même attribut

       5 < A < 10, Ville = Paris

       5 < A < 10, Ville = Lyon

       A <= 5, Ville = Paris

       A <= 5, Ville = Lyon

       A >=10, Ville = Paris

       A >= 10, Ville = Lyon

C. L. Roncancio,- C. Labbé  notes de cours       ³

5

Propriétés de la fragmentation ?

! Complétude :

tout n-uplet t vérifie une des ce et nous avons éliminé seulement les cc impossibles ! Disjonction :

Supposons t valide deux cc (cc1 et cc2) alors :

" ci tq ci # cc1et¬ci # cc2

et donc t satisfit ci et $ci , contradiction !!

3

6

Bonne propriétés

! Obtenir une partition de l’ensemble de n-uplets telle que : pour tout B de la partition, deux n-uplets de B aient la même probabilité d’être accédés par toute application/requête importante

C. L. Roncancio,- C. Labbé  notes de cours       ³

7

Bonne propriétés - exemple

Emp( Enum, Nom, Ville,Sal, …)

! FAQ :

–  select * from Emp where Ville = Paris

–  select * from Emp where Ville = Lyon

! Ensemble vide de conditions : partition P1 = {B1}

! Mauvais : certains n-uplets de B1 ont 0 chances de répondre à la première requête,  d’autres non

3

8

Ne pas oublier les règles – suite exemple

La partition ne doit pas être un raffinement d’une autre qui est déjà bonne

! Partition P2  avec conditions : Ville = Paris  et Ville = Lyon ! Partition P3  avec conditions :

(Ville = Paris et Sal < 10000) … et (Ville = Lyon et Sal >= 10000)

! P3 n’est pas minimale : il vaut mieux commencer par une minimale et distribuer plus si nécessaire.

C. L. Roncancio,- C. Labbé  notes de cours       ³

9

Analyse Fragmentation Horizontale Dérivée

! R est fragmentée en R1,…Rk ! S est fragmentée en S " R1,…,S " Rk ! Conditions pour que ça marche :

Reconstruction   S = U (S " Ri)

Disjonction  (i != j)  (S " Ri)   (S " " Rj) = "

Conception : association 1-n entre entités R et S

Intégrité : S a une clé étrangère de R

… Condition suffisante pour reconstruction et disjonction

4

0

 Analyse Fragmentation Verticale

Emp( Enum, Nom, Ville,Sal)

Emp1( Enum, Nom, Ville)    Emp2( Enum,Sal)

! Complétude et reconstruction

Jointure sans perte d’information

Condition suffisante : répéter la clé dans chaque fragment

Autre choix : utiliser une dépendance fonctionnelle pour la décomposition (cf. normalisation)

! Disjonction : seulement répéter la clé

C. L. Roncancio,- C. Labbé  notes de cours       ⁴

1

Comment fragmenter verticalement ?

! Utiliser le sens commun...essayer d’automatiser ! Heuristiques :

" Clustering - rapprochement en partant d’un attribut par fragment

" Splitting - décomposition en partant d’un fragment unique pour obtenir une partition selon l’affinité des attributs

4

2

 Outil - Matrice d’affinité (1)

Exemple Projet(Pnum, Pnom, Budget, Loc)

                            A1        A2     A3        A4

q1: budget d’un projet étant donné son numéro q2: nom et budget de tous les projets q3 : nom des projets d’une ville q4 : budget total des projets d’une ville

C. L. Roncancio,- C. Labbé  notes de cours       ⁴

3

Matrice d ’utilisation

!                                           "1 si q_iutilise A_j

Ut(q_i,A_j ) = #

                                                           $      0 sinon

! Example

     A1  A2  A3  A4 q1   1 0     1     0 q2   0 1     1     0 q3   0 1     0     1 q4   0 0     1     1

4

4

 Matrice d’affinité - Définition

! Ref_s( q_k ), pour  deux attributs (A_i, A_k) =   nombre d’accès faits par une exécution de q_k (sur le site s) à A_i et A_k

! Acc_s( q_k) = fréquence de q_k sur le site s (mesurée pendant une certaine période)

! Matrice d’affinité

Aff (A_i,A_j ) = " "Ref_s(q_k)Acc_s(q_k)

k tq                    s

Ut(q_k ,A_i )=1

#Ut(q_k ,A _j )=1

C. L. Roncancio,- C. Labbé  notes de cours       ⁴

5

Matrice d’affinité - Exemple

! Supposons :   Ref_s( q_k )  = 1 %s, k ! Les accès suivants (3 sites):

Acc₁(q₁)=15 Acc₂(q₁) = 20  Acc₃(q₁) = 10

Acc₁(q₂)=5 Acc₂(q₂) = 0    Acc₃(q₂) = 0

Acc₁(q₃)=25 Acc₂(q₃) = 25  Acc₃(q₃) = 25

Acc₁(q4)= 3   Acc₂(q₄) = 0    Acc₃(q₄) = 0

4

6

Matrice d’affinité - Exemple (2)

! Aff(A1, A3) = & _K=1 &_s Acc_s(q_k)

  = Acc₁(q₁) +Acc₂(q₁) +Acc₃(q₁)  = 45 ! La matrice :

      A1  A2  A3  A4

A1  45   0     45   0

A2  0    80     5   75

A3  45   5     53   3

A4   0   75     3   78

C. L. Roncancio,- C. Labbé  notes de cours       ⁴

7

Regroupement des attributs

! Regroupement des attributs ayant une haute affinité ! Exemple :

       A1  A3  A2 A4

A1   45   45    0    0

A3   45   53    5    3

A2    0    5    80   75

A4    0    3    75   78

4

8

Partitionnement

! Trouver un point dans la matrice pour créer deux ensembles d’attributs : AttrHaut (AH) et AttrBas (AB) ! Quelle requête accède quel ensemble ?

–  AR(q_i) = {A_i / Ut(q_i,A_i) = 1 }

–  RH = { q_i / AR( q_i) ’ AH }

–  RB = { q_i / AR( q_i) ’ AB }

–  Autres = Q – { RH ( RB }

C. L. Roncancio,- C. Labbé  notes de cours       ⁴

9

Partitionnement - Exemple

! Q = { q1, q2, q3, q4 }

! AH = { A1, A3 }

! AB = { A2, A4}

! RH = { q1 }

! RB = { q3 }

! Autres = { q2, q4 }

5

0

Partitionnement (suite)

! Objectif :

–  Maximiser les accès à un seul fragment

–  Minimiser les accès aux deux fragments

! TotalAccès = )qi *Q )%site sRefs(qi)Accs(qi)

= 128

! TotalRH = )qi *RH )%site sRefs(qi)Accs(qi)

= 45

C. L. Roncancio,- C. Labbé  notes de cours       ⁵

1

Partitionnement (suite 2)

! TotalRB = )_qi*RB )_{%site s}Refs(qi)Accs(qi)

= 75

! TotalAutres

                = )qi *Autres )%site s Refs(qi)Accs(qi)

= 8

5

2

Partitionnement (suite 3)

! Trouver un point dans la matrice pour créer deux ensembles d’attributs AH et AB tels que :

      z = (TotalRH * TotalRB) – TotalAutres²

est maximisé

C. L. Roncancio,- C. Labbé  notes de cours       ⁵

3

Fin exemple !

! La relation Projet est fragmentée en

Projet1( Num, Budget)

Projet2( Num, Nom, Loc)

! Dans l’exemple (simple) la clé est dans l’ensemble d’attributs considéré

! Duplication de la clé pour garantir la reconstruction

5

4

Partitionnement (fin)

! Si beaucoup d’attributs alors il est peut être nécessaire de trouver plusieurs points dans la matrice.

! Utiliser plutôt une approche récursive : partir de deux groups AH et AB et raffiner.

C. L. Roncancio,- C. Labbé  notes de cours       ⁵

5

Fragmentation Hybride

! Fragmentation horizontale suivit de verticale ou vice-versa

Reconstruction

                                        R                                                 (

Horizontale

Verticale

            R11                    R22                  R11                  R22

                  R12                                             R12

5

6

Allocation

! Problème d’optimisation très difficile

! Minimiser coûts: stockage, traitement, communication

! Maximiser performances: temps de réponse,  débit du système

! Modèle coût / performances

! Utiliser modèle simple / sens commun

e.g: considérer les com.  / Accès

C. L. Roncancio,- C. Labbé  notes de cours       ⁵

7

Exemple Client + Commandes

! Client1 = ! Ville = Paris (Client)

Client2 = ! Ville != Paris (Client)

Commande1 = Commande " Client1           Commande2 = Commande " Client2

! Allocation

@Site1 : Client1, Commande1

@Site2 : Client2, Commande2

5

8

Duplication

! Redondance

! Compromis requêtes (plus vite) / mises à jour (plus lent)

Quelques fois ralentissement des requêtes…

! Bons candidats : peu de modifications, beaucoup de consultations e.g. « style annuaire  »

! Approche itérative : pour chaque fragment potentiellement duplicable, Bénéfice ? Coût ?

Ok si (Bénef – Coût) > 0   ou Maximale

C. L. Roncancio,- C. Labbé  notes de cours       ⁵

9

Conclusion

! Fragmentation des relations

–  Décomposition / reconstruction

–  Horizontale simple / dérivée, verticale, hybride

–  Propriétés : reconstruction, complétude, disjonction

! Allocation / duplication

–  Modèle de coût

–  Approche itérative

6

0