Table of Contents

Übungen

Übung 1

Aufgabe 1

Mögliche Abhängigkeiten

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$ & $S_2$ sind nicht Konfliktäquivalent!

b

⇒ Gleiche Tranasktions- & Aktionsmenge!

Abhängigkeiten:

⇒ $S_1$ & $S_2$ sind Konfliktäquivalent!

Aufgabe 2

Serialisierungs-/Abhängigkeitsgraph:

a) T1, T2, T4, T3 oder T1, T4, T2, T3 b) nicht serialisierbar

Aufgabe 3

⇒ Annomalien können nur auftreten, wenn Isolation verletzt wird!

Übung 2

Aufgabe 1

Legaler Schedule

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

Es gild

S0

S1

S2

S3

S4

Aufgabe 2

Verklemmung bezgl. Zugriff auf Verschiedene Objekte:

  1. T1 hält x(x)
  2. T1 will x(y)
  3. T2 hält x(y)
  4. 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)

Aufbau

Anwendungen (mehrere)
Externe Ebene Views (mehrere)
↓↓ Logische Datenunabhängigkeit ↓↓
Konzeptionelle Ebene
↓↓ Physische Datenunabhängigkeit ↓↓
Interne Ebene Speicherformat

Probeklausur 1/2

Aufgabe 1

Aufgabe 2

a)

Zyklus in Graph ⇒ Es liegen verklemmungen vor

b)

⇒ $T_1$ kommt durch

c)

⇒ $T_3$ & $T_1$ kommen durch

Aufgabe 3

$T_2, T_3, T_5, T_4, T_1$

Anforderungen

Neben an:

Drüber:

Übung 4

Aufgabe 1

a)

Loggranulat ⇐ Sperrgranulat, sonst Lost Updates ???

Update-in-place: geänderte Werte auf ursprüngliche Pos

b)

Einbringstrategien

Aufgabe 4

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

REDO Info muss vor COMMIT-Durchführung in der Log-Datei stehen (⇒ relevant für No-Focre)

Übung 5

Aufgabe 1

Aufgabe des Logging:

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:

Phasen der Crash-Recovery:

  1. Analysephase
    1. Lies Log-Datei von letztem Check Point bis Ende
    2. Bestimme Gewinner & Verlierer TAs:
      • Gewinner: COMMIT-Satz in Log
      • Verlierer: Kein COMMIT-Satz im Log
    3. Ermittler geänderte Seiten
  2. REDO-Phase
    1. Vorwärtslesen der Log-Datei, ausgehend vom letzten Sicherungspunkt.
    2. 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
  3. UNDO-Phase
    1. Rückwärtslesen der Log-Datei bis BOT der ältesten Verlierer TA
    2. 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)

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

Ü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)

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.

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?

Welche der folgenden Punkte machen für Big Data Sinn?

Was sind Probleme im Umgang mit Computerclustern?

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: 

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