Sichtenäquivalenz

Sichtenäquivalenz

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

Inhaltsverzeichnis

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. Schreibeunbekanntin das FeldAutorder KarteDie Schatzinsel
  2. Lies das FeldErscheinungsjahrder KarteDer Graf von Monte Christo
  3. SchreibeRobert Louis Stevensonin das FeldAutorder KarteDie 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 FeldErscheinungsjahrder KarteDer Graf von Monte Christo
  2. Schreibeunbekanntin das FeldAutorder KarteDie Schatzinsel
  3. SchreibeRobert Louis Stevensonin das FeldAutorder KarteDie 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 FeldAutorder KarteDie SchatzinselstehtRobert Louis Stevenson“. Nicht sichtenäquivalent zu diesen beiden Historien wäre eine Historie wie die folgende:
  1. Lies das FeldErscheinungsjahrder KarteDer Graf von Monte Christo
  2. SchreibeRobert Louis Stevensonin das FeldAutorder KarteDie Schatzinsel
  3. Schreibeunbekanntin das FeldAutorder KarteDie Schatzinsel

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

Dasletzte Schreiben

Das letzte Schreiben eines Datenelements x in einer Historie H, notiert als FINH[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.


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 1-Serialisierbarkeit — Als serialisierbar bezeichnet man in Transaktionssystemen eine Historie, die zum selben Ergebnis führt wie eine serielle Historie über dieselben Transaktionen. Man unterscheidet Konfliktserialisierbarkeit, Sichtenserialisierbarkeit und 1… …   Deutsch Wikipedia

  • Commit-Serialisierbarkeit — Als serialisierbar bezeichnet man in Transaktionssystemen eine Historie, die zum selben Ergebnis führt wie eine serielle Historie über dieselben Transaktionen. Man unterscheidet Konfliktserialisierbarkeit, Sichtenserialisierbarkeit und 1… …   Deutsch Wikipedia

  • Final-State-Serialisierbarkeit — Als serialisierbar bezeichnet man in Transaktionssystemen eine Historie, die zum selben Ergebnis führt wie eine serielle Historie über dieselben Transaktionen. Man unterscheidet Konfliktserialisierbarkeit, Sichtenserialisierbarkeit und 1… …   Deutsch Wikipedia

  • Konflikt-Serialisierbarkeit — Als serialisierbar bezeichnet man in Transaktionssystemen eine Historie, die zum selben Ergebnis führt wie eine serielle Historie über dieselben Transaktionen. Man unterscheidet Konfliktserialisierbarkeit, Sichtenserialisierbarkeit und 1… …   Deutsch Wikipedia

  • Konfliktserialisierbarkeit — Als serialisierbar bezeichnet man in Transaktionssystemen eine Historie, die zum selben Ergebnis führt wie eine serielle Historie über dieselben Transaktionen. Man unterscheidet Konfliktserialisierbarkeit, Sichtenserialisierbarkeit und 1… …   Deutsch Wikipedia

  • Serialisierbar — Als serialisierbar bezeichnet man in Transaktionssystemen eine Historie, die zum selben Ergebnis führt wie eine serielle Historie über dieselben Transaktionen. Man unterscheidet Konfliktserialisierbarkeit, Sichtenserialisierbarkeit und 1… …   Deutsch Wikipedia

  • Sichten-Serialisierbarkeit — Als serialisierbar bezeichnet man in Transaktionssystemen eine Historie, die zum selben Ergebnis führt wie eine serielle Historie über dieselben Transaktionen. Man unterscheidet Konfliktserialisierbarkeit, Sichtenserialisierbarkeit und 1… …   Deutsch Wikipedia

  • Sichtenserialisierbarkeit — Als serialisierbar bezeichnet man in Transaktionssystemen eine Historie, die zum selben Ergebnis führt wie eine serielle Historie über dieselben Transaktionen. Man unterscheidet Konfliktserialisierbarkeit, Sichtenserialisierbarkeit und 1… …   Deutsch Wikipedia

  • Serialisierbarkeit — Als serialisierbar bezeichnet man in Transaktionssystemen eine Historie, die zum selben Ergebnis führt wie eine serielle Historie über dieselben Transaktionen. Man unterscheidet Konfliktserialisierbarkeit, Sichtenserialisierbarkeit und 1… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
https://de-academic.com/dic.nsf/dewiki/1285229 Do a right-click on the link above
and select “Copy Link”