Transaktionen, 2PL & Konfliktgraphen

Analysieren Sie verzahnte Ablaufpläne (Schedules) interaktiv auf Konflikt-Serialisierbarkeit, erkennen Sie Zyklen im Abhängigkeitsgraphen ($G$), berechnen Sie topologische Sortierungen und simulieren Sie das 2-Phasen-Sperrprotokoll (2PL / Strict 2PL) mit Deadlock-Erkennung.

[+] Klausur-Schedules:

Schedule-Eingabe (Ablaufprotokoll)

Syntax: r1(A), w2(A)...

Operationen: r_i(X) = Read von $X$ in $T_i$, w_i(X) = Write auf $X$ in $T_i$, c_i = Commit, a_i = Abort.

Transaktions-Timeline

3 Transaktionen

Zeitachse verläuft chronologisch von links nach rechts ($t_1 \to t_n$).

Konflikt-Serialisierbar?

Ja (Kreisfrei)

Konflikt-Kanten ($E$)

2 Kanten

Äquivalenter Serieller Plan

T1 → T2 → T3

2PL Lock-Einhaltung

Konform (Strict 2PL)

Konfliktgraph $G = (V, E)$

Knoten: $T_i$ • Kanten: Konflikte

Konflikt-Bedingungen ($op_i(X)$ vor $op_j(X)$):

• Read-Write: $r_i(X) < w_j(X) \implies T_i \to T_j$

• Write-Read: $w_i(X) < r_j(X) \implies T_i \to T_j$

• Write-Write: $w_i(X) < w_j(X) \implies T_i \to T_j$

Gefundene Konflikt-Paare

Ausführliche Begründung

[>] Klausur-Satz:

Ein Schedule $S$ ist genau dann konflikt-serialisierbar, wenn sein Konfliktgraph $G(S)$ azyklisch (kreisfrei) ist. Jede topologische Sortierung von $G(S)$ liefert einen konflikt-äquivalenten seriellen Schedule.