Historie (Transaktionsverarbeitung)

Als Historie (der einem vollständigen Schedule entspricht, siehe Abschnitt Schedule und Schuffleprodukt) bezeichnet man in der Informatik im Bereich der Datenbanktheorie einen Ausführungsplan für die parallele Ausführung mehrerer Transaktionen (siehe auch Transaktionssystem), welcher angibt, in welcher Reihenfolge die Transaktionsoperationen ausgeführt werden. Zu den möglichen Arten von Transaktionsoperationen gehören Lese- und Schreiboperationen, und die Terminierungsoperationen Commit (erfolgreicher Abschluss der Transaktion) und Abort (Abbruch der Transaktion). Die Historie ist also eine Bezeichnung für die Ausführungsreihenfolge aller Operationen der parallel ausgeführten Transaktionen.

Schedule und Schuffleprodukt

Im Zusammenhang mit Historie sollte auch der Begriff Schedule genannt werden. Ein Schedule ist ein sogenanntes Präfix einer Historie. Präfix heißt in diesem Zusammenhang, das erste bis n-te Element der Historie. Ein vollständiger Schedule entspricht demnach einer Historie. Ein (formales) Beispiel für einen Schedule wäre:

Gegeben seien folgende Elemente:

x, y, z: Datenobjekte in einer Datenbank

Ti: eine von n parallel ausgeführten Transaktion

Ri(x): Leseoperation der Transaktion i auf dem Objekt X

Wi(x): Schreiboperation der Transaktion i auf dem Objekt X

Ci: Commit-Operation der Transaktion i (erfolgreicher Abschluss der Transaktion)

Ai: Abort-Operation der Transaktion i (Abbruch der Transaktion)

Hi: eine von i möglichen Historien für T1 bis Tn

Si(Hi): ein Schedule der Historie Hi

Für die parallele Ausführung von 3 Transaktionen (T1, T2, T3), sieht eine der möglichen Historien (H1), mit Ihren Schreiboperationen (Wi()) und Leseoperationen (Ri()) auf den Objekten (x, y, z) sowie den dazugehörigen Commitoperationen (Ci) und Abbruchopperationen (Ai), wie folgt aus:

Historie H1 = R1(x), R1(y), R2(x), R2(y), W2(x), R3(y), A3, W2(y), C2, W1(x), C1

Ein möglicher Schedule (S1), in diesem Fall der vollständige Schedule, für diese Historie wäre dann:

Schedule S1(H1) = R1(x), R1(y), R2(x), R2(y), W2(x), R3(y), A3, W2(y), C2, W1(x), C1

Ein weiterer möglicher Schedule (S2) (unvollständig) für diese Historie wäre:

Schedule S2(H1) = R1(x), R1(y), R2(x), R2(y), W2(x), R3(y), A3, W2(y), C2

Noch ein weiterer möglicher Schedule (S3) (unvollständig) für diese Historie wäre:

Schedule S3(H1) = R1(x), R1(y), R2(x), R2(y), W2(x), R3(y), A3

Für die Parallele Ausführung der drei Transaktionen gibt es natürlich noch weitere Historien, z.B. wenn wir die beiden Operationen der dritten Transaktion einfach nach hinten stellen:

Historie H2 = R1(x), R1(y), R2(x), R2(y), W2(x), W2(y), C2, W1(x), C1, R3(y), A3

Die Menge aller möglichen Kombinationen der Lese- und Schreiboperationen, allerdings ohne die Commit- und Abbruchoperationen, nennt man Shuffleprodukt. Nehmen wir unsere zweite Historie (H2) als Grundlage, dann würde das Element (s2) aus der Menge der Schuffleprodukte (S) lauten:

s2 = R1(x), R1(y), R2(x), R2(y), W2(x), W2(y), W1(x), R3(y)

Bei genauer Betrachtung erkennt man, das die Kombination der Lese- und Schreiboperationen gleich bleibt, aber die Commit- und Abbruchoperationen entfernt wurden.

Serielle und nicht/serialisierbare Historien, Korrekheitskriterium "Serialisierbarkeit"

Neben der Darstellung von bestimmten Ausführungsreihenfolge der Operationen, dienen Historien zur Definition (und sind Grundlage zur Prüfung) der Serialisierbarkeit dieser Ausführungsfolgen.

Man stelle sich folgende Transaktionen auf einem Konto vor:

1. T₁: Hebe 100,- € von Konto Nr. 777980 ab.
2. T₂: Zahle 52,- € auf Konto Nr. 777980 ein.

T1 umfasst eine Leseoperation zum Einlesen des Kontostands und eine Schreiboperation zur Modifikation des Kontostands. Das gleiche gilt für T2. Insgesamt sind für diese beiden Transaktionen also vier Operationen auszuführen. Eine Historie legt nun die Reihenfolge fest, in der diese Operationen abgearbeitet werden. Die naheliegendste Lösung wäre die Ausführung der Transaktionen nacheinander („seriell“), also beispielsweise zunächst alle Operationen von T1 und danach alle Operationen von T2. Eine solche Historie bezeichnet man als serielle Historie.

Ein Problem entsteht, wenn die serielle Ausführung von Transaktionen ineffizient ist. Wenn etwa eine ganze Reihe von Transaktionen warten muss, weil die erste Transaktion gerade auf eine Benutzereingabe wartet. In einigen Fällen ist die strikte Hintereinanderausführung aber gar nicht notwendig, z.B. wenn die Transaktionen auf ganz verschiedenen Datenobjekten arbeiten, oder nur Leseoperationen durchführen. In diesem Fall erhalten wir eine geringe Transkationsdurchsatzrate (abgeschlossene Transaktionen pro Zeiteinheit). Um den Transaktionsdurchsatz zu erhöhen, werden in Transaktionssystemen auch Historien zugelassen, bei denen gleichzeitig mehrere Transaktionen sogenannt "aktiv" sind. Aktiv bedeutet, dass eine Transaktion T1 kann mit der Ausführung beginnen bevor die laufenden Transaktionen abgeschlossen sind, und es können bereits Operationen nachfolgender Transaktionen durchgeführt werden bevor T1 abgeschlossen ist. Korrekt ist eine solche nebenläufige Historie wenn sie die gleichen Ergebnisse liefert wie eine serielle Historie.

Formal läßt sich so ein Korrektheitskriterium Serialisierbarkeit für die nebenläufige Ausführung von Transaktionen definieren: Eine Historie H ist dann serialisierbar, wenn sie äquivalent zu einer seriellen Historie H' ist. Die Reihenfolge der Transaktionen in H' nennt man dann Serialisierungsreihenfolge. Wichtig ist dabei, dass die relative Reihenfolge konfligierender Operationen (z.B. zwei Schreiboperationen) in der Historie H der Serialisierungsreihenfolge der zugehörigen Transaktionen entspricht. Konfligierende Operation bedeutet, dass zwei Operationen verschiedener Transaktionen auf das gleiche Datenobjekt zugreifen und mindestens eine der beteiligten Operationen eine Schreiboperation ist.

Total und partial geordnete Historien

Da für manche Operationen die Reihenfolge keine Rolle spielt, definieren Historien i.A. keine totale Ordnung auf allen Operationen, sondern nur eine partielle Ordnung, die in erster Linie die relative Reihenfolge konfligierender Operationen festlegt. Solche partiellen Ordnungen können mit Hilfe eines gerichteten Graphen dargestellt werden:

$\begin{matrix} r_{1}[x] & \rightarrow & w_{1}[x] & & r_{1}[x] & \rightarrow & c_{1} & \rightarrow & c_{2} \\ & & \downarrow & \nearrow \\ r_{2}[y] & \rightarrow & w_{2}[x] \end{matrix}$

In der hier dargestellten Historie wird eine Leseoperation der Transaktion T1 auf einem Objekt x als r₁[x] notiert, während eine Schreiboperation von T1 auf x als w₁[x] notiert wird. Die Pfeile geben die relative Reihenfolge konfligierender Operationen an. Die hier dargestellte Historie ist nicht serialisierbar.

Literatur

• Alfons Kemper, André Eickler: Datenbanksysteme. Oldenbourg, 2004, ISBN 3-486-25706-4.
• Theo Härder, Erhard Rahm: Datenbanksysteme, Konzepte und Techniken der Implementierung. Springer, Berlin 2001, ISBN 3-540-42133-5.