Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Graphe de précédence
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.