$\small \text{seriell} \sub \text{strikt ST} \sub \text{ohne kask. zurück. ACA} \sub \text{rücksetzbar RC}$

konfliktserialisierbar $\Rarr$ serialisierbar nur ohne $\small \tt abort$

Update durch die erste Schreiboperation geht durch Überschreibung verloren.

Datensatz wird gelesen, obwohl es nicht $\small \tt commit$ ed wurde.

Lese-Operation hat bei mehrfacher Ausführung unterschiedliche Ergebnisse

Gleich aber via count(*)

($\small i$steht für die Nummer der Transaktion)

Menge an elementaren Operationen mit partieller Ordnung .

DMBS sieht keine Logik:

Ohne insert und delete.

Ordnung $<_i$

Paar greift auf das selbe Datenobjekt zu

$\left(r_{i}(A), w_{j}(A)\right), \quad\left(w_{i}(A), r_{j}(A)\right), \quad\left(w_{i}(A), w_{j}(A)\right)$

Eine mögliche execution-order

Ordnung $<_H$

$T_{1} \mid T_{2} \mid T_{3} \ldots$

sequentielle, ununterbrochene Abarbeitung (eine Transaktion nach dem anderen)

Ohne abort sind alle Transaktionen bereits erfolgreich abgeschlossen.

Auswirkung der Historie muss auf jeder konsistenten Ausprägung

Konfliktäquivalent zu einer seriellen Historie.

• Beispiel

  Alle diese Historien sind konfliktäquivalent - die letzte ist eine serielle Historie - dadurch sind alle konfliktserialisierbar.

  Sie sind alle über genau 2 Transaktionen und 2 Datenobjekten.

  Konflikte sind nur bei Datenobjekt$\small A$möglich.

  $\small r_{1}(A) \rightarrow r_{2}(C) \rightarrow w_{1}(A) \rightarrow w_{2}(C) \rightarrow r_{1}(B) \rightarrow w_{1}(B) \rightarrow c_{1} \rightarrow r_{2}(A) \rightarrow w_{2}(A) \rightarrow c_{2}$

  $\small r_{1}(A) \rightarrow w_{1}(A) \rightarrow r_{2}(C) \rightarrow w_{2}(C) \rightarrow r_{1}(B) \rightarrow w_{1}(B) \rightarrow c_{1} \rightarrow r_{2}(A) \rightarrow w_{2}(A) \rightarrow c_{2}$

  $\small r_{1}(A) \rightarrow w_{1}(A) \rightarrow r_{1}(B) \rightarrow r_{2}(C) \rightarrow w_{2}(C) \rightarrow w_{1}(B) \rightarrow c_{1} \rightarrow r_{2}(A) \rightarrow w_{2}(A) \rightarrow c_{2}$

  $\small \underbrace{ r_{1}(A) \rightarrow w_{1}(A) \rightarrow r_{1}(B) \rightarrow w_{1}(B) \rightarrow c_{1}}_{T_1} ~~ \underbrace{ \rightarrow r_{2}(C) \rightarrow w_{2}(C) \rightarrow r_{2}(A) \rightarrow w_{2}(A) \rightarrow c_{2}}_{T_2}$

von 2 Historien (über die selben, nicht abgebrochenen Transaktionen) wenn

$\small H$ konfliktserilisierbar $\Lrarr$$\small SG(H)$ azyklisch

Jede topologische Sortierung von einem azyklischen $\small SG(H)$ ist eine konfliktserialisierbare Historie.

• Beispiel

  

• Topologischer Sortierungs-Algorithmus

  In jedem azyklischen gerichteten Graphen gibt es mindestens einen Knoten ohne eingehende Kante.

  $\small \bold{In}:$ akzyklischer Serialisierbarkeitsgraph $\small SG(H)$

  $\small \bold{Out}:$ mögliche topologische Sortierung

  1. wähle Knoten $\small T_i$ in $\small SG(H)$ ohne eingehende Kante

  2. Schreibe $\small T_i$ in den Output

  3. Lösche $\small T_i$ und alle ausgehenden Kanten

  4. Falls es noch einen Knoten gibt, gehe zum 1. Schritt

Knoten = abgeschlossene Transaktion $\small T_i$

Gerichtete Kante = $\small T_{i} \rightarrow T_{j}$ wenn für min einem Konflikt $\small \left(p_{i}, q_{j}\right)$ gilt $\small p_{i}<_H q_{j}$

Konflikt-Serialisierbar $\Rarr$ Serialisierbar

Nicht umgekehrt: Es gibt serialisierbare Historien die nicht konfliktserialisierbar sind.

Konflikt-Serialisierbar $\not\Rarr$ Serialisierbar

Für alle $(T_{i}, ~T_{j})$ gilt:

Transaktion darf nur $\small \tt commit$ en wenn alle von denen sie gelesen hat auch $\small \tt commit$ ed haben.

Wenn für min ein Datenobjekt $\small T_i$ genau den Wert liest den $\small T_j$ geschrieben hat:

2 mögliche Definitionen:

(Nach jeder schreib-operation muss die Transaktion commited oder aborted werden bevor die nächste Transaktion lesen oder schreibenkann → also auch wenn die nächste Transaktion nicht von der vorherigen liest)

Wenn für ein beliebiges $\small T_{i}, ~T_{j}$