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 13.9 gezeigte Historie über den Transaktionen T₁, T₂, T₃ 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:

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 13.2

Der zu Historie H konstruierte Serialisierbarkeitsgraph

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