Wiki - uni:8:dbs2

Datenbanksysteme II

anonymous@undisclosed.example.com (Anonymous) — Wed, 18 Nov 2020 17:11:25 +0000

2015-07-16 17:08		current
Line 1:		Line 1:
	====== Datenbanksysteme II ======		====== Datenbanksysteme II ======
-	[übungen]	+	* [[übungen]]
		+	* [[zusammenfassung]]

	===== ACID =====		===== ACID =====

Synchronisation

anonymous@undisclosed.example.com (Anonymous) — Wed, 18 Nov 2020 17:11:25 +0000

2015-07-17 23:26		current
Line 1:		Line 1:
	====== Synchronisation ======		====== Synchronisation ======
	===== Pessimistische Synchronisation mit Sperren =====		===== Pessimistische Synchronisation mit Sperren =====
-
	==== Sperrprotokoll ====		==== Sperrprotokoll ====

Line 18:		Line 17:
	\| 3 \| lang \| lang \|		\| 3 \| lang \| lang \|

-	===== Sperrverfahren =====	+	==== Sperrverfahren ====
-	==== Verfahren ====	+	=== Verfahren ===
-	=== (Voll) ===	+	== (Voll) ==
	^ ^ X ^		^ ^ X ^
	^ X \| (-) \|		^ X \| (-) \|

-	=== RX ===	+	== RX ==
	^ ^ R ^ X ^		^ ^ R ^ X ^
	^ R \| (+) \| (-) \|		^ R \| (+) \| (-) \|
	^ X \| (-) \| (-) \|		^ X \| (-) \| (-) \|

-	=== RUX ===	+	== RUX ==
	* U: update/lesen		* U: update/lesen

Line 41:		Line 40:
	* U -> X: Möchte jetzt schreiben		* U -> X: Möchte jetzt schreiben

-	=== RAX ===	+	== RAX ==
	* A: = U (update/lesen)		* A: = U (update/lesen)

Line 51:		Line 50:
	Übergänge:		Übergänge:
	* A -> X: Möchte jetzt schreiben		* A -> X: Möchte jetzt schreiben
-	=== RIX ===	+
		+
		+	== RIX ==
	Auf oberer Ebene (Tabelle):		Auf oberer Ebene (Tabelle):
	^ ^ R ^ X ^ IR ^ IX ^ RIX ^		^ ^ R ^ X ^ IR ^ IX ^ RIX ^
Line 73:		Line 74:

	Auf unterer Ebene (Tupel): RX/RUX/RAX		Auf unterer Ebene (Tupel): RX/RUX/RAX
-	=== RAC ===	+
		+	== RAC ==
	* A Änderung $V_\text{neu}$ im cache		* A Änderung $V_\text{neu}$ im cache
	* C $V_\text{alt}$ wird noch von alten Lesern gelesen		* C $V_\text{alt}$ wird noch von alten Lesern gelesen
Line 84:		Line 86:
	Übergänge:		Übergänge:
	* A -> C: Bei commit		* A -> C: Bei commit
-	==== Eigenschaften ====	+	=== Eigenschaften ===
	^ Verfahren ^ Kein Verhungern ^ Deadlockfrei \\ selbes Obj. ^ Deadlockfrei \\ anderes Obj. ^ Schedule ^ Bemerkung ^		^ Verfahren ^ Kein Verhungern ^ Deadlockfrei \\ selbes Obj. ^ Deadlockfrei \\ anderes Obj. ^ Schedule ^ Bemerkung ^
	\| RX \| (X) \| (X) \| (X) \| kaskadierte freies rücksetzen \| Parallele Leser \|		\| RX \| (X) \| (X) \| (X) \| kaskadierte freies rücksetzen \| Parallele Leser \|
	\| RUX \| (V) \| (V) \| (X) \| \| Parallele Leser \|		\| RUX \| (V) \| (V) \| (X) \| \| Parallele Leser \|
	\| RAX \| (X) \| (V) \| (X) \| \| Zwar nach kein verklemmen, dafür verhungern für mehr Parallelität \|		\| RAX \| (X) \| (V) \| (X) \| \| Zwar nach kein verklemmen, dafür verhungern für mehr Parallelität \|
		+
		+	==== Deadlocks ====
		+	Können entweder
		+	* Vermeiden werden (konservatives 2PL/precaiming) oder
		+	* Erkannt werden
		+	* Wartegraph (Teuer)
		+	* Time-Out
		+
		+	=== Wartegraph ===
		+	Ich -> warte auf X
		+
		+	=== Time-Out ===
		+
		+	^ ^ Jüngere TA hält Sperre ^ Ältere TA hält Sperre ^
		+	^ Wound-Wait \| => ältere TA "verwundet" (Wound) jüngere TA; \\ //jüngere// TA wird //zurückgesetzt//! \| => //jüngere// TA "//wartet//" (Wait) \|
		+	^ Wait-Die \| => //ältere// TA "//wartet//" (Wait) \| => ältere TA "tötet" (Die) jüngere TA; \\ //jüngere// TA wird //zurückgesetzt//! \|
		+
		+	* Es wird immer die Jüngere getötet
		+	* Es wird immer die anfragende warten
		+	* Name: <Jüngere TA hält Sperre>-<Ältere TA hält Sperre>
		+
		+	===== Pessimistische Synchronisation mit Zeitstempeln =====
		+	* Jedes Objekt hat Zeitstepel der jüngsten TA pro read/write
		+	* Beim Zugriff prüfen:
		+	\| Leser \| älter als jüngster Schreiber \| des Objekts => Leser zurücksetzen \| $TS(T_i) < \text{writeTS}(O)$ \|
		+	\| Schreiber \| älter als jüngster Schreiber oder Leser \| des Objekts => Schreiber zurücksetzen \| $TS(T_i) < \text{writeTS}(O) \vee TS(T_i) < \text{readTS}(O)$ \|
		+
		+	===== Optimistische Synchronisation mit Zeitstempeln =====
		+	* Änderungen im RAM
		+	* RS und WS der angefassten Objekte pro TA speichern
		+	* Bei Commit validieren, dann raus schreiben
		+
		+	==== BOCC ====
		+	Mein RS mit WS, beendeter TA (während meiner TA)
		+
		+	Bei Konflikt:
		+	* Nur ich kann noch zurückgesetzt werden
		+
		+	==== BOCC+ ====
		+	==== FOCC ====
		+	Mein RS mit WS, laufender TA
		+
		+	Bei Konflikt:
		+	* Kill: Ich kill die laufenden TAs
		+	* Die: I die

Übungen

anonymous@undisclosed.example.com (Anonymous) — Wed, 18 Nov 2020 17:11:25 +0000

2026-04-25 10:44	current
Line 1:	Line 1:
	+	====== Ü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 $\{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>
	+
	+	=== c) ===
	+	Spark nutzt den Hauptspeicher und reduziert dadurch die Anzahl der Plattenzugriffe.
	+
	+
	+	==== Aufgabe 3 ====
	+	Polynomielle Multiplikation um mögliche Ergebnisse aufzuzählen!
	+
	+	<code>
	+	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.8x + 0.2) + (0.5x + 0.5) + (0.6x + 0.4) + (0.1x + 0.9)
	+	= (0.4x^2 + 0.4x^1 + 0.1x^1 + 0.1x^0) * (0.6x + 0.4) (0.1*x + 0.9)
	+	= (0.4x^2 + 0.5x^1 + 0.1x^0) ...
	+	= (0.024x^4 + 0.216x^3 + 0.046^x^3 + 0.414x^2 + 0.026x^2 + 0.234x + 0.004x + 0.036
	+	= 0.024x^4 + 0.262x^3 + 0.440x^2 + 0.238x^1 + 0.036*x^0
	+	</code>

Zusammenfassung

anonymous@undisclosed.example.com (Anonymous) — Wed, 18 Nov 2020 17:11:25 +0000

2015-07-19 18:00		current
Line 199:		Line 199:
	== Star ==		== Star ==
	Eine Tabelle pro Dimension		Eine Tabelle pro Dimension
		+
		+
		+	===== Recovery =====
		+	==== Fehlerarten ====
		+	* Transaktionsfehler => Rücksetzen
		+	* Lokales UNDO
		+	* Systemfehler => Warmstart
		+	* Globales UNDO
		+	* Globales REDO
		+	* Medienfehler => Geräte-Recovery
		+	* Globales REDO
		+
		+	==== Logging ====
		+	* Physisch [Bit-Blöcke]
		+	* Übergangslogging [XOR]
		+	* Zustandslogging [Volle ...]
		+	* Seiten-Logging [... Seiten]
		+	* Eintrags-Logging [... Einträge]
		+	* Logisches Logging [Befehle/Parameter loggen]
		+	* Physiologisches Logging [Befehle/Parameter pro Seite]
		+
		+	=== Aufbau Log-File ===
		+	Ringbuffer
		+	* LSN (Fortlaufende Nummer)
		+	* TA-ID (Welche Transaktion)
		+	* Page-ID (Welche Seite)
		+	* REDO
		+	* UNDO
		+	* PrevLSN
		+
		+	Log-Granularität $<=$ Sperrgranularität
		+
		+	=== Einbringungsstrategie (wo in DB) ===
		+	* Direkt (NonAtomic, Update in-place) => UNDO nötig
		+	* Indirektes Einbringen (Atomic) ["Daneben ablegen"] => Kein UNDO nötig
		+
		+	=== Verdrängungsstrategien (wann frühestens Puffer -> DB) ===
		+	* No-Steal [Nach COMMIT] => Kein UNDO
		+	* Steal [egal] => UNDO
		+
		+	WAL-Prinzip: UNDO muss vor Änderungen an DB im Log stehen
		+
		+	=== Ausschreibungsstrategie (wann spätestens Puffer -> DB) ===
		+	* Force [Vor COMMIT] => Kein REDO
		+	* No-Force [egal] => REDO
		+
		+	COMMIT-Regel: REDO muss vor COMMIT im Log stehen
		+
		+	==== Sicherungen ====
		+	=== Arten ===
		+	* TOC: Sicherung //einer// TA (entspricht Force)
		+	* TCC: Alle Änderungen raus schreiben, derweil keine //TA//.
		+	* ACC: Alle Änderungen raus schreiben, derweil keine //Operation//.
		+
		+	=== Ablauf ===
		+	\| 1. Analyse \| Gewinner/Verlierer Bestimmen \|\|
		+	\| 2. REDO \| Vollständiges REDO \| Gewinner REDO \|
		+	\| 3. UNDO \| UNDO (damals) laufender TAs \| UNDO verlierer TA \|
		+	\| 4. Abschluss \| Sicherungspunkt erstellen \|\|
		+
		+	* Gewinner => COMMIT im log
		+	* Verlierer => Rest