Historie (Informatik)
aus Wikipedia, der freien Enzyklopädie
Als Historie bezeichnet man in der Informatik im Zusammenhang mit Transaktionssystemen einen Ausführungsplan für die gemeinsame Ausführung mehrerer Transaktionen.
[Bearbeiten] Sinn und Zweck von Historien
Man stelle sich folgende Transaktionen auf einem Konto vor:
- T1: Hebe 100,- € von Konto Nr. 777980 ab.
- T2: Zahle 52,- € auf Konto Nr. 777980 ein.
Eine Historie legt nun den Ablaufplan fest, nachdem diese Transaktionen abgearbeitet werden. Die naheliegendste Lösung wäre die Ausführung der Transaktionen nacheinander („seriell“), also nach dem Plan einer der folgenden beiden Historien:
- H1: T1T2
- H2: T2T1
Die Reihenfolge der Ausführung ist dabei oft essentiell. Falls etwa das Guthaben des Kontos Nr. 777980 nur noch 74,- € beträgt und das Konto nicht überzogen werden darf, so wäre die Historie H1 nicht zulässig.
Die serielle Ausführung von Transaktionen kann ineffizient sein, etwa wenn eine ganze Reihe von Transaktionen warten muss, weil die erste Transaktion in der Warteschlange gerade auf eine Benutzereingabe wartet. Daher erhöht eine gute Historie die Nebenläufigkeit - das heißt die Abwicklung mehrerer Transaktionen nebeneinander her - so weit wie möglich. Dazu werden statt ganzer Transaktionen deren einzelne Operationen betrachtet:
- T1: r1[x]w1[x]c1
- T2: r2[x]w2[x]c2
Es resultieren dann Historien wie zum Beispiel die Folgende:
![\begin{matrix} r_{1}[x] & \rightarrow & w_{1}[x] & \rightarrow & c_{1} & \rightarrow & c_{2} \\ & & \uparrow \\ r_{2}[x] & \rightarrow & w_{2}[x] \end{matrix}](../../../math/b/d/4/bd48081b0b538d2eb5c922060c9eb3d6.png)
Das Korrektheitskriterium für die nebenläufige Ausführung von Transaktionen ist die Serialisierbarkeit der zugehörigen Historie. 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 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.
[Bearbeiten] Darstellung von Historien
Historien werden meist als gerichtete Graphen dargestellt:
![\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}](../../../math/d/1/6/d16e90e3966e23c3c883f01234b5bf29.png)
Ist keine Nebenläufigkeit vorhanden, kann auch die einfachere Darstellung als Folge gewählt werden:
[Bearbeiten] Serielle Historien
Eine serielle Historie ist eine solche, die eine Transaktion nach der anderen („seriell“) ausführt.
Beispiel:
- T1, T2 und T3 sind Transaktionen. Es gibt sechs mögliche serielle Historien: T1T2T3, T1T3T2, T2T1T3, T2T3T1, T3T1T2 und T3T2T1
