Bases de données réparties

1. Définitions et architecture

Définition Une base de données répartie est un ensemble de données stockées sur plusieurs sites connectés par un réseau.

Site : machine avec une BDD locale.
Réseau : moyen de communication entre sites.
Critères de choix : coût d'installation, communication, sûreté, disponibilité.

Pour gérer une BD répartie, il faut un SGBD Réparti.

Une BDDR = plusieurs BDDs locales + un réseau qui les relie.

Méthodes de conception

⬇️ Top-down design
Définition d'un schéma global → distribution vers schémas locaux → fragmentation et allocation des fragments.

⬆️ Bottom-up design
Intégration de schémas locaux existants dans un schéma global.

2. Intérêts et inconvénients

✅ Intérêts

Plus grande fiabilité (résilience aux pannes matérielles)
Meilleures performances locales
Facilite la croissance du système

❌ Inconvénients

Coûts : trafic réseau, hardware, software
Synchronisation pour accéder aux données
Sécurité des données
Interblocage distribué

3. La fragmentation

Deux grandes techniques de répartition : la fragmentation et la réplication. On commence par la fragmentation.

Principe Répartir une relation (table) sur plusieurs sites. Sur chaque site est stockée une partie de la relation. Problème : pouvoir recomposer la relation initiale.

Découpage	Opérateur algébrique	Recomposition
Horizontal	⇔ Sélection (σ)	UNION
Vertical	⇔ Projection (π)	JOINTURE (la clé doit être dans chaque fragment)
Mixte	⇔ Projection puis Sélection	JOINTURE puis UNION

Fragmentation horizontale

Fragmentation horizontale : chaque site stocke un sous-ensemble de lignes.

Formellement :

On considère la relation R, Att un attribut de R.
vAtt₁, vAtt₂, …, vAttₙ : la liste exhaustive des valeurs de Att.
∀ i ∈ {1, …, n}, on stocke sur le site sᵢ : σ(R; Att = vAttᵢ)
Reconstruction : R = ∪ᵢ σ(R; Att = vAttᵢ)

-- Client(NClient, Nom, Ville)
Client1 = σ Ville = Paris (Client)
Client2 = σ Ville != Paris (Client)

-- Reconstruction par UNION
Client = Client1 ∪ Client2

Fragmentation horizontale dérivée

Fragments définis par (semi) jointure. Très utile pour propager une fragmentation H d'une table à une table liée par clé étrangère.

-- Commande(NC, NClient, Produit, Qté)
Commande1 = Commande ⋈ Client1   -- commandes des clients parisiens
Commande2 = Commande ⋈ Client2   -- commandes des autres

-- Reconstruction par UNION
Commande = Commande1 ∪ Commande2

Fragmentation verticale

Fragmentation verticale : chaque site stocke un sous-ensemble de colonnes. La clé doit être présente dans tous les fragments pour pouvoir recomposer.

Formellement :

(Att₁,₁, …, Att₁,k₁) … (Attₙ,₁, …, Attₙ,kₙ) : liste d'ensembles d'attributs de R.
Chaque ensemble contient une clé de R.
La réunion des ensembles recouvre tous les attributs de R.
Sur le site i : π(R; Attᵢ,₁, …, Attᵢ,kᵢ)

-- Commande(NC, NClient, Produit, Qté)
CommandeA = π NC, NClient (Commande)
CommandeB = π NC, Produit, Qté (Commande)

-- Reconstruction par jointure
Commande = CommandeA ⋈ CommandeB

-- Utile si forte affinité entre certains attributs

Fragmentation mixte

On considère une relation R.
On la fragmente verticalement (projections).
Chaque fragment vertical peut être lui-même décomposé en fragments horizontaux (sélections).

🎯 Comment choisir ?
• Si les requêtes filtrent souvent par une valeur (ex : ville) → horizontale.
• Si certaines colonnes sont rarement consultées ensemble (ex : infos paie vs infos administratives) → verticale.
• Si les deux → mixte.

4. La solution Oracle — database link

La couche Oracle Net

`Listener.ora`	Configuration pour traiter les connexions distantes
`tnsnames.ora`	Alias de bases de données
Net Configuration Assistant	Outil pour mettre à jour ces fichiers
Programme `listener`	Détecte les requêtes de connexion distantes

Le lien de base de données (database link)

create [public] database link nomLien
connect to user identified by passwd
using 'nomService';
-- nomService = alias de BD défini sur le serveur de connexion

Exemple canonique du cours

create database link db_toulouse connect to user_distant
identified by password using 'XE';

-- Requête locale
select * from table_name;

-- Requête DISTANTE via le lien
select * from table_name@db_toulouse;

🔗 La syntaxe magique : @dblink
Pour accéder à une table distante depuis ta session, ajoute @nom_du_lien après le nom de la table. Le SGBD gère le réseau pour toi.

Opérations sur les liens

Opération	Syntaxe
Fermeture (utile si forte charge)	`ALTER SESSION CLOSE DATABASE LINK lien;`
Suppression	`DROP DATABASE LINK lien;`

Recomposition / Défragmentation via vue

-- Recomposer une fragmentation HORIZONTALE
CREATE VIEW V1 AS
  SELECT Table1.cle, Table1.attr1 FROM Table1@site1
  UNION
  SELECT Table2.cle, Table2.attr1 FROM Table2@site2;

-- Recomposer une fragmentation VERTICALE
CREATE VIEW V1 AS
  SELECT Table1.cle, Table1.attr1, Table2.attr2
  FROM Table1@site1, Table2@site2
  WHERE Table1.cle = Table2.cle;

💡 Utiliser les vues pour cacher la répartition L'utilisateur ne sait pas où sont les données — il fait SELECT * FROM V1 comme s'il s'agissait d'une table locale unique. La BDDR est transparente.

5. La réplication

Principe : une relation stockée sur un site est recopiée sur un ou plusieurs sites.

✅ Avantages

Disponibilité des données
Augmentation du parallélisme en lecture
Diminution du coût des transmissions

❌ Inconvénients

Cohérence des différentes copies
Propagation des mises à jour

Mise en œuvre Oracle

create materialized view image REFRESH FAST …
AS SELECT … FROM T@Lien;

📸 Vue matérialisée distante
La VM stocke localement le résultat d'une requête sur une table distante. REFRESH FAST propage uniquement les changements via le MATERIALIZED VIEW LOG sur la source.

6. L'exemple pratique du cours

Énoncé

Relations : Employé(nss, nom, loc, …) et Taux(pays, valeur, …).
12 bureaux d'environ la même taille : 6 à Paris, 4 à Marseille, 2 à Lyon.
80% des requêtes d'une ville portent sur les employés de cette ville.
10% des requêtes d'une ville portent sur Taux.

Solution proposée

Site	Stocke
P (Paris)	Employés de Paris + copie de Taux
M (Marseille)	Employés de Marseille + copie de Taux
L (Lyon)	Employés de Lyon + copie de Taux

Si trop cher : fusionner M et L, ou ne maintenir Taux qu'à M (puis accès distant depuis L).

🎓 Pourquoi cette solution ?
Employé est fragmentée H par loc (chaque ville chez elle → 80% des requêtes locales).
Taux est répliquée partout (10% des requêtes la touchent, mieux vaut éviter le réseau).

7. Validation d'une transaction répartie

Quoi : une transaction T répartie ⇒ n transactions Tᵢ locales sur les sites Sᵢ. Il faut coordonner les sites.

Comment : un site coordinateur + le protocole de validation à deux phases (consensus).

Règle d'or du consensus

La décision de validation est prise si et seulement si tous les participants ont voté oui. Un participant ne peut plus revenir sur sa décision.

Validation à deux phases : préparation (vote) puis décision unanime.

Phase 1 : préparation

Le coordinateur C écrit <T préparée> dans son journal.
C envoie « préparation » à tous les sites Sᵢ.
Chaque Sᵢ prend une décision pour Tᵢ :
- S'il valide : écrit <T prête> dans son journal, envoie « T prête » à C.
- S'il refuse : écrit <non T>, envoie « abandon T » à C.

Phase 2 : décision

À partir des messages reçus, C prend une décision :

✓ Tous OK → valider

Ajoute <T validée> à son journal
Envoie « valider T » à tous les Sᵢ

✗ Au moins un non → abandonner

Ajoute <T abandonnée> à son journal
Envoie « abandon T » à tous les Sᵢ

Chaque Sᵢ inscrit le message reçu et envoie un accusé. Quand C a tous les accusés, il ajoute <T finie>.

Reprise après panne

Panne	Moment	Action
Coordinateur	Phase préparatoire (avant diffusion du statut)	Abandonner T
Coordinateur	Après décision prise	Ne rien faire
Exécutant (Sᵢ)	Phase préparatoire	Abandonner T
Exécutant (Sᵢ)	Décision déjà connue	Ne rien faire

★ Réviser le chapitre

Pour vérifier ta compréhension

Sur quel critère choisir entre fragmentation horizontale et verticale ?

La horizontale s'utilise quand les requêtes filtrent souvent sur une valeur d'attribut (ville, classe, statut) et qu'on veut localiser ces lignes près des utilisateurs concernés.
La verticale s'utilise quand certains attributs sont rarement consultés ensemble (ex : infos de paie vs infos administratives) ou pour des raisons de confidentialité — on les sépare en fragments distincts.

Pourquoi la clé primaire doit-elle figurer dans chaque fragment vertical ?

Sans la clé dans chaque fragment, on ne peut pas faire la jointure qui recompose la relation initiale. La clé sert d'identifiant commun. Si on a π(NC, NClient) à un site et π(Produit, Qté) à un autre, on ne sait pas relier les lignes — pas de recomposition possible.

Quelle est la différence entre fragmentation et réplication ?

Fragmentation : on découpe la relation en morceaux distincts, chaque morceau sur un seul site. Pas de doublons.
Réplication : on copie tout ou partie de la relation sur plusieurs sites. Doublons assumés. Avantage : disponibilité et parallélisme en lecture. Inconvénient : cohérence et propagation des MAJ.

Pourquoi le 2PC est-il dit « pessimiste » ?

Parce qu'il bloque tous les participants tant que le coordinateur n'a pas pris la décision finale. Pendant la phase préparatoire, chaque site qui a voté « T prête » garde ses ressources verrouillées en attente du verdict. C'est sûr mais lent. Des protocoles plus rapides (Paxos, Raft) existent pour les cas où la fiabilité totale n'est pas critique.

Comment l'utilisateur voit-il une BDDR ?

Idéalement, de façon transparente : il fait SELECT * FROM clients comme s'il s'agissait d'une table locale, sans savoir que clients est en fait une vue qui assemble des fragments distants via UNION ou JOIN sur des @dblink.

🃏 Flashcards éclair

Clique pour retourner.

BDDR

Définition.

tourne →

Ensemble de données stockées sur plusieurs sites connectés par un réseau.

3 types de fragmentation

Et leurs opérateurs.

tourne →

Horizontale = sélection (σ)
Verticale = projection (π)
Mixte = projection puis sélection

Recomposer H

Quel opérateur ?

tourne →

UNION des fragments
R = Client1 ∪ Client2

Recomposer V

Quel opérateur ? Quelle condition ?

tourne →

JOINTURE sur la clé.
La clé doit être dans chaque fragment.

Fragmentation dérivée

Définition.

tourne →

Fragments d'une table définis par (semi) jointure avec une autre table déjà fragmentée H.

Database link

Syntaxe.

tourne →

CREATE DATABASE LINK nom
CONNECT TO user
IDENTIFIED BY pwd
USING 'service';

Accès distant

Syntaxe SELECT.

tourne →

SELECT * FROM table@dblink;

Vue de recomposition H

Pattern SQL.

tourne →

CREATE VIEW V AS
SELECT … FROM T@s1
UNION
SELECT … FROM T@s2;

Vue de recomposition V

Pattern SQL.

tourne →

CREATE VIEW V AS
SELECT T1.cle, T1.a, T2.b
FROM T1@s1, T2@s2
WHERE T1.cle = T2.cle;

Réplication Oracle

Syntaxe.

tourne →

CREATE MATERIALIZED VIEW img
REFRESH FAST
AS SELECT … FROM T@lien;

2PC — règle du oui

Combien de oui faut-il ?

tourne →

TOUS les participants doivent voter oui pour valider. Un seul non = abandon global.

2PC — deux phases

Les nommer.

tourne →

Phase 1 : préparation (vote)
Phase 2 : décision (valider ou abandonner)

✎ Quiz éclair

test rapide · 6 questions

0 / 6

1.Une fragmentation horizontale correspond à quel opérateur de l'algèbre relationnelle ?

Projection
Jointure
Sélection
Différence

Fragmentation horizontale = on prend un sous-ensemble de lignes selon un critère = sélection (σ).

2.Pour recomposer une fragmentation verticale :

UNION des fragments
JOINTURE sur la clé commune
DIFFÉRENCE
PRODUIT cartésien

La V partage les attributs entre fragments. Pour reconstituer une ligne complète, on fait une jointure sur la clé qui figure obligatoirement dans chaque fragment.

3.Quelle syntaxe accède à une table distante via un database link ?

SELECT * FROM dblink.table;
SELECT * FROM table USING dblink;
SELECT * FROM "dblink"."table";
SELECT * FROM table@dblink;

Le suffixe @nom_du_lien après le nom de la table.

4.Dans la validation à 2 phases, à la phase 2, si UN seul site a voté « non » :

On revote sans lui
On valide quand même (majoritaire)
On abandonne T sur tous les sites
On lance une nouvelle phase 1

Le consensus exige l'unanimité. Un seul « non » = abandon global.

5.Quel critère justifie au mieux la solution P/M/L de l'exemple du cours ?

80% des requêtes locales → fragmentation H par ville ; Taux peu utilisée → réplication
Toutes les requêtes sont distantes
Le réseau est gratuit
Les bureaux ont des employés différents

Employés fragmentés H sur la localisation (limiter le trafic réseau pour les 80%). Taux peu requêtée → réplication acceptable (évite le réseau pour les 10%).

6.Pour la fragmentation verticale, quel attribut DOIT figurer dans chaque fragment ?

Le premier attribut listé
L'attribut le plus utilisé
La clé primaire
Aucun en particulier

Sans la clé dans chaque fragment, impossible de joindre pour recomposer la relation initiale.

📌 Pour la feuille recto-verso

BDDR = données sur plusieurs sites + réseau + SGBD réparti
Conception : top-down (global → local) OU bottom-up (local → global)
Fragmentation H = σ (sélection) · recomposer par UNION
Fragmentation V = π (projection) · recomposer par JOINTURE · clé dans chaque fragment
Fragmentation mixte = V puis H
Fragmentation dérivée = définie par (semi) jointure avec une autre table
CREATE DATABASE LINK nom CONNECT TO user IDENTIFIED BY pwd USING 'service';
Accès distant : SELECT * FROM table@dblink;
ALTER SESSION CLOSE DATABASE LINK · DROP DATABASE LINK
Recomposition vue H : UNION de SELECT … FROM T@s
Recomposition vue V : JOIN sur clé entre T1@s1 et T2@s2
Réplication : CREATE MATERIALIZED VIEW … REFRESH FAST AS SELECT … FROM T@lien;
2PC : phase 1 préparation (vote) · phase 2 décision (unanimité requise)
Reprise panne : phase préparatoire → abandon · décision connue → ne rien faire