Wykres pierwszeństwa - Precedence graph

Wykres pierwszeństwo , nazywane również wykres konflikt i serializability wykres , używany jest w kontekście kontroli współbieżności w bazach danych .

Wykres pierwszeństwa harmonogramu S zawiera:

• Węzeł dla każdej zatwierdzonej transakcji w S
• Łuk od T _i do T _j, jeśli akcja T _i poprzedza i koliduje z jedną z akcji T _j . Oznacza to, że akcje należą do różnych transakcji, co najmniej jedna z nich jest operacją zapisu, a akcje mają dostęp do tego samego obiektu (odczyt lub zapis).

Przykłady wykresów pierwszeństwa

Przykład 1

Przykład 2

${\ Displaystyle S = {\ zacząć {bmatrix} T1 i T2 \\ R (A) i R (A) \\ A = A * 5 i R (B) \\ W (A) i B = B + A \\ R (B) & W (B) \\ B = B * 10 & \\ W (B) & \\\ end {bmatrix}}}$

Przykład 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}$

Wykres pierwszeństwa harmonogramu D z 3 transakcjami. Ponieważ istnieje cykl (o długości 2; z dwoma krawędziami) przez zatwierdzone transakcje T1 i T2, ten harmonogram (historia) nie jest możliwy do serializacji w przypadku konfliktu . Zauważ, że zatwierdzenie Transakcji 2 nie ma żadnego znaczenia przy tworzeniu grafu pierwszeństwa.

Testowanie serializacji za pomocą wykresu pierwszeństwa

Przykład testowania możliwości serializacji

Algorytm do testowania konfliktu serializacji harmonogramu S wraz z przykładowym harmonogramem.

${\ Displaystyle S = {\ zacząć {bmatrix} T1 i T2 i T3 \\ R (A) && \\ & W (A) i \\ & Com. & \\ W (A) && \\ Com. && \\ && W (A) \ \ && Com. \\\ end {bmatrix}}}$

lub

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

1. Dla każdej transakcji T _x uczestniczącej w harmonogramie S utwórz węzeł oznaczony T _i na wykresie pierwszeństwa. Zatem wykres pierwszeństwa zawiera T ₁ , T ₂ , T ₃ .
2. Dla każdego przypadku w S, gdzie T _j wykonuje read_item (X) po tym, jak T _i wykonuje write_item (X), utwórz krawędź (T _i → T _j ) w grafie pierwszeństwa. To nie występuje nigdzie w powyższym przykładzie, ponieważ nie ma odczytu po zapisaniu.
3. Dla każdego przypadku w S, w którym T _j wykonuje element write_item (X) po wykonaniu przez T _i elementu read_item (X), utwórz krawędź (T _i → T _j ) w grafie pierwszeństwa. Powoduje to krawędź skierowana z T ₁ do T ₂ (jak T ₁ jest R (A) przed T ₂ o W (A) ).
4. Dla każdego przypadku w S, gdzie T _j wykonuje write_item (X) po tym, jak T _i wykonuje write_item (X), utwórz krawędź (T _i → T _j ) w grafie pierwszeństwa. To skutkuje z T skierowanych krawędziach ₂ do T ₁ , T ₂ do T ₃ i T ₁ do T ₃ .
5. Harmonogram S można serializować wtedy i tylko wtedy, gdy wykres pierwszeństwa nie ma cykli. Ponieważ T ₁ i T ₂ stanowią cykl, powyższy przykład nie jest możliwy do serializacji (konflikt).

Bibliografia

Zewnętrzne linki

• The Fundamentals of Database Systems, wydanie 5. Korzystanie z grafów pierwszeństwa jest omówione w rozdziale 17, ponieważ odnoszą się one do testów serializacji konfliktów .
• Abraham Silberschatz, Henry Korth i S. Sudarshan. 2005. Koncepcje systemów baz danych (wyd. 5), PP. 628–630. McGraw-Hill, Inc., Nowy Jork, NY, USA.