TD2_corrige.doc

TD 2 - Bases de données Exercice 1 : Contrôle de concurrence On suppose que x, y, z et t sont des granules d'une base de données. On
suppose, de plus, que l'on a cinq transactions qui souhaitent accéder à ces
granules. On donne une exécution ci-dessous des cinq transactions : r1(x) r2(y) w1(y) w3(x) w1(t) w5(x) r4(z) r2(z) w4(z) w5(z) r3(t) r5(t) où r désigne une opération de lecture, w une opération d'écriture. Ces
opérations sont indicées par la transaction demanderesse et suivies entre
parenthèses par le granule concerné. 1) Tracer le graphe de dépendances. [pic] 2) Cette exécution est-elle conflit-sérialisable ? Si oui, donnez une
exécution en série qui lui soit conflit-équivalente. conflit-sérialisable car le graphe est acyclique Exécution conflit-équivalente avec l'exécution en série 2-4-1-3-5 Exercice 2 : Comportement d'éxécution 1) Construisez les graphes de sérialisation pour les trois exécutions
suivantes. Indiquez les éxécutions sérialisables et vérifiez si parmi
ces exécutions il y a des exécutions équivalentes. E1 : w2[x] w3[z] w2[y] c2 r1[x] w1[z] c1 r3[y] c3 E2 : r1[x] w2[y] r3[y] w3[z] c3 w1[z] c1 w2[x] c2 E3 : w3[z] w1[z] w2[y] w2[x] c2 r3[y] c3 r1[x] c1 [pic] H1 et H3 sont sérialisables (pas de cycle dans le graphe), H2 ne l'est pas
(cycle T1T2T3).
H1 et H3 sont toutes les deux équivalentes à l'exécution en série T2T3T1.
Cela est visible dans le graphe de
sérialisation, car les arcs indiquent l'ordre des opérations conflictuelles
(d'abord T2, ensuite T3, ensuite T1).
En ce qui concerne l'équivalence d'exécutions, H2 ne peut être équivalente
aux autres, car elle n'est pas sérialisable
et les autres le sont. Il reste à vérifier si H1 est équivalent à H3.
Il semblerait que H1 est équivalent à H3, car on retrouve les mêmes
opérations et les mêmes conflits dans
le même ordre. Cependant, H1 et H3 ne sont pas équivalentes ! Pour avoir
équivalence, deux conditions sont
nécessaires : (i) avoir les mêmes transactions et les mêmes operations, et
(ii) avoir le meme ordre des operations
conflictuelles.
Ici la seconde condition est remplie, mais pas la premiere ! En effet, si
on extrait la transaction T1 de ces histoires,
on remarque que pour H1 on a T1 = r1[x]w1[z]c1, tandis que pour H3, T1 =
w1[z]r1[x]c1. Et c'est pareil pour
T2. 2) Classez les exécutions suivantes suivant leur comportement par rapport
aux annulations, en non-recouvrables, recouvrables, évitant les
annulations en cascade ou strictes. E1 : r1[x] w2[y] r1[y] w1[x] c1 r2[x] w2[x] c2 E2 : r1[x] w1[y] r2[y] c1 w2[x] c2 E3 : r1[y] w2[x] r2[y] w1[x] c2 r1[x] c1 1. H1 : r1[x] w2[y] r1[y] w1[x] c1 r2[x] w2[x] c2
Solution :
Généralement, on commence par chercher les écritures dans l'exécution.
Ensuite, pour une écriture donnée,
on vérifie s'il existe après celle-ci d'autres lectures/écritures sur la
même variable, réalisées par
d'autres transactions. Une lecture peut indiquer un problème de
recouvrabilité / annulation en cascade,
une écriture un problème d'exécution stricte.
T1 lit y de T2 (r1[y] après w2[y]), mais T1 se termine avant T2 =?H1 non-
recouvrable
H1 n'est pas sérialisable (les conflits w2[y] - r1[y] et w1[x] - r2[x]
forment un cycle)
2. H2 : r1[x] w1[y] r2[y] c1 w2[x] c2
Solution :
T2 lit y de T1 (r2[y] après w1[y]) avant que T1 se termine =? H2
recouvrable, mais n'évite pas les
annulations en cascade
H2 est sérialisable (les seuls conflits sont r1[x] - w2[x] et w1[y] -
r2[y])
3. H3 : r1[y] w2[x] r2[y] w1[x] c2 r1[x] c1
Solution :
T1 lit x de T2 (r1[x] après w2[x]) après la fin de T2, mais écrit x (w1[x]
après w2[x]) avant la fin de T2
=? H3 évite les annulations en cascade, mais n'est pas stricte
H3 est sérialisable (les seuls conflits sont w2[x] - w1[x] et w2[x] -
r1[x]) Exercice 3 : Ordonnancement Soit l'ordonnancement suivant ou : . le temps progresse du haut vers le bas, . on suppose qu'il n'y a pas d'échec. Quelles sont les valeurs fournies respectivement par les trois select de
la fin de cet ordonnancement ? Niveau READ COMMITED : chaque transaction garantit au moins que le cas des lectures salissantes ne peut se produire. Cas de tous les SGBD modernes. Ce niveau n'est pas très sûr pour assurer la cohérence....lecture
non renouvelable ou fantome Niveau SERIALIZABLE : niveau fourni par le système qui évite les 3 types d'incohérence et signifie que les requêtes sont exécutées comme si elles étaient lancées les unes après les autres. Ce résultat serait-il différent si la transaction 2 etait serializable ?
pourquoi Si les transactions s 'exécutent au niveau SERIALISABLE, alors
n'importe quelle exécution entrelacée de ces transaction est
garantie être sérialisable[pic] Exercice 4 : Soit la procédure : [pic] Quand une transaction execute la procedure Maj et qu'il n'y a pas de
probleme de serialisabilite, donner les instructions executees par la
transaction (i.e. tracer l'execution). Que se passe-t-il lors du update si une autre transaction non terminee a
deja modifiée la meme ligne de la table ? Que se passe-t-il quand cette autre transaction se termine par un commit ? Dérouler ce qui se passe ensuite pour la transaction dont le update a
échouée et en déduire qu'il y a une GROSSE erreur !