prev up next


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 T1 einen bestimmten Betrag von A nach B und T2 transferiere einen Betrag von C nach A. Eine mögliche Historie zeigt Tabelle 12.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 12.4: Serialisierbare Historie
Offenbar wird derselbe Effekt verursacht, als wenn zunächst T1 und dann T2 ausgeführt worden wäre, wie Tabelle 12.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 12.5: Serielle Historie
Wir nennen deshalb das (verzahnte) Schedule serialisierbar .

Tabelle 12.6 zeigt ein Schedule der Transaktionen T1 und T3 , 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 12.6: Nicht-serialisierbares Schedule
Der Grund liegt darin, daß bzgl. Datenobjekt A die Transaktion T1 vor T3 kommt, bzgl. Datenobjekt B die Transaktion T3 vor T1 kommt. Dies ist nicht äquivalent zu einer der beiden möglichen seriellen Ausführungen T1T3 oder T3T1 .

Im Einzelfall kann die konkrete Anwendungssemantik zu einem äquivalenten seriellen Schedule führen, wie Tabelle 12.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 12.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 T1 einen Betrag von 50,- DM von A nach B überweisen und Transaktion T2 würde beiden Konten jeweils 3 % Zinsen gutschreiben. Tabelle 12.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 12.8: Überweisung verzahnt mit Zinsgutschrift
Offenbar entspricht diese Reihenfolge keiner möglichen seriellen Abarbeitung T1T3 oder T3T1 , denn es fehlen in jedem Falle Zinsen in Höhe von 3 % von 50,- DM = 1,50 DM.


prev up next