Historie (Transaktionsverarbeitung)

Als Historie bezeichnet man in der Informatik im Zusammenhang mit Transaktionssystemen einen Ausführungsplan für die gemeinsame Ausführung mehrerer Transaktionen, welcher angibt, in welcher Reihenfolge die zugehörigen Operationen ausgeführt werden.

Sinn und Zweck von Historien

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.

Die serielle Ausführung von Transaktionen kann ineffizient sein, etwa wenn eine ganze Reihe von Transaktionen warten muss, weil die erste Transaktion gerade auf eine Benutzereingabe wartet. Dabei wäre die strikte Hintereinanderausführung gar nicht notwendig, wenn die Transaktionen beispielsweise auf ganz verschiedenen Daten arbeiten, oder nur Leseoperationen durchführen. Um den Transaktionsdurchsatz zu erhöhen, werden deswegen in Transaktionssystemen auch Historien zugelassen, bei denen gleichzeitig mehrere Transaktionen aktiv sind. Das bedeutet: 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. Dieses Korrektheitskriterium für die nebenläufige Ausführung von Transaktionen wird auch Serialisierbarkeit genannt. 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 in der Historie H der Serialisierungsreihenfolge der zugehörigen Transaktionen entspricht. Zwei Operationen verschiedener Transaktionen konfligieren dann, wenn sie das gleiche Datenobjekt betreffen und mindestens eine der beteiligten Operationen eine Schreiboperation ist.

Darstellung von 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.