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 12.4.

Schritt T₁ T₂

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

Schritt T₁ T₂

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

Schritt T₁ T₃

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 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 12.7 zeigt.

Schritt T₁ T₃

1. BOT

2. read( A,a₁ )

3. a₁ : = a₁ - 50

4. write( A,a₁ )

5. BOT

6. read( A,a₂ )

7. a₂ : = a₂ - 100

8. write( A,a₂ )

9. read( B,b₂ )

10. b₂ : = b₂ + 100

11. write( B,b₂ )

12. commit

13. read( B,b₁ )

14. b₁ : = b₁ + 50

15. write( B,b₁ )

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 T₁ einen Betrag von 50,- DM von A nach B überweisen und Transaktion T₂ würde beiden Konten jeweils 3 % Zinsen gutschreiben. Tabelle 12.8 zeigt den Ablauf.

Schritt T₁ T₃

1. BOT

2. read( A,a₁ )

3. a₁ : = a₁ - 50

4. write( A,a₁ )

5. BOT

6. read( A,a₂ )

7. a₂ : = a₂*1.03

8. write( A,a₂ )

9. read( B,b₂ )

10. b₂ : = b₂*1.03

11. write( B,b₂ )

12. commit

13. read( B,b₁ )

14. b₁ : = b₁ + 50

15. write( B,b₁ )

16. commit

Tabelle 12.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.