Konfliktäquivalenz

Konfliktäquivalent sind in der Informatik im Zusammenhang mit Transaktionssystemen zwei Historien, die konfliktäre Operationen in der gleichen Reihenfolge anordnen.

Anschauliches Beispiel

Um sich die wichtigsten Begriffe dieses Artikels anschaulich vorstellen zu können, soll folgendes Beispiel dienen:

In einer Bücherei wird ein Karteikarten-System zur Verwaltung des Bestandes an Büchern verwendet. Hierbei könnte folgende Historie entstehen:

1. Lies das Feld „Autor“ der Karte „Die Schatzinsel“

2. Lies das Feld „Erscheinungsjahr“ der Karte „Der Graf von Monte Christo“

3. Schreibe „Robert Louis Stevenson“ in das Feld „Autor“ der Karte „Die Schatzinsel“

Die Operationen 1 und 3 sind konfliktär, denn ihre Reihenfolge kann nicht vertauscht werden, ohne das Ergebnis zu verändern. Eine zweite Historie aus den gleichen Operationen - nur in anderer Reihenfolge - könnte so aussehen:

1. Lies das Feld „Erscheinungsjahr“ der Karte „Der Graf von Monte Christo“

2. Lies das Feld „Autor“ der Karte „Die Schatzinsel“

3. Schreibe „Robert Louis Stevenson“ in das Feld „Autor“ der Karte „Die Schatzinsel“

Diese beiden Historien sind konfliktäquivalent, denn die konfliktären Operationen „Lies das Feld „Autor“ der Karte „Die Schatzinsel““ und „Schreibe „Robert Louis Stevenson“ in das Feld „Autor“ der Karte „Die Schatzinsel““ werden in beiden Historien in derselben Reihenfolge abgearbeitet. Nicht konfliktäquivalent zu diesen beiden Historien wäre eine Historie wie die folgende:

1. Lies das Feld „Erscheinungsjahr“ der Karte „Der Graf von Monte Christo“

2. Schreibe „Robert Louis Stevenson“ in das Feld „Autor“ der Karte „Die Schatzinsel“

3. Lies das Feld „Autor“ der Karte „Die Schatzinsel“

Mathematische Definition

In Formeln:

Sei H eine Historie über der Menge von Transaktionen T, die die Menge der Operationen O umfasst, H' eine Historie über der Menge von Transaktionen T', die die Menge der Operationen O' umfasst. H und H' heißen konfliktäquivalent, genau dann wenn:

1. T = T'
2. O = O'
3. $\forall o_{1}\in T_{1}\in T,o_{2}\in T_{2}\in T;o_{1}\not\| o_{2};a_{1},a_{2}\not\in H:o_{1}<_{H}o_{2}\Rightarrow o_{1}<_{H'}o_{2}$

In Worten:

Zwei Historien heißen konfliktäquivalent, genau dann wenn:

1. sie dieselbe Menge von Transaktionen umfassen,
2. sie dieselbe Menge von Operationen umfassen und
3. konfliktäre Operationen aus nicht abgebrochenen Transaktionen in beiden Historien gleich angeordnet sind.

Konfliktäquivalenz wird notiert als:

$H\equiv H'$

Anwendungszweck

Sind zwei Historien konfliktäquivalent, so bedeutet das, dass ihre Ausführung zum selben Ergebnis führt. Die Konfliktäquivalenz bildet die Grundbedingung für die Konfliktserialisierbarkeit einer Historie.