Wiki

A universe of ideas

User Tools

Site Tools

You are here: A universe of ideas » Uni » 8. Semester » Datenbanksysteme II
Trace:
uni:8:dbs2:start

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
uni:8:dbs2:start [2015-06-16 15:46] – [Aufgabe 1] skrupellosuni:8:dbs2:start [2020-11-18 18:11] (current) – external edit 127.0.0.1
Line 1: Line 1:
 ====== Datenbanksysteme II ====== ====== Datenbanksysteme II ======
-===== Übung 1 ===== +  * [[übungen]] 
-  * **Transaktion** \\ Folge von Aktionen (read/write) die die DB von einem konsistenten Zustand in einen anderen Konsistenten Zustand überführt. +  * [[zusammenfassung]]
-  * **Hauptaufgabe der Transaktionen - Verwaltung** +
-    * Synchronisation (Koordination von mehreren Benutzerproxessen => Logische Einbenutzerbetrieb) +
-    * Recovery (Behebung von Fehlersituationen) +
-  * **Eigenschaften von Transaktionen (ACID-Prinzip)** +
-    * **A**tomicy (Atomarität: EffektTransaktion trifft ganz oder gar icht in ???) +
-    * **C**onsistency (Konsistenz/Integritätserhaltung: Konsistenter Zustand => Konsistenter Zustand) +
-    * **I**solation (Isoliertheit: Logischer Einbenutzerbetrieb) +
-    * **D**urability (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! +
- +
-==== Aufgabe 1 ==== +
-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)) +
- +
-=== a === +
-=> 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! +
- +
-=== b === +
-=> 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! +
- +
- +
-==== Aufgabe 2 ==== +
-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 +
- +
-==== Aufgabe 3 ==== +
-  * 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! +
- +
-===== Übung 2 ===== +
-==== Aufgabe 1 ==== +
-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): +
-    - Wachstumsphase (lock) +
-    - 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 +
-  *  +
- +
-==== Aufgabe 2 ==== +
-Verklemmung bezgl. Zugriff auf Verschiedene Objekte: +
-  - T1 hält x(x) +
-  - T1 will x(y) +
-  - T2 hält x(y) +
-  - 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) | (V) | (V) | (V) | +
-^ b) | (V) | (X) | (X) | +
-^ c) | (V) | (X) | (V) | +
- +
-==== Aufgabe 3 ==== +
-^      ^ 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. +
-==== Aufbau ==== +
-  * DB-Anwendung +
-  * DBS +
-    * DBMS +
-    * DB +
- +
-|  Anwendungen (mehrere)                                       || +
-^         Externe Ebene | Views (mehrere)                       | +
-^                       |  ↓↓ Logische Datenunabhängigkeit ↓↓   | +
-^  Konzeptionelle Ebene |                                       | +
-^                       |  ↓↓ Physische Datenunabhängigkeit ↓↓  | +
-^         Interne Ebene | Speicherformat                        | +
-===== Probeklausur 1/2 ===== +
-==== Aufgabe 1 ==== +
-  * Falsch \\ Die Knoten sind die Transaktionen +
-  * Wahr +
-  * Wahr \\ mindestens alles was ich  +
-  * Fals \\ Das währe FOCC +
- +
-==== Aufgabe 2 ==== +
-=== a) === +
-Zyklus in Graph => Es liegen verklemmungen vor +
- +
-=== b) === +
-  * 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 +
- +
-=== c) === +
-  * 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 +
- +
-==== Aufgabe 3 ==== +
-$T_2, T_3, T_5, T_4, T_1$ +
- +
-==== Anforderungen ==== +
-  * **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 +
-  *  +
- +
-===== Übung 4 ===== +
-==== Aufgabe 1 ==== +
-=== a) === +
-Loggranulat <= Sperrgranulat, sonst Lost Updates ??? +
- +
- +
-Update-in-place: geänderte Werte auf ursprüngliche Pos +
-=== b) === +
-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 +
- +
- +
- +
-==== Aufgabe 4 ==== +
-  * ''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) +
- +
-===== Übung 5 ===== +
-==== Aufgabe 1 ==== +
-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. +
-    *  +
- +
-=== b) === +
-^ Seite ^ PageLSN // (Puffer) ^ PageLSN // (Platte) ^ +
-| $P_A$ | 90 | 90 | +
-| $P_B$ | 130 | 0 | +
-| $P_C$ | 50 | 50 | +
-| $P_D$ | 70 | 0 | +
-| $P_E$ | 110 | 60 | +
- +
-==== Aufgabe 2 ==== +
-=== a) === +
-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: +
-  - Analysephase +
-    - Lies Log-Datei von letztem Check Point bis Ende +
-    - Bestimme Gewinner & Verlierer TAs: +
-      * Gewinner: COMMIT-Satz in Log +
-      * Verlierer: Kein COMMIT-Satz im Log +
-    - Ermittler geänderte Seiten +
-  - REDO-Phase +
-    - Vorwärtslesen der Log-Datei, ausgehend vom letzten Sicherungspunkt. +
-    - 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 +
-  - UNDO-Phase +
-    - Rückwärtslesen der Log-Datei bis BOT der ältesten Verlierer TA +
-    - 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) +
- +
-=== b) === +
-  * Gewinner TAs: $T_1$ & $T_3$ +
-  * Verlierer TAs: $T_2$ & $T_4$ +
-  * Betroffene Seiten: $P_A$, $P_B$, $P_C$, $P_D$, $P_E$ +
- +
-Vollständiges REDO:+
  
 ===== ACID ===== ===== ACID =====
Line 326: Line 8:
   * Isolation (Man muss sich aleine fühlen)   * Isolation (Man muss sich aleine fühlen)
   * Durability (Abgeschlossene Transaktionen sind von dauer)   * Durability (Abgeschlossene Transaktionen sind von dauer)
-  *  
- 
  
  
uni/8/dbs2/start.1434462379.txt.gz · Last modified: 2020-11-18 18:10 (external edit)