• Transaktion
  Folge von Aktionen (read/write) die die DB von einem konsistenten Zustand in einen anderen Konsistenten Zustand überführt.
• Hauptaufgabe der Transaktionen - Verwaltung
  • Synchronisation (Koordination von mehreren Benutzerproxessen ⇒ Logische Einbenutzerbetrieb)
  • Recovery (Behebung von Fehlersituationen)
• Eigenschaften von Transaktionen (ACID-Prinzip)
  • Atomicy (Atomarität: EffektTransaktion trifft ganz oder gar icht in ???)
  • Consistency (Konsistenz/Integritätserhaltung: Konsistenter Zustand ⇒ Konsistenter Zustand)
  • Isolation (Isoliertheit: Logischer Einbenutzerbetrieb)
  • Durability (Dauerhaftigkeit, Persistenz)
• Schedule
  Folge von Aktionen (read/write) für eine Menge $\{T_1, \ldots, T_n\}$ von Transaktionen, die durch Mischen der Aktionen der Transaktionen entsteht, wobei die Reihenfolge innerhalb der Transaktionen beibehalten wird.
• Serieller Schedule
  Schedule S von $\{T_1, \ldots, T_n\}$, in dem die Aktionen der einzelnen Transaktionen nicht unter einander verzahnt sind, sondern sin Blöcken hintereinander ausgeführt werden
• Serialisierbarer Schedule
  Schedule S von $\{T_1, \ldots, T_n\}$, der die selbe Wirkung hat, wie ein belibiger serieller von $\{T_1, \ldots, T_n\}$ ⇒ Nur serialisierbarer Schedules dürfen zugelassen werden!

Mögliche Abhängigkeiten

• rw
• wr
• ww

Für $S_1$ $T_1$ = (r(v), w(v)) $T_2$ = (w(x), w(w), r(v)) $T_3$ = (w(z), r(y), w(x)) $T_4$ = (r(w), r(z), W(y))

⇒ Gleiche Tranasktions- & Aktionsmenge!

Abhängigkeiten:

• $S_1$: $rw_{4,2}(w), wr_{1,2}(v), wr_{3,4}(z), ww_{2,3}(x), rw_{3,4}(y)$
• $S_2$: $rw_{4,2}(w), wr_{1,2}(v), ww_{2,3}(x), rw_{4,3}(z), rw_{3,4}(y)$

⇒ $S_1$ & $S_2$ sind nicht Konfliktäquivalent!

⇒ Gleiche Tranasktions- & Aktionsmenge!

Abhängigkeiten:

• $S_1$: $rw_{4,2}(w), wr_{1,2}(v), wr_{3,4}(z), ww_{2,3}(x), rw_{3,4}(y)$
• $S_3$: $wr_{3,4}(z), wr_{1,2}(v), ww_{2,3}(x), rw_{4,2}(w), rw_{3,4}(y)$

⇒ $S_1$ & $S_2$ sind Konfliktäquivalent!

Serialisierungs-/Abhängigkeitsgraph:

• Knoten: Transaktionen
• Kanten: Abhängigkeiten
• Zyklenfrei: Topologische Ordnung = serielle Ausführung
• enthält zyklen: S ist nicht seriallisierbar

a) T1, T2, T4, T3 oder T1, T4, T2, T3 b) nicht serialisierbar

• a): Lost Update $S(r_1(x), w_2(x), w_1(x))$
  ⇒ Änderungen einer Transaktion werden durch eine andere Transaktion überschrieben und gehen verloren.
• b): Dirty Read/Write: $S(w_1(x), r_2(x), w_1(x))$
  ⇒ Zugriff auf “Schmutzige” Daten ⇒ Objekte, die von einer noch nicht beendenen Transaktion geändert werden
• c): Non-Repeatable Read: $S(r_1(x). w_2(x), r_1(x)$
  ⇒ Transaktion liest unterschiedliche Werte des selben Objekts

⇒ Annomalien können nur auftreten, wenn Isolation verletzt wird!

Legaler Schedule

• LOCK (L) vor jedem Zugriff
• UNLOCK (U) spätestens bei TA=Ende
• Keine TA fordert Sperre an, die sie bereits besitzt
• Sperren werden respektiert
• Man darf keine sperren zurückgeben, die man nicht hat

• 2-Phasen-Sperrprotokoll (2PL):
  1. Wachstumsphase (lock)
  2. Schrumpfungsphase (unlock)

Problem von 2PL: Kaskadierendes Rücksetzen (T1 wird nach U1(x) zurückgesetzt (ABORT) ⇒ alle T2. die nach U1(x) auf x zugegriffen haben, müssen auch zurückgesetzt werden ⇒ Durability

• Striktes 2PL
  • alle Sperren werden bis zum COMMIT gehalten
  • COMMIT wird atomar durchgeführt

Es gild

• 2PL ⇒ serialisierbar
• serialisierbar NOT ⇒ 2PL

S0

• wird nicht freigegeben vor TA ende
• T2 gibt sperre frei, die sie nie hatte
• ⇒ Nicht legal

S1

• nicht legal, da sperre auf x doppelt vergeben wird
• ⇒ Nicht legal

S2

• ⇒ Legal
• ⇒ Nicht 2PL, da T1 nach U1(x) noch L1(y) anfordert
• ⇒ s2 ist serialisierbar, da keine Abhängigkeiten zu T1 & T2!

S3

• Unlock von T1 nicht atomar ⇒ kein striktes 2PL
• TODO

S4

• ⇒ Legal
• ⇒ 2PL erfüllt

Verklemmung bezgl. Zugriff auf Verschiedene Objekte:

1. T1 hält x(x)
2. T1 will x(y)
3. T2 hält x(y)
4. T2 will x(x)

⇒ Verlemmung, da T1 und T2 gegenseitig warten

Verklemmung bzgl. Sperrkonversion: T1 und T2 warten gegenseitig, aber weil das Protokoll es so will

Verhungern einer Transaktion auf erforderliche Sperre.

bestehend → angefordert	R	X
R
X

bestehend → angefordert	R	U	X
R
U
X

bestehend → angefordert	R	A	X
R
A
X

	RX	RUX	RAX
a)
b)
c)

	R	X	IR	IX	RIX
R
X
IR				X	X
IX			X	X
RIX			X

IR-Sperre: tiefere Ebene hat R-Sperre IX-Sperre: tiefere Ebene hat X-Sperre RIX-Sperre:Volle lesesperre, tiefe schreibsperre (R-IX-Sperre)

a) R-Sperre auf Tutpelebene entspricht IR-Sperre (auf Relationsebene) ⇒ Falls es sich um das selbe Tupel handelt, darf die Sperre nicht vergeben werden, sonst schon

b)

• Phantomproblem: Spätere Generierung eines Tupels , das während der Abarbeitung hätte berücksichtigt werden müssen.
• Hierachisches Sperren: Für Aggregartfunktionen R-Sperre auf gesammter Relation anfordern, Einfügen würde IX-Sperre anfordern, die aber nicht gewährt wird.

• DB-Anwendung
• DBS
  • DBMS
  • DB

• Falsch
  Die Knoten sind die Transaktionen
• Wahr
• Wahr
  mindestens alles was ich
• Fals
  Das währe FOCC

Zyklus in Graph ⇒ Es liegen verklemmungen vor

• Jüngere TA hält Sperre
  ⇒ ältere TA “verwundet” (wound) jüngere TA; jüngere TA wird zurückgesetzt!
• Ältere TA hält Sperre
  ⇒ jüngere TA “wartet” (wait)

• $L_1(y)$ ⇒ $T_3$ wird zurückgesetzt
• $L_2(z)$ ⇒ $T_2$ wartet
• $L_1(x)$ ⇒ $T_2$ wird zurückgesetzt
• $L_3(x)$ ⇒ $T_3$ bereits zurückgesetzt

⇒ $T_1$ kommt durch

• Jüngere TA hält Sperre
  ⇒ ältere TA “wartet” (wait)
• Ältere TA hält Sperre
  ⇒ ältere TA “tötet” (die) jüngere TA; jüngere TA wird zurückgesetzt!

• $L_1(y)$ ⇒ $T_1$ wartet
• $L_2(z)$ ⇒ $T_2$ wird zurückgesetzt
• $L_1(x)$ ⇒ $T_1$ wartet bereits auf die Freigabe von y
• $L_3(x)$ ⇒ $T_3$ bekommt sperre, da $T_2$ zurückgesetzt wurde und $T_1$ noch auf die Freigabe von y wartet (nicht so weit kam sich x zu schnappen)

⇒ $T_3$ & $T_1$ kommen durch

$T_2, T_3, T_5, T_4, T_1$

• Integration einheitlicher Zugriff auf alle Daten einer Anwendung
• Operationen auf den Daten (ändern, löschen, …)
• Data Dictionary Schema anschauen
• Benutzersicheten views
• Konsistenzüberwachung bei Änderung
• Zugriffskontrolle
• Transaktionen
• Synchronisation (Mehrbenutzersystem)
• Datensicherung

• Datensystem (deskriptive Anfragen, Mengenzugriffe)
• Zugriffssystem (Satzzugriffe)
• Speichersystem (Seitenzugriffe)
• DB (Blocktransfer)

Neben an:

• Transfermanagement???
• Metadatenverwaltung

Drüber:

• Anwendung

Loggranulat ⇐ Sperrgranulat, sonst Lost Updates ???

Update-in-place: geänderte Werte auf ursprüngliche Pos

Einbringstrategien

• direktes Einbringne (???-in-phase)
  • Geänderte Werte werden auf ihre ursprüngliche Position zurückgeschrieben. d.h. Schreibe ist gleichzeitig Einbringen i.d. DB

• WAL-Prinzip (Write-Ahead-Log)
  UNDO Info muss vor Einbringen der änderungen in der DB in der Log-Datei stehen
  ⇒ relevant für Steal

denn sonsst: 4-1 c) Schritt 4 (save[B', D]) findet vor EOT1 statt, d.h. wenn WAL-Prinzip verletzt würde, also keine Protokollierung hat Statgefunden & T1 wird zurückgespult ⇒ ursprünglicher Zustand d. DB kann nicht hergestellt werden

• Commit-Regel (Force log ab commit):

REDO Info muss vor COMMIT-Durchführung in der Log-Datei stehen (⇒ relevant für No-Focre)

Aufgabe des Logging:

• Jede Änderung auf der DB im Normalbetrieb wird protokolliert:
  • REDO: Informationen zum Nachvollziehen der Änderungen erfolgreicher TAs
  • UNDO: Informationen zum Zurücknehmen der Änderungen unvollständiger transaktionen
• Klassifikation von Logging-Verfahren:
  • physisch: Protokoll auf Ebene der Seiten, Datensätze, Indexeinträge
    • Zustands-Logging: aller Zustands Before-Image (BFIM), neuer Zustand After-Image (AFIM)
    • Übergangs-Logging: Speicherung der Zustandsdifferenzen
  • Logisch: Speicherung der Änderungsoperationen mit ihren Parametern → kürzere Logeinträge
  • PhysiologischL Kombination aus beidem
• Struktur der Log-Einträge für Anderungen:
  • LSN (Log Sequence Number): Eindeutige Kennung des Log-Eintrags in chronologischer Reihenfolge
  • TA-ID: Eindeutige Kennung der TA, die die Änderung durchgeführt hat
  • Page-ID: Kennung der Seite auf der die Änderungsoperation vollzogen wurde (ein Eintrag pro geänderter Seite)
  • REDO: Gibt an, wie die Änderung nachvollzogen werden kann
  • UNDO: Beschreibt, wie die Änderung rückgängig gemacht werden kann
  • PerLSN: Zeiger auf den vorhergehenden Log-Eintrag der jeweiligen TA (Effizienzgründe)
• Log-Sätze: Ein Log-Satz wird für jede der follgenden Aktionen geschrieben: UPDATE, COMMIT, ABORT, END, CLR
  • CLR (Compensation Log Record): Beim Zurücksetzen der TA (UNDO) werden Aktionen rückgängig gemacht, das Logging hiervon geschieht durch das Schreiben eines CLR.

Weitere Datenstrukturen beim Recovery:

• TA-Tabelle:
  • Ein Eintrag pro aktive TA
  • Enthält
    • TA-ID
    • Status (running / commited / aborted)
    • LastLSN (letzte vergebe LSN)
• DirtyPage-Tabelle: nachführen aler bereits abgeschlossenen TAs, die noch nicht in die DB eingebracht wurden.
  • Ein Eintrag pro Schmutziger Seite im Puffer
  • Einthält recLSN (LSN des Log-Satzes, durch den erstmals die Seite schmutzige wurde)

Phasen der Crash-Recovery:

1. Analysephase
   1. Lies Log-Datei von letztem Check Point bis Ende
   2. Bestimme Gewinner & Verlierer TAs:
      • Gewinner: COMMIT-Satz in Log
      • Verlierer: Kein COMMIT-Satz im Log
   3. Ermittler geänderte Seiten
2. REDO-Phase
   1. Vorwärtslesen der Log-Datei, ausgehend vom letzten Sicherungspunkt.
   2. Wiederholen der Änderunge die noch nicht in der DB stehen pageLSN(DB) < LSN
      • Vollständiges REDO: Wiederholung aller UPDATES & LLRs (auch der abgebrochenen TAs)
      • Selektives REDO: Wiederhochung der Updates der Gewinner TAs & LLRs
3. UNDO-Phase
   1. Rückwärtslesen der Log-Datei bis BOT der ältesten Verlierer TA
   2. Verlierer TAs zurücksetzen
      • Vollständiges REDO: Nur wenn Fehlerzeitpunkt laufende TAs zurücksetzen
      • Selektives REDOL alle verlierer TAs zurücksetzen genau dann wenn LSN ⇐ pageLSN(DB)

• Gewinner TAs: $T_1$ & $T_3$
• Verlierer TAs: $T_2$ & $T_4$
• Betroffene Seiten: $P_A$, $P_B$, $P_C$, $P_D$, $P_E$

Idempotenz von UNDO & REDO:
REDO- und UNDO-Phasen müssen idempotent sein, d.h. sie müssen auch bei mehrfacher Ausführung immer wieder das selbe Ergebniss liefern: $f(f(x)) = f(x)$

Idempotenz von REDO wird durch Check der pageLSN (Platte) sichergestellt.

Idempotenz von UNDO wird durch CLRs sichergestellt.

Vollständiges REDO:

UNDO:

Slektives REDO:

UNDO:

SELECT
  s.Name
FROM
  student s, 
  lehrveranstaltung v, 
  Dozent d, 
  Hoert h, 
  Haelt hl
WHERE
  d.Titel = "Prof." AND
  d.Name = "Einstein" AND
  v.LVType = "Seminar" AND
  s.MatrNr = h.MatrNr
  h.LVNr = v.LVNr AND
  hl.LVNr = v.LVNr AND
  hl.DozNr = d.DozNr AND 

• Selektionen nach unten Verschieben.
  • Name & Titel nach unten zu Dozenten verschieben
  • Vortragstyp “Seminar” nach unten verschieben (zu Lehrveranstaltungen)
• Kreuzproduktreihenfolge ändern
  • Weniger Dozenten als LVs
  • Weniger LVs als Studenten …

Anmerkung 1: Es bleiben genau die Tupel erhalten, für die gilt d.DozNr = hl.DozNr d.h. für ursprünglich jedes Tupel aus Haelt bleibt genau ein Tupel aus der neuen Relation erhaten $\hat = \nicefrac{1}{5}$.

Anmerkung 2: Die 10 Tupel nach s.MatrNr = h.MatrNr entsprechen genau den Elementen aus Hoert ⇒ vgl. h.LVNr mit v.LVNr ⇒ 2, 9, 9, 7 ⇒ 4 Tupel

• Atomic (Wenn, dann wird man als ganzes abgebrochen)
• Consistency (Konsistenter Zystand → Konsistenter Zustand)
• Isolation (Man muss sich aleine fühlen)
• Durability (Abgeschlossene Transaktionen sind von dauer)

Non-repeatable read mit Aggregiertem read

Graph Zeichen

• Knoten: Transaktionen
• Kanten: Abhängigkeiten

Kein rr(x)

Zyklenfrei? ⇒ Serialisierbar durch topologisches sorieren

• Pessimistische Ablaufsteuerung (Locking)
• Optimistische Ablaufsteuerung (Zeitstempelverfahren)
  Notfalls rollback