Serialisierbarkeit - DB Klausur

Zusammenfassung

Serialisierbarkeit ist das zentrale Korrektheitskriterium fuer parallele Transaktionsausfuehrung im Mehrbenutzerbetrieb: Eine verzahnte Historie gilt als korrekt, wenn sie zu einer seriellen Historie aequivalent ist. Konflikt-Serialisierbarkeit wird effizient ueber den Praezedenzgraphen SG(H) geprueft, in dem Transaktionen die Knoten und Konfliktpaare (gleiches Objekt, mindestens ein write) die gerichteten Kanten bilden. Nach dem Serialisierbarkeitstheorem ist eine Historie genau dann konfliktserialisierbar, wenn ihr Graph azyklisch ist.

Kernkonzepte

Historie (Transaction Schedule)

Eine Historie ist eine sequenzielle Anordnung aller Aktionen (read, write, commit, abort) von einer oder mehreren Transaktionen. Sie enthaelt alle Aktionen jeder beteiligten Transaktion, wobei die Reihenfolge innerhalb einer Transaktion erhalten bleibt. Aktionen verschiedener Transaktionen koennen verzahnt (interleaved) sein.

Merke: Historie = Reihenfolge aller Operationen aller Transaktionen, verzahnt aber intern konsistent.

Serielle Historie

Transaktionen werden strikt hintereinander ausgefuehrt: erst T1 komplett, dann T2, dann T3. Keine Verzahnung. Immer korrekt, aber schlecht fuer die Performance. Seriell dient als Referenzmodell fuer die Korrektheit paralleler Ausfuehrungen.

Merke: Seriell = Transaktionen laufen sequentiell hintereinander, nie verzahnt.

Serialisierbare Historie

Eine Historie H ist serialisierbar, wenn sie zu einer seriellen Historie aequivalent ist, also das gleiche Endergebnis in der Datenbank liefert. Ziel des DBMS: verzahnte Ausfuehrung erlauben, aber nur wenn Serialisierbarkeit gewaehrleistet ist. Korrekt = serialisierbar.

Merke: Verzahnt darf sein, solange das Ergebnis wie bei serieller Ausfuehrung ist.

Konflikt zwischen Operationen

Zwei Operationen stehen in Konflikt, wenn sie dasselbe Datenobjekt betreffen UND mindestens eine ein write ist. Konfliktarten: r/w, w/r, w/w. read/read ist KEIN Konflikt. Das write allein macht den Konflikt aus.

Merke: Gleiches Objekt + mindestens ein write. r/r ist harmlos.

Konfliktaequivalenz

Zwei Historien sind konfliktaequivalent, wenn sie die Konfliktoperationen der nicht-abgebrochenen Transaktionen in derselben Reihenfolge ausfuehren. Nicht-konfligierende Operationen duerfen umsortiert werden.

Merke: Gleiche Reihenfolge aller Konfliktpaare, egal wie der Rest sortiert ist.

Konflikt-Serialisierbarkeit

Eine Historie H ist konfliktserialisierbar, wenn sie konfliktaequivalent zu einer seriellen Historie ist. Man kann die verzahnte Historie durch Vertauschen unabhaengiger Operationen in eine serielle Form ueberfuehren. Strenger als Ergebnis-Aequivalenz, aber effizient testbar.

Merke: Konflikte in seriell umsortierbar ohne Reihenfolgeverletzung.

Praezedenzgraph SG(H)

Gerichteter Graph. Knoten sind die Transaktionen T1, ..., Tn. Fuer jedes Konfliktpaar p_i(X) vor q_j(X) mit i != j wird eine Kante T_i -> T_j eingezeichnet. Verdichtet die Konfliktbeziehung auf Transaktionsebene.

Merke: Knoten pro Transaktion, Kante T_i->T_j bei Konflikt von T_i vor T_j.

Serialisierbarkeitstheorem

Eine Historie H ist konfliktserialisierbar genau dann, wenn ihr Serialisierbarkeitsgraph SG(H) azyklisch ist. Ein Zyklus bedeutet widerspruechliche Reihenfolgeanforderungen. Topologische Sortierung des azyklischen Graphen liefert die aequivalente serielle Reihenfolge.

Merke: Azyklisch = serialisierbar. Zyklus = nicht serialisierbar.

Wichtige Details

Ziel der Serialisierbarkeit: parallele Ausfuehrung erlauben, aber Korrektheit wie bei sequentieller Ausfuehrung gewaehrleisten (Korrekt = Serialisierbar).
Wichtige Aktionen einer Historie: read (r_i), write (w_i), commit (c_i), abort (a_i). Reihenfolge innerhalb einer Transaktion bleibt erhalten.
Konflikt = gleiches Datenobjekt + mindestens ein write. r/r ist NIE ein Konflikt, w/r und r/w und w/w sind Konflikte.
Praezedenzgraph SG(H): Knoten = Transaktionen, Kante T_i -> T_j bei Konfliktpaar p_i vor q_j.
Serialisierbarkeitstheorem: H ist konfliktserialisierbar genau dann, wenn SG(H) azyklisch ist.
Topologische Sortierung des azyklischen SG(H) liefert eine aequivalente serielle Ausfuehrungsreihenfolge.
Konflikt-Serialisierbarkeit ist konservativer als Ergebnis-Aequivalenz: manche semantisch korrekten Historien werden abgelehnt, da das DBMS keine Rechenoperationen auswertet.
Serieller Isolationslevel SERIALIZABLE in SQL setzt genau dieses Konzept technisch um.
Nur die abgeschlossenen (committeten) Transaktionen sind fuer den finalen SG relevant, abgebrochene werden nicht beruecksichtigt.
Zwei entgegenlaufende Kanten T_i -> T_j und T_j -> T_i bilden bereits einen Zyklus und damit eine nicht serialisierbare Historie.

Beispiele

Serialisierbare Historie (T1 vor T2 aequivalent)

Zwei Transaktionen T1 und T2 arbeiten verzahnt auf Datenobjekten A, B, C. T1 nutzt A und B, T2 nutzt C und A. Da T1 und T2 nur bei A auf dasselbe Objekt zugreifen und die Reihenfolge dort korrekt ist (T1 schreibt A vor T2), ist die verzahnte Historie aequivalent zur seriellen Historie T1 vor T2.

Verzahnt: BOT1 r1(A) BOT2 r2(C) w1(A) w2(C) r1(B) w1(B) c1 r2(A) w2(A) c2
Aequivalente serielle Historie: T1 -> T2
T1: r1(A) w1(A) r1(B) w1(B) c1
T2: r2(C) w2(C) r2(A) w2(A) c2
Ergebnis identisch = serialisierbar.

Nicht serialisierbare Historie (Konflikt bei A)

T1 schreibt A und liest spaeter B. T3 startet zwischen w1(A) und liest sofort das noch nicht commitete A. Es gibt keine aequivalente serielle Historie, weil sowohl w1(A) vor r3(A) als auch spaeter ein Konflikt zurueck zu T1 entstehen wuerde. Konfliktgraph waere zyklisch.

Schritt T1        T3
1     BOT
2     read(A)
3     write(A)  <---
4               BOT
5               read(A)   <- Konflikt: T1 -> T3
6               write(A)
7               read(B)
8               write(B)
9               commit
10    read(B)             <- Konflikt: T3 -> T1 (Zyklus)
11    write(B)
12    commit
=> Nicht serialisierbar

Ueberweisung + Zinsgutschrift (Rechenoperationen zaehlen NICHT)

T1 ist eine Ueberweisung von 50 (A-50, B+50), T2 eine Zinsgutschrift (A*1.03, B*1.03). Verzahnte Ausfuehrung ergibt Konto A = (A-50)*1.03, Konto B = B*1.03+50. Aequivalente serielle Historie T1 vor T2 ergibt (A-50)*1.03 und (B+50)*1.03 = anderes Ergebnis. Aber: das DBMS wertet Rechenoperationen NICHT aus, sondern nur read/write-Konflikte. Deshalb kann die Historie trotzdem konfliktserialisierbar sein.

Merksatz: DBMS betrachtet nur read/write-Zugriffe auf gleiche Objekte,
nicht die semantische Berechnung.
Serialisierbarkeit ist eine konservative Approximation.

Konfliktgraph / Praezedenzgraph zeichnen

Fuer jede Transaktion T_i wird ein Knoten gezeichnet. Fuer jedes Paar konfliktierender Operationen p_i(X) vor q_j(X) mit i != j und mindestens einer Schreiboperation wird eine Kante T_i -> T_j eingefuegt. Ist der Graph azyklisch, so ist die Historie konfliktserialisierbar.

Historie H: w1(A) -> r3(A) und w1(A) -> r2(A) und r2(A) -> w3(A) usw.
Kanten: T1 -> T3 (wegen w1(A) vor r3(A)), T1 -> T2, T2 -> T3
SG(H) = Knoten T1, T2, T3 mit Pfeilen T1->T2, T1->T3, T2->T3
=> Azyklisch => serialisierbar. Serielle Reihenfolge: T1, T2, T3.

Visualisierung: Historie und Praezedenzgraph

Links: Historie H als Schrittfolge auf Transaktionsspalten. Rote Zellen markieren Konfliktzugriffe. Rechts: Praezedenzgraph SG(H) mit drei Transaktionsknoten und roten Konfliktkanten. Azyklisch => H ist konfliktserialisierbar. Die topologische Sortierung ergibt die aequivalente serielle Reihenfolge T1 -> T2 -> T3.

FAQ

Was ist der Unterschied zwischen serieller und serialisierbarer Historie?

Seriell = Transaktionen laufen strikt hintereinander, keine Verzahnung. Serialisierbar = verzahnt, aber es existiert eine aequivalente serielle Historie mit gleichem Ergebnis.

Was zaehlt als Konflikt zwischen zwei Operationen?

Zwei Operationen konfligieren, wenn sie dasselbe Datenobjekt betreffen und mindestens eine davon ein write ist. Also: r/w, w/r, w/w konfligieren, r/r nicht.

Warum reicht read/read nicht als Konflikt?

Weil beide Transaktionen denselben Wert lesen, unabhaengig von der Reihenfolge. Es gibt keine Reihenfolgeabhaengigkeit, das Ergebnis der Datenbank bleibt gleich.

Wie testet man Konflikt-Serialisierbarkeit?

Man zeichnet den Serialisierbarkeitsgraph SG(H): Knoten sind Transaktionen, Kanten gehen von T_i zu T_j, wenn eine Operation aus T_i mit einer spaeteren Operation aus T_j konfligiert. Ist der Graph azyklisch, ist H serialisierbar.

Kann eine Historie zwar semantisch korrekt, aber trotzdem nicht konfliktserialisierbar sein?

Ja. Das DBMS wertet keine Rechenoperationen aus, sondern nur Datenzugriffe. Konfliktserialisierbarkeit ist eine konservative Naeherung: manche Historien mit gutem Ergebnis werden als nicht serialisierbar abgelehnt.

Was ist Konfliktaequivalenz?

Zwei Historien sind konfliktaequivalent, wenn sie exakt dieselben Konfliktoperationen der nicht abgebrochenen Transaktionen in derselben Reihenfolge ausfuehren. Nicht-konfligierende Operationen duerfen umsortiert werden.

Wie erkenne ich einen Zyklus im Praezedenzgraphen?

Wenn man von einem Knoten T_i ueber gerichtete Kanten wieder zu T_i zurueckkommt. Zwei Transaktionen bilden einen Zyklus, wenn T_i -> T_j UND T_j -> T_i existieren.

Welcher SQL-Isolationslevel garantiert Serialisierbarkeit?

Nur SERIALIZABLE garantiert vollstaendige Serialisierbarkeit. READ UNCOMMITTED, READ COMMITTED und REPEATABLE READ lassen jeweils bestimmte Probleme wie Dirty Read, Nonrepeatable Read oder Phantom zu.

Pruefungsfragen

0 von 12 Fragen beantwortet