Differences

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

--- uni:8:dbs2:start [2015-06-09 16:52] – [Aufgabe 1] skrupellos
+++ uni:8:dbs2:start [2020-11-18 18:11] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
 ====== 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
-    *
 ===== ACID =====
   * Atomic (Wenn, dann wird man als ganzes abgebrochen)
@@ Line 247: / Line 8: @@
   * Isolation (Man muss sich aleine fühlen)
   * Durability (Abgeschlossene Transaktionen sind von dauer)
-  *