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₁ und H₂ über der gleichen Menge von Transaktionen sind äquivalent (in Zeichen H₁ $\equiv$ H₂ ), wenn sie die Konfliktoperationen der nicht abgebrochenen Transaktionen in derselben Reihenfolge ausführen. D. h., für die durch H₁ und H₂ induzierten Ordnungen auf den Elementaroperationen < _H1 bzw. < _H2 wird verlangt: Wenn p_i und q_j Konfliktoperationen sind mit p_i < _H1q_j , dann muß auch p_i < _H2q_j gelten. Die Anordnung der nicht in Konflikt stehenden Operationen ist irrelevant.