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₁ einen bestimmten Betrag von A nach B und T₂ transferiere einen Betrag von C nach A. Eine mögliche Historie zeigt Tabelle 13.4.

Schritt	T1	T2
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₁ und dann T₂ ausgeführt worden wäre, wie Tabelle 13.5 demonstriert.

Schritt	T1	T2
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₁ und T₃, welches nicht serialisierbar ist.

Schritt	T1	T3
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₁ vor T₃ kommt, bzgl. Datenobjekt B die Transaktion T₃ vor T₁ kommt. Dies ist nicht äquivalent zu einer der beiden möglichen seriellen Ausführungen T₁T₃ oder T₃T₁.

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

Schritt	T1	T3
1.	BOT
2.	read(A, a1)
3.	a1 : = a1 - 50
4.	write(A, a1)
5.		BOT
6.		read(A, a2)
7.		a2 : = a2 - 100
8.		write(A, a2)
9.		read(B, b2)
10.		b2 : = b2 + 100
11.		write(B, b2)
12.		commit
13.	read(B, b1)
14.	b1 : = b1 + 50
15.	write(B, b1)
16.	commit

Tabelle 13.7: Zwei verzahnte Überweisungen

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

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

Schritt	T1	T3
1.	BOT
2.	read(A, a1)
3.	a1 : = a1 - 50
4.	write(A, a1)
5.		BOT
6.		read(A, a2)
7.		a2 : = a2*1.03
8.		write(A, a2)
9.		read(B, b2)
10.		b2 : = b2*1.03
11.		write(B, b2)
12.		commit
13.	read(B, b1)
14.	b1 : = b1 + 50
15.	write(B, b1)
16.	commit

Tabelle 13.8: Überweisung verzahnt mit Zinsgutschrift

Offenbar entspricht diese Reihenfolge keiner möglichen seriellen Abarbeitung T₁T₃ oder T₃T₁, denn es fehlen in jedem Falle Zinsen in Höhe von 3 % von 50,- DM = 1,50 DM.