Grafic de precedență - Precedence graph

Un grafic prioritate , numit , de asemenea , graficul de conflict și serializabilitate grafic , este utilizat în contextul controlului concurenței în bazele de date .

Graficul de prioritate pentru un program S conține:

• Un nod pentru fiecare tranzacție angajată în S
• Un arc de la T _i la T _j dacă o acțiune a lui T _i precede și intră în conflict cu una dintre acțiunile lui T _j . Adică acțiunile aparțin unor tranzacții diferite, cel puțin una dintre acțiuni este o operație de scriere, iar acțiunile accesează același obiect (citire sau scriere).

Exemple de grafice de precedență

Exemplul 1

Exemplul 2

${\ displaystyle 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}}}$

Exemplul 2

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

Un grafic de prioritate al graficului D, cu 3 tranzacții. Deoarece există un ciclu (de lungime 2; cu două margini) prin tranzacțiile angajate T1 și T2, acest program (istoric) nu este serializabil Conflict . Observați că comiterea tranzacției 2 nu are nicio semnificație în ceea ce privește crearea unui grafic de prioritate.

Testarea serializabilității cu graficul de precedență

Exemplu de testare a serializabilității

Algoritm pentru testarea serializabilității conflictelor a unei planificări S împreună cu un exemplu de planificare.

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

sau

${\ displaystyle S = R1 (A)}$ ${\ displaystyle W2 (A)}$ ${\ displaystyle Com.2}$ ${\ displaystyle W1 (A)}$ ${\ displaystyle Com.1}$ ${\ displaystyle W3 (A)}$ ${\ displaystyle Com.3}$

1. Pentru fiecare tranzacție T _{x care} participă la programul S, creați un nod etichetat T _i în graficul de precedență. Astfel, graficul de prioritate conține T ₁ , T ₂ , T ₃ .
2. Pentru fiecare caz în S unde T _j execută un read_item (X) după ce T _i execută un write_item (X), creați o margine (T _i → T _j ) în graficul de precedență. Acest lucru nu se întâmplă nicăieri în exemplul de mai sus, deoarece nu există citire după scriere.
3. Pentru fiecare caz în S unde T _j execută un element write_item (X) după ce T _i execută un read_item (X), creați o margine (T _i → T _j ) în graficul de precedență. Aceasta are ca rezultat o margine direcționată de la T ₁ la T ₂ (deoarece T ₁ are R (A) înainte ca T _{2 să} aibă W (A) ).
4. Pentru fiecare caz în S în care T _j execută un element write_ (X) după ce T _i execută un write_item (X), creați o margine (T _i → T _j ) în graficul de precedență. Acest lucru are ca rezultat muchii direcționate de la T ₂ la T ₁ , T ₂ la T ₃ și T ₁ la T ₃ .
5. Programul S este serializabil dacă și numai dacă graficul de precedență nu are cicluri. Deoarece T ₁ și T ₂ constituie un ciclu, exemplul de mai sus nu este serializabil (conflict).

Referințe

linkuri externe

• Fundamentele sistemelor de baze de date, ediția a 5- a, utilizarea graficelor de prioritate este discutată în capitolul 17, deoarece acestea se referă la testele pentru serializarea conflictelor .
• Abraham Silberschatz, Henry Korth și S. Sudarshan. 2005. Concepte de sisteme de baze de date (5 ed.), PP. 628–630. McGraw-Hill, Inc., New York, NY, SUA.