Differences

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

--- uni:8:dbs2:start [2015-07-07 15:12] – [Aufgabe 2] 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
-==== 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$
-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:
-^ TA ^ Seite ^ PageLSN vs LSN ^ Änderungen in \\ der DB (Platte) ^
-|  $T_1$  |  $P_B$  |   $0 < 20$        |  $P_B, 20$   |
-|  $T_4$  |  $P_C$  |   $50 \not< 50$   |            |
-|  $T_1$  |  $P_E$  |   $60 \not< 60$   |            |
-|  $T_4$  |  $P_D$  |   $0 < 70$        |  $P_D, 70$   |
-|  $T_2$  |  $P_A$  |   $90 \not< 90$   |            |
-|  $T_3$  |  $P_E$  |   $60 < 110$      |  $P_E, 110$  |
-|  $T_2$  |  $P_B$  |   $0 < 130$       |  $P_B, 130$  |
-UNDO:
-^ TA ^ Seite ^ Zur Log-Date hinzugefügte Log-Einträge ^ Änderungen auf der DB Platte ^
-|  $T_2$  |  $P_B$  |  $180, T_2, P_B, R(B), U(B), 130$  |  $P_B, 180$  |
-|  $T_2$  |  $P_A$  |  $190, T_2, P_A, R(A), U(A), 180$  |  $P_A, 190$  |
-|  $T_4$  |  $P_D$  |  $200, T_4, P_D, R(D), U(D), 70$   |  $P_D, 200$  |
-|  $T_4$  |  $P_C$  |  $210, T_4, P_C, R(C), U(C), 200$  |  $P_C, 210$  |
-Slektives REDO:
-^ TA ^ Seite ^ Page LSN vs LSN ^ Änderungen in DB (Platte) ^
-|  $T_1$  |  $P_B$  |   $0 < 20$         |  $P_B, 20$   |
-|  $T_1$  |  $P_E$  |   $60 \not< 60$    |            |
-|  $T_3$  |  $P_E$  |   $60 \not< 110$   |  $P_E, 110$  |
-UNDO:
-^ TA ^ Seite ^ PageLSN >= LSn
-===== Übung 6 =====
-==== Aufgabe 2 ====
-=== a) ===
-<code sql>
-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
-</code>
-=== b) ===
-  * 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 ...
-=== d) ===
-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
-===== Übung 7 =====
-==== Aufgabe 1 ====
-=== a) ===
-Jeder mit jedem
- $|R| \cdot |S| = 10 \cdot 10 = 100$
-=== b) ===
-Ein Pointer pro Vergleichssetz.
-Bei <= wird auf der einen Seite weitergegangen. Bei > wird auf der anderen Seite weitergegangen.
-Hierfür dürfen keine Duplikate in dem einen Set sein.
- $18$
-=== c) ===
-Hashfunktion h(x) = x mod 5
-^ h(x) ^ Elemente aus R ^ Elemente aus S ^ Vergleiche ^
-|  0 | 10,      | 5, 10  |  $1 \cdot 2 = 2$  |
-|  1 | 1, 6, 11 | 1, 6   |  $3 \cdot 2 = 6$  |
-|  2 | 2, 7, 12 | 2      |  $3 \cdot 1 = 3$  |
-|  3 | 3,13     | 3,8,13 |  $2 \cdot 3 = 6$  |
-|  4 | 9        | 4, 14  |  $1 \cdot 2 = 2$  |
-^  Sum ^^^  $19$  ^
-Jeder wird mit jedem, aber nur innerhalb des Buckets verglichen.
- $19$
-=== d) ===
-Hashfunktion für Blockbildung:  $h_B(x) = x mod 3$
-^  $h_B(x)$  ^ Elemente in R ^ Elemente in S ^
-|  0 | 3, 6, 9, 12  | 3, 6         |
-|  1 | 1, 7, 10, 13 | 1, 4, 10, 13 |
-|  2 | 2, 11        | 2, 5, 8, 14  |
-Hashfunktion für Join:  $h(x) = x mod 2$  (gerade und ungerade im Block miteinander Vergleichen)
- $16$
-==== Aufgabe 2 ====
- $|C|-1$  Blöcke der äußeren Relation werden in den Cache eingelesen. Zu jedem Block der inneren Relation werden dies Blöcke gejoint.
-  * Jede R-Relation (äußere Relation) wird einmal i.d. Cache geladen
-  * Jede S-Relation (innere Relation) wird  $\left\lceil\frac{B_R}{|C|-1}\right\rceil$  mal i.d. Cache geladen.
-  * Insgesammt:  $B_R + B_S \cdot \left\lceil\frac{B_R}{|C|-1}\right\rceil$  = Plattenzugriffe
-=== a) ===
-Plattenzugriffe =  $B_R + B_S \cdot \left\lceil\frac{B_R}{|C|-1}\right\rceil = 10000 + 10000 \cdot \left\lceil\frac{10000}{|1000|-1}\right\rceil = 120000$
-=== b) ===
-Höchstens 100.000 Plattenzugriffe
- $10000 + 10000 \cdot \left\lceil\frac{10000}{|C|-1}\right\rceil <= 100000$
-$\left\lceil\frac{10000}{|C|-1}\right\rceil <= 9
- $frac{10000}{9} < |C| - 1$
- $1112,111 <= |C|$
-Für max. 100000 Plattenzugriffe benötigt man einen Cache von 1113 Blöcken
-=== c) ===
-Die selbe Rechnung nochmal => D.h. für ein Fünftel d. Plattenzugriffe benötigt man ca. das 10-Fache an cache
-==== Aufgabe 3 ====
-=== c) ===
-Für den Schnitt aus R_1 und R_2 erhält man genau die Tupel, die sowohl in R1 als auch in R2 vorhanden sind
-R_1
-^ A ^ B ^
-| a | b |
-R_2
-^ A ^ B ^
-| b | b |
-Dann gilt  $\pi_B(R_1 \cap R_2) = \{\}$ , aber  $\pi_B(R_1) \cap \pi_B(R_2) = {b}$
-=== d) ===
- $\pi_l(R_1 \ cup R_2) = \pi_l(R_1) \cup \pi_l(R_2)$
- $\text{sei } t \in \pi_l(R_1 \cup R_2) \Leftrightarrow \exists a \in R_1 \cup R_2: a.l = t$
- $\Leftrightarrow \exists b \in R_1: b.l = t \vee \exists c \in R_2: c.l = t$
-....
-=== e) ===
- $\pi_l(R_1 - R_2) = \pi_l(R_1) - \pi_l(R_2)$  (Für die Differenz werden alle Tupel aus  $R_1$  entfernt, die auch in  $R_2$  vorhanden sind)
-s.o.
-===== Übung 8 =====
-==== Aufgabe 1 ====
-Warum eignen sich traditionalle Ansätze eher nicht für Big Data?
-  * Big Data passt nicht auf eine einzelne Maschine \\ Die Datenmengen bei Big Data sind meist zu groß für einzelne Maschinen.
-  * Das Lesen aus dem Speicher dauert zu lange \\ Speicherzugriffe hat man auch bei Big Data Ansätzen
-  * Traditionelle Ansätze skalieren sehr gut mit großen Mengen unstrukturierter Daten \\ Unstrukturierten Daten (Bilder, Plain Text) sind durch traditionelle Ansätze i.d.R. nicht handhabbar
-  * Für Big Data lässt sich kein relationales Schema finden \\ Nach Verarbeitungsschritten können sich für Big Date relationale Schemen finden lassen
-Welche der folgenden Punkte machen für Big Data Sinn?
-  * Benutzung von komplexer Hardware \\ Miderne Big Data HW basiert auf günstiger HW. Wie gewöhnliche User PCs, die es leicht machen Kapazitäten zu erhöhen
-  * Benutzung von komplexer Software \\ Um komplexe Probleme zu lösen wird auf SW-Lösungen zurück gegriffen
-  * Einfache Möglichkeit der Kapazitätserweiterung \\ Viele Maschinen => Mehr ausfälle
-  * Verwendung von gewöhnlichen User-PCs \\ Problem der Ausfallbehebung
-Was sind Probleme im Umgang mit Computerclustern?
-  * Viele Maschinen bedeutet erhöhte Ausfallrate
-  * Viele Maschinen bedeutet, dass auch mit langsamen Maschinen umgegangen werden muss
-  * Die Rechenleistung einzelner Maschinen sinkt
-  * Das Verschicken von Daten ist teuer
-==== Aufgabe 2 ====
-=== a) ===
-<code java>
-JavaRDD<String[]> gefiltert = linesfilter(
-  new Function<String[]>, Boolean>() {
-    public Boolean call(String[] s) {
-      return !(s[5] == "404" && Integer.parseInt(s[6] > 0));
-    }
-  }
-);
-</code>
-<code python>
-gefiltert = linesfilter(lambda x : not(x[5] == "404" and int(x[6]) > 0))
-</code>
-=== b) ===
-MapReduce:
-  * Im Map-Schritt werden key-value-Paare erzeugt, bei denen die IP-Adresse (als key) auf die Anzahl  übertragener Bytes (als Value) mapt. (''map()''-Methode oder ''mapToPair()''-Methode).
-  * Im Reduce0SChritt werden die übertragenen Bytes pro IP-Adresse aufaddiert (''reduceByKye()''-Methode)
-<code Java>
-JavaPairRDD<String, Integer> pairs = getfilter.mapToPair(
-  new PairFunction<String[], String, Integer>() {
-    public Tupel2<String, Integer> call(String[]) {
-      return new Tupel2(s[0], Integer.parseInt(s[6]));
-    }
-  }
-);
-JavaRDD<String, Integer> summiert = pairs.reduceByKey(
-  new Function2<Integer, Integer, Integer>() {
-    public Integer call<Integeri, Integer j) {
-      return i+j;
-    }
-  }
-);
-</code>
 ===== ACID =====
@@ Line 546: / Line 8: @@
   * Isolation (Man muss sich aleine fühlen)
   * Durability (Abgeschlossene Transaktionen sind von dauer)
-  *