Eine Historie ist eine sequenzielle Anordnung aller Aktionen (read, write, commit, abort) von einer oder mehreren Transaktionen. Sie enthält alle Aktionen jeder beteiligten Transaktion, wobei die Reihenfolge innerhalb einer Transaktion erhalten bleibt. Aktionen verschiedener Transaktionen können verzahnt (interleaved) sein.
Transaktionen werden strikt hintereinander ausgeführt: erst T1 komplett, dann T2, dann T3. Keine Verzahnung. Immer korrekt, aber schlecht für die Performance. Seriell dient als Referenzmodell für die Korrektheit paralleler Ausführungen.
Eine Historie H ist serialisierbar, wenn sie zu einer seriellen Historie äquivalent ist, also das gleiche Endergebnis in der Datenbank liefert. Ziel des DBMS: verzahnte Ausführung erlauben, aber nur wenn Serialisierbarkeit gewährleistet ist. Korrekt = serialisierbar.
Zwei Operationen stehen in Konflikt, wenn sie dasselbe Datenobjekt betreffen UND mindestens eine ein write ist. Konfliktarten: r/w, w/r, w/w. read/read ist KEIN Konflikt. Das write allein macht den Konflikt aus.
Zwei Historien sind konfliktäquivalent, wenn sie die Konfliktoperationen der nicht-abgebrochenen Transaktionen in derselben Reihenfolge ausführen. Nicht-konfligierende Operationen dürfen umsortiert werden.
Eine Historie H ist konfliktserialisierbar, wenn sie konfliktäquivalent zu einer seriellen Historie ist. Man kann die verzahnte Historie durch Vertauschen unabhängiger Operationen in eine serielle Form überführen. Strenger als Ergebnis-Äquivalenz, aber effizient testbar.
Gerichteter Graph. Knoten sind die Transaktionen T1, ..., Tn. Für jedes Konfliktpaar p_i(X) vor q_j(X) mit i != j wird eine Kante T_i -> T_j eingezeichnet. Verdichtet die Konfliktbeziehung auf Transaktionsebene.
Eine Historie H ist konfliktserialisierbar genau dann, wenn ihr Serialisierbarkeitsgraph SG(H) azyklisch ist. Ein Zyklus bedeutet widersprüchliche Reihenfolgeanforderungen. Topologische Sortierung des azyklischen Graphen liefert die äquivalente serielle Reihenfolge.
Zwei Transaktionen T1 und T2 arbeiten verzahnt auf Datenobjekten A, B, C. T1 nutzt A und B, T2 nutzt C und A. Da T1 und T2 nur bei A auf dasselbe Objekt zugreifen und die Reihenfolge dort korrekt ist (T1 schreibt A vor T2), ist die verzahnte Historie äquivalent zur seriellen Historie T1 vor T2.
Verzahnt: BOT1 r1(A) BOT2 r2(C) w1(A) w2(C) r1(B) w1(B) c1 r2(A) w2(A) c2 Aequivalente serielle Historie: T1 -> T2 T1: r1(A) w1(A) r1(B) w1(B) c1 T2: r2(C) w2(C) r2(A) w2(A) c2 Ergebnis identisch = serialisierbar.
T1 schreibt A und liest später B. T3 startet zwischen w1(A) und liest sofort das noch nicht commitete A. Es gibt keine äquivalente serielle Historie, weil sowohl w1(A) vor r3(A) als auch später ein Konflikt zurück zu T1 entstehen würde. Konfliktgraph wäre zyklisch.
Schritt T1 T3 1 BOT 2 read(A) 3 write(A) <--- 4 BOT 5 read(A) <- Konflikt: T1 -> T3 6 write(A) 7 read(B) 8 write(B) 9 commit 10 read(B) <- Konflikt: T3 -> T1 (Zyklus) 11 write(B) 12 commit => Nicht serialisierbar
T1 ist eine Überweisung von 50 (A-50, B+50), T2 eine Zinsgutschrift (A*1.03, B*1.03). Verzahnte Ausführung ergibt Konto A = (A-50)*1.03, Konto B = B*1.03+50. Äquivalente serielle Historie T1 vor T2 ergibt (A-50)*1.03 und (B+50)*1.03 = anderes Ergebnis. Aber: das DBMS wertet Rechenoperationen NICHT aus, sondern nur read/write-Konflikte. Deshalb kann die Historie trotzdem konfliktserialisierbar sein.
Merksatz: DBMS betrachtet nur read/write-Zugriffe auf gleiche Objekte, nicht die semantische Berechnung. Serialisierbarkeit ist eine konservative Approximation.
Für jede Transaktion T_i wird ein Knoten gezeichnet. Für jedes Paar konfliktierender Operationen p_i(X) vor q_j(X) mit i != j und mindestens einer Schreiboperation wird eine Kante T_i -> T_j eingefügt. Ist der Graph azyklisch, so ist die Historie konfliktserialisierbar.
Historie H: w1(A) -> r3(A) und w1(A) -> r2(A) und r2(A) -> w3(A) usw. Kanten: T1 -> T3 (wegen w1(A) vor r3(A)), T1 -> T2, T2 -> T3 SG(H) = Knoten T1, T2, T3 mit Pfeilen T1->T2, T1->T3, T2->T3 => Azyklisch => serialisierbar. Serielle Reihenfolge: T1, T2, T3.