Schedules

Schedule Definition:

Ein Schedule 𝑆 ist eine Folge von Aktionen für eine Menge 𝑇 = {𝑇1, … 𝑇𝑛} von Transaktionen. Der Schedule 𝑆 entsteht durch das Mischen der Aktionen der einzelnen Transaktionen 𝑇𝑖, wobei die Reihenfolge der Aktionen innerhalb jeder Transaktion 𝑇𝑖 beibehalten wird.

Serieller Schedule

Ein Schedule ist seriell, wenn die einzelnen Transaktionen $(\mathbf{T}=T_1,\dots ,T_n)$ nicht verzahnt werden, sondern blockweise hintereinander ausgeführt werden.

$⟹$ Isolation ist gegeben, aber langsam, da nicht parallel

Serialisierbarer Schedule

Info

Ein serialisierbarer Schedule ist eine Anordnung von Transaktionen in einer Datenbank, bei der die Transaktionen zwar möglicherweise überlappend ausgeführt werden, aber das Ergebnis am End so ist, also ob die Transaktionen nacheinander (seriell) ausgeführt worden wären. Dies gewährleistet, dass keine Inkonsistenzen in den Daten entstehen, auch wenn die Transaktionen gleichzeitig laufen.

Ein Schedule 𝑆 von $\mathbf{T}=\{T_1,\dots ,T_n\}$ ist serialisierbar, wenn er die gleiche Wirkung hat wie ein beliebiger serieller Schedule von $\mathbf{T}=\{T_1,\dots ,T_n\}$

$⟹$ Auch hier ist die Isolation nicht verletzt $⟹$ Bessere Performanz also bei seriellen Schedules

$⟹$ Nur serialisierbare Schedules dürfen zugelassen werden

Abhängigkeiten in Schedules

Abhängigkeit: unterschiedliche Transkationen, gleiches Object Sei $S$ ein Schedule:

• Schreib-Lese Abhängigkeit von $T_i$ → $T_j$

  • Es gibt ein $x$, so dass $S$ $w_i(x)$ vor $r_j(x)\text{ kommt }\to wr{i}_{i,j}(x)$

• Lese-Schreib Abhängigkeit von $T_i\to T_j$:

  • Es gibt ein $x$, so dass in $S$ $r_i(x)$ vor $w_j(x)$ kommt $\to rw{i}_{i,j}(x)$

• Schreib-Schreib Abhängigkeit von $T_i\to T_j$:

  • Es gibt ein $x$, so dass in $S$ $w_i(x)$ vor $w_j(x)$ kommt $\to ww{i}_{i,j}(x)$

Serialisierungsgraph

• Ein Serialisierungsgraph $G$ ist ein gerichteter Graph $G=(V,E)$:

  • Mit Knoten $V=\{T_1,\dots ,T_n\}$ (beteiligten Transaktionen)
  • Mit Kanten $E$ = Abhängigkeiten $(T_i\to T_j)$ zwischen den Transaktionen

• Wenn der Graph zyklenfrei ist $\to$ serialisierbar

• Wenn der Graph Zyklen enthält $\to$ nicht serialisierbar

Serialisierung Graph - Beispiel

$$S=(r_1(x),r_2(y),r_3(z),w_3(z),w_2(y),w_1(x),w_2(y),r_1(y),r_3(x),w_1(y))$$

• Abhängigkeiten: $w{r}_{1,3}(x)$, $r{w}_{2,1}(y)$, $w{r}_{2,1}(y)$, $w{w}_{2,1}(y)$

• $T_2\stackrel{rw(y),wr(y),ww(y)}{\to }{T}_1\stackrel{wr(x)}{\to }{T}_3$

$\Rightarrow$ Zyklenfrei → $S$ ist serialisierbar

---