Datenbanksysteme Klausurvorbereitung

Transaktionen

ACID-Bedingungen

Bedingung	Beschreibung
Atomicity	- Transaktion ist kleinste, atomare Ausführungseinheit - Entweder alle Änderungen durch Transaktion in der Datenbasis werden wirksam oder gar keine
Consistency	- Transaktion überführt Datenbank von konsistentem Zustand in anderen konsistenten Zustand - (Inkonsistenzen innerhalb Transaktionen erlaubt)
Isolation	- Transaktion ist gegenüber anderen Transaktionen isoliert - Ergebnis einer Transaktion kann nicht direkt durch andere Transaktionen beeinflusst werden - Jede Transaktion wird logisch so ausgeführt, als gäbe es keine andere Transaktion
Durability	- Wirkung einer Transaktion auf Datenbasis bleibt nach erfolgreichem Abschluss dauerhaft erhalten - auch bei Systemfehlern

Ausführungspläne

Beispiel

$H = < T1.bot(),\ T2.bot(),\ T3.bot(),\ T1.r(a),\ T2.r(a),\\ T3.w(b),\ T2.w(a),\ T2.r(b),\ T1.c(),\ T2.a(),\ T3.c()>$

Elementaroperationen

Operation	Beschreibung
.bot()	Initialisierung (wird oft nicht explizit genutzt)
.r(a) .read(a, var_A)	Lesen von Objekt a und Übergabe an Programmvariable A
.w(b) .write(b, var_B)	Schreiben von Programmvariable B in Objekt b
.a() .abort()	Abbruch der Transaktion (alle Änderungen werden unwirksam)
.c() .commit()	Erfolgreiche Beendigung der Transaktion (Änderungen werden geschrieben)

Ordnungsrelationen

mit Ordnungsrelation H:

$T1.bot() <_H T2.bot() <_H T3.bot() <_H T1.r(a) <_H T2.r(a) <_H T3.w(b)\\ <_H T2.w(a) <_H T2.r(b) <_H T1.c() <_H T2.a() <_H T3.c()$

auch innerhalb einzelner Transaktionen:

$T1.bot() <_{T1} T1.r(a) <_{T1} T1.c()$

$T2.bot() <_{T2} T2.r(a) <_{T2} T2.w(a) <_{T2} T2.r(b) <_{T2} T2.a()$

$T3.bot() <_{T3} T3.w(b) <_{T3} T3.c()$

Synchronisationsprobleme

Lost update

Es läuft gerade die Buchung des monatlichen Gehalts
gleichzeitig werden die letzten 100,-€ am Geldautomaten abgehoben
Beiden Transaktionen lesen den Kontostand + 100,-€ auf dem Konto
Zuerst wird das neue Guthaben (100,-€ + Gehalt) auf des Konto geschrieben
Dann werden 100,-€ aus dem Geldautomaten gezahlt und der neue Kontostand wird auf 0,-€ gesetzt

T1.r(Kontostand);\\ T2.r(Kontostand);\\ T1.w(Kontostand);\\ T1.c();\\ T2.w(Kontostand);\\ T2.c();

Das Gehalt ist zwar eingegangen, aber der neue Kontostand mit Gehalt ist zwischenzeitlich verloren gegangen.

Inkonsistente Sicht auf die Datenbank

Das Konto eines Unternehmers ist für die üblichen monatlichen Ausgaben gerade ausreichend gedeckt.
Eine automatischen Transaktion (T1) der Bank bucht die monatlichen Ausgaben als Daueraufträge und zieht nacheinander die beauftragten Lastschriften seiner Kinden auf das Konto gut
Er möchte nun am Geldautomaten (T2) 500,-€ abheben. Der Geldautomat verneint den Wunsch, da obige Transaktion gerade alle Ausgaben gebucht hat und der Verfügungsrahmen überzogen wäre.
Er versucht es verärgert erneut. Nun hat die automatische Transaktion alle Lastschriften gutgeschrieben und der Geldautomat (T3) liefert 500,-€

T1.r(Kontostand);\\ T1.w(Kontostand);\\ ...\\ T1.w(Kontostand);\\ T2.r(Kontostand);\\ T2.c();\\ T1.w(Kontostand);\\ ...\\ T1.w(Kontostand);\\ T1.c();\\ T3.r(Kontostand);\\ T3.w(Kontostand);\\ T3.c();

Veränderungen können zwischenzeitlich Inkonsistenzen erzeugen, die jedoch bereinigt werden. Ohne entsprechende Isolation werden jedoch andere Transaktionen beeinflusst.

inkonsistente Datenbank

$K_1$ $K_2$
- $K_1 + K_2 \ge 0$
- $K_1 = -200$ €
- $K_2 = +200$ €
T1 $K_1$ $K_2$ aus
Transaktion T2100€ $K_1$ aus
$K_1 + K_2 = -100 + 1 = -99 \ngeq 0$

T1.r(K_1);\\ T1.r(K_2);\\ T1.w(K_1);\\ T2.r(K_1);\\ T2.r(K_2);\\ T2.w(K_1);\\ T2.c();\\ T1.w(K_1);\\ T1.c();

Das zwischenzeitlich erzeugte Guthaben von T1 konnte T2 nutzen, um 100€ auszuzahlen und die Datenbank in einen inkonsistenten Zustand zu bringen.

Phantom-Problem

Transaktion T1 liest n Elemente von A in Array a ein.
Transaktion T2 fügt ein n+1-tes Element in A ein.
Transaktion T1 wird erst danach mit Summenberechnung b fertig.

Die Summenberechnung in T1 berücksichtigt also das n+1-te Element (= Phantomobjekt) nicht.

H = < T1.bot();\ T1.read(A[1],a[1]);\ ...;\ T1.read(A[n], a[n]),\ b = \sum_{i=1}^{n}{a[i]};\\ T2.bot();\ a[n+1] = 1,\ T2.write(A[n + 1],\ a[n+1]);\ T2.commit();\\ T1.write(B,b);\ T1.commit(); >

Serialisierbarkeit

äquivalente Ausführungspläne

$T^*$ mit den Ausführungsplänen G und H.

H und G sind äquivalent, falls ihre Konflikte identisch sind.

$T_1, T_2 \in T^*$ :

$T_1.r(A) <_H T_2.w(A) \Leftrightarrow T_1.r(A) <_G T_2.w(A)$
$T_1.w(A) <_H T_2.r(A) \Leftrightarrow T_1.w(A) <_G T_2.r(A)$
$T_1.w(A) <_H T_2.w(A) \Leftrightarrow T_1.w(A) <_G T_2.w(A)$

serialisierbare Ausführungspläne

Ein Ausführungsplan ist serialisierbar, wenn es einen äquivalenten sequentiellen Ausführungsplan gibt.

Beispiel: (sequentieller Ausführungsplan)

H = < T1.bot,\ T1.r(a),\ T1.c,\ T3.bot,\ T3.w(b),\ T3.c,\\ T2.bot,\ T2.r(a),\ T2.w(a),\ T2.r(b),\ T2.c >

$G_H$

gerichteter $G_H = (K,U)$ $K$ $U \subseteq K \times K$ $H$ .

Transaktion $T \in T^*$ gibt es genau einen Knoten mit Label T
$(T_1,T_2) \in U \Leftrightarrow$ H $T_1$ $T_2$

H $G_H$ zyklenfrei ist.

Beispiel

Konflikte:

$T1.r(a) <_H T2.w(a)$
$T3.w(b) <_H T2.r(b)$

Der Graph ist zyklenfrei und damit serialisierbar mit äquivalenten sequentiellen Ausführungsformen:

$T1 \rightarrow T3 \rightarrow T2$
$T3 \rightarrow T1 \rightarrow T2$

Es kann nicht mit T2 begonnen werden, da sonst die Konflikte nicht entstünden und der Ausführungsplan damit per Definition nicht äquivalent wäre.

Sperrprotokolle

= präventive Verfahren zur Verhinderung nicht-serialisierbarer Ausführungspläne

Zwei-Phasen Sperrprotokoll (2PL)

Objekt muss vor Benutzung durch Transaktion gesperrt werden
Nach erster Entsperrung darf keine weitere Sperrung mehr folgen

Es werden dadurch nur serialisierbare Ausführungspläne erzeugt.

Es können aber Verklemmungen auftreten.

Konservatives 2PL

alle Sperren werden zu Beginn der Transaktion gesetzt
Sperren werden nach und nach freigegeben

Problem: kaskadierendes Zurücksetzten

Striktes 2PL

Sperren werden nach und nach gesetzt
alle Sperren werden erst zum Schluss der Transaktion freigegeben

Beispiel

H = < T1.bot,\ T2.bot,\ T1.w(A),\ T2.r(B),\ T1.r(B),\ T2.r(A),\ T1.r(A),\ T2.w(B),\ T1.c,\ T2.c >

Zeitpunkt	T1	T2	Bemerkung
1	BOT
2		BOT
3	lock(A)
4	write(A)
5		lock(B)
6		read(B)
7	lock(B)		T1 muss auf T2 warten
8		lock(A)	T2 muss auf T1 warten
9	...	...	Deadlock

RX-Protokoll

(bisher keine Unterscheidung für Schreibe- oder Leseoperationen)

Zwei Sperrmodi:

R-Sperre: Objekt darf nur gelesen werden
- Mehrere Sperren pro Objekt möglich
X-Sperre: Exklusiver Lese- und Schreibzugriff auf Objekt
- Nur eine Sperre pro Objekt möglich

Recovery

= Fehlerbehandlung, um ACID-Bedingungen zu bewahren

alle Änderungen der abgebrochenen Transaktion rückgängig $\rightarrow$ Logging

Fehlerklassen

Transaktionsfehler
- z.B. wenn Integritätsbedingung verletzt wird
Systemfehler
- bei Informationsverlust im RAM (z.B. durch Stromausfall oder OS-Absturz)
Speicherfehler
- bei Informationsverlust auf Externspeicher (z.B. durch Headcrash)

Logging

= Protokollierung aller vorgenommenen Änderungen

Varianten

physisches Logging
- Protokollierung von vorheringem und Danach-Zustand der Seite
logisches Logging
- Protokollierung von Änderungsoperationen und zugehörigen inversen Operationen
- Aufbau
  - Log Sequence Number (LSN)
  - Transaktionsnummer
  - Seitennummer
  - REDO-Information
  - UNDO-Information
  - Zeiger auf vorheringen Eintrag der Transaktion
- Beispiel:
  Logische Protokolldatei
  ...
  <#42, T04, begin TA, 0>
  <#43, T04, P1, A = A+10, A A-10, #42>
  <#44, T04, P1, B = B*2, B = B/2, #43>
  <#45, T03, P2, D = D+1, A = D-1, #40>
  <#46, T03, commit, #45>
  ...
physiologisches Logging
- Hybridlösung aus beinden anderen Lösungen

Logische Protokolldatei
...
<#42, T04, begin TA, 0>
<#43, T04, P1, A = A+10, A A-10, #42>
<#44, T04, P1, B = B*2, B = B/2, #43>
<#45, T03, P2, D = D+1, A = D-1, #40>
<#46, T03, commit, #45>
...

Write Ahead Logging (WAL-Prinzip)

Protokolleinträge werden im Voraus geschrieben.

Vor einem Commit wurden alle Logs geschrieben
Vor dem Schreiben einer Seite wurden alle Logs geschrieben
Vor dem Schreiben eines Logs wurden alle Logs mit kleineren Sequenznummern geschrieben

Vorgehen bei Systemfehler (Recovery-Ablauf)

Analysephase
- Identifiziere Winner- (mit Commit abgeschlossen) und Loser-Transaktionen (nicht abgeschlossen)
REDO-Phase
- Durchlaufe alle Einträge vom Anfang bis zum Ende
- $LSN_{Seite} < LSN_{Eintrag}$ REDO $LSN_{Seite}$ aktualisieren
UNDO-Phase
- Durchlaufe alle Einträge vom Ende bis zum Anfang
- Führe UNDO-Operation für alle Loser-Transaktionen durch
- Schreibe Kompensationseinträge für alle UNDO-Operationen in Log-Datei
  - Aufbau:
    - Sequenznummer
    - Transaktionsnummer
    - Seitenkennung
    - REDO-Operation
      (UNDO-Operation des jeweiligen zu kompensierenden Eintrags)
    - leeres UNDO-Feld
    - Zeiger auf zuletzt ausgeführte UNDO-Operation

Beispiel

Zeitpunkt	Logische Protokolldatei
...	...
71	<#71, T08, P1, B = B+4, B = B-4, #69>
72	<#72, T09, begin_TA, 0>
73	<#73, T09, P1, A = A-1, A = A+1, #72>
74	<#74, T08, P2, D = D-3, D = D+3, #71>
75	<#75, T08, commit, #74>
76	<#76, T09, P1, A = A*4, A = A/4, #73>
	*CRASH*
77	<#77, T09, P1, A=A/4, , #73>
78	<#78, T09, P1, A=A+1, , #72>

Winner-Transaktion: T08 (wegen commit zu Zeitpunkt 75)

Loser-Transaktion: T09 (weil kein commit)

Sicherungspunkte

Problem/Motivation: Log-Dateien können sehr groß werden

$\rightarrow$ Wiederanlauf startet bei Sicherungspunkt

Varianten

Transaktionskonsistente Sicherungspunkte
Aktionsbasierte Sicherungspunkte
Unscharfe Sicherungspunkte

Aktionsbasierte Sicherungspunkte

Puffer werden nach WAL-Prinzip geschrieben. Bei Erzeugung des Sicherungspunktes wird eine Liste mit aktiven Transaktionen und die kleinste LSN (MIN_LSN) aller noch aktiven Transaktionen gespeichert.

Recovery-Ablauf:

Analyse- und REDO-Phase starten ab Sicherungspunkt
UNDO-Phase läuft bis MIN_LSN

Beispiel

Zustand nach REDO-Phase:

P1 {A=160, B=12}
P2 {D=24}

Zustand nach UNDO-Phase:

P1 {A=41, B=12}
P2 {D=24}

Isolationslevel

Isolationslevel	dirty reads	dirty writes	non-repeatable reads	Phantome
read uncommited	möglich	möglich (wenn schreibend)	möglich	möglich
read commited	nein	möglich (wenn schreibend)	möglich	möglich
repeatable reads	nein	nein	nein	möglich
serializable	nein	nein	nein	nein

read uncommited

Leseoperationen in Transaktionen ignorieren die Sperren anderer Transaktionen
dirty-reads erlaubt
- $T_1$ $T_2$ $T_2$ später abgebrochen wird

read commited

Transaktion setzt Schreibsperre auf geändertes Tupel und hält diese bis commit / rollback
Leseoperationen halten Sperren nur kurz (nicht bis zum Ende der Transaktion)
non-repeatable reads sind möglich
- beim mehrmaligem Lesen des gleichen Tupels kann es zu unterschiedlichen Ergebnissen kommen

repeatable reads

Lesesperren und Schreibsperren werden bis zum Ende der Transaktion gehalten
Transaktionen sehen immer den gleichen Zustand eines Tupels in der Datenbank
Phantome sind möglich
- während einer Transaktion eingefügte Tupel $\rightarrow$ unterschiedliche Ergebnisse bei gleichen Anfragen unterschiedlicher Transaktionen

serializable

$\rightarrow$ Ergebnisse der Ausführungsreihenfolge äquivalent zu sequentieller Ausführung

Beispiel

Relation M

MId	Gehalt
M1	1000
M2	2000

Transaktion 1 (wird im Isolationslevel SERIALIZABLE ausgeführt)


x
begin transaction;
update M set Gehalt = Gehalt * 2 where MId = 'M1';
update M set Gehalt = Gehalt + 100 where MId = 'M1';
commit;

Transaktion 2


x
begin transaction;
select sum (Gehalt) as G1 from M;
select sum ( Gehalt) as G2 from M;
commit;

Werte von G1, G2 mit unterschiedlichen Isolationsleveln für T2:

SERIALIZABLE

Ausführungsreihenfolge	G1	G2
T1 < T2	4100	4100
T2 < T1	3000	3000

READ COMMITED

Ausführungsreihenfolge	G1	G2
T1 < T2	4100	4100
T2 < T1	3000	3000
T2 < T1 < T2	3000	4100

READ UNCOMMITED

Ausführungsreihenfolge	G1	G2
T1 < T2	4100	4100
T2 < T1	3000	3000
T2 < T1 < T2	3000	4100
T2 < T1 < T2 < T1	3000	4000
T1 < T2 < T1 < T2	4000	4100

Snapshot-Isolation

Ziele:

Erhöhung des Parallelitätsgrads bei Transaktionen
Garantie der Serialisierbarkeit

*=verifizierendes (optimistisches) Verfahren**

(2-Phasen-Sperrprotokoll ist präventives Verfahren)

Zeitstempel-Verfahren

Beispiel

Historie:

initiale Werte:

Zeitpunkt	Tupel	Version (k)	Wert	read-ts	write-ts
2	z	2 (weil bei Schreiben neue Version und initial 1)	2	1 (wird mit write gesetzt)	1 (weil BOT zu Zeitpunkt 1)
4	x	1 (weil initial 1 und keine Änderung bei Lesen)	1	3 (weil BOT zu Zeitpunkt 3)	0 (weil initial 0 und keine Änderung bei Lesen)
7	y	2 (weil bei Schreiben neue Version und initial 1)	5	6 (wird mit write gesetzt)	6 (weil BOT zu Zeitpunkt 6)
10	y	3 (weil bei Schreiben neue Version und letzte Version von T2 = 2)	4	9 (wird mit write gesetzt)	9 (weil BOT zu Zeitpunkt 9)
12	x	2 (weil bei Schreiben neue Version und initial 1)	8	11 (wird mit write gesetzt)	11 (weil BOT zu Zeitpunkt 11)
13	y	4 (weil bei Schreiben neue Version und letzte Version von T3 = 3)	1	11 (wird mit write gesetzt)	11 (weil BOT zu Zeitpunkt 11)
14	y	1 (weil BOT von T5 als erstes und somit kein Update bekannt)	3 (weil initial 3 und T5 Stand von Zeitpunkt 1 hat)	1 (weil BOT zu Zeitpunkt 1)	0 (weil initial 0 und keine Änderung bei Lesen)

Datenbanksysteme Klausurvorbereitung

Transaktionen

ACID-Bedingungen

Ausführungspläne

Beispiel

Elementaroperationen

Ordnungsrelationen

Synchronisationsprobleme

Lost update

Inkonsistente Sicht auf die Datenbank

inkonsistente Datenbank

Phantom-Problem

Serialisierbarkeit

äquivalente Ausführungspläne

serialisierbare Ausführungspläne

Serialisierbarkeitsgraph G_H

Beispiel

Sperrprotokolle

Zwei-Phasen Sperrprotokoll (2PL)

Konservatives 2PL

Striktes 2PL

Beispiel

RX-Protokoll

Recovery

Fehlerklassen

Logging

Varianten

Write Ahead Logging (WAL-Prinzip)

Vorgehen bei Systemfehler (Recovery-Ablauf)

Beispiel

Sicherungspunkte

Varianten

Aktionsbasierte Sicherungspunkte

Beispiel

Isolationslevel

read uncommited

read commited

repeatable reads

serializable

Beispiel

SERIALIZABLE

READ COMMITED

READ UNCOMMITED

Snapshot-Isolation

Zeitstempel-Verfahren

Beispiel

$G_H$