Graphique de précédence

Un graphe de priorité , également appelé graphe de conflit et graphe de sérialisation , est utilisé dans le contexte du contrôle de concurrence dans les bases de données . Il s'agit du graphe orienté représentant la priorité des transactions dans le planning, telle que reflétée par la priorité des opérations conflictuelles dans les transactions. Un planning est sérialisable en cas de conflit si et seulement si son graphe de priorité des transactions validées est acyclique .

Le graphique de priorité pour un planning 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 . C'est-à-dire que les actions appartiennent à des transactions différentes, qu'au moins l'une des actions est une opération d'écriture et que les actions accèdent au même objet (lecture ou écriture).

Les cycles de transactions validées peuvent être évités en interrompant une transaction indécise (ni validée, ni abandonnée) à chaque cycle dans le graphique de priorité de toutes les transactions, ce qui peut sinon se transformer en un cycle de transactions validées (et une transaction validée ne peut pas être abandonnée). Une transaction abandonnée par cycle est à la fois nécessaire et suffisante en nombre pour interrompre et éliminer le cycle (davantage d'abandons sont possibles et peuvent se produire sous certains mécanismes, mais ne sont pas nécessaires pour la sérialisabilité). La probabilité de génération de cycles est généralement faible, mais, néanmoins, une telle situation est gérée avec soin, généralement avec une quantité considérable de surcharge, car l'exactitude est impliquée. Les transactions abandonnées en raison de la prévention de violation de sérialisabilité sont redémarrées et exécutées à nouveau immédiatement.

Un graphique de priorité du planning D, avec 3 transactions. Comme il existe un cycle (de longueur 2 ; avec deux arêtes) à travers les transactions validées T1 et T2, ce planning (historique) n'est pas sérialisable en cas de conflit . Notez que la validation de la transaction 2 n'a aucune signification concernant la création d'un graphique de priorité.

Algorithme pour tester la sérialisabilité des conflits d'un planning S avec un exemple de planning.

ou

1. Pour chaque transaction T _x participant au programme S, créez un nœud étiqueté T _i dans le graphe de priorité. Ainsi, le graphe de priorité contient T ₁ , T ₂ , T ₃ .
2. Pour chaque cas dans S où T _j exécute un read_item (X) après que T _i a exécuté 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 une écriture (X) après que T _i a exécuté une lecture (X), créez une arête (T _i → T _j ) dans le graphe de priorité. Cela donne une arête dirigée de T ₁ vers T ₂ (car T ₁ a R(A) avant que T ₂ ait W(A) ).
4. Pour chaque cas dans S où T _j exécute un write_item (X) après que T _i a exécuté un write_item (X), créez une arête (T _i → T _j ) dans le graphe de priorité. Cela donne des arêtes dirigées de T ₂ vers T ₁ , T ₂ vers T ₃ et T ₁ vers T ₃ .
5. Le planning S est sérialisable si et seulement si le graphe de précédence ne comporte pas de cycles. Comme T ₁ et T ₂ constituent un cycle, l'exemple ci-dessus n'est pas sérialisable (conflit).