Schedule
Zunächst ist es nötig, eine Transaktion formal zu definieren. Im Folgenden wird unter einer Transaktion T eine Folge von read-, write-, commit- und abort-Aktionen verstanden, wobei die letzte Aktion einer Transaktion entweder commit oder abort sein muß.
Die einzelnen Aktionen werden durch ihre Anfangsbuchstaben abgekürzt, bei read- und write-Aktionen wird in Klammern auch das Datenobjekt angegeben, auf das sich die Aktion beziehen soll.
r(X) r(Y) w(X) c
ist eine Beispieltransaktion, die erst das Datum X und dann das Datum Y liest, danach X einen neuen Wert zuweist und dann erfolgreich beendet wird.
Wenn man voraussetzt, dass alle Aktionen in der Transaktion paarweise verschieden sind (jedes Datenelement wird nur ein mal gelesen oder geschrieben, nur entweder ein commit oder abort kommt vor), kann man anstatt von einer Folge von Aktionen zu sprechen auch annehmen, dass eine Ordnung zwischen den Aktionen vorliegt:
r(X) < r(Y) < w(X) < c.
Ein vollständiger Schedule (complete schedule) ist eine Folge von Aktionen mehrerer Transaktionen, wobei die Einschränkung gilt, dass die Aktionen einer Transaktion in der gleichen Reihenfolge im Schedule auftreten müssen wie in der Transaktion. Außerdem müssen alle Einzelaktionen aller beteiligten Transaktionen im Schedule enthalten sein.
Dieser Sachverhalt läßt sich ebenfalls mittels einer Ordnungsrelation ausdrücken. Dazu versieht man die Aktionen einer Transaktion mit einem numerischen Suffix, damit sie von den Aktionen anderer Transaktionen unterschieden werden können.
T1: r1(X) < r1(Y) < w1(X) < c1
T2: r2(X) < w2(X) < c2
Für einen vollständigen Schedule S muß gelten:
• S ist eine irreflexive Ordnungsrelation;
• dom(S) = dom(T1) + dom(T2) + ... + dom(Tn);
• für alle i und alle p,q aus dom(Ti): aus p < q in Ti folgt p < q in S.
Ein möglicher Schedule aus den oben genannten Beispieltransaktionen T1 und T2 ist
r1(X) < r2(X) < r1(Y) < w1(X) < w2(X) < c2 < c1.
Es ist möglich, einen vollständigen Schedule als partielle Ordnung zu definieren. Dann muß zusätzlich für alle p, q aus dom(S) gelten: Falls p und q in Konflikt stehen, dann ist entweder p < q oder p > q.
Zwei Aktionen stehen dann in Konflikt, wenn mindestens eine von ihnen eine write-Aktion ist und sich beide auf das gleiche Datenobjekt beziehen und beide aus verschiedenen Transaktionen stammen.
Schedules werden in verschiedene Klassen eingeteilt. Ein serieller Schedule führt die zu einer Transaktion gehörenden Schritte ohne Unterbrechung durch andere Transaktionen durch. Einer von zwei seriellen Schedules zu den Beispieltransaktionen T1 und T2 ist:
r1(X) < r1(Y) < w1(X) < c1 < r2(X) < w2(X) < c2.
Bei n Transaktionen existieren n! (n Fakultät) verschiedene serielle Schedules.
Ein Schedule heißt rücksetzbar (recoverable) wenn jede Transaktion erst dann commit ausführt, nachdem alle Transaktionen von denen sie gelesen hat commit ausgeführt haben.
Ein Schedule vermeidet kaskadierende Aborts (avoids cascading aborts), wenn jede Transaktion nur Werte liest, die von erfolgreich abgeschlossenen Transaktionen geschrieben wurden.
Ein Schedule heißt strikt (strict), wenn jede Transaktion nur Werte liest oder (über-)schreibt, die von erfolgreich abgeschlossenen Transaktionen geschrieben wurden.
Ein Schedule heißt serialisierbar (serializable), wenn er äquivalent zu einem oder mehreren seriellen Schedules ist.
Nun stellt sich die Frage, wann zwei Schedules äquivalent sind. Es gibt mindestens zwei verschiedene Definitionen: die Konflikt-Äquivalenz und die View-Äquivalenz.
Die einzelnen Aktionen werden durch ihre Anfangsbuchstaben abgekürzt, bei read- und write-Aktionen wird in Klammern auch das Datenobjekt angegeben, auf das sich die Aktion beziehen soll.
r(X) r(Y) w(X) c
ist eine Beispieltransaktion, die erst das Datum X und dann das Datum Y liest, danach X einen neuen Wert zuweist und dann erfolgreich beendet wird.
Wenn man voraussetzt, dass alle Aktionen in der Transaktion paarweise verschieden sind (jedes Datenelement wird nur ein mal gelesen oder geschrieben, nur entweder ein commit oder abort kommt vor), kann man anstatt von einer Folge von Aktionen zu sprechen auch annehmen, dass eine Ordnung zwischen den Aktionen vorliegt:
r(X) < r(Y) < w(X) < c.
Ein vollständiger Schedule (complete schedule) ist eine Folge von Aktionen mehrerer Transaktionen, wobei die Einschränkung gilt, dass die Aktionen einer Transaktion in der gleichen Reihenfolge im Schedule auftreten müssen wie in der Transaktion. Außerdem müssen alle Einzelaktionen aller beteiligten Transaktionen im Schedule enthalten sein.
Dieser Sachverhalt läßt sich ebenfalls mittels einer Ordnungsrelation ausdrücken. Dazu versieht man die Aktionen einer Transaktion mit einem numerischen Suffix, damit sie von den Aktionen anderer Transaktionen unterschieden werden können.
T1: r1(X) < r1(Y) < w1(X) < c1
T2: r2(X) < w2(X) < c2
Für einen vollständigen Schedule S muß gelten:
• S ist eine irreflexive Ordnungsrelation;
• dom(S) = dom(T1) + dom(T2) + ... + dom(Tn);
• für alle i und alle p,q aus dom(Ti): aus p < q in Ti folgt p < q in S.
Ein möglicher Schedule aus den oben genannten Beispieltransaktionen T1 und T2 ist
r1(X) < r2(X) < r1(Y) < w1(X) < w2(X) < c2 < c1.
Es ist möglich, einen vollständigen Schedule als partielle Ordnung zu definieren. Dann muß zusätzlich für alle p, q aus dom(S) gelten: Falls p und q in Konflikt stehen, dann ist entweder p < q oder p > q.
Zwei Aktionen stehen dann in Konflikt, wenn mindestens eine von ihnen eine write-Aktion ist und sich beide auf das gleiche Datenobjekt beziehen und beide aus verschiedenen Transaktionen stammen.
Schedules werden in verschiedene Klassen eingeteilt. Ein serieller Schedule führt die zu einer Transaktion gehörenden Schritte ohne Unterbrechung durch andere Transaktionen durch. Einer von zwei seriellen Schedules zu den Beispieltransaktionen T1 und T2 ist:
r1(X) < r1(Y) < w1(X) < c1 < r2(X) < w2(X) < c2.
Bei n Transaktionen existieren n! (n Fakultät) verschiedene serielle Schedules.
Ein Schedule heißt rücksetzbar (recoverable) wenn jede Transaktion erst dann commit ausführt, nachdem alle Transaktionen von denen sie gelesen hat commit ausgeführt haben.
Ein Schedule vermeidet kaskadierende Aborts (avoids cascading aborts), wenn jede Transaktion nur Werte liest, die von erfolgreich abgeschlossenen Transaktionen geschrieben wurden.
Ein Schedule heißt strikt (strict), wenn jede Transaktion nur Werte liest oder (über-)schreibt, die von erfolgreich abgeschlossenen Transaktionen geschrieben wurden.
Ein Schedule heißt serialisierbar (serializable), wenn er äquivalent zu einem oder mehreren seriellen Schedules ist.
Nun stellt sich die Frage, wann zwei Schedules äquivalent sind. Es gibt mindestens zwei verschiedene Definitionen: die Konflikt-Äquivalenz und die View-Äquivalenz.