Durchschnittlicher Fortschritt
Empfohlene Karteikarten-Sets
Karteikarten im Karteikarten-Set
Noch nicht gestartet (123)
Integritätsaspekte
Semantische Integrität
Ablaufintegrität
Semantische Integrität
Korrekter (konsistenter) DB-Zustand nach Ende der Transaktion
Ablaufintegrität
Fehler durch „gleichzeitigen“ Zugriff mehrerer Benutzer auf dieselben
Daten vermeiden
Von wem werden Transaktionen verwaltet ?
Transaktionsverwaltung ist eine Kernaufgabe eines DBS
Was sind die Kerneigenschaften einer Transaktion?
Atomicity
Alles oder Nichts-Prinzip
Beispiel: Ab- und Aufbuchung oder keines von beiden
Consistency
DB von einem konsistenten Zustand in den nächsten überführen
Beispiel: Summe der Kontostände konstant
Isolation
Laufende Transaktionen beeinflussen sich nicht gegenseitig
Beispiel: Überbuchung verhindert
Durability
Dauerhafte Wirkung einer erfolgreich beendeten Transaktion
Beispiel: Überwiesener Betrag sowie Reservierung gespeichert
Start einer Transaktion
explizit mit BoT-Befehl oder implizit mit erstem SQL-Befehl
- Transaktionslose DB-Operationen nicht erlaubt!
- jeder RW-Zugriff nur innerhalb einer Transaktion erlaubt
Abschluss einer Transaktion
Erfolgreicher Abschluss einer Transaktion
- nur mit dem commit-Befehl korrekt abgeschlossen
- lstellt Persistenz aller Änderungen der Transaktion sicher
Nicht-Erfolgreicher Abschluss einer Transaktion
- explizit mit rollback oder implizit durch ein äußeres Ereignis
- Zustand wird wiederhergestellt, der vor T-Beginn gültig war
Rücksetz-Einheiten
Savepoints
Probleme im Merbenutzerbetrieb
(1) Non-Repeatable Read
(2) Lesen inkonsistenter Zustände
(3) Dirty Read
(4) Phantom-Problem
(5) Lost Update
(6) Mehrbenutzer-Anomalie
(7) Cursor-Referenzen
Was ist das für ein Problem ?
Non-Repeatable Read
Was ist das für ein Problem ?
Lost Update
Was ist das für ein Problem ?
Phantom-Problem
Was ist das für ein Problem ?
Dirty Read
Was ist das für ein Problem ?
Cursor-Referenzen
Was ist das für ein Problem ?
Lesen Inkonsistenter Zustände
Was ist das für ein Problem ?
Mehrbenutzer-Anomalie
Woraus besteht eine Transaktion?
Eine Transaktion (T) ist eine Folge von DB-Operationen die DB-Objekte x lesen r(x) oder schreiben w(x)
Eine einzelne Transaktion T erzeugt gemäß Consistency Eigenschaft
immer korrekte Effekte
Wann sind Effekte mehrerer Transaktionen korrekt?
Mehrere Transaktionen erzeugen korrekte Effekte falls sie seriell ausgeführt werden
(da vollständige Isolation gegeben)
ODER
Wenn Verzahnte Ausführung serialisierbar ist.
d.h. äquivalente Effekte liefert wie eine beliebige serielle Ausführung
Schedule stellt ____ dar
Die lokale Reihenfolge der Einzelschritte jeder Transaktion
„konfliktäre“ Operationen
Wann sind Operationen konfliktär ?
Zwei Operationen o1, o2 sind konfliktär wenn sie zu verschiedenen Transaktionen (T1, T2) gehören & sie auf das gleiche DB-Objekt (y) zugreifen & mindestens eine Operation eine Schreib-Operationen ist.
Wovon ist der Effekt eines Schedules abhängig?
Der Effekt eines Schedules ist abhängig von der Reihenfolge
in der „konfliktäre“ Operationen ausgeführt werden
Wann ist Effekt-Äquivalenz gegeben?
Was ist CSR
Als "CSR“ wird die Menge aller konfliktserialisierbaren
Schedules bezeichnet.
Konfliktserialisierbare Schedules oder kurz ___ ?
CSR
Wie kann man Konfliktserialisierbarkeit überprüfen?
Konfliktgraph
Wie ist Konfliktserialisierbarkeit überprüfbar?
Konfliktgraph
Wozu dient ein Konfliktgraph ?
Um die Konfliktserialisierbarkeit zu überprüfen.
Ist konfliktserialisierbar ? Wie sieht der Graph aus?
r1(x)
r2(y)
w1(x)
r1(y)
w2(y)
r2(z)
w1(y)
w2(z)
Nein!
Konfliktgraph G(s)=(N,E) von Schedule s
Knotenmenge N enthält alle ____________von s
Transaktionen
Konfliktgraph G(s)=(N,E) von Schedule s
Kantenmenge E enthält alle ______________
als gerichtete Kanten
konfliktären Operationen
Ist konfliktserialisierbar ? Wie sieht der Graph aus?
r1(x)
w1(x)
r1(y)
w1(y)
r2(z)
w2(z)
r2(y)
w2(y)
Ja
Ist konfliktserialisierbar ? Wie sieht der Graph aus?
r2(y)
w2(y)
r2(z)
w2(z)
r1(x)
w1(x)
r1(y)
w1(y)
Ja
Ist konfliktserialisierbar ? Wie sieht der Graph aus?
r1(x)
w2(z)
w1(y)
r2(z)
r1(y)
w2(y)
w1(x)
r2(y)
Ja
Ist konfliktserialisierbar ? Wie sieht der Graph aus?
r1(x)
w2(z)
w1(y)
r2(z)
r1(y)
w2(y)
w1(x)
r2(y)
Nein
Was bedeutet ein azyklischer Konfliktgraph ?
Verzahnte schedules mit azyklischen Konfliktgraphen sind
in serielle überführbar (z.B. durch topologisches Sortieren)
Schedule ist konflikserialisierbar.
Was bedeutet ein zyklischer Konfliktgraph ?
Verzahnte schedules mit azyklischen Konfliktgraphen sind
in serielle nicht überführbar.
Schedule ist nicht konflikserialisierbar.
Konfliktgrap – Regeln für Aufbau
Erzeuge für jeden Fall in s, bei dem Tj ein read(x) ausführt, nachdem Ti ein write(x) ausgeführt hat ein(e/en) _____
eine Kante (Ti -> Tj)
Konfliktgrap – Regeln für Aufbau
Erzeuge für jeden Fall in s, bei dem Tj ein write(x) ausführt,
nachdem Ti ein read(x) ausgeführt hat ein(e/en) _____
eine Kante (Ti -> Tj)
Ist konfliktserialisierbar ? Wie sieht der Graph aus?
r1(y)
r3(u)
r2(y)
w1(y)
w1(x)
w2(x)
w2(z)
w3(x)
r1(y)
r3(u)
r2(y)
w1(y)
w1(x)
w2(x)
w2(z)
w3(x)
T3 -> T1 -> T2
T3 -> T1 -> T2
T3 -> T2 ->T1
Konfliktgraph für Schedule s
s = T3 -> T2 ->T1
s heißt rücksetzbar (recoverable), falls folgende Bedingung erfüllt ist:
Eine Transaktion darf erst dann ihr COMMIT durchführen, wenn alle Transaktionen, von denen sie gelesen hat, beendet sind.
Aus Sicht der Fehlersicherheit sind alle Schedule akzeptabel ?
Nein
Kann jede Transaktion zu jedem Zeitpunkt vor Ausführung eines commit zurückgesetzt werden, ohne dass davon andere Transaktionen beeinträchtigt werden?
Nein
Ist aus Sicht der Fehlersicherheit folgender Schedule s
akzeptabel:
s = r1(x)w1(x)r2(x)a1w2(x)c2
Nein, aber serialisierbar in CSR
Kriterien um Fehlersituation zu vermeiden sind :
Rücksetzbarkeit – RC
Vermeidung kaskadierender Abbrüche
Striktheit ST
s heißt rücksetzbar (recoverable), falls folgende Bedingung erfüllt ist:
Eine Transaktion darf erst dann ihr COMMIT durchführen, wenn alle Transaktionen, von denen sie gelesen hat, beendet sind.
Eine Transaktion darf erst dann ihr COMMIT durchführen, wenn alle Transaktionen, von denen sie gelesen hat, beendet sind.
Ist eine Bedingung für ?
Rücksetzbarkeit – RC
Ist s1 rücksetzbar ?
s1 = w1(x)w1(y)r2(u)w2(x)r2(y)w2(y)c2w1(z)c1
In s1 liest T2 das Datenobjekt y von T1, aber c2 kommt vor c1=> s1 ist gemäß ACID-Eigenschaft nicht rücksetzbar
Ist s rücksetzbar ?
s2 = w1(x)w1(y)r2(u)w2(x)r2(y)w2(y)w1(z)c1 c2
s2 ist rücksetzbar – s2 ε RC
d.h. T2 wird zwingend abgebrochen, wenn T1 abbricht
Schedule s vermeidet kaskadierende Abbrüche
„Schneeballeffekt“ (avoiding cascading aborts), falls
folgende Bedingung erfüllt ist:
Eine Transaktion darf nur Daten lesen, die zuletzt von einer
bereits abgeschlossenen Transaktion geschrieben wurden
(-> Dirty Read wird verhindert)
Was heißt die Abkürzung ACA ?
avoiding cascading aborts
Wie/womit wirt Dirty Read verhindert?
avoiding cascading aborts
Eine Transaktion darf nur Daten lesen, die zuletzt von einer bereits abgeschlossenen Transaktion geschrieben wurden (-> Dirty Read wird verhindert)
vermeidet s kaskadierende Abbrüche?
s = w1(x)w1(y)r2(u)w2(x)w1(z)c1r2(y)w2(y)c2
ja
vermeidet s kaskadierende Abbrüche?
s = w1(x)w1(y)r2(u)w2(x)r2(y)w2(y)w1(z)c1 c2
nein
Schedule s heißt strikt, falls folgende Bedingung gilt:
Es darf kein geändertes Datenobjekt einer noch nicht
beendeten Transaktion gelesen oder überschrieben werden
Heißt Schedule s strikt ?
s = w1(x)w1(y)r2(u)w2(x)w1(z)c1r2(y)w2(y)c2
ja
Heißt Schedule s strikt ?
s = w1(x)w1(y)r2(u)w1(z)c1w2(x)r2(y)w2(y)c2
ja
ST ∈ ACA ∈ RC?
ja
ACA ∈ RC ∈ ST ?
nein ST ∈ ACA ∈ RC?
- RC ∈ ST ∈ ACA
- ACA ∈ RC ∈ ST
- ACA ∈ ST ∈ RC
- ST ∈ RC ∈ ACA
- ST ∈ ACA ∈ RC
5
Prüfung eines Schedules auf Serialisierbarkeit /
Fehlersicherheit in der Praxis _______________________
Weil
- ______
- ______
schwierig & aufwändig
Zur Laufzeit nur unvollständige Schedules verfügbar
Überwachung unvollständiger Schedules notwendig
Transaktionen, die noch kein commit gemacht haben
können noch jederzeit abgebrochen werden
Nenne die pessimistischen Verfahren
- Sperrbasiert
- Nicht-sperrbasiert
- Zeitstempel Verfahren
erzwingen eine korrekte Reihenfolge der Bearbeitungsschritte mittels geeigneter
Markierungen („Timestamps“) der Transaktionen
MVCC ?
Multi-Version Concurrency Control
Sperrprotokoll ist ein optimistisches verfahren?
Nein.
Sperrbasierte Verfahren werden am häufigsten verwendet.
Ja
Sperrbasierte Verfahren werden selten verwendet.
Nein! Sperrbasierte Verfahren werden am häufigsten verwendet.
Wie funktioniert das Sperrbasierte Verfahren ?
Bevor eine Transaktion eine Operation ausführen darf
muss sie eine entsprechende Sperre für das betreffende DBObjekt erhalten haben
Was ist das Sperrprotokoll ?
= Vorschrift bzgl. des Setzens von Sperren
Was garantiert das Sperrprotokoll?
Das Sperrprotokoll garantiert Konfliktserialisierbarkeit ohne zusätzliche Tests!
Notation für das Entsperren (von Objekt x)
Entsperren ru(x) und wu(x), oft zusammengefasst u(x)
Welche Sperren werden gewährt ?
Angeforderte Sperre wird
gewährt (3) oder nicht gewährt (7)
7 heißt die Sperre wurde gewährt
Nein!
gewährt (3)
nicht gewährt (7)
3 heißt die Sperre wurde gewährt
Ja!
gewährt (3)
nicht gewährt (7)
Lesezugriff r(x) ist nur nach rl(x) erlaubt
Nein! Lesezugriff r(x) ist nur nach rl(x) oder wl(x) erlaubt
Lesezugriff r(x) ist nur nach rl(x) oder wl(x) erlaubt
Ja!
Vor einem _________ müssen alle Sperren aufgehoben werden
Commit
Was heißt das Zwei-Phasen Sperrprotokoll ?
Jede Transaktion durchläuft zwei Phasen
- Anforderungsphase, in der Sperren angefordert werden, aber keine freigegeben werden dürfen
- Freigabephase, in der bisher erworbene Sperren freigegeben werden, aber keine neuen angefordert werden dürfen
Bei T-Ende müssen alle Sperren zurückgegeben werden
Kaskadierendes Rücksetzen
Wie kann man "kaskadierendes Rücksetzen" ausschließen ?
Striktes 2PL
Alle Sperren werden bis zum T-Ende gehalten.
Was für ein Problem hat man beim
Zwei-Phasen Sperrprotokoll ?
Sperren können Deadlocks verursachen
Deadlocks von vornherein vermieden durch______
Konservatives 2PL-Protokoll (Preclaiming)
(in der Praxis nicht realisierbar!)
Deadlocks erkennen und beseitigen durch T-Abbruch
Auswahlkritieren für abzubrechende Ts
- Rücksetzaufwand / T-Länge
- Wichtigkeit einer Transaktion
- Anzahl der aufgebrochenen Zyklen
Was ist ein Sperrgranulat ?
= Größe des zu sperrenden Objekts
Einschränkung auf nur eine Sperrgranularität hat für
alle Transaktionen Nachteile:
- ____
- ____
- Zu kleine Granularität belastet Transaktionen, da sie viele Sperren anfordern müssen
- Zu große Granularität schränkt den Parallelitätsgrad des Systems unnötig ein, da DB-Objekte feinerer Granularität implizit gesperrt werden, die gar nicht benötigt werden
Einschränkung auf nur eine Sperrgranularität hat für
alle Transaktionen Nachteile, wie lautet die Lösung ?
Lösung – Flexible Sperrgranularität
Einführung zusätzlicher Sperrmodi, welche eine flexible
Auswahl eines bestimmten Sperrgranulats pro Transaktion unterstützen
„Intensionale Sperren“ – Hierarchisches Sperrverfahren
Erkläre intensionale Sperren
Zeigen auf höherer Ebene der Granularitätshierarchie die
„Absicht“ einer weiter unten in der Hierarchie gesetzten
Sperre an
Intensionale Lesesperre (irl)
l Weiter unten in der Hierarchie ist eine Lesesperre (rl)
beabsichtigt
Intensionale Schreibsperre (iwl)
l Weiter unten in der Hierarchie ist eine Schreibsperre (wl) beabsichtigt
Lese- und intensionale Schreibsperre (riwl)
l Setzt eine Lesesperre (rl) auf der aktuellen Hierarchiestufe und zeigt an, daß weiter unten in der Hierarchie eine Schreibsperre (wl) beabsichtigt ist
Was heißt riwl ?
Lese- und intensionale Schreibsperre (riwl)
l Setzt eine Lesesperre (rl) auf der aktuellen Hierarchiestufe und zeigt an, daß weiter unten in der Hierarchie eine Schreibsperre (wl) beabsichtigt ist
Intensionale Sperren – Konfliktmatrix
In welcher Reihenfolge sollen die Sperren gesetzt
bzw. freigegeben werden?
Sperren werden auf einem Pfad in der Reihenfolge von der
Wurzel zum Zielobjekt gesetzt
Kann ein irl zum rl werden ?
Ja! Sperren können verschärft werden das heißt
ein rl kann zum wl werden
ein irl zum rl und
ein irl zum iwl
Hierarchische Sperrverfahren
Ablaufregeln
1. Sperren werden auf einem Pfad in der Reihenfolge von der Wurzel zum Zielobjekt gesetzt
2. DB-Objekt, auf dem gearbeitet werden soll, wird mit
herkömmlicher Schreib- oder Lesesperre explizit gesperrt
3. Alle anderen Knoten auf dem Pfad bekommen
intensionale Sperren
4.
Sperren können verschärft werden das heißt
ein rl kann zum wl werden
ein irl zum rl und
ein irl zum iwl
5. Freigabe erfolgt in umgekehrter Reihenfolge
auf niedriger Hierarchiestufe (= kleine Granularität) zu sperren ________ Parallelitätsgrad
höherer
Erkläre "Lock Escalation"
sobald eine bestimmte Anzahl von Sperren auf einer
bestimmten Granularitätsstufe erworben wurde, wird
automatisch eine entsprechende Sperre auf der nächsthöheren Granularitätsstufe gesetzt
sobald eine bestimmte Anzahl von Sperren auf einer
bestimmten Granularitätsstufe erworben wurde, ________
sobald eine bestimmte Anzahl von Sperren auf einer
bestimmten Granularitätsstufe erworben wurde, wird
automatisch eine entsprechende Sperre auf der nächsthöheren Granularitätsstufe gesetzt
Was ermöglicht das hierarchische Sperrverfahren?
Ermöglichen Transaktionen mit wenigen Zugriffen pro
Granularitätsstufe
lauf niedriger Hierarchiestufe (= kleine Granularität) zu sperren
höherer Parallelitätsgrad
n Ermöglichen Transaktionen mit vielen Zugriffen pro
Granularitätsstufe
auf entsprechend höherer Hierarchiestufe (= große Granularität) zu sperren
geringerer Sperraufwand
Das Zeitstempel Verfahren dient zu ?
Serialisierbarkeitsprüfung (basierend auf Zeitstempelvergleichen)
Zeitstempel Verfahren
Grundregeln
Das Zeitstempel Verfahren ist ein sperrbasiertes Verfahren
Nein! Das Zeitstempel Verfahren ist ein nicht-sperrbasiertes Verfahren
Das Zeitstempel Verfahren ist ein nicht-sperrbasiertes Verfahren
Ja
Multiversion Concurrency Control (MVCC)
Kernidee
Reduzierung der Konflikte, wenn zu den geänderten
Datenobjekten mehrere Versionen geführt werden
Jede Transaktion bekommt eine eigene Momentaufnahme der Datenobjekte zu sehen
Jede Änderungsoperation w erzeugt neue Version w' des Datenobjektes
Leseoperationen können passende Version wählen
Was für ein Problem hat man hier ?
s = r1(x) w1(x) r2(x) w2(y) r1(y) w1(z) c1 c2
Dirty Read
Multiversion Concurrency Control (MVCC)
Vorteile
Jede Änderungsoperation w erzeugt neue Version w' des Datenobjektes
Leseoperationen können passende Version wählen
Versionen sind transparent für Applikationen
Entkopplung von Lese- und Änderungsoperationen
→ Lesetransaktion hat Sicht auf DB wie bei BOT
l Keine Synchronisation von Lesetransaktionen notwendig
¡ → Reduzierung der Konfliktwahrscheinlichkeit
¡ → Erhöhung des Durchsatzes
l Synchronisation von Änderungs-Op. durch andere Verfahren
¡ Sperrverfahren, Zeitstempel
Jede Änderungsoperation w erzeugt neue Version w' des
Datenobjektes
Ja
Isolation garantiert "automatisch" ________
Korrektheit
Wie wird isolation realisiert ?
Realisierung (meist durch Sperren) muss alle möglichen
Operationen (Lesen, Ändern, Einfügen, Löschen) in Betracht ziehen
Parallelitätsgrad wird durch Sperren (Blockierungszeiten) eingeschränkt
Was wird durch Sperren eingeschränkt ?
Parallelitätsgrad wird durch Sperren (Blockierungszeiten) eingeschränkt
Isolationsebenen in SQL beim Lesen
ist Korrektheit immer erforderlich?
Korrektheit ist bei nur lesender Zugriff für statistische Auswertungen nicht erforderlich
READ UNCOMMITTED heißt ?
Lesen von nicht endgültig geschriebenen Daten
z.B. für statistische Transaktionen
l ungefährer Überblick
Keine Sperren auf Tabellen-Ebene nötig, keine
Lesesperren
READ COMMITTED
Welche Fehler sind hier möglich?
Nur Lesen endgültig geschriebener Daten
Non-Repeatable Read und Phantom-Problem möglich
REPEATABLE READ
Welche Fehler sind hier möglich?
Gelesene Daten einer Transaktion können durch
andere Transaktionen nicht verändert werden
Phantom-Problem möglich
Realisierung basiert auf einer Lese-Sperre, die bis zum Transaktionsende gehalten wird
SERIALIZABLE
Garantiert Serialisierbarkeit einer Transaktion
Transaktion sieht nur Änderungen, die zu Beginn der
Transaktion endgültig geschrieben wurden (inkl. natürlich eigene Änderungen)
Realisierung basiert im einfachsten Fall auf einer LeseSperre der gesamten Tabelle
Isolationsebenen in SQL
Mögliche Inkonsistenzen
Die Abschwächung der Isolationsebene
hat den Vorteil, dass _____________
hat den Nachteil, dass ______________
Die Abschwächung der Isolationsebene
hat den Vorteil, dass die Parallelität erhöht wird
hat den Nachteil, dass gewisse Inkonsistenzen auftreten
können, bzw. in Kauf genommen werden
Isolationsebene
- kurze Transaktionen und niedrig belastete DB
- Bei hoher DB-Belastung
- Hoch = Für kurze Transaktionen und niedrig belastete DB kann generell mit der höchsten Isolationsebene gearbeitet werden
- Niedrig = Bei hoher DB-Belastung muss eine schwächere Einstellung der Isolationsebene geprüft werden