Sichtenäquivalenz

Sichtenäquivalent sind in der Informatik im Zusammenhang mit Transaktionssystemen zwei Historien, die dasselbe Ergebnis produzieren.

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. Schreibe „unbekannt“ in 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. Schreibe „unbekannt“ in das Feld „Autor“ der Karte „Die Schatzinsel“
3. Schreibe „Robert Louis Stevenson“ in das Feld „Autor“ der Karte „Die Schatzinsel“

Diese beiden Historien sind sichtenäquivalent, denn sie führen zu demselben Ergebnis: Das Erscheinungsjahr des Grafen von Monte Christo wurde gelesen und im Feld „Autor“ der Karte „Die Schatzinsel“ steht „Robert Louis Stevenson“. Nicht sichtenä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. Schreibe „unbekannt“ in das Feld „Autor“ der Karte „Die Schatzinsel“

Die „Liest-von-Beziehung“

Man sagt, eine Transaktion A lese ein Datenelement x von einer anderen Transaktion B, wenn A eine Operation enthält, die genau den Wert von x abruft, den B x zugewiesen hat.

Das „letzte Schreiben“

Das letzte Schreiben eines Datenelements x in einer Historie H, notiert als $FIN_{H}[x]$, ist diejenige Operation aus H, die x zum letzten Mal einen Wert zuweist.

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 genau dann sichtenäquivalent, wenn:

1. T = T'
2. O = O'
3. $\forall T_{1},T_{2}\in T;a_{1},a_{2}\not \in H:T_{2}\triangleright _{H}T_{1}\Leftrightarrow T_{2}\triangleright _{H'}T_{1}$
4. $\forall x:FIN_{H}[x]=FIN_{H'}[x]$

In Worten:

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

1. sie dieselbe Menge von Transaktionen umfassen,
2. sie dieselbe Menge von Operationen umfassen,
3. alle Operationen aus nicht abgebrochenen Transaktionen nach der Liest-von-Beziehung in beiden Historien gleich angeordnet sind und
4. ihre letzten Schreiben für alle Datenelemente identisch sind.

Sichtenäquivalenz wird notiert als:

$H\equiv _{V}H'$

Anwendungszweck

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