Theorie der Serialisierbarkeit

Eine $Transaktion$ $T_i$ besteht aus folgenden elementaren Operationen:

• $r_i$(A) zum Lesen von Datenobjekt A,
• $w_i$(A) zum Schreiben von Datenobjekt A,
• $a_i$ zur Durchführung eines abort,
• $c_i$ zur Durchführung eines commit.

Eine Transaktion kann nur eine der beiden Operationen abort oder commit durchführen; diese müssen jeweils am Ende der Transaktion stehen. Implizit wird ein BOT vor der ersten Operation angenommen. Wir nehmen für die Transaktion eine feste Reihenfolge der Elementaroperationen an.

Eine $Historie$, auch genannt $Schedule$, ist eine Festlegung der Reihenfolge für sämtliche beteiligten Einzeloperationen.

Gegeben Transaktionen $T_i$ und $T_j$, beide mit Zugriff auf Datum A. Folgende vier Fälle sind möglich:

• $r_i$(A) und $r_j$(A) : kein Konflikt, da Reihenfolge unerheblich
• $r_i$(A) und $w_j$(A) : Konflikt, da Reihenfolge entscheidend
• $w_i$(A) und $r_j$(A) : Konflikt, da Reihenfolge entscheidend
• $w_i$(A) und $w_j$(A) : Konflikt, da Reihenfolge entscheidend

Von besonderem Interesse sind die $Konfliktoperationen$.

Zwei Historien $H_1$ und $H_2$ über der gleichen Menge von Transaktionen sind äquivalent (in Zeichen $H_1 \equiv H_2$), wenn sie die Konfliktoperationen der nicht abgebrochenen Transaktionen in derselben Reihenfolge ausführen. D. h., für die durch $H_1$ und $H_2$ induzierten Ordnungen auf den Elementaroperationen $\/<_{H_1}$ bzw. $\/<_{H_2}$ wird verlangt: Wenn $p_i$ und $q_j$ Konfliktoperationen sind mit $p_i <_{H_1} q_j$, dann muß auch $p_i <_{H_2} q_j$ gelten. Die Anordnung der nicht in Konflikt stehenden Operationen ist irrelevant.