prev up next

Algorithmus zum Testen auf Serialisierbarkeit:

Input:
Eine Historie H für Transaktionen T1,..., Tk.
Output:
entweder: ,,nein, ist nicht serialisierbar`` oder ,,ja, ist serialisierbar`` + serielles Schedule
Idee:
Bilde gerichteten Graph G, dessen Knoten den Transaktionen entsprechen. Für zwei Konfliktoperationen pi, qj aus der Historie H mit pi < Hqj fügen wir die Kante Ti $ \rightarrow$ Tj in den Graph ein.
Es gilt das Serialisierbarkeitstheorem:
Eine Historie H ist genau dann serialisierbar, wenn der zugehörige Serialisierbarkeitsgraph azyklisch ist. Im Falle der Kreisfreiheit läßt sich die äquivalente serielle Historie aus der topologischen Sortierung des Serialisierbarkeitsgraphen bestimmen.

Als Beispiel-Input für diesen Algorithmus verwenden wir die in Tabelle 13.9 gezeigte Historie über den Transaktionen T1, T2, T3 mit insgesamt 14 Operationen.

Schritt T1 T2 T3
1. r1(A)    
2.   r2(B)  
3.   r2(C)  
4.   w2(B)  
5. r1(B)    
6. w1(A)    
7.   r2(A)  
8.   w2(C)  
9.   w2(A)  
10.     r3(A)
11.     r3(C)
12. w1(B)    
13.     w3(C)
14.     w3(A)
Tabelle 13.9: Historie H mit drei Transaktionen
Folgende Konfliktoperationen existieren für Historie H:

w2(B) < r1(B),

w1(A) < r2(A),

w2(C) < r3(C),

w2(A) < r3(A).

Daraus ergeben sich die Kanten

T2 $\displaystyle \rightarrow$ T1,

T1 $\displaystyle \rightarrow$ T2,

T2 $\displaystyle \rightarrow$ T3,

T2 $\displaystyle \rightarrow$ T3.

Den resultierenden Graph zeigt Abbildung 13.2


Der zu Historie H konstruierte Serialisierbarkeitsgraph

Da der konstruierte Graph einen Kreis besitzt, ist die Historie nicht serialisierbar.


prev up next