Algorithmus zum Testen auf Serialisierbarkeit:

Input:

Eine Historie H für Transaktionen $T_1, \dots, 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 \/<_H q_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_1, T_2, T_3$ mit insgesamt 14 Operationen.

Schritt	$T_1$	$T_2$	$T_3$
1.	$r_1$(A)
2.		$r_2$(B)
3.		$r_2$(C)
4.		$w_2$(B)
5.	$r_1$(B)
6.	$w_1$(A)
7.		$r_2$(A)
8.		$w_2$(C)
9.		$w_2$(A)
10.			$r_3$(A)
11.			$r_3$(C)
12.	$w_1$(B)
13.			$w_3$(C)
14.			$w_3$(A)

Tabelle 13.9: Historie H mit drei Transaktionen

Folgende Konfliktoperationen existieren für Historie H:

$$w_2(B) \/< r_1(B),$$

$$w_1(A) \/< r_2(A),$$

$$w_2(C) \/< r_3(C),$$

$$w_2(A) \/< r_3(A).$$

Daraus ergeben sich die Kanten

$$T_2 \rightarrow T_1,$$

$$T_1 \rightarrow T_2,$$

$$T_2 \rightarrow T_3,$$

$$T_2 \rightarrow T_3.$$

Den resultierenden Graph zeigt Abbildung 13.2

Abbildung 13.2: Der zu Historie H konstruierte Serialisierbarkeitsgraph

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