• 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 $\{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!

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

⇒ 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!

⇒ 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!

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

• 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!

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):
  1. Wachstumsphase (lock)
  2. 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

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)
b)
c)

	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.

• DB-Anwendung
• DBS
  • DBMS
  • DB

• Falsch
  Die Knoten sind die Transaktionen
• Wahr
• Wahr
  mindestens alles was ich
• Fals
  Das währe FOCC

Zyklus in Graph ⇒ Es liegen verklemmungen vor

• 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

• 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

$T_2, T_3, T_5, T_4, T_1$

• 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

Loggranulat ⇐ Sperrgranulat, sonst Lost Updates ???

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

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

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

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.

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:

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)

• 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:

UNDO:

Slektives REDO:

UNDO:

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 

• 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 …

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

Jeder mit jedem $|R| \cdot |S| = 10 \cdot 10 = 100$

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$

Hashfunktion h(x) = x mod 5

Jeder wird mit jedem, aber nur innerhalb des Buckets verglichen.

$19$

Hashfunktion für Blockbildung: $h_B(x) = x mod 3$

Hashfunktion für Join: $h(x) = x mod 2$ (gerade und ungerade im Block miteinander Vergleichen)

$16$

$|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

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$

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

Die selbe Rechnung nochmal ⇒ D.h. für ein Fünftel d. Plattenzugriffe benötigt man ca. das 10-Fache an cache

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

R_2

Dann gilt $\pi_B(R_1 \cap R_2) = \{\}$, aber $\pi_B(R_1) \cap \pi_B(R_2) = {b}$

$\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$

….

$\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.

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

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

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)

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;
    }
  }
);

Spark nutzt den Hauptspeicher und reduziert dadurch die Anzahl der Plattenzugriffe.

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