Index

Stockahe des données: Les données sont stockées sur un support persistant en pages de taille fixe,
comme le disque magnétique ou le flash.
Enregistrement: correspond à une ligne d’une table, stockée dans les pages d’un fichier.
ROWID: Chaque enregistrement possède un identifiant unique appelé ROWID, qui localise l’enregistre-
ment via le nom du fichier, le numéro de page et la position.
Organisation indexée: Les données sont regroupées ou triées selon la clé de l’index pour un accès rapide.
— Index Plaçant : Organise les données pour un accès rapide en fonction des valeurs de la clé. (ID)
— Index Plaçant Non Dense : Stocke uniquement les valeurs essentielles pour réduire l’espace
occupé par l’index. (Date)
— Index Non Plaçant : Indexer les données sans se soucier de leur organisation physique. (Nom)
Entrée d’un Index : Associe une clé à des identifiants d’enregistrements pour localiser leur
emplacement physique. (ID)
Entrée Unique : satisfait une contrainte d’unicité, avec une seule entrée par valeur. (Email)
Entrée Multiple : lorsque l’attribut indexé n’est pas unique, permettant plusieurs entrées par
valeur. (Code Postal)
Accès par Index: Utilisé pour évaluer une sélection basée sur des opérations telles que l’égalité, l’inter-
valle, l’inégalité, ou la comparaison de préfixe.
Index Couvrant: Un index couvre une requête s’il est possible d’évaluer la requête sans lire les données,
ce qui permet une évaluation plus rapide.
Index Composé: Une clé composée est considérée comme une clé simple formée de la concaténation des
attributs, permettant un accès efficace à une requête en utilisant un seul index.

Solution Exercices : Pour qu’un index soit efficacement utilisé, les attributs du pré-
dicat de la requête doivent correspondre à l’ordre des attributs de l’index par rapport aux
critères de sélection de la requête, et le prédicat doit permettre un accès direct à l’index (at-
tribut=valeur).

Index ART
Propriétés: Un nœud contient une partie de la clé, et la hauteur de l’arbre dépend de la longueur de la
clé, permettant une mise à jour efficace sans fusion ni redistribution de valeurs.
Découpage de la clé: La clé est découpée en morceaux d’un octet pour une recherche efficace.
Types de Noeuds: Les ART utilisent différents types de nœuds adaptés au nombre de valeurs à indexer :
— Node 4 : Ce type de noeud contient un tableau de 4 clés et un tableau de 4 pointeurs, ce qui
permet une recherche en temps constant. [0, 2, 3, 255] = 3 → [0, 0, 1, 0] & [a,b,c,d] → c
— Node 16 : Ce type de noeud fonctionne comme le nœud 4 mais avec des tableaux de taille 16 pour
une recherche encore plus rapide.
— Node 48 : Ce type de noeud ajout d’un mini-index des valeurs de clés avec un tableau de 255 cas.
p = index[3] = 2 → child = children[p] = c
— Node 256 : Ce type de noeud donne un accès direct au tableau contenant les adresses des fils pour
une recherche instantanée. child = children[3] → c

1
 Hachage
Hachage Extensible: Permet d’éviter les pages de débordement.
— Profondeur globale (PG) : Utilisée pour retrouver une entrée via une fonction de hachage.
— Profondeur locale (PL) : Indique la capacité d’un paquet à éclater sans agrandir le répertoire.
— Insertion :
si Paquet Pi Pas Plein : h(v) = v mod 2P G .
si Paquet Pi Plein et PL<PG : Eclater le paquet, incrementer PL de Pi et Pj et repartir les
valeurs de Pi entre Pi et Pj .
si Paquet Pi Plein et PL=PG : Doubler le repertoire, P G = P G + 1 et appliquer le 2e cas.

— Suppression : Si le Paquet Pi devient vide

si PL<PG : Pas de fusion, Pi reste vide.
si PL=PG : Fusionner Pj avec Pi , décrémenter PL de Pj .
si Tous les PL<PG : PG=PG/2 et décrémenter PG.

Hachage Linéaire: Permet d’éviter l’utilisation d’un répertoire en utilisant des pages de débordement.
— Taux d’Occupation : Nombre moyen d’enregistrements par paquet ne dépasse pas le seuil.
— Prochain Paquet (P) : Le prochain paquet à éclater initialisé à 0 sachant qu’il y a N paquets.
— Insertion :
Sans Débordement : h(v) = v mod N .
Avec Débordement et Occup<Seui : Pas d’éclatement et ajouté h(v) = v mod N dans la
zone de débordement.
Avec Débordement et Occup>=Seui : Eclater le paquet (P) et Répartir les valeur de P et
le nouveau paquet et incrémenter P = (P + 1) mod 2N .

2
 Optimisation de Requêtes (Coût)
Selection: σ
— Si E est une expression composée alors Coût(σp(A) (E)) = Coût(E)
— Si T est une table et l’attribut A n’est pas indexé alors Coût(σp(A) (E)) = page(T )
— Clustering Factor (CF) : CF = card(R)/(N/P )
— Selectivity Factor (SF) : SF = Nombre de tuples satisfaisants/Nombre total de tuples.
— Index Non Plaçant : Coût(σp(A) (R)) = Cindex + Crowid + Card(σp(A) (R)) × CF/Card(R)
— Index Plaçant : Coût(σp(A) (R)) = page(R) × SF (p(A))
— Remarque : Si on utilise pas d’index → Lecture Sequencielle.

Projection: π
— Coût(πAttr (R)) =Coût(R)

Jointure: ▷◁
— Boucles Impbriquées par Blocs :
— Supposant que M+2 pages de R puissent être stockées en mémoire.
— Itération principale sur R par blocs de taille M.
— Chaque n-uplet de S est joint avec le bloc actuellement en cours de traitement de R.
— Coût : Coût(R ▷◁ S) = coût(R) + page(R)/M × page(S)
— Boucles Impbriquées avec Matérialisation :
— Utilisé lorsque S n’est pas une table mais une sous-expression.
— Coût : Coût(R ▷◁M at S) = coût(S) + page(S)+coût(R ▷◁ S)
— Boucles Impbriquées avec Index :
— un index sur l’attribut a de S, évitant ainsi de parcourir S entièrement à chaque bloc de R.
— Coût : Coût(R ▷◁ S) = coût(R)+card(R)×coût(σa=v (S))
— Boucles Impbriquées sans Index :
— Coût : Coût(R ▷◁ S) = coût(R)+card(R)×coût(σ(S))
— Hachage : page(R) ≥ page(S)
— Charger en mémoire R.
— Lire S pour la hacher selon la clé de jointure.
— Itérer sur les tuples de R et jointure sur clé.
— Coût : Coût(R ▷◁ S) =coût(S)+coût(R)

Tri:
— Nombre d’étape : s = logk (page(R))
— Coût total des s etapes : Coût(tri(R)) = 2 × page(R) × s
— Si on ne matérialise pas le résultat de la dernière étape : Coût(tri(R)) = 2 × page(R) × (s − 1) +
page(R)
— Si E est une expression composée (E ̸= table) : Coût(tri(E)) =coût(E) + 2 × page(E) × (s − 1)

3
 Optimisation de Requêtes (Card)
Selection: σ
— card(σpred (R)) = SF (pred) × card(R)
— Facteur de Sélectivité (SF) :
— Sur un attribut :
Egalité : SF = nombre de valeurs sélectionnées/D(R, A)
Intervalle : SF = longueur du segment sélectionné/L(A)
— Sur plusieurs attribut :
Conjonction (AND) : SF (predA AN DpredB ) = SF (predA ) × SF (predB )
Disjonction (OR) : SF (predA ORpredB ) = SF (predA )+SF (predB )−SF (predA )×SF (predB )
— Negation : SF (not(pred)) = 1 − SF (pred)
— Projection : SF (πA (R)) ≤ card(R)
— Produit Cartésien : SF (R × S) = card(R) × card(S)
— Union :
Borne Sup : card(R ∪ S) = card(R) + card(S)
Borne Inf : card(R ∪ S) = max{card(R), card(S)}
— Différence : card(R − S) = card(R)
Jointure: ▷◁
— Jointure Naturelle :
— A est clé primary key de R.
— A est clé étrangère (*) dans S.
— card(R ▷◁A S) = card(S).1
— Jointure entre Deux Clés Etrangères : card(R ▷◁A S) = card(R) × card(S)/D(Entit, A)
— Jointure entre Deux Sélections : card(σp1 (R) ▷◁A σp2 (S)) = SF (p1) × SF (p2) × card(R ▷◁A S)
Forme des Arbres Explorés: Limiter l’espace de recherche.

Les commandes utilisés en TP:

— DESCRIBE : Affiche la structure d’une table.
— SUMMARIZE : Donne un résumé des statistiques d’une table ou d’une requête.
— EXPLAIN : Explique comment une requête SQL sera exécutée.
— run_and_profile_query : Exécute et profile une requête SQL.
— PRAGMA explain_output : Contrôle le format de sortie d’EXPLAIN.
— PRAGMA enable_profiling : Active le profilage des requêtes SQL.
— PRAGMA enable_optimizer : Active l’optimiseur de requêtes SQL.
— Créer un Index
1 db . execute ( " create index name_index on table ( attribut ) " )
— Supprimer un Index
1 db . execute ( " drop index if exists name_index ; " )
— Vérifier la Présence d’un Index
1 db . execute ( " select index_name , table_name , is_unique , is_primary ,
sql from duckdb_indexes () " ) . df ()

4
Ordre Jointure: sachant que Card(A) > Card(B) > Card(C) > Card(D)
— ((A, B), (C, D))
1 SELECT A. ab
2 FROM (A JOIN B ON A. ab = B . ba )
3 JOIN (C JOIN D ON C . cd = D. dc ) ON A. ac = C . ca ;

1 def query_plan1 () :
2 res = []
3 resAB = []
4 resCD = []
5 queryA = " SELECT ab , ac FROM A "
6 queryB = " SELECT ba FROM B WHERE ba =? "
7 queryC = " SELECT cd , ca FROM C "
8 queryD = " SELECT dc FROM D WHERE bc =? "
9

10 for c in db . execute ( queryC ) . fetchall () :

11 d = db . execute ( queryD , ( c [0]) ) . fetchall ()
12 if d is not None :
13 resCD . append ( c [1])
14

15 for a in db . execute ( queryA ) . fetchall () :

16 b = db . execute ( queryB , ( a [0]) ) . fetchall ()
17 if b is not None :
18 resAB . append (( a [0] , a [1]) )
19

20 for ab0 , ab1 , ac in resAB , resCD :

21 if ab0 == ac :
22 res . append ( ab1 )
23 return res

— (((A, B), C), D)

1 SELECT C . cd
2 FROM ( (A JOIN B ON A. ab = B . ba ) JOIN C ON A. ac = C . ca )
3 JOIN D ON C . cd = D. dc ;

1 def query_plan1 () :
2 res = []
3 queryA = " SELECT ab , ac FROM A "
4 queryB = " SELECT ba FROM B WHERE ba =? "
5 queryC = " SELECT ca , cd FROM C WHERE ca =? "
6 queryD = " SELECT dc FROM D WHERE dc =? "
7

8 for a in db . execute ( queryA ) . fetchall () :

9 b = db . execute ( queryB , ( a [0]) ) . fetchall ()
10 if b is not None :
11 c = db . execute ( queryC , ( a [1]) ) . fetchall ()
12 if c is not None :
13 d = db . execute ( queryD , ( c [1]) ) . fetchall ()
14 if d is not None :
15 res . append ( c [1])
16 return res

5
— (A, (B, (C, D)))
1 SELECT B . bc
2 FROM A
3 JOIN (B JOIN (C JOIN D ON C . cd = D. dc ) ON B . bc = C . cb ) ON A. ab = B . ba ;

1 def query_plan1 () :
2 res = []
3 queryA = " SELECT ab FROM A WHERE ab =? "
4 queryB = " SELECT ba , bc FROM B WHERE bc =? "
5 queryC = " SELECT cb , cd FROM C WHERE cd =? "
6 queryD = " SELECT dc FROM D "
7

8 for d in db . execute ( queryD ) . fetchall () :

9 c = db . execute ( queryC , ( d ) ) . fetchall ()
10 if c is not None :
11 b = db . execute ( queryB , ( c [0]) ) . fetchall ()
12 if b is not None :
13 a = db . execute ( queryA , ( b [0]) ) . fetchall ()
14 if a is not None :
15 res . append ( b [1])
16 return res

— (A, (B, C), D)

1 SELECT D. da
2 FROM A
3 JOIN (B JOIN C ON B . bc = C . cb ) ON A. ab = B . ba
4 JOIN D ON A. ad = D. da ;

1 def query_plan1 () :
2 res = []
3 resBC = []
4 queryA = " SELECT ab , ad FROM A "
5 queryB = " SELECT bc , ba FROM B "
6 queryC = " SELECT cb FROM C WHERE cb =? "
7 queryD = " SELECT da FROM D WHERE da =? "
8

9 for b in db . execute ( queryB ) . fetchall () :

10 c = db . execute ( queryC , ( b [0]) ) . fetchall ()
11 if c is not None :
12 resBC . append ( b [1])
13

14 for a , bc in db . execute ( queryA ) . fetchall () , resBC :

15 if a [0] == bc :
16 d = db . execute ( queryD , ( a [1]) ) . fetchall ()
17 if d is not None :
18 res . append ( d )
19 return res

6
 Exercices TD
Index: Pour choisir un bon Index :
— Priorité à la condition s’il y a une condition d’égalité puis à la projection et enfin au clause ORDER
BY , GROUP BY...
— Priorité à la projection s’il y a une projection sur un attribut ou un DISTINCT.
— Les conditions de critère de selection (LIKE ou Intervalle de comparaison) sont à éviter.

Index ART: Création d’une valeur :

— Si la lettre n’existe pas alors ajoutée la lettre
à la racine et créer une feuille directement.
— Si la lettre existe, vérifier la prochaine lettre
et ainsi de suite.
— Si deux valeurs ont au début les mêmes lettres
alors écrire la lettre qui les différencie dans la
racine et mettre P = lettre_pareil.
Hachage Extensible: Soit R[A,B] avec PL=1 et PG=1 et un paquet peut contenir 2 valeurs max.
Paquet A(10,2) et le Paquet B(1,5)
— Insérer 15 : R[15 mod 2P G ] = R[1] = B → Plein et PL=PG alors doubler le repertoire, P G =
P G + 1 = 2. Eclater le paquet B et créer un paquet C tel que R[3] = C et P L(B) = P L(C) = 2 →
R[A,B,A,C]. Répartir les valeur du paquet B entre B et C → B(1,5) et C(15).
— Insérer 16 R[16 mod 2P G ] = R[0] = A → Plein et PL<PG alors Créer un paquet D tel que
R[2] = D et P L(A) = P L(D) = 2 et le raccrocher → R[A,B,D,C]. Répartir les valeur du paquet A
entre A et D → A(16) et D(10,2).
— Supprimer 15 R[15 mod 2P G ] = R[3] = C → PL=PG alors supprimer C et fusionner C et B tel
que R[3] = B et P L(B) = 1 → R[A,B,D,B].

Hachage Linéaire: Soit R[A,B,C,D] avec P=A et seuil=75% et un paquet peut contenir 2 valeurs max.
A(4,8), B(1), C(10,14), D(15) donc N=4 et occup=0.75
— Insérer 22 : R[22 mod N] = R[2] = C → Plein et occup≥seuil alors Eclater P=A et créer un paquet
E → R[A,B,C,D,E]. Répartir les valeur du paquet A entre A et E sachant que N = 4 × 2 = 8 →
A(8) et E(4) et occup=0.6. R[22 mod N] = R[2] = C → Plein et occup≤seuil → Pas d’éclatement
et créer C’(22) chainée a C et occup=0.7.

Optimisation des Requêtes: (Cout et Card)

1) Ecrire sous forme algébrique → πmention ((σmention=B (E)) ▷◁nF (σregion=′ idf ′ (F ))
1 S e l e c t e . mention
2 From E t ud i an t e , Formation f
3 WHERE e . nF=F . n f and e . mention=B and f . r e g i o n= ’ i d f ’

2) Jointure entre deux Table avec la même clé primaire → Card de la table la plus petite.
3) Pour calculer le coût d’une table, si elle n’a pas d’index → Nombre de page : Page(table)
4) Calculer le Coût de la jointure de la requête sachant qu’il y a un index sur R.a et R.b :
1 Select ∗
2 From R, S
3 WHERE R. a = S . c and R. b = 1

— Hachage → Cout(R) + Cout(S) = P age(R) + P age(S)

— Avec Index → Cout(S) + card(S) × Cout(σa=c (R)) = P age(S) + Card(S) + Card(R) × SF (a = c)
— Sans Index → Cout(R)+Card(R)×Cout(σa=c (S)) = P age(R)+Card(R)+Card(S)×SF (a = c))
— Acces par Index puis Hachage → Cout(σb=1 (R)) + Cout(S) = Card(R) × SF (b = 1) + P age(S)

7
 Base de Données Réparties
BDR: Système logiciel de gestion rendant la distribution (répartition) des donnèes transparente.
Types de Fragmentation:
— Fragmentation Horizontale Fragments définis par sélection.
— Fragmentation Verticale Fragments définis par projection.
— Fragmentation Horizontale Dérivée Fragments définis par semi jointure.

Figure 1 – Fragmentation Horizontale, Verticale et Horizontale Dérivée

Réduction: éliminer l’accès aux fragments et aux relations de base inutiles et distribuer les jointures par
rapport aux unions.

Figure 2 – Réduction Horizontale et Verticale

Figure 3 – Réduction Horizontale Dérivée

Optimisation: 4 stratégies possibles pour effectuer R ▷◁ S sur l’attribut A, avec l’algorithme des Boucles
Imbriquées (R relation externe, S relation interne)
On note LC le coût du traitement local et CC le coût de communication et s= Card(S▷◁ A R)
Card(R)
— Envoyer R sur S : Coût total = LC(retrouver card(R) n-uplets de R) + CC(size(R)) + LC(retrouver
s n-uplets de S)×card(R))
— Envoyer S sur R : Coût total = LC(retrouver card(S) n-uplets de S) + CC(size(S)) + LC(stocker
card(S) n-uplets dans T) + LC(retrouver card(R) n-uplets de R) + LC(retrouver s n-uplets de
T)×card(R)
— Chercher les n-uplets de S nécessaires pour chaque n-uplet de R sachant que l’attribut
A est unique : Coût total = LC(retrouver card (R) n-uplets de R) + CC(length(A))×card(R) +
LC (retrouver s n-uplets de S)×card (R) + CC(s×length(S))×card (R)
— Transférer les deux relations sur un troisième site et calculer la jointure sur ce site :
Coût total = LC(retrouver card(S) n-uplets de S) + CC(size(S)) + LC (stocker card(S) n-uplets
dans T) + LC (retrouver card (R) n-uplets de R) + CC (size(R)) + LC (retrouver s n-uplets de
T)×card(R)

8
 Exercice 1: Soit la base de données AutoRoul d’une chaîne de garages automobiles :
Personne (idpers, nom, prenom, age, tél) /* mécanicien ou client */
Garage (idgarage, nom, ville, jourdefermeture)
Habilite (idgarage, marque) /* garage répare des véhicules de la marque */
Mecanicien (idpers, idgarage, niveau) /* mécanicien travaille dans un garage */
Client (idpers, taille)
Possede (immat, marque, modele, idclient)
Reparation (idmecanicien, immat, date, intervention) /* immat ∈ [1 − 10000] */
Tarif (intervention, prix)
Fragmentation par Ville:
Fragmentation Disjointe: Lorsque chaque tuple de la base de données n’apparaît que dans un seul
fragment. Dans cette exercice, :
— Garagev = σville=v (Garage)
— M ecanicienv = M ecanicien ▷◁idgarage Garagev
— Habitev = Habite ▷◁idgarage Garagev
— Reparationv = Reparation ▷◁idmecanicien=idpers M ecanicienv
— T arifv = T arif ▷◁intervention Reparationv
Fragmentation Non Disjointe: Dans cette exemple, une fragmentation n’est pas disjointe si l’élément
peut se trouver dans plusieurs fragments.
— P ossedev = P ossede ▷◁immat Reparationv ⇒ ∃v1, v2 P ossedev1 ∩ P ossedev2 ̸= ∅
ainsi la fragmentatin n’est pas disjointe si un vehicule (immat) est réparé dans plusieurs ville.
— Clientv = Client ▷◁idclient P ossedev
— P ersonnev = P ersonne ▷◁idpers (πidpers Clientv ∪ πidpers M ecanicienv )
On suppose maintenant que les relations sont réparties sur deux sites, S1 et S2 tel que T ableSi est le
fragment de Table alloué au site Si . On a :
— P ossedeS1 = σimmat<7000 P ersonne et P ossedeS2 = P ersonne − P ersonneS1
— ReparationS1 = σimmat<7000 Reparation et ReparationS2 = Reparation − ReparationS1 .
— T arifS1 = T arifS2 = T arif = T arifS1∨S2

Soit la requête R :
1 S e l e c t p . marque
2 from R e p a r a t i o n r , T a r i f t , Possede p
3 where r . i n t e r v e n t i o n = t . i n t e r v e n t i o n and t . p r i x < 100 and r . immat = p . immat
4 and p . immat < 6 0 0 0 ;

Requête Algébrique:
— T1 = Reparation ▷◁intervention σprix<100 T arif
— T2 = T1 ▷◁immat σimmat<6000 P ossede
— R = πmarque T2
Simplifier l’expression algébrique, on pose :
— T3 = σimmat<6000 P ossede1
— T4 = σprix<100 T arif
— T5 = (Reparation1 ▷◁ T4 ) ∪ (Reparation2 ▷◁ T4 )
— T6 = T5 ▷◁ T3 = σimmat<6000 Reparation1 ▷◁ T4 ▷◁ σimmat<6000 P ossede1
— R = πmarque T6
R peut être traitée entierement sur S1

9
 Exercice 2: Soient R1(A,B) dans S1 et S2 et R2(C,A) dans S2 et R3(B,D) dans S3
Les trois sites ont une mémoire principale de 201 pages. La tailled’une page est de 4000 octets. Le nombre
de pages de P(R1)=10 000 et P(R2)=100 000 et P(R3)=10 000. La taille de chaque attribut est 10 octets.
On note : tIo coût Lecture/Ecriture d’une page sur disque et Ts coût de transfert d’une page sur le réseau.
— Card(R1) = P (R1) × 10+104000
= 2 × 106
— Card(T ) = Card(R1 ▷◁ R2) = Card(R2) = P (R2) + 4000
10+10
= 2 × 107
— P (T ) = Card(T
4000
)
= 150 × 103
30

— P (Q) = P (T ▷◁ R3) = Card(T )

4000 = 200 × 103
40

Calcul du Coût pour Executer Q

1. Calcul de T sur S2 :
— Lire R1 et R2 + Ecrire R1 et R2 par morceaux (Hachage) + Lire R1 et R2 (Jointure)
— Cout(T ) = 3(P (R1) + P (R2)) × tIO
2. Transfert de T sur S3 :
— P (T ) × ts
3. Calcul de Q sur S3 :
— Lire R3 + Ecrire R3 et T par morceaux (Hachage) + Lire R3 et T (Jointure)
— Cout(Q) = (2P (T ) + 3P (R3)) × tI0
4. Transfert de Q sur S1 :
— P (Q) × ts

T otal = [3P (R1) + 3P (R2) + 2P (T ) + 3P (R3)] × tIO + [P (T ) + P (Q)] × ts = 66 × 104 × tIO + 35 × 104 × ts

Exercice 3: Soient Perf (ids, comp, rang) sur S1 et Sportif (ids, nom) sur S2
Le sportif ids est classé à la position rang pour la compétition comp, s’il n’est pas classé, son rang vaut 0.
JDBC: Ecrire le programme JDBC :
Calculer A1(ids, rang). Les performances du sportif ids pour les compétition où son rang<rang, trié
par comp et rang.
1 v o i d A1( i n t X, i n t Y) {
2 s 1 = DriverManager . g e t C o n n e c t i o n ( u r l 1 ) ; // s i t e S1
3 PreparedStatement q1 = s 1 . p r e p a r e S t a t e m e n t ( " s e l e c t comp , rang from P e r f where i d s = ?
o r d e r by comp , rang " ) ;
4 q1 . s e t I n t ( 1 , X) ;
5 R e s u l t S e t r 1 = q1 . executeQuery ( ) ;
6 w h i l e ( r 1 . next ( ) ) {
7 i f ( r 1 . g e t I n t ( 2 ) < Y)
8 out . p r i n t l n ( r 1 . g e t S t r i n g ( 1 ) + " " + r 1 . g e t I n t ( 2 ) ) ;
9 }
10 q1 . c l o s e ( ) ; s 1 . c l o s e ( ) ;
11 }

10
 Calculer A2(comp). Le nombre de sportif qui ont participé à au moins comp compétition.
1 v o i d A2( i n t X) {
2 s 1 = DriverManager . g e t C o n n e c t i o n ( u r l 1 ) ; // s i t e S1
3 PreparedStatement q1 = s 1 . p r e p a r e S t a t e m e n t ( " s e l e c t i d s from P e r f group by i d s having
count ( ∗ ) >= ? " ) ;
4 q1 . s e t I n t ( 1 , X) ;
5 R e s u l t S e t r 1 = q1 . executeQuery ( ) ;
6 i n t c =0;
7 w h i l e ( r 1 . next ( ) ) { c = c +1; } // f i n du w h i l e
8 out . p r i n t l n ( c ) ;
9 q1 . c l o s e ( ) ; s 1 . c l o s e ( ) ;
10 }

Requêtes Réparties: Ecrire la requête répartie :

Le traitement utilise des semi-jointures. On utilise les tables auxilliaires T1(a int, b varchar) et T2(a int).
1. J1 = Perf ▷◁ids Sportif et le schéma du résultat de J1 est (ids, comp, rang, nom)
1 s u r S1 : q1 = SELECT ∗ FROM p e r f ORDER BY i d s
2 T1 = S1 . e x e c u t e ( q1 )
3 T1 −> S0
4 s u r S0 : f o r t 1 i n T1 :
5 s u r S2 : q2 = SELECT ∗ FROM s p o r t i f WHERE i d s ={t 1 . i d s }
6 T2 = S2 . e x e c u t e ( q2 )
7 T2 −> S0
8 f o r t 2 i n T2 :
9 r e s . append ( t 1 . i d s , t 1 . comp , t 1 . rang , t 2 . nom)

2. soit la requete suivnte :

1 SELECT p . i d s , s . nom , p . comp
2 FROM S p o r t s , P e r f p
3 WHERE s . i d s = p . i d s AND p . rang >10
4 ORDER BY s . nom

1 s u r S2 : q2 = SELECT ∗ FROM s p o r t i f ORDER BY nom

2 T2 = S2 . e x e c u t e ( q2 )
3 T2 −> S0
4 s u r S0 : f o r t 2 i n T2 :
5 s u r S1 : q1 = SELECT comp FROM p e r f WHERE rang >10 and i d s ={t 2 . i d s }
6 T1 = S1 . e x e c u t e ( q1 )
7 T1 −> S0
8 f o r t 1 i n R1 :
9 r e s . append ( t 2 . i d s , t 1 . comp , t 2 . nom)

11
 Transactions
Exercice: Si deux transactions Ti posée sur Ma et Tj posée sur Mb accèdent à au moins une donnée
commune, on a :
— si a < b, alors Ti précède Tj .
— si a = b et i < j, alors Ti précède Tj .
Les données sont placées sur les machines comme suit : M1 : A,B | M2 : C,D | M3 : E,F | M4 : G
Les transactions reçues pendant la période P1 sont :
— M1 : T4(E,G), T5(A)
— M2 : T2(C,E), T6(B,A)
— M3 : T1(G), T7(D,G)
— M4 : T3(G,B)
Les Transactions Locales: Les transactions dont tous ses éléments s’éxecute dans la même machine.
Dans cette exemple : T5 et T6 (car A et B s’execute sur M1) et T1 (car G s’execute sur M4).
Les Transactions Globales: Les transactions dont chaque éléments s’éxecute sur une machine différente.
Dans cette exemple : T2, T3, T4, T7.
Traitement des Transactions: Une machine M traite une transaction seulement si dans la transaction
il y a une écriture sur un élément qui s’execute M . Dans cette exemple :
— M1 : T5, T6, T3 (car il y a soit l’élément A ou B qui doit être traité que dans M1).
— M2 : T2, T7 (car il y a soit l’élément C ou D qui doit être traité que dans M2).
— M3 : T4, T2 (car il y a soit l’élément E ou F qui doit être traité que dans M3).
— M4 : T4, T1, T7, T3 (car il y a l’élément G qui doit être traité que dans M4).
L’exécution d’une Transaction:
— Traiter : Si et seulement si ayant au moins une donnée à écrire localement.
— Envoyer : Si et seulement si le site traite la transaction.
— Recevoir : S’il y a Lecture.

12