Preferensgraf

En prioritetsgraf , även kallad konfliktgraf och serialiseringsgraf , används i samband med samtidighetskontroll i databaser .

Preferensgrafen för ett schema S innehåller:

• En nod för varje genomförd transaktion i S
• En båge från T _i till T _j om en åtgärd av T _i föregår och står i konflikt med en av T _j: s handlingar. Det vill säga att åtgärderna tillhör olika transaktioner, åtminstone en av åtgärderna är en skrivoperation, och åtgärderna kommer åt samma objekt (läs eller skriv).

Exempel på prioritetsdiagram

Exempel 1

Exempel 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}}$

Exempel 2

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

En prioritetsgraf för schemat D, med 3 transaktioner. Eftersom det finns en cykel (av längd 2; med två kanter) genom de genomförda transaktionerna T1 och T2, är detta schema (historik) inte konfliktserialiserbart . Lägg märke till att förpliktelsen av transaktion 2 inte har någon betydelse när det gäller skapandet av en prioritetsgraf.

Testar serialiserbarhet med Precedence Graph

Testa serialiseringsexempel

Algoritm för att testa konfliktserialisering av ett schema S tillsammans med ett exempelschema.

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

eller

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

1. För varje transaktion T _x som deltar i schema S, skapa en nod märkt Ti _i prioritetsdiagrammet. Sålunda innehåller prioritetsgrafen T ₁ , T ₂ , T ₃ .
2. För varje fall i S där T _j exekverar ett read_item (X) efter att T _i exekverar ett write_item (X), skapa en kant (T _i → T _j ) i prioritetsgrafen. Detta förekommer ingenstans i exemplet ovan, eftersom det inte finns någon läsning efter skrivning.
3. För varje fall i S där T _j exekverar ett write_item (X) efter att T _i exekverar ett read_item (X), skapa en kant (T _i → T _j ) i prioritetsgrafen. Detta resulterar i en riktad kant från Ti _till T2 ₍ eftersom Ti _har R (A) före T2 _som har W(A) ).
4. För varje fall i S där T _j exekverar en write_item (X) efter att Ti _exekverar en write_item (X), skapa en kant (T _i → T _j ) i prioritetsgrafen. Detta resulterar i riktade kanter från _T2 till _T1 , T2 till _T3 och _T1 till _{T3 .}
5. Schemat S är serialiserbart om och endast om prioritetsgrafen inte har några cykler. Eftersom T ₁ och T ₂ utgör en cykel är exemplet ovan inte (konflikt) serialiserbart.

externa länkar

• The Fundamentals of Database Systems, 5:e upplagan, användningen av prioritetsgrafer diskuteras i kapitel 17, eftersom de hänför sig till tester för att serialisera konflikter .
• Abraham Silberschatz , Henry Korth och S. Sudarshan. 2005. Databas System Concepts (5 uppl.), PP. 628–630. McGraw-Hill, Inc., New York, NY, USA.