Graf priority - Precedence graph

A prioritní graf, také pojmenovaný konfliktní graf[1] a serializovatelnost graf, se používá v kontextu řízení souběžnosti v databáze.^[1]

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 konflikty s jedním z T_jakce.

Příklady grafu priority

Příklad 1

Příklad 2

${displaystyle S = {egin {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. Protože existuje cyklus (o délce 2; se dvěma okraji) prostřednictvím potvrzených transakcí T1 a T2, toto plán (historie) je ne Konflikt lze serializovat.Upozornění, ž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 k testování Serializovatelnost konfliktů plánu S spolu s ukázkovým plánem.

${displaystyle S = {egin {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 prioritním grafu. Graf priority tedy obsahuje T₁, T₂, T₃.
2. Pro každý případ v S, kde T_j provede a read_item(X) po T_i provede a write_item(X), vytvořte hranu (T_i → T_j) v prioritním grafu. 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 a write_item(X) po T_i provede a read_item(X), vytvořte hranu (T_i → T_j) v prioritním grafu. Výsledkem je směrovaná hrana od T₁ do T₂ (jako T₁ má R (A) před T₂ mít W (A)).
4. Pro každý případ v S, kde T_j provede a write_item(X) po T_i provede a write_item(X), vytvořte hranu (T_i → T_j) v prioritním grafu. Výsledkem jsou směrované hrany od T₂ do T₁, T₂ do T₃ a T₁ do 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í (konfliktní) 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 vztahují k testům na serializovatelnost konfliktu.
• Abraham Silberschatz, Henry Korth a S. Sudarshan. 2005. Database Systems Concepts (5. vydání), PP. 628–630. McGraw-Hill, Inc., New York, NY, USA.