−Table of Contents
Übungen
Übung 1
- Transaktion
Folge von Aktionen (read/write) die die DB von einem konsistenten Zustand in einen anderen Konsistenten Zustand überführt. - Hauptaufgabe der Transaktionen - Verwaltung
- Synchronisation (Koordination von mehreren Benutzerproxessen ⇒ Logische Einbenutzerbetrieb)
- Recovery (Behebung von Fehlersituationen)
- Eigenschaften von Transaktionen (ACID-Prinzip)
- Atomicy (Atomarität: EffektTransaktion trifft ganz oder gar icht in ???)
- Consistency (Konsistenz/Integritätserhaltung: Konsistenter Zustand ⇒ Konsistenter Zustand)
- Isolation (Isoliertheit: Logischer Einbenutzerbetrieb)
- Durability (Dauerhaftigkeit, Persistenz)
- Schedule
Folge von Aktionen (read/write) für eine Menge {T1,…,Tn} von Transaktionen, die durch Mischen der Aktionen der Transaktionen entsteht, wobei die Reihenfolge innerhalb der Transaktionen beibehalten wird. - Serieller Schedule
Schedule S von {T1,…,Tn}, 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 {T1,…,Tn}, der die selbe Wirkung hat, wie ein belibiger serieller von {T1,…,Tn} ⇒ Nur serialisierbarer Schedules dürfen zugelassen werden!
Aufgabe 1
Mögliche Abhängigkeiten
- rw
- wr
- ww
Für S1 T1 = (r(v), w(v)) T2 = (w(x), w(w), r(v)) T3 = (w(z), r(y), w(x)) T4 = (r(w), r(z), W(y))
a
⇒ Gleiche Tranasktions- & Aktionsmenge!
Abhängigkeiten:
- S1: rw4,2(w),wr1,2(v),wr3,4(z),ww2,3(x),rw3,4(y)
- S2: rw4,2(w),wr1,2(v),ww2,3(x),rw4,3(z),rw3,4(y)
⇒ S1 & S2 sind nicht Konfliktäquivalent!
b
⇒ Gleiche Tranasktions- & Aktionsmenge!
Abhängigkeiten:
- S1: rw4,2(w),wr1,2(v),wr3,4(z),ww2,3(x),rw3,4(y)
- S3: wr3,4(z),wr1,2(v),ww2,3(x),rw4,2(w),rw3,4(y)
⇒ S1 & S2 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(r1(x),w2(x),w1(x))
⇒ Änderungen einer Transaktion werden durch eine andere Transaktion überschrieben und gehen verloren. - b): Dirty Read/Write: S(w1(x),r2(x),w1(x))
⇒ Zugriff auf “Schmutzige” Daten ⇒ Objekte, die von einer noch nicht beendenen Transaktion geändert werden - c): Non-Repeatable Read: S(r1(x).w2(x),r1(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) | ![]() | ![]() | ![]() |
b) | ![]() | ![]() | ![]() |
c) | ![]() | ![]() | ![]() |
Aufgabe 3
R | X | IR | IX | RIX | |
---|---|---|---|---|---|
R | ![]() | ![]() | ![]() | ![]() | ![]() |
X | ![]() | ![]() | ![]() | ![]() | ![]() |
IR | ![]() | ![]() | ![]() | ![]() | ![]() |
IX | ![]() | ![]() | ![]() | ![]() | ![]() |
RIX | ![]() | ![]() | ![]() | ![]() | ![]() |
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)
- L1(y) ⇒ T3 wird zurückgesetzt
- L2(z) ⇒ T2 wartet
- L1(x) ⇒ T2 wird zurückgesetzt
- L3(x) ⇒ T3 bereits zurückgesetzt
⇒ T1 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!
- L1(y) ⇒ T1 wartet
- L2(z) ⇒ T2 wird zurückgesetzt
- L1(x) ⇒ T1 wartet bereits auf die Freigabe von y
- L3(x) ⇒ T3 bekommt sperre, da T2 zurückgesetzt wurde und T1 noch auf die Freigabe von y wartet (nicht so weit kam sich x zu schnappen)
⇒ T3 & T1 kommen durch
Aufgabe 3
T2,T3,T5,T4,T1
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) |
---|---|---|
PA | 90 | 90 |
PB | 130 | 0 |
PC | 50 | 50 |
PD | 70 | 0 |
PE | 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: T1 & T3
- Verlierer TAs: T2 & T4
- Betroffene Seiten: PA, PB, PC, PD, PE
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) |
---|---|---|---|
T1 | PB | 0<20 | PB,20 |
T4 | PC | 50≮50 | |
T1 | PE | 60≮60 | |
T4 | PD | 0<70 | PD,70 |
T2 | PA | 90≮90 | |
T3 | PE | 60<110 | PE,110 |
T2 | PB | 0<130 | PB,130 |
UNDO:
TA | Seite | Zur Log-Date hinzugefügte Log-Einträge | Änderungen auf der DB Platte |
---|---|---|---|
T2 | PB | 180,T2,PB,R(B),U(B),130 | PB,180 |
T2 | PA | 190,T2,PA,R(A),U(A),180 | PA,190 |
T4 | PD | 200,T4,PD,R(D),U(D),70 | PD,200 |
T4 | PC | 210,T4,PC,R(C),U(C),200 | PC,210 |
Slektives REDO:
TA | Seite | Page LSN vs LSN | Änderungen in DB (Platte) |
---|---|---|---|
T1 | PB | 0<20 | PB,20 |
T1 | PE | 60≮60 | |
T3 | PE | 60≮110 | PE,110 |
UNDO:
TA | Seite |
---|
Übung 6
Aufgabe 2
a)
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
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 ˆ=\nicefrac15.
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|⋅|S|=10⋅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⋅2=2 |
1 | 1, 6, 11 | 1, 6 | 3⋅2=6 |
2 | 2, 7, 12 | 2 | 3⋅1=3 |
3 | 3,13 | 3,8,13 | 2⋅3=6 |
4 | 9 | 4, 14 | 1⋅2=2 |
Sum | 19 |
Jeder wird mit jedem, aber nur innerhalb des Buckets verglichen.
19
d)
Hashfunktion für Blockbildung: hB(x)=xmod3
hB(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)=xmod2 (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 ⌈BR|C|−1⌉ mal i.d. Cache geladen.
- Insgesammt: BR+BS⋅⌈BR|C|−1⌉ = Plattenzugriffe
a)
Plattenzugriffe = BR+BS⋅⌈BR|C|−1⌉=10000+10000⋅⌈10000|1000|−1⌉=120000
b)
Höchstens 100.000 Plattenzugriffe
10000+10000⋅⌈10000|C|−1⌉<=100000
⌈10000|C|−1⌉<=9
frac100009<|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 πB(R1∩R2)={}, aber πB(R1)∩πB(R2)=b
d)
πl(R1 cupR2)=πl(R1)∪πl(R2)
sei t∈πl(R1∪R2)⇔∃a∈R1∪R2:a.l=t
⇔∃b∈R1:b.l=t∨∃c∈R2:c.l=t
….
e)
πl(R1−R2)=πl(R1)−πl(R2) (Für die Differenz werden alle Tupel aus R1 entfernt, die auch in R2 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)
JavaRDD<String[]> gefiltert = linesfilter( new Function<String[]>, Boolean>() { public Boolean call(String[] s) { return !(s[5] == "404" && Integer.parseInt(s[6] > 0)); } } );
gefiltert = linesfilter(lambda x : not(x[5] == "404" and int(x[6]) > 0))
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 odermapToPair()
-Methode). - Im Reduce0SChritt werden die übertragenen Bytes pro IP-Adresse aufaddiert (
reduceByKye()
-Methode)
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; } } );
c)
Spark nutzt den Hauptspeicher und reduziert dadurch die Anzahl der Plattenzugriffe.
Aufgabe 3
Polynomielle Multiplikation um mögliche Ergebnisse aufzuzählen!
F = (P(Attenberger) * x + 1-P(Attenberger)) * (P(Brunner) * x + 1-P(Brunner)) * (P(Carl) * x + 1-P(Carl)) * (P(Deschler) * x + 1-P(Deschler)) = (0.8*x + 0.2) + (0.5*x + 0.5) + (0.6*x + 0.4) + (0.1*x + 0.9) = (0.4*x^2 + 0.4*x^1 + 0.1*x^1 + 0.1*x^0) * (0.6*x + 0.4) * (0.1*x + 0.9) = (0.4*x^2 + 0.5*x^1 + 0.1*x^0) * ... = (0.024*x^4 + 0.216*x^3 + 0.046^x^3 + 0.414*x^2 + 0.026*x^2 + 0.234*x + 0.004*x + 0.036 = 0.024*x^4 + 0.262*x^3 + 0.440*x^2 + 0.238*x^1 + 0.036*x^0