Title: IN0008_GDB / GDB: Kapitel 11: Mehrbenutzersynchronisation
On every note of this deck, unless a note says otherwise:
Title: IN0008_GDB::GDB: Kapitel 11: Mehrbenutzersynchronisation
Logo: tum_logo.png

Front: Was ist das Phantomproblem?
Back: Arbeiten auf unterschiedlichen Datensätzen während der Ausführung der TA (durch äußere Einflüsse, wie andere TAs).

Front: Was besagt das Serialisierbarkeitstheorem?
Back: Eine Historie H ist genau dann serialisierbar, wenn der zugehörige Serialisierbarkeitsgraph SG(H) azyklisch ist.

Front: Was versteht man unter einer topologischen Sortierung des Serialisierbarkeitsgraphen (SG)?
Back: Eine Sequentielle Anordnung der Transaktionen des SG in der Form, dass keine Transaktion T_i vor einer Transaktion T_j steht, wenn es einen gerichteten Pfad von T_j nach T_i im Serialisierbarkeitsgraphen gibt.

Front: Was ist die Minimalanforderung bezüglich der Recovery und in Folge rücksetzbaren Historien?
Back: Man kann noch aktive Transaktionen jederzeit abbrechen, ohne das andere schon mit commit abgeschlossene Transaktionen ungültig werden.

Front: Wann bezeichnet man eine Historie als rücksetzbar?
Back: Falls immer die schreibende Transition T_i vor der lesenden Transaktion T_i ihr commit durchführt, also c_j <_H c_i.
Also wenn alle Transaktionen, von denen sie gelesen hat, beendet sind.

Front: Welchen unangenehmen Effekt können selbst rücksetzbare Historien verursachen?
Back: Das Rücksetzen einer Transaktion kann eine Lawine von weitern Rollbacks auslösen.

Front: Wann vermeidet eine Historie kaskadierendes Rücksetzen?
Back: Wenn c_j <_H r_i(H) gilt, wann immer T_i ein Datum A von T_j liest.
Änderungen werden erst nach dem commit freigegeben.

Front: Was versteht man unter strikten Historien?
Back: Bei strikten Historien dürfen auch veränderte Daten einer noch laufenden Transaktion nicht überschrieben werden.

Front: Nenne alle 4 Historienklassen
Back: 1. SR: serialisierbare Historien (SeRializable)
2. RC: rücksetzbare Historien (ReCoverable)
3. ACA: Historien ohen kaskadierendes Rücksetzen (Avoiding Cascading Abort)
4. ST: Strikte (STrict) Historien

Front: Was ist die Aufgabe des Datenbank-Schedulers?
Back: Einzeloperationen verschiedener TAs in einer Reihenfolge ausführen, sodass die Historie mindestens serialisierbar ist. (Oft auch ACA verlangt)

Front: Welche zwei Synchronisations-Methoden werden u.A. vom Datenbank-Scheduler eingesetzt?
Back: - sperrbasierte Synchronisation
- Zeitstempel-basierte Synchronisation

Front: Welche zwei Sperrmodi gibt es bei der sperrbasierten Synchronisation?
Back: Sperrmodi werden je nach Operation (read, write) unterschieden:
- S (shared, read lock, Lesesperre): Mehrere TAs können gleichzeitig ein Objekt lesen.
- X (exclusive, write lock, Schreibsperre): Nur eine TA darf Zugriff auf das Objekt haben.

Front: Was wird von einer Transaktion bei dem Zwei-Phasen-Sperrprotokoll (2PL) verlangt?
Back: 1. TA muss jedes verwendete Objekt zuvor sperren
2. TA besitzt nur eine Sperre pro Objekt
3. Falls eine Sperre nicht gewährt wird, muss die TA warten
4. Eine TA durchläuft Wachstumsphase und Schrumpfungsphase
5. Bei EOT (TA-Ende) müssen alle Sperren zurückgegeben werden

Front: Was ist das Problem bei 2PL?
Back: 2PL garantiert zwar Serialisierbarkeit, aber nicht ACA (Historien ohen kaskadierendes Rücksetzen).

Front: Was ist der Unterschied zwischen dem normalen und strengen 2PL-Protokol?
Back: - Anforderungen (1) bis (5) des 2PL-Protokolls bleiben erhalten
- Es gibt keine Schrumpfungsphase mehr. Alle Sperren werden erst zum EOT freigegeben.

Front: Wie ist ein Wartegraph aufgebaut?
Back: - Gerichtete Kanten
- Wenn T_i auf Freigabe einer Sperre durch T_j wartet, wird die Kante T_i -> T_j eingefügt
- Erkennung anhand von Zyklen

Front: Was versteht man unter Preclaiming
Back: TAs werden erst begonnen, wenn alle ihre Sperranforderung schon bei BOT erfüllt werden können.
-> In der Praxis meist nicht realisierbar

Front: Wie funktioniert die Deadlock-Vermeidung mittels Time-out Verfahren?
Back: Falls TA innerhalb eines gewählten Zeitmaßes (z.B.: 1s) keinen Fortschritt erzielt, wird sie zurückgesetzt.

Front: Nenne ein Problem bei der Deadlock-Vermeidung mittels Time-out Verfahren?
Back: Es ist schwer ein gutes Zeitmaß zu finden.

Front: Wie funkioniert das Zeitstempel Verfahren?
Back: Priorisierungsverfahren, welches das Alter von TAs vergleicht. Zurücksetzen von TAs entweder nach wound-wait oder wait-die Verfahren.

Front: Nenne ein Problem bei der Deadlock-Vermeidung mittels Zeitstempel Verfahren?
Back: I.A. werden zu viele TAs zurückgesetzt, ohne dass tatsächlich ein Deadlock auftreten würde.

Front: Nenne die Sperrmodi beim Multi-Granularity Locking (MGL)?
Back: - NL: Keine Sperrung (no lock)
- S: Lesesperre
- X: Schreibsperre
- IS (Intention Share): Weiter unten in der Hierarchie ist eine Lesesperre beabsichtigt
- IX (Intention Exclusive): Weiter unten in der Hierarchie ist eine Schreibsperre beabsichtigt