Raphael Das Gupta · a51a50ff · 93e23854 · a51a50ff
--- a/Week 11/01 Transaktionen.ipynb

+ 2

− 2
+++ b/Week 11/01 Transaktionen.ipynb

+ 2

− 2
 %% Cell type:markdown id: tags:

 <img src="https://intranet.rj.ost.ch/fileadmin/user_upload/Kommunikation/logos/ost_logo_de_rgb.svg" alt="OST Logo" style="width: 200px; float: right;"/>

 # Transaktionen

 ## Einführung

 ### Ziele
 - Anwendung der Transaktionen in SQL sowie Vertiefen der Theorie der Serialisierbarkeit und der SQL Isolation Levels.

 %% Cell type:markdown id: tags:

 ### 1. Serialisierbarkeit
 Schauen Sie zur Notation (z.B. "$r1(b)$") unbedingt nochmals Folie 27 "Operationen – Formalisierung" in "Transaktionen Teil 1 (pdf)" (auf Moodle) an.

 Gegeben sind zwei Schedules (Schedules sind voneinander völlig unabhängig).

 #### Fragen:
 1. Bestimmen Sie je separat die Serialisierbarkeit der Schedules S1 und S2 mit Hilfe eines Serialisierbarkeitsgraphs.
 2. Wenn serialisierbar, geben Sie einen konflikt-äquivalenten seriellen Schedule an. Der neue Begriff "konflikt-äquivalent" bedeutet, dass der Serialisierbarkeitsgraph derselbe bleibt. T1 bis T5 in serielle Reihenfolge bringen, aber nur so viel wie nötig ("Teilsortierung" der Transaktionen). Tipp: Vertauschen der konfliktfreien Operationen.
 3. Wenn serialisierbar, definieren Sie eine passende Commit-Reihenfolge für die Transaktionen.

 %% Cell type:markdown id: tags:

 #### Schedule 1
 $S1 = r1(b) r2(b) w2(b) r2(c) r2(d) w3(a) r4(d) r3(b) w4(d) r5(c) r5(a) w4(c)$
 1. Ist der Schedule serialisierbar?

 %% Cell type:raw id: tags:

 Antwort:

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 Folgende Konfliktpaare lassen sich identifizieren:

 <table style="margin-left: 0">
 <tr>
 <td>

 $r1(b) < w2(b)$

 </td>
 <td>

 $w2(b) < r3(b)$

 </td>
 <td>

 $r2(d) < w4(d)$

 </td>
 <td>

 $r4(d) < w4(d)$

 </td>
 </tr>
 <tr>
 <td>

 $r2(b) < w2(b)$

 </td>
 <td>

 $r2(c) < w4(c)$

 </td>
 <td>

 $w3(a) < r5(a)$

 </td>
 <td>

 $r5(c) < w4(c)$

 </td>
 </tr>
 </table>

 Daraus wiederum lässt sich folgender Serialisierbarkeitsgraph ableiten:
 ![graph2_1.png](attachment:8cf26d53-7896-4570-b818-58fa59cce4e2.png)
 Anhand des Graphen ist sofort sichtbar, dass dieser keine Zyklen enthält und der Schedule $S1$ entsprechend **serialisierbar** ist.

 </details>

 %% Cell type:markdown id: tags:

 2. Herleitung eines konflikt-äquivalenten Schedules (falls serialisierbar).

 %% Cell type:raw id: tags:

 Antwort:

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 Ein konflikt-äquivalenten seriellen Schedule zu $S1$ lässt sich durch vertauschen der konfliktfreien Operationen herleiten:
 $S1 = r1(b) r2(b) w2(b) r2(c) r2(d) w3(a) r4(d) r3(b) w4(d) r5(c) r5(a) w4(c)$
 Da $r4(d)$ nicht in Konflikt mit $r3(b)$ steht, können wir diese Operationen vertauschen und
 erhalten:
 $r1(b) r2(b) w2(b) r2(c) r2(d) w3(a) r3(b) r4(d) w4(d) r5(c) r5(a) w4(c)$
 Ebenfalls keine Konfliktpaare sind $w4(d)$ und $r4(d)$ mit $r5(c)$ und $r5(a)$,
 deshalb können wir die Operation von $T4$ hinter die Operationen von $T5$ verschieben
 (die relative Reihenfolge innerhalb der Transaktionen muss dabei aber erhalten bleiben):
 $S1' = \underbrace{r1(b)}_{T1} \enspace \underbrace{r2(b) \enspace w2(b) \enspace r2(c) \enspace r2(d)}_{T2} \enspace \underbrace{w3(a) \enspace r3(b)}_{T3} \underbrace{\enspace r5(c) \enspace r5(a)}_{T5} \underbrace{\enspace r4(d) \enspace w4(d)  \enspace w4(c)}_{T4}$

 </details>

 %% Cell type:markdown id: tags:

 3. Bestimmung der Commit-Reigenfolge (falls serialisierbar). Falls nicht serialisierbar: Wie lösen Sie das Problem des Schedules, um ihn zu serialisieren?

 %% Cell type:raw id: tags:

 Antwort:

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 Die Commit-Reihenfolge bestimmt sich aus der topologischen Sortierung des Serialisierbarkeitsgraphen:
 $c1$ $c2$ $c3$ $c5$ $c4$

 </details>

 %% Cell type:markdown id: tags:

 #### Schedule 2
 $S2 = r1(a) w2(a) w3(b) w4(b) r2(b) w1(b) r3(c) w4(a) r4(b) w4(a)$
 1. Ist der Schedule serialisierbar?

 %% Cell type:raw id: tags:

 Antwort:

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 Folgende Konfliktpaare lassen sich identifizieren:

 <table style="margin-left: 0">
 <tr>
 <td>

 $r1(a) < w2(a)$

 </td>
 <td>

 $w3(b) < w4(b)$

 </td>
 <td>

 $w3(b) < r4(b)$

 </td>
 <td>

 $w4(b) < r4(b)$

 </td>
 </tr>
 <tr>
 <td>

 $r1(a) < w4(a)$

 </td>
 <td>

 $w3(b) < r2(b)$

 </td>
 <td>

 $w4(b) < r2(b)$

 </td>
 <td>

 $r2(b) < w1(b)$

 </td>
 </tr>
 <tr>
 <td>

 $w2(a) < w4(a)$

 </td>
 <td>

 $w3(b) < w1(b)$

 </td>
 <td>

 $w4(b) < w1(b)$

 </td>
 <td>

 $w1(b) < r4(b)$

 </td>
 </tr>
 </table>

 Daraus wiederum lässt sich folgender Serialisierbarkeitsgraph ableiten:
 ![graph2_2.png](attachment:graph2_2.png)
 Mit dem Graph wird sofort sichtbar, dass dieser Zyklen enthält und der Schedule $S2$ entsprechend **nicht serialisierbar** ist.

 </details>

 %% Cell type:markdown id: tags:

 2. Herleitung eines konflikt-äquivalenten Schedules (falls serialisierbar).

 %% Cell type:raw id: tags:

 Antwort:

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 Ein konflikt-äquivalenten seriellen Schedule zu S2 lässt sich nicht erstellen

 </details>

 %% Cell type:markdown id: tags:

 3. Bestimmung der Commit-Reigenfolge (falls serialisierbar). Falls nicht serialisierbar: Wie lösen Sie das Problem des Schedules, um ihn zu serialisieren?

 %% Cell type:raw id: tags:

 Antwort:

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 Es lässt sich keine Commit-Reihenfolge festlegen für einen nicht serialisierbaren Schedule.

 Der Zyklus lässt sich lösen, indem man zum Beispiel $T2$ und $T4$ rückgängig macht. Angenommen es gibt ein Rollback von $T2$ und $T4$, dann folgt auch ein Rollback aller Transaktionen $T_n$, die eine Konflikt-Operation $op_2 < op_n$ oder $op_4 < op_n$ haben. Aus der Liste der Konfliktoperationen folgt, dass in diesem Beispiel auch für $T1$ ein Rollback erfolgen muss und das heisst, es gibt Cascading Rollback.

 </details>

 %% Cell type:markdown id: tags:

 ### 2. Transaktionen in SQL
 #### Vorbemerkungen:
 - Die Isolationsgrade und Fehlersituationen werden in nächster Woche 12 besprochen. Dies ist eine vorbereitende Aufgabe dazu.
 - Schlagen Sie die Syntax zu `BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;` bzw. `BEGIN; SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;` in Folien 6 und 7 in "Transaktionen Teil 2 (pdf)" (auf Moodle) nach – oder schauen Sie in die offizielle PostgreSQL-Dokumentation.

 Ausgangslage ist die Datenbank [AngProj](../Week%2006/01%20SQL%20DML%20Einleitung.ipynb) und folgende Szenarien bestehend aus je zwei nebenläufigen Transaktionen T1 und T2.
 Tipp: Wenn in `psql` das Resultat einer Query genau eine Zeile hat, [kann es mit `\gset` in `psql`-Variablen gespeichert werden](https://www.postgresql.org/docs/current/app-psql.html), die wie die Spaltennamen des Resultats heissen.

 %% Cell type:markdown id: tags:

 #### Szenario 1:
 Schreiben Sie die SQL-Befehle für folgende Vorgänge, und probieren Sie diese aus:
 - In einer Transaktion (T1) wird das Salär des Angestellten mit dem niedrigsten Salär um CHF 1'000 angehoben.
 - In einer weiteren Transaktion (T2) werden CHF 10'000 als Salärerhöhunggleichmässig auf alle Angestellten verteilt.

 Bestimmen Sie den minimalen Isolationsgrad, um diese Transaktionen korrekt zu isolieren. Betrachten Sie dazu folgenden verzahnten Ablauf und überlegen Sie, ob dieser zum korrekten Ergebnis führen würde:


 > T1: Starte Transaktion
  T2: Starte Transaktion
  T1: Suche den Angestellten X mit dem niedrigstem Salär
  T2: Bestimme die Anzahl Angestellter
  T1: Erhöhe das Salär des Angestellten X um 1000 Franken.
  T2: Verteile das Budget von 10'000 gleichmässig als Salärerhöhung für alle Angestellten
  T1: Ende Transaktion
  T2: Ende Transaktion

 Öffnen Sie für diese Aufgabe zwei Terminals und führen Sie `psql angproj` aus.
 Diese Aufgabe lässt sich nicht sinnvoll in einem Notebook lösen.
 Ordnen Sie das Fenster am besten wie gezeigt an:

 <details><summary>Beispiel für Fensteranordnung (klicken zum Anzeigen)</summary>

 ![image.png](attachment:4273b404-b7f0-48ae-b2b4-eecc431cabfe.png)

 </details>

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 Eingaben für $T1$ und $T2$ sind in 2 separaten `psql`-Sessions zu tätigen:
 ```sql
 -- T1: Starte Transaktion
 BEGIN TRANSACTION;

 -- T2: Starte Transaktion
 BEGIN TRANSACTION;

 -- T1: Suche den Angestellten X mit dem niedrigstem Salär
 SELECT persnr AS persnr_x
 FROM angestellter
 WHERE salaer = (
    SELECT min(salaer)
    FROM angestellter
 );
 -- T1: Resultat in Variable gemäss Spaltenname speichern:
 \gset

 -- T2: Bestimme die Anzahl Angestellter
 SELECT count(*) AS anzahl_angestellte
 FROM angestellter;
 -- T2: Resultat in Variable gemäss Spaltenname speichern:
 \gset

 -- T1: Erhöhe das Salär des Angestellten X um 1000 Franken.
 UPDATE angestellter
 SET salaer = salaer + 1000
 WHERE persnr = :persnr_x;

 -- T2: Verteile das Budget von 10'000 gleichmässig als Salärerhöhung für alle Angestellten
 UPDATE angestellter
 SET salaer = salaer + 10000 / :anzahl_angestellte;
 /*
 Beobachtung:
 Ausführung von T2 blockiert nun.
 */

 -- T1: Commit
 COMMIT;
 /*
 Beobachtung:
 Nun wurde das UPDATE in T2 ausgeführt.
 */

 -- T2: Commit
 COMMIT;
 ```

 In diesem Szenario beträgt der minimale Isolationsgrad `READ UNCOMMITTED`.
 Dies ist der schwächste Isolationsgad nach dem `ANSI SQL-92` Standard und in diesem Szenario genügend.
 Beachten Sie aber, dass dieser Isolationsgrad für die meisten Szenarien ungenügend ist.

 </details>

 %% Cell type:markdown id: tags:

 #### Szenario 2:
 Schreiben Sie die SQL-Befehle für folgende Vorgänge, und probieren Sie diese aus:
- In einer Transaktion (T1) wird Herbert Rey das Salär um CHF 3'000 gekürzt, dafür sein Bonus um CHF 8'000 erhöht.
- In einer weiteren Transaktion (T2) wird der gesamte Lohnaufwand (Saläre + Boni) der Firma ermittelt.
+- In einer Transaktion (T1) wird der gesamte Lohnaufwand (Saläre + Boni) der Firma ermittelt.
+- In einer weiteren Transaktion (T2) wird Herbert Rey das Salär um CHF 3'000 gekürzt, dafür sein Bonus um CHF 8'000 erhöht.

 Bestimmen Sie den minimalen Isolationsgrad, um diese Transaktionen korrekt zu isolieren. Betrachten Sie dazu folgenden verzahnten Ablauf und überlegen Sie, ob dieser zum korrekten Ergebnis führen würde:


 > T1: Starte Transaktion
  T2: Starte Transaktion
  T1: Bestimme die Summe aller Saläre der Angestellten
  T2: „Rey, Herbert" soll 3'000 weniger Salär erhalten, dafür 8'000 mehr Bonus.
  T1: Bestimme die Summe der Boni aller Angestellten
      => Aus der Summe der Saläre und Boni ergibt sich der gesamte Lohnaufwand.
  T1: Commit
  T2: Commit

 > Gehen Sie bei dieser Aufgabe wie beim vorherigen Szenario vor.

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 Eingaben für $T1$ und $T2$ sind in 2 separaten `psql`-Sessions zu tätigen:
 ```sql
 -- T1: Starte Transaktion
 BEGIN TRANSACTION;

 -- T2: Starte Transaktion
 BEGIN TRANSACTION;

 -- T1: Bestimme die Summe aller Saläre der Angestellten
 SELECT sum(salaer) AS salaersumme
 FROM angestellter;
 -- T1: Resultat in Variable gemäss Spaltenname speichern:
 \gset

 -- T2: „Rey, Herbert" soll 3'000 weniger Salär erhalten, dafür 8'000 mehr Bonus.
 UPDATE angestellter
 SET    salaer = salaer - 3000,
       bonus = bonus + 8000
 WHERE name = 'Rey, Herbert';

 -- T1: Bestimme die Summe der Boni aller Angestellten
 SELECT sum(bonus) AS bonisumme
 FROM angestellter;
 -- T1: Resultat in Variable gemäss Spaltenname speichern:
 \gset

 --     => Aus der Summe der Saläre und Boni ergibt sich der gesamte Lohnaufwand.
 SELECT :salaersumme + :bonisumme AS gesamter_lohnaufwand;

 -- T1: Commit
 COMMIT;

 -- T2: Commit
 COMMIT;
 ```

 Der minimale Isolationsgrad in diesem Szenario ist `REPEATABLE READ`.
 Würde ein schwächerer Isolationsgrad gewählt könnten zum Beispiel `Fuzzy Reads` auftreten,
 da sich Lohn und Bonus von Herbert Rey zwischen zwei Read-Operationen geändert hat und
 somit der gesamte Lohnaufwand nicht mit den Summen aus Bonus und Salär korrelieren.

 </details>

 %% Cell type:markdown id: tags:

 #### Szenario 3:
 Schreiben Sie die SQL-Befehle für folgende Vorgänge, und probieren Sie diese aus:
 - Ein neuer Angestellter wurde zu einem Salär von CHF 10'000 angestellt.
  - T1 fügt diesen in die Datenbank ein und erstellt danach einen SAVEPOINT.
  - T1 setzt dann den Bonus des neuen Angestellten auf CHF 30'000 fest.
  - T1 wird zum zuvor erstellten SAVEPOINT zurückgerollt und dann committet.
 - T2 erhöht die Saläre und Boni aller Angestellten um 1%

 Bestimmen Sie den minimalen Isolationsgrad, um diese Transaktionen korrekt zu isolieren. Betrachten Sie dazu folgenden verzahnten Ablauf und überlegen Sie, ob dieser zum korrekten Ergebnis führen würde:


 > T1: Starte Transaktion
  T2: Starte Transaktion
  T1: Füge einen neuen Angestellten X mit Lohn 10'000 ein (Einstellung)
  T1: Setze einen Savepoint
  T2: Erhöhe die Saläre aller Angestellter um 1%.
  T1: Setze den Bonus 30'000 für Angestellter X.
  T2: Erhöhe Bonus aller Angestellter um 1%.
  T1: Partieller Rollback zum letzten Savepoint
  T1: Commit
  T2: Commit

 > Gehen Sie bei dieser Aufgabe wie beim vorherigen Szenario vor.

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 Eingaben für $T1$ und $T2$ sind in 2 separaten `psql`-Sessions zu tätigen:
 ```sql
 -- T1: Starte Transaktion
 BEGIN TRANSACTION;

 -- T2: Starte Transaktion
 BEGIN TRANSACTION;

 -- T1: Füge einen neuen Angestellten X mit Lohn 10'000 ein (Einstellung)
 INSERT INTO angestellter
            (persnr,NAME,tel,salaer,chef,abtnr,wohnort)
 VALUES      (1234, 'Kuster, Peter', 843, 10000,
             1001, 1, 'Zuerich');

 -- T1: Setze einen Savepoint
 SAVEPOINT angesteller_erstellt;

 -- T2: Erhöhe die Saläre aller Angestellter um 1%.
 UPDATE angestellter ang
 SET    salaer = ang.salaer + ang.salaer * 0.01;

 -- T1: Setze den Bonus 30'000 für Angestellter X.
 UPDATE angestellter ang
 SET    bonus = 30000
 WHERE  ang.persnr = 1234;

 -- T2: Erhöhe Bonus aller Angestellter um 1%.
 UPDATE angestellter ang
 SET    bonus = ang.bonus + ang.bonus * 0.01;

 -- T1: Partieller Rollback zum letzten Savepoint
 ROLLBACK TO SAVEPOINT angesteller_erstellt;

 -- T1: Commit
 COMMIT;

 -- T2: Commit
 COMMIT;
 ```

 Hier muss der minimale Isolationsgrad auf `SERIALIZABLE` gesetzt werden.
 Wäre der Isolationsgrad schwächer könnte der Rollback in $T1$ in $T2$ zu einem `Phantom Read` in $T2$ führen.

 </details>

 %% Cell type:markdown id: tags:

 ### 3. Fehlerszenarien
 Versuchen Sie, die folgenden drei nebenläufigen Fehlerszenarien in SQL mit Beispielen anhand der Übungsdatenbank [AngProj](../Week%2006/01%20SQL%20DML%20Einleitung.ipynb) zu demonstrieren:
 - Dirty Read
 - Fuzzy Read (Inconsistent Analysis)
 - Phantom Read

 Ab welchem Isolationsgrad treten Ihre Szenarien in Postgres nicht mehr auf?

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 1. Dirty Reads können ab der Isolationsstufe `READ COMMITED` nicht mehr vorkommen.
 2. Fuzzy Reads können ab der Isolationsstufe `REPEATABLE READ` nicht mehr vorkommen.
 3. Phantom Reads können ab der Isolationsstufe `SERIALIZABLE` nicht mehr vorkommen.

 </details>

 %% Cell type:markdown id: tags:

 ### 4. Write Skew (optional, kein Prüfungsstoff!)
 Wir betrachten 2 Transaktionen:
 $T1 = r1(x) r1(y) w1(x) c1$
 und
 $T2 = r2(x) r2(y) w2(y) c2$

 Gegeben Sei folgender Schedule, der ein sogenannte Write Skew darstellt:
 $S = r1(x) r1(y) r2(x) r2(y) w1(x) w2(y) c1 c2$

 %% Cell type:markdown id: tags:

 Lösen Sie folgende Fragen:
 1. Ist dieser Schedule serialisierbar?

 %% Cell type:raw id: tags:

 Antwort:

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 Folgende Konfliktpaare lassen sich identifizieren:

 <table style="margin-left: 0">
 <tr>
 <td>

 $r1(x) < w1(x)$

 </td>
 <td>

 $r1(y) < w2(y)$

 </td>
 <td>

 $r2(x) < w1(x)$

 </td>
 <td>

 $r2(y) < w2(y)$

 </td>
 </tr>
 </table>

 Daraus wiederum lässt sich folgender Serialisierbarkeitsgraph ableiten:
 ![graph4.png](attachment:e0163350-bae4-49f8-8e51-f025680a3bb0.png)
 Anhand des Graphen ist sofort sichtbar, dass dieser Zyklen enthält und der Schedule $S$ entsprechend **nicht serialisierbar** ist.

 </details>

 %% Cell type:markdown id: tags:

 2. Was ist der minimale Isolationsgrad (nach SQL-92) für eine korrekt isolierte Ausführung der zwei Transaktionen T1 und T2?

 %% Cell type:raw id: tags:

 Antwort:

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 Der minimale Isolationsgrad ist `SERIALIZABLE`.

 </details>

 %% Cell type:markdown id: tags:

 3. Prüfen Sie in PostgreSQL, ob dieser Schedule mit diesem Isolationsgrad ausgeführt werden kann. Stimmt die Theorie in Postgres?

 %% Cell type:raw id: tags:

 Antwort:

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 In Postgres vor 9.1 ist das (sogar bei `SERIALIZABLE`) möglich, da Postgres _Snapshot Isolation_ verwendet (mehr dazu in der nächsten Vorlesung).
 In Postgres ab Version 9.1 wird `SERIALIZABLE` durch _Serializable Snapshot Isolation_ implementiert, das Write Skew ausschliesst.

 </details>

 %% Cell type:markdown id: tags:

 ### 5. Deadlock in PostgreSQL
 Wir betrachten folgenden Deadlock-Schedule:
 $S = w1(x) w2(y) w1(y) w2(x) c1 c2$

 Definieren Sie ein analoges SQL Beispielszenario für das Zugriffsmuster und probieren Sie es in PostgreSQL auf Basis der AngProj Datenbank aus.
 Tipp: Schauen Sie auf Folie 53 in "Transaktionen_Teil_1.pdf (auf Moodle)" mit Bob und Alice auf das SQL-Skript auf "Transaktionen_Teil_2_Demo.sql Datei".

 > Gehen Sie bei dieser Aufgabe wie bei Aufgabe 2 vor.

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 Analog zum gegebenen Schedule lassen sich zum Beispiel folgende zwei Transaktionen in SQL formulieren. Der Deadlock tritt sogleich nach $w(x)$ auf, da dann $T1$ auf $T2$ und umgekehrt $T2$ auf $T1$ wartet. PostgreSQL detektiert den Deadlock und bricht $T2$ ab (Rollback). $T1$ kann danach normal committed werden.

 <table>
    <caption>Verzahnter Ablauf</caption>
    <thead>
        <tr>
            <th style="border: 1px dashed gray;" scope="col">
            </th>
            <th style="border: 1px dashed gray;" scope="col">1. Terminal<br></th>
            <th style="border: 1px dashed gray;" scope="col">2. Terminal<br></th>
        </tr>
    </thead>
    <tbody>
        <tr>
            <th style="border: 1px dashed gray;" scope="row">\(T1\) starten<br></th>
            <td style="border: 1px dashed gray;">
                <div data-canvas-width="152.84384284903143"><span class="" style="font-family: Courier New, Courier, mono;">BEGIN TRANSACTION</span></div>
                <div><span class="" style="font-family: Courier New, Courier, mono;">ISOLATION LEVEL READ COMMITTED;</span></div>
            </td>
            <td style="border: 1px dashed gray;"></td>
        </tr>
        <tr>
            <th style="border: 1px dashed gray;" scope="row">\(T2\) starten<br></th>
            <td style="border: 1px dashed gray;"></td>
            <td style="border: 1px dashed gray;">
                <div data-canvas-width="152.84384284903143"><span class="" style="font-family: Courier New, Courier, mono;">BEGIN TRANSACTION</span></div>
                <div><span class="" style="font-family: Courier New, Courier, mono;">ISOLATION LEVEL READ COMMITTED;</span></div>
            </td>
        </tr>
        <tr>
            <th style="border: 1px dashed gray;" scope="row"><span>\(w1(x)\)</span></th>
            <td style="border: 1px dashed gray;">
                <div data-canvas-width="171.02905724302684"><span class="" style="font-family: Courier New, Courier, mono;">UPDATE angestellter</span></div>
                <div data-canvas-width="81.56933895456898"><span class="" style="font-family: Courier New, Courier, mono;">SET salaer = 6000.00</span></div>
                <div><span class="" style="font-family: Courier New, Courier, mono;">WHERE name = 'Steiner, Hans';</span></div>
            </td>
            <td style="border: 1px dashed gray;"></td>
        </tr>
        <tr>
            <th style="border: 1px dashed gray;" scope="row"><span><span>\(</span>w2(y)\)</span>
            </th>
            <td style="border: 1px dashed gray;"></td>
            <td style="border: 1px dashed gray;">
                <div data-canvas-width="171.02905724302684"><span class="" style="font-family: Courier New, Courier, mono;">UPDATE angestellter</span></div>
                <div data-canvas-width="81.56933895456898"><span class="" style="font-family: Courier New, Courier, mono;">SET salaer = 5000.00</span></div>
                <div><span class="" style="font-family: Courier New, Courier, mono;">WHERE name = 'Pauli, Monika';</span><br></div>
            </td>
        </tr>
        <tr>
            <th style="border: 1px dashed gray;" scope="row"><span><span>\(</span>w1(y)\)</span>
            </th>
            <td style="border: 1px dashed gray;">
                <div data-canvas-width="171.02905724302684"><span class="" style="font-family: Courier New, Courier, mono;">UPDATE angestellter</span></div>
                <div data-canvas-width="81.56933895456898"><span class="" style="font-family: Courier New, Courier, mono;">SET bonus = 2000.00</span></div>
                <div><span class="" style="font-family: Courier New, Courier, mono;">WHERE name = 'Pauli, Monika';</span><br><br><span class="" style="color: rgb(153, 153, 153); font-family: Courier New, Courier, mono;">-- T1 wartet auf T2</span><br></div>
            </td>
            <td style="border: 1px dashed gray;"></td>
        </tr>
        <tr>
            <th style="border: 1px dashed gray;" scope="row"><span><span>\(</span>w2(x)\)</span>
            </th>
            <td style="border: 1px dashed gray;"></td>
            <td style="border: 1px dashed gray;">
                <div data-canvas-width="171.02905724302684"><span class="" style="font-family: Courier New, Courier, mono;">UPDATE angestellter</span></div>
                <div data-canvas-width="81.56933895456898"><span class="" style="font-family: Courier New, Courier, mono;">SET bonus = 3000.00</span></div>
                <div><span class="" style="font-family: Courier New, Courier, mono;">WHERE name = 'Steiner, Hans';</span></div>
                <div><br></div>
                <div><span class="" style="color: rgb(153, 153, 153); font-family: Courier New, Courier, mono;">-- ERROR: deadlock detected</span><br></div>
            </td>
        </tr>
        <tr>
            <th style="border: 1px dashed gray;" scope="row"><span>\(</span>c1\)</th>
            <td style="border: 1px dashed gray;"><span class="" style="font-family: Courier New, Courier, mono;">COMMIT;</span></td>
            <td style="border: 1px dashed gray;"></td>
        </tr>
        <tr>
            <th style="border: 1px dashed gray;" scope="row"><span>\(</span>c2\)</th>
            <td style="border: 1px dashed gray;"></td>
            <td style="border: 1px dashed gray;"><span class="" style="font-family: Courier New, Courier, mono; color: rgb(153, 153, 153);">-- nicht möglich, da Transaktion bereits abgebrochen</span><br><span class="" style="font-family: Courier New, Courier, mono;">COMMIT;</span><span class=""
                    style="color: rgb(153, 153, 153); font-family: Courier New, Courier, mono;"></span><br></td>
        </tr>
    </tbody>
 </table>

 </details>

 %% Cell type:markdown id: tags:

 ### 6. Deadlock in PostgreSQL
 Wir betrachten folgenden Deadlock-Schedule:
 $S = w1(x) r2(y) w2(y) w3(z) w1(y) r2(y) w2(z) w3(x)$

 %% Cell type:markdown id: tags:

 Fragen:
 1. Zeichnen Sie den dazugehörigen Betriebsmittel-Graphen sowie den Wartegraphen für den Zeitpunkt am Ende des Schedules.

 %% Cell type:raw id: tags:

 Antwort:

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 Betriebsmittel-Graph
 ![Betriebsmittel-Graph.png](attachment:36de1071-c27d-4be2-902e-a83129e33572.png)

 Wartegraph
 ![Wartegraph.png](attachment:3b2cb754-8608-43ae-8040-6ef274ab7c6d.png)

 </details>

 %% Cell type:markdown id: tags:

 2. Wie lässt sich der Deadlock beheben?

 %% Cell type:raw id: tags:

 Antwort:

 %% Cell type:markdown id: tags:

 <details><summary><strong>Musterlösung</strong> (klicken zum Anzeigen)</summary>

 In diesem Beispiel lassen sich ein Zyklus identifizieren:
 $T1 \rightarrow T2 \rightarrow T3 \rightarrow T1$

 Um den Deadlock zu lösen, müssen wir eine der im Zyklus vorkommenden Transaktionen zurücksetzen. Das heisst, wir haben mehrere Transaktionen zur Auswahl, um den Deadlock zu beheben. Grundsätzlich gilt: Je nachdem welche Transaktion gewählt wird, bewirkt dies andere Effekte bei der Rücksetzung (Minimierung des Rücksetzungsaufwands, Maximierung der freigegebenen Ressourcen, etc.). Da in diesem Beispiel aber alle Transaktionen gleich viele Ressourcen besetzen, ist es egal, welche Transaktion wir zurücksetzen. Wir wählen zum Beispiel $T3$.

 </details>