prev up next

Theorie der Serialisierbarkeit

Eine Transaktion Ti besteht aus folgenden elementaren Operationen:

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 Ti und Tj, beide mit Zugriff auf Datum A. Folgende vier Fälle sind möglich:

Von besonderem Interesse sind die Konfliktoperationen.

Zwei Historien H1 und H2 über der gleichen Menge von Transaktionen sind äquivalent (in Zeichen H1 H2), wenn sie die Konfliktoperationen der nicht abgebrochenen Transaktionen in derselben Reihenfolge ausführen. D. h., für die durch H1 und H2 induzierten Ordnungen auf den Elementaroperationen < H1 bzw. < H2 wird verlangt: Wenn pi und qj Konfliktoperationen sind mit pi < H1qj, dann muß auch pi < H2qj gelten. Die Anordnung der nicht in Konflikt stehenden Operationen ist irrelevant.


prev up next