Serialisierbarkeit

Eine $Historie$, auch genannt $Schedule$, für eine Menge von Transaktionen ist eine Festlegung für die Reihenfolge sämtlicher relevanter Datenbankoperationen. Ein Schedule heißt $seriell$, wenn alle Schritte einer Transaktion unmittelbar hintereinander ablaufen. Wir unterscheiden nur noch zwischen $read$- und $write$-Operationen.

Zum Beispiel transferiere $T_1$ einen bestimmten Betrag von A nach B und $T_2$ transferiere einen Betrag von C nach A. Eine mögliche Historie zeigt Tabelle 13.4.

Schritt	$T_1$	$T_2$
1.	BOT
2.	read($A$)
3.		BOT
4.		read($C$)
5.	write($A$)
6.		write($C$)
7.	read($B$)
8.	write($B$)
9.	commit
10.		read($A$)
11.		write($A$)
12.		commit

Tabelle 13.4: Serialisierbare Historie

Offenbar wird derselbe Effekt verursacht, als wenn zunächst $T_1$ und dann $T_2$ ausgeführt worden wäre, wie Tabelle 13.5 demonstriert.

Schritt	$T_1$	$T_2$
1.	BOT
2.	read($A$)
3.	write($A$)
4.	read($B$)
5.	write($B$)
6.	commit
7.		BOT
8.		read($C$)
9.		write($C$)
10.		read($A$)
11.		write($A$)
12.		commit

Tabelle 13.5: Serielle Historie

Wir nennen deshalb das (verzahnte) Schedule $serialisierbar$.

Tabelle 13.6 zeigt ein Schedule der Transaktionen $T_1$ und $T_3$, welches nicht serialisierbar ist.

Schritt	$T_1$	$T_3$
1.	BOT
2.	read($A$)
3.	write($A$)
4.		BOT
5.		read($A$)
6.		write($A$)
7.		read($B$)
8.		write($B$)
9.		commit
10.	read($B$)
11.	write($B$)
12.	commit

Tabelle 13.6: Nicht-serialisierbares Schedule

Der Grund liegt darin, daß bzgl. Datenobjekt A die Transaktion $T_1$ vor $T_3$ kommt, bzgl. Datenobjekt B die Transaktion $T_3$ vor $T_1$ kommt. Dies ist nicht äquivalent zu einer der beiden möglichen seriellen Ausführungen $T_1 T_3$ oder $T_3 T_1$.

Im Einzelfall kann die konkrete Anwendungssemantik zu einem äquivalenten seriellen Schedule führen, wie Tabelle 13.7 zeigt.

Schritt	$T_1$	$T_3$
1.	BOT
2.	read($A, a_1$)
3.	$a_1 := a_1 - 50$
4.	write($A, a_1$)
5.		BOT
6.		read($A, a_2$)
7.		$a_2 := a_2 - 100$
8.		write($A, a_2$)
9.		read($B, b_2$)
10.		$b_2 := b_2 + 100$
11.		write($B, b_2$)
12.		commit
13.	read($B, b_1$)
14.	$b_1 := b_1 + 50$
15.	write($B, b_1$)
16.	commit

Tabelle 13.7: Zwei verzahnte Überweisungen

In beiden Fällen wird Konto A mit 150,- Euro belastet und Konto B werden 150,- Euro gutgeschrieben.

Unter einer anderen Semantik würde $T_1$ einen Betrag von 50,- Euro von A nach B überweisen und Transaktion $T_2$ würde beiden Konten jeweils 3 % Zinsen gutschreiben. Tabelle 13.8 zeigt den Ablauf.

Schritt	$T_1$	$T_3$
1.	BOT
2.	read($A, a_1$)
3.	$a_1 := a_1 - 50$
4.	write($A, a_1$)
5.		BOT
6.		read($A, a_2$)
7.		$a_2 := a_2 * 1.03$
8.		write($A, a_2$)
9.		read($B, b_2$)
10.		$b_2 := b_2 * 1.03$
11.		write($B, b_2$)
12.		commit
13.	read($B, b_1$)
14.	$b_1 := b_1 + 50$
15.	write($B, b_1$)
16.	commit

Tabelle 13.8: Überweisung verzahnt mit Zinsgutschrift

Offenbar entspricht diese Reihenfolge keiner möglichen seriellen Abarbeitung $T_1 T_3$ oder $T_3 T_1$, denn es fehlen in jedem Falle Zinsen in Höhe von 3 % von 50,- Euro = 1,50 Euro.