Graf priority - Precedence graph

Přednost graf , také nazývaný konflikt graf a sériovost graf se používá v souvislosti s souběžnosti kontroly v databázích .

Graf priority pro plán S obsahuje:

• Uzel pro každou potvrzenou transakci v S.
• Oblouk z T _i do T _j, pokud akce T _i předchází a je v konfliktu s jednou z akcí T _j . To znamená, že akce patří do různých transakcí, alespoň jednou z akcí je operace zápisu a akce přistupují ke stejnému objektu (čtení nebo zápis).

Příklady grafu priority

Příklad 1

Příklad 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}}}$

Příklad 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}$

Prioritní graf plánu D se 3 transakcemi. Vzhledem k tomu, je cyklus (o délce 2, se dvěma hranami) přes potvrzených transakcí T1 a T2, tento program (historie) je není konflikt serializovatelný . Všimněte si, že potvrzení transakce 2 nemá žádný význam, pokud jde o vytvoření prioritního grafu.

Testování serializovatelnosti s grafem priority

Příklad testování serializovatelnosti

Algoritmus pro testování Serializovatelnosti konfliktu plánu S spolu s ukázkovým plánem.

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

nebo

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

1. Pro každou transakci T _x účastnící se plánu S vytvořte uzel označený T _i v grafu priority. Graf priority tedy obsahuje T ₁ , T ₂ , T ₃ .
2. Pro každý případ v S, kde T _j provede read_item (X) po T _i provede write_item (X), vytvořit hranu (T _i → T _j ) v přednost graf. Ve výše uvedeném příkladu se to nikde nevyskytuje, protože po zápisu není čtení.
3. Pro každý případ v S, kde T _j provede write_item (X) po T _i provede read_item (X), vytvořit hranu (T _i → T _j ) v přednost graf. To má za následek směřující hrany od T ₁ až T ₂ (jako T ₁ má R (A) , než T ₂ s W (A) ).
4. Pro každý případ v S, kde T _j provede write_item (X) po T _i provede write_item (X), vytvořit hranu (T _i → T _j ) v přednost graf. To má za následek směřujících hran od T ₂ až T ₁ , T ₂ až T ₃ a T ₁ až T ₃ .
5. Plán S je serializovatelný právě tehdy, pokud graf priority nemá žádné cykly. Jako T ₁ a T ₂ tvoří cyklus, výše uvedený příklad není (konflikt) serializovatelný.

Reference

externí odkazy

• Základy databázových systémů, 5. vydání, použití prioritních grafů je popsáno v kapitole 17, protože se týkají testů serializovatelnosti konfliktů .
• Abraham Silberschatz, Henry Korth a S. Sudarshan. 2005. Database Systems Concepts (5. vydání), PP. 628–630. McGraw-Hill, Inc., New York, NY, USA.