Algorithmus zum Testen auf Serialisierbarkeit:

Input:

Eine Historie H für Transaktionen T₁,...,T_k .

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 p_i,q_j aus der Historie H mit p_i < _Hq_j fügen wir die Kante T_i $\rightarrow$ T_j 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 12.9 gezeigte Historie über den Transaktionen T₁,T₂,T₃ mit insgesamt 14 Operationen.

Schritt T₁ T₂ T₃

1. r₁ (A)

2. r₂ (B)

3. r₂ (C)

4. w₂ (B)

5. r₁ (B)

6. w₁ (A)

7. r₂ (A)

8. w₂ (C)

9. w₂ (A)

10. r₃ (A)

11. r₃ (C)

12. w₁ (B)

13. w₃ (C)

14. w₃ (A)

Tabelle 12.9: Historie H mit drei Transaktionen

Folgende Konfliktoperationen existieren für Historie H:

w₂(B) < r₁(B),

w₁(A) < r₂(A),

w₂(C) < r₃(C),

w₂(A) < r₃(A).

Daraus ergeben sich die Kanten

T₂ $$\rightarrow$$ T₁,

T₁ $$\rightarrow$$ T₂,

T₂ $$\rightarrow$$ T₃,

T₂ $$\rightarrow$$ T₃.

Den resultierenden Graph zeigt Abbildung 12.2

Der zu Historie H konstruierte Serialisierbarkeitsgraph

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