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 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). vignette| Exemple 1 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 . Notez que le commit de la transaction 2 n'a aucune signification concernant la création d'un graphe de priorité. vignette| Exemple de test de sérialisabilité Algorithme pour tester la sérialisabilité des conflits d'une annexe S avec un exemple d'horaire. 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 1, T 2, T 3 . 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. 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 1 à T 2 (car T 1 a R(A) avant T 2 a W(A) ). 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 2 vers T 1, T 2 vers T 3 et T 1 vers T 3 . L'ordonnancement S est sérialisable si et seulement si le graphe de précédence n'a pas de cycles.