Dissertation les bases de donnees reparties

•

REPLICATION

• PRINCIPE Copie de chaque relation sur plusieurs sites Réplication complète = copie sur tous les sites • AVANTAGES Disponibilité des données Augmentation du parallélisme en lecture Diminution du coût imposé par les transmissions • INCONVENIENTS Cohérence des différentes copies Propagation des mises à jour

FRAGMENTATION

• PRINCIPE Répartir une relation sur plusieurs sites, un fragment de la relation sur un site • TECHNIQUES DECOUPAGE HORIZONTAL DECOUPAGE VERTICAL DECOUPAGE MIXTE

-> -> ->

RESTRICTION PROJECTION SELECTION

• PROBLEME RECOMPOSER LA RELATION INITIALE

FRAGMENTATION HORIZONTALE

• REPARTITION DE VINS VIN_BDX : vins avec σ (VINS;REGION = 'Bordeaux‘) (stockés à Bordeaux) VIN_BGN : vins avec σ (VINS; REGION = 'Bourgogne’) (stockés à Dijon) VIN_AUT : vins des autres régions (stockés à Paris)

•

CALCUL DE LA RELATION VINS VINS = VIN_BDX ∪ VIN_BGN ∪ VIN_AUT

FRAGMENTATION VERTICALE

• REPARTITION DE VINS VIN_LOC = projection de VINS sur les attributs REGION et CRU, stockée à Bordeaux VIN_MIL = projection de VINS sur l'attribut MILL, stockée à Paris VIN_DEG = projection de VINS sur l'attribut DEGRE, stockée à Dijon Π (VINS; REGION, CRU)

FRAGMENTATION VERTICALE (2)

• PROBLEME : CALCUL DE VINS On ne sait pas reconstituer la relation VINS, car les trois relations n'ont pas d'attribut commun => Ajouter l'attribut clé primaire NV au schéma de chacune des trois relations, alors : VINS = VIN_LOC * VIN_MIL * VIN_DEG Notion de TID (Tuple IDentifier) -> identifie de manière unique un tuple dans une relation (adresse logique ou physique) -> il ajoute de lui-même le TID comme attribut de chacune des trois relations -> transparent à l'utilisateur

•

FRAGMENTATION MIXTE

• 1 FRAGMENTATION VERTICALE -> VIN_LOC (NV, REGION, CRU) -> VIN_MIL (NV, MIL) à Paris -> VIN_DEG (NV, DEG) à Dijon VINS = VIN_LOC * VIN_MIL * VIN_DEG • 2 FRAGMENTATION HORIZONTALE -> VIN_LOC_BDX (NV, REGION, CRU) avec REGION = 'Bordeaux' (stockée à Bordeaux) -> VIN_LOC_BGN (NV, REGION, CRU) avec REGION = 'Bourgogne' (stockée à Dijon) VINS = (VIN_LOC_BDX ∪ VIN_LOC_BGN) *VIN_MIL *VIN_DEG

REPLICATION + FRAGMENTATION

• 1 REPLICATION COPIE DE LA RELATION VINS SUR LES TROIS SITES : VIN_B, VIN_D, VIN_P • 2 FRAGMENTATION FRAGMENTATION DES REPLICAS -> VIN_B et VIN_D fragmentées horizontalement sur l'attribut REGION -> VIN_P non fragmentée • REMARQUE UNE FRAGMENTATION HORIZONTALE PEUT CONDUIRE A UNE REPLICATION SUR LES TUPLES D'UNE RELATION

METHODES DE CONCEPTION D'UNE BD REPARTIE

• METHODE DESCENDANTE -> Schéma conceptuel global de la base -> Fragmentation des relations -> Allocation des fragments

•

METHODE ASCENDANTE -> N schémas conceptuels locaux -> Intégration des n vues locales afin d'obtenir un unique schéma conceptuel global -> Modification éventuelle de la fragmentation et de la réplication D'OU : --> règles de répartition des données --> outils automatises d'aide à la répartition

TRAITEMENT REPARTI

• 1 Objectifs -> Minimiser les accès disque -> Minimiser le temps CPU -> Minimiser la transmission réseau -> Exploiter le parallélisme 2 Réplication et fragmentation 3 Traitement d'une jointure 4 Exploitation du parallélisme 5 Utilisation de la semi-jointure

• • • •

REPLICATION ET FRAGMENTATION

• PRINCIPES DU TRAITEMENT -> Transformation d'une requête globale en requêtes s sur les fragments -> Optimisation des stratégies d'accès aux données : 1. entre sites (coût transmission) 2. sur chaque site (coût accès disque, temps CPU)

EXEMPLE

• select * from VINS -> VINS répliquée sans fragmentation : choisir le replicat avec le plus faible coût de transmission -> VINS répliquée avec fragmentation : choisir un ensemble optimum de réplicats qui permet la reconstruction de VINS en minimisant : (i) le coût de transmission (ii) le temps CPU pour réaliser l'union ou la jointure des réplicats

TRAITEMENT D'UNE JOINTURE

• REPARTITION DES RELATIONS -> VIN à Bordeaux -> BUV à Paris -> CDE à Dijon QUESTION : (posée sur le site de Toulouse) select * from VIN, BUV, CDE where VIN.NV = CDE.NV and CDE.NB = BUV.NB;

•

TRAITEMENT

• Stratégie 1 Copie des relations VIN, BUV et CDE à Exécution de la requête à Toulouse Toulouse

•

Stratégie 2 Copie de CDE à Bordeaux Exécution de VIN Join CDE à Bordeaux, et envoi du résultat TMP_VC à Paris. Exécution de BUV Join TMP_VC à Paris, et envoi du résultat TMP_BVC à Toulouse.

PARALLELISME

• REPARTITION DES RELATIONS -> PRO à Bordeaux -> VIN à Dijon -> CDE à Paris -> BUV à Toulouse REQUETE : initialisée à Lille Q = PRO VIN CDE BUV NV NV NB EXPLOITER LE PARALLELISME

•

•

(1) Envoi de VIN à Bordeaux calcul de PRO VIN à Bordeaux (2) Envoi de CDE à Toulouse calcul de CDE BUV à Toulouse (3) Bordeaux et Toulouse envoient les tuples qui joignent à Lille, au fur et à mesure => PARALLELISME ENTRE Bordeaux, Toulouse et Lille

STRATEGIE DE SEMI-JOINTURE

• REPARTITION DES RELATIONS -> VIN à Bordeaux -> CDE à Paris QUESTION :(initialisée à Dijon) Q = VIN

•

CDE NV

• STRATEGIE DE SEMI-JOINTURE (1) calcul de T1 = Π(VINS;� NV) à Bordeaux envoi de T1 à Paris calcul de T2=CDE T1 à Paris envoi de T2 à Dijon (2) calcul de T'1 = Π(CDE;� NV) à Paris envoi de T'1 à Bordeaux calcul de T'2 =VIN T'1 à Bordeaux envoi de T'2 à Dijon (3) calcul de T2 T'2 à Dijon

VALIDATION D'UNE