Précédent Index

4   Concurrence (5 points)

L'exécution suivante est reçue par un SGBD utilisé pour des applications de commerce éléctronique.

H : r1[x] r2[y] w1[x] r2[z] r3[z] r3[x] w2[z] r1[z] c2 w1[x] c1 w3[x] c3



  1. (1 point) L'une des opérations dans l'application de commerce électronique est la modification du prix d'un produit suite à une réduction de prix d'un pourcentage donné (le prix du produit et le taux de réduction sont stockés dans la base de données). Y a-t-il une ou plusieurs transactions de H qui puissent provenir de l'exécution de cette opération? Justifiez votre réponse.



    Solution : Les transactions de l'exécution H sont :
    T    1: r1[x] w1[x] r1[z] w1[x] c1
    T    2: r2[y] r2[z] w2[z] c2
    T    3: r3[z] r3[x] w3[x] c3

    La réduction du prix nécessite la lecture du taux de réduction et ensuite la mise-à-jour (lecture+écriture) du prix. Les transactions T2 et T3 correspondent à cette suite d'actions. Mais les deux ne peuvent pas être en même temps des réductions de prix, car z ne peut pas être à la fois prix (pour T2) et taux de réduction (pour T3). Donc la réponse correcte est oui, soit T2, soit T3, mais pas les deux ensemble.

  2. (1 point) Vérifiez si H est sérialisable en identifiant les conflits et en construisant le graphe de sérialisation.



    Solution : Les conflits :
    sur     x : r1[x]-w3[x], w1[x]-r3[x], w1[x]-w3[x], r3[x]-w1[x]
    sur     y : pas de conflit
    sur     z : r3[z]-w2[z], w2[z]-r1[z]

    Le graphe de sérialisation contient un cycle T    1 T3 T2 et un autre cycle T1 T3, donc H n'est pas sérialisable.

  3. (1,5 points) Montrez que l'exécution H n'évite pas les annulations en cascade. Est-elle recouvrable? Est-il possible, en modifiant seulement la position des Commit d'éviter les annulations en cascade?



    Solution : Après w1[x], on a plus tard r3[x] avant la fin de T1, donc H n'évite pas les annulations en cascade. Pareil pour w2[z] suivi de r1[z]. Par contre H est recouvrable, car dans les deux cas la transaction qui écrit est validée avant celle qui lit.

    Pour éviter les annulations en cascade, il faudrait déplacer c    1 avant r3[x], respectivement c2 avant r1[z]. Le second déplacement est possible, par contre le premier est impossible, car r1[z] et w1[x] resteraient après c1. Donc la réponse est non.

  4. (1,5 points) Quelle est l'exécution obtenue par verrouillage à deux phases à partir de H?

    On considère qu'il existe deux verrous pour chaque enregistrement, un de lecture et un d'écriture. Le relâchement des verrous d'une transaction se fait au Commit et à ce moment on exécute en priorité les opérations bloquées en attente de verrou, dans l'ordre de leur blocage.



    Solution : H : r1[x] r2[y] w1[x] r2[z] r3[z] r3[x] w2[z] r1[z] c2 w1[x] c1 w3[x] c3

    r1[x], r2[y] s'exécutent, en prenant les verrous de lecture
    w    1[x] s'exécute, pas de conflit avec r1[x] (même transaction)
    r    2[z] prend le verrou de lecture sur z et s'exécute
    r    3[z] partage le verrou de lecture sur z avec r2[z] et s'exécute
    r    3[x] bloquée par w1[x], donc T3 bloquée
    w    2[z] bloquée par r3[z], donc T2 bloquée
    r    1[z] partage le verrou de lecture sur z avec r2[z] et r3[z] et s'exécute
    c    2 bloquée car T2 bloquée
    w    1[x] a déjà le verrou et peut s'exécuter
    c    1 s'exécute et relâche les verrous de T1 Þ r3[x] peut obtenir le verrou sur x et s'exécuter, par contre T2 reste bloquée
    w    3[x] prend le verrou d'écriture sur x et s'exécute
    c    3 s'exécute et relâche les verrous de T3 Þ toutes les opérations de T2 sont débloquées, donc w2[z] et c2 s'exécutent

    Le résultat final est donc     H' : r1[x] r2[y] w1[x] r2[z] r3[z] r1[z] w1[x] c1 r3[x] w3[x] c3 w2[z] c2
Précédent Index