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₁ 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.