imported>At40mha: Hilfe:Wikisyntax/Validierung#Ignoriertes Tag behoben

2025-02-27T16:19:55Z

Hilfe:Wikisyntax/Validierung#Ignoriertes Tag behoben

Neue Seite

Der Begriff ''Serialisierbarkeit'' stammt aus der Datenbanktheorie der Informatik. In [[Transaktionssystem]]en existiert ein Ausführungsplan für die parallele Ausführung mehrerer Transaktionen. Der Plan wird auch [[Historie (Transaktionsverarbeitung)|Historie]] genannt und gibt an, in welcher Reihenfolge die einzelnen Operationen der Transaktion ausgeführt werden. Als '''serialisierbar''' wird eine Historie bezeichnet, wenn sie zum selben Ergebnis führt wie eine nacheinander ([[seriell]]) ausgeführte Historie über dieselben [[Transaktion (Informatik)|Transaktionen]].

Man unterscheidet '''Konfliktserialisierbarkeit''', '''Sichtenserialisierbarkeit''' und '''1-Serialisierbarkeit'''. Steht der Begriff Serialisierbarkeit allein, wird er meistens als Konfliktserialisierbarkeit verstanden.

== Anschauliches Beispiel ==
Um sich die wichtigsten Begriffe dieses Artikels anschaulich vorstellen zu können, soll folgendes Beispiel dienen:
<div style="margin-left:1.6em">
In einer Bücherei wird ein Karteikarten-System zur Verwaltung des Bestandes an Büchern verwendet. Eine '''Historie''' bzw. eine '''Ausführungsreihenfolge''' könnte hier lauten:
# Hake den letzten Eintrag im Feld „ausgeliehen an“ auf der Karte „Moby Dick“ ab.
# Schreibe „Hans Meier“ in das Feld „ausgeliehen an“ auf der Karte „Moby Dick“.
# Streiche den letzten Eintrag im Feld „Rückgabe am“ auf der Karte „Moby Dick“.
# 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:
<poem style="margin-left: 1.6em;">
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“.
</poem>
Transaktion B ist ein '''Ausleihvorgang''' und lautet:
<poem style="margin-left: 1.6em;">
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“.
</poem>

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. Eine Begründung lautet: Operationen A.1 und A.2 beziehen sich jeweils 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.
</div>

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 [[Mathematische Formel|Formeln]]: Sei H eine Historie, C(H) die Commit-abgeschlossene Projektion von H. H heißt genau dann konfliktserialisierbar, wenn: <math>\exists</math> serielle Historie <math>H_{s}:C(H)\equiv H_{s}</math>
* 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 (Transaktionsverarbeitung)|Historie]] näher erläutert.

Konfliktserialisierbarkeit kann mit Hilfe eines [[Serialisierbarkeitsgraph]]en getestet werden: Ist der entstehende [[Azyklisch zusammenhängender Graph|Graph azyklisch]] (kreisfrei), 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: <math>\exists</math> serielle Historie <math>H_{s}:C(H)\equiv_{V} H_{s}</math>
* 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 [[Polygraph (Informatik)|Polygraphen]] getestet werden: Ist der entstehende Graph azyklisch, so ist die getestete Historie sichtenserialisierbar.

== Zusammenhang zwischen Konflikt- und Sichtenserialisierbarkeit ==
Die [[Menge (Mathematik)|Menge]] aller konfliktserialisierbaren Historien bildet eine echte [[Mengenlehre|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ändigkeit|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 <math>H_{MV}</math> eine Mehrversionen-Historie, <math>C(H_{MV})</math> die Commit-abgeschlossene Projektion von <math>H_{MV}</math>. <math>H_{MV}</math> heißt genau dann 1-serialisierbar, wenn: <math>\exists</math> 1-serielle Mehrversionen-Historie <math>H_{1s,MV}:C(H_{MV})\equiv_{V} H_{1s,MV}</math>
* In Worten: Eine Mehrversionen-Historie <math>H_{MV}</math> heißt genau dann 1-serialisierbar, wenn es eine 1-serielle Mehrversionen-Historie gibt, zu der die Commit-abgeschlossene Projektion von <math>H_{MV}</math> 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 [[Sichtenäquivalenz|letzten Schreibens]] hinfällig. Der Test, ob zwei Mehrversionen-Historien sichtenäquivalent sind, wird dadurch vereinfacht.

1-Serialisierbarkeit kann mit Hilfe eines [[Mehrversionen-Serialisierbarkeitsgraph]]en 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.

== Datenbank-Scheduler ==
Ein Datenbank-Scheduler dient der Verwaltung von Schreib- und Lesezugriffen (sogenannten [[Operation (Informatik)|Operationen]]) auf [[Datenbankobjekt]]en. Er sorgt dafür, dass keine Konflikte bei nebenläufigen [[Transaktion (Informatik)|Transaktionen]] auftreten. Transaktionen werden nach Möglichkeit parallel ausgeführt, um die Systemressourcen optimal ausnutzen zu können bzw. sie in kürzerer Zeit abzuschließen als wenn man sie nacheinander (seriell) ausführt. Dies kommt besonders bei Mehrbenutzerdatenbanken zum Tragen, da in solchen Systemen viele Datenbankzugriffe in sehr kurzer Zeit stattfinden können beispielsweise im zentralen [[Server]] einer Bank, der die Konten aller Filialen verwaltet.

Mit anderen Worten, der Scheduler ist die Komponente eines [[Datenbank#Datenbankmanagementsystem|DBMS]], welche die Ablaufreihenfolge (auch Schedule oder [[Historie (Transaktionsverarbeitung)|Historie]] genannt) der Datenzugriffe auf der Datenbank ([[Operation (Informatik)|Datenbankoperation]]) so konstruiert, dass sie einem bestimmten [[Protokoll (Datenbank)|Protokoll]] gehorchen. Außerdem übernimmt ein Scheduler die Ablaufkontrolle. Dabei hat er die Möglichkeit eine [[Operation (Informatik)|Operation]] sofort auszuführen (d. h. an den [[Datenverwalter]] weitergeben), sie zu verzögern (meist realisiert über eine Warteschlange) um den Operationen andere Transaktionen den Vorzug zu geben oder sie zurückzuweisen (durch Abbruch / abort der zugehörigen Transaktion).

Ein Scheduler muss folgende Eigenschaften eines Schedules sicherstellen:

* Serialisierbarkeit
* Fehlersicherheit

=== Serieller Schedule ===
In einem '''seriellen''' [[Prozess-Scheduler|Schedule]] werden die enthaltenen [[Transaktion (Informatik)|Transaktionen]] strikt nacheinander ausgeführt. Ein serieller Schedule ist damit immer korrekt, weil keine Überschneidungen der Transaktionen auftreten können. Allerdings ist ein serieller Schedule auch verhältnismäßig ineffizient, weil eine Transaktion immer die Beendigung der anderen Transaktion abwarten muss und damit keine Parallelisierung ausgenutzt werden kann.

Ein Schedule wird als '''serialisierbar''' bezeichnet, wenn er äquivalent zu einem seriellen Schedule ist. Es gibt dabei folgende [[Äquivalenzklasse]]n:

* [[Final-State-Serialisierbarkeit]] Schedules sind [[Finalstateäquivalenz|final-state-äquivalent]], wenn ihre Operationen ausgehend von einem gleichen Anfangszustand den gleichen Endzustand erzeugen. Dabei wird die globale Konsistenz nach Ausführung aller beteiligter Transaktionen betrachtet. FSR (final state serializability) ist die Klasse aller final-state-serialisierbaren Historien.
* [[Sichten-Serialisierbarkeit]] Schedules sind [[Sichtenäquivalenz|sichten-äquivalent]], wenn alle Transaktionen den gleichen Datenbank-Zustand 'sehen', d. h. wenn gilt: Transaktionen lesen gleiche Werte <math>\Rightarrow</math> sie produzieren das gleiche Ergebnis. Es wird also sowohl die globale Konsistenz nach Ausführung aller beteiligten Transaktionen als auch die lokale Konsistenz nach Ausführung jeder einzelnen Transaktion betrachtet. VSR (view serializability) ist die Klasse aller sichten-serialisierbaren Historien.
* [[Konflikt-Serialisierbarkeit]] Schedules sind [[Konfliktäquivalenz|konflikt-äquivalent]], wenn unverträgliche Operationen in der gleichen Reihenfolge angeordnet sind. CSR (conflict serializability) ist die Klasse aller konflikt-serialisierbaren Historien.
* [[Commit-Serialisierbarkeit]] CMFSR (commit final state serializability) ist die Klasse aller commit-final-state-serialisierbaren Historien. CMVSR (commit view serializability) ist die Klasse aller commit-view-serialisierbaren Historien. CMCSR (commit conflict serializability) ist die Klasse aller commit-conflict-serialisierbaren Historien.Fehlersicherheit eines Schedules ist die Eigenschaft, dass dieser Schedule sich bei Abbruch einer oder mehreren Transaktionen genauso verhält wie ein ähnlicher Schedule, der ausschließlich die nicht abgebrochenen Transaktionen enthält.

Es gibt folgende Klassen von Schedules bzgl. der Fehlersicherheit:
* RC – recoverable. Es ist möglich, nach einer abgebrochenen Transaktion die Verarbeitung der restlichen Schedules weiterzuführen ohne Inkonsistenzen zu erhalten.
* ACA – avoids cascading abort. Geschachtelte Abbrüche werden vermieden, indem Transaktionen nur von abgeschlossenen Transaktionen lesen dürfen.
* ST – strict schedules.
* RG – rigorous schedules.

[[Kategorie:Datenbanktheorie]]

Serialisierbarkeit - Versionsgeschichte

imported>At40mha: Hilfe:Wikisyntax/Validierung#Ignoriertes Tag behoben