Graphe de précédence

Un graphe de précédence, également appelé graphe de conflit ou graphe de serializability, est utilisé dans le cadre du concurrency control^[Quoi ?] dans les bases de données.

Le graphe de précédence pour un programme S contient :

• Un nœud pour chaque transaction validée dans S ;
• Un arc de T _i à T _j si une action de T _i précède et entre en conflit avec l'une des actions de T _j . Autrement dit, les actions appartiennent à différentes transactions, au moins une des actions est une opération d'écriture et les actions accèdent au même objet (lecture ou écriture).

Exemples d'un graphe de précédence

Exemple 1

Exemple 1

$S={\begin{bmatrix}T1&T2\\R(A)&R(A)\\A=A*5&R(B)\\W(A)&B=B+A\\R(B)&W(B)\\B=B*10&\\W(B)&\\\end{bmatrix}}$

Exemple 2

$D=R1(A)$ $R2(B)$ $W2(A)$ $Com.2$ $W1(A)$ $Com.1$ $W3(A)$ $Com.3$

Un graphe de précédence du programme D, avec 3 transactions. Comme il existe un cycle (de longueur 2 ; avec deux arêtes) à travers les transactions validées T1 et T2, cette planification (historique) n'est pas Conflict serializable (en). Notez que le commit de la transaction 2 n'a aucune signification concernant la création d'un graphe de priorité.

Test de la sérialisabilité avec le graphe de précédence

Exemple de test de sérialisabilité

Algorithme pour tester la sérialisabilité des conflits d'une annexe S avec un exemple d'horaire.

$S={\begin{bmatrix}T1&T2&T3\\R(A)&&\\&W(A)&\\&Com.&\\W(A)&&\\Com.&&\\&&W(A)\\&&Com.\\\end{bmatrix}}$

$S=R1(A)$ $W2(A)$ $Com.2$ $W1(A)$ $Com.1$ $W3(A)$ $Com.3$

1. Pour chaque transaction T _x participant à l'horaire S, créez un nœud étiqueté T _i dans le graphe de priorité. Ainsi le graphe de précédence contient T ₁, T ₂, T ₃ .
2. Pour chaque cas dans S où T _j exécute un read_item (X) après que T _i exécute un write_item (X), créez une arête (T _i → T _j ) dans le graphe de priorité. Cela ne se produit nulle part dans l'exemple ci-dessus, car il n'y a pas de lecture après écriture.
3. Pour chaque cas dans S où T _j exécute un write_item (X) après que T _i ait exécuté un read_item (X), créez une arête (T _i → T _j ) dans le graphe de priorité. Il en résulte un bord dirigé de T ₁ à T ₂ (car T ₁ a R(A) avant T ₂ a W(A) ).
4. Pour chaque cas dans S où T _j exécute un write_item (X) après que T _i exécute un write_item (X), créez une arête (T _i → T _j ) dans le graphe de priorité. Il en résulte des fronts dirigés de T ₂ vers T ₁, T ₂ vers T ₃ et T ₁ vers T ₃ .
5. L'ordonnancement S est sérialisable si et seulement si le graphe de précédence n'a pas de cycles. Comme T ₁ et T ₂ constituent un cycle, l'exemple ci-dessus n'est pas (conflit) sérialisable.

Liens externes

• The Fundamentals of Database Systems, 5th Edition, l'utilisation des graphes de précédence est abordée au chapitre 17, car ils se rapportent aux tests de Conflict serializability (en).
• Abraham Silberschatz (en), Henry Korth et S. Sudarshan. 2005. Concepts du système de base de données (5 éd. ), PP. 628–630. McGraw-Hill, Inc., New York, NY, États-Unis.