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-Serialisierbarkeit; ohne Zusatz wird unter Serialisierbarkeit meist die Konfliktserialisierbarkeit verstanden.

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. Eine Historie könnte hier lauten:

1. Hake den letzten Eintrag im Feld „ausgeliehen an“ auf der Karte „Moby Dick“ ab.
2. Schreibe „Hans Meier“ in das Feld „ausgeliehen an“ auf der Karte „Moby Dick“.
3. Streiche den letzten Eintrag im Feld „Rückgabe am“ auf der Karte „Moby Dick“.
4. Schreibe „15. März 2003“ in das Feld „Rückgabe am“ auf der Karte „Moby Dick“.

Hier werden zwei Transaktionen gemischt ausgeführt. Transaktion A ist ein Rückgabevorgang und lautet:

A.1: Hake den letzten Eintrag im Feld „ausgeliehen an“ auf der Karte „Moby Dick“ ab.

A.2: Streiche den letzten Eintrag im Feld „Rückgabe am“ auf der Karte „Moby Dick“.

Transaktion B ist ein Ausleihvorgang und lautet:

B.1: Schreibe „Hans Meier“ in das Feld „ausgeliehen an“ auf der Karte „Moby Dick“.

B.2: Schreibe „15. März 2003“ in das Feld „Rückgabe am“ auf der Karte „Moby Dick“.

Die Operationen A.1 und B.1 sind konfliktär, ebenso wie die Operationen A.2 und B.2; würde man sie in vertauschter Reihenfolge ausführen, wäre das Ergebnis der Historie ein unverständliches Durcheinander. (Grund: Operationen A.1 und A.2 beziehen sich auf den letzten Eintrag, welcher der letzte Eintrag ist wird aber von den Operationen B.1 bzw. B.2 bestimmt. Wird also B.1 (B.2) vor A.1 (A.2) ausgeführt wird ein neuer Eintrag für "Hans Meier" hinzugefügt. Dieser Eintrag ist nun der Letzte in der Liste, entspricht aber nicht mehr dem letzten Ausleiher, sondern schon dem Neuen. Somit wird der falsche Eintrag abgehakt bzw. gestrichen.)

Mit Hilfe der Konfliktserialisierbarkeit können wir die Historie darauf hin überprüfen, ob diese konfliktären Operationen in der richtigen Reihenfolge ausgeführt werden. Die Sichtenserialisierbarkeit hingegen sagt uns, dass das Ergebnis der Historie dasselbe ist, wie wenn wir nur die letztendlich sichtbaren Operationen der Transaktionen in der richtigen Reihenfolge ausgeführt hätten.

Die 1-Serialisierbarkeit stellt eine Erweiterung des Begriffs auf Mehrversionen-Historien dar. Die Verwendung einer Mehrversionen-Historie würde in diesem Beispiel bedeuten, dass bei jeder Änderung einer Bücherkarte eine neue Karte erstellt und gleichzeitig die alte Karte aufgehoben wird. Es werden dann Operationen möglich wie:

„Lies das Feld „Autor“ der Karte „Moby Dick“ in der Kartenversion vom 17. März 1993“.

Alle Formen der Serialisierbarkeit garantieren, dass das Ergebnis einer Historie richtig ist.

Konfliktserialisierbarkeit

Zur Überprüfung der Äquivalenz der Historien wird hier die Konfliktäquivalenz herangezogen. Die Bedingungen der Konfliktserialisierbarkeit lauten in Formeln:

Sei H eine Historie, C(H) die Commit-abgeschlossene Projektion von H. H heißt genau dann konfliktserialisierbar, wenn:

$\exists$ serielle Historie $H_{s}:C(H)\equiv H_{s}$

In Worten:

Eine Historie H heißt genau dann konfliktserialisierbar, wenn es eine serielle Historie gibt, zu der die Commit-abgeschlossene Projektion von H konfliktäquivalent ist.

Die Commit-abgeschlossene Projektion einer Historie enthält nur noch diejenigen Transaktionen, die durch Commit abgeschlossen werden (also nicht abgebrochen werden). Diese Projektion wird im Artikel Historie näher erläutert.

Konfliktserialisierbarkeit kann mit Hilfe eines Serialisierbarkeitsgraphen getestet werden: Ist der entstehende Graph azyklisch, so ist die getestete Historie serialisierbar.

Sichtenserialisierbarkeit

Hier wird zur Überprüfung der Äquivalenz die Sichtenäquivalenz verwendet. Die Bedingungen der Sichtenserialisierbarkeit lauten - analog zu oben - in Formeln:

Sei H eine Historie, C(H) die Commit-abgeschlossene Projektion von H. H heißt genau dann sichtenserialisierbar, wenn:

$\exists$ serielle Historie $H_{s}:C(H)\equiv_{V} H_{s}$

In Worten:

Eine Historie H heißt genau dann sichtenserialisierbar, wenn es eine serielle Historie gibt, zu der die Commit-abgeschlossene Projektion von H sichtenäquivalent ist.

Sichtenserialisierbarkeit kann mit Hilfe eines Polygraphen getestet werden: Ist der entstehende Graph azyklisch, so ist die getestete Historie sichtenserialisierbar.

Zusammenhang zwischen Konflikt- und Sichtenserialisierbarkeit

Die Menge aller konfliktserialisierbaren Historien bildet eine echte Untermenge der Menge aller sichtenserialisierbaren Historien. Historien, die konfliktserialisierbar sind, sind demnach automatisch auch sichtenserialisierbar. Sichtenserialisierbarkeit ist theoretisch die effektivere Form der Serialisierbarkeit, denn sie ermöglicht mehr Nebenläufigkeit und damit bessere Leistungen als Konfliktserialisierbarkeit. Das Problem dabei ist, dass der Test auf Sichtenserialisierbarkeit mit einem Polygraphen NP-vollständig ist, also extrem lange dauert. Dadurch ist eine Ausnutzung der Sichtenserialisierbarkeit praktisch nicht möglich.

1-Serialisierbarkeit

Die 1-Serialisierbarkeit ist eine Spezialisierung der Sichtenserialisierbarkeit auf Mehrversionen-Historien. In Formeln:

Sei H_MV eine Mehrversionen-Historie, C(H_MV) die Commit-abgeschlossene Projektion von H_MV. H_MV heißt genau dann 1-serialisierbar, wenn:

$\exists$ 1-serielle Mehrversionen-Historie $H_{1s,MV}:C(H_{MV})\equiv_{V} H_{1s,MV}$

In Worten:

Eine Mehrversionen-Historie H_MV heißt genau dann 1-serialisierbar, wenn es eine 1-serielle Mehrversionen-Historie gibt, zu der die Commit-abgeschlossene Projektion von H_MV sichtenäquivalent ist.

Prinzipiell ist die hierzu verwendete Äquivalenzrelation identisch mit der Sichtenäquivalenz, die besonderen Beschaffenheiten der Mehrversionen-Historien machen aber die Überprüfung der Gleichheit des letzten Schreibens hinfällig. Der Test, ob zwei Mehrversionen-Historien sichtenäquivalent sind, wird dadurch vereinfacht.

1-Serialisierbarkeit kann mit Hilfe eines Mehrversionen-Serialisierbarkeitsgraphen getestet werden: Ist der entstehende Graph azyklisch, so ist die getestete Historie 1-serialisierbar.

Vergleich zwischen Sichten- und 1-Serialisierbarkeit

Ausschließlich gewöhnliche (Einversionen-)Historien können sichtenserialisierbar sein, während Mehrversionen-Historien ausschließlich 1-serialisierbar sein können. Die Grundbedeutung beider Begriffe ist - sieht man von der Form der Historie ab - identisch: „Wenn ich nur diejenigen Operationen ausführe, die das Ergebnis sichtbar beeinflussen, und das in der richtigen Reihenfolge, ist das Ergebnis korrekt“. Beide Eigenschaften bestätigen also die Korrektheit der überprüften Historie. Beide Eigenschaften werden in der Praxis kaum verwendet, da die Überprüfung über die zugehörigen Graphen extrem lange dauert.