Die Mega-Übersicht

Synchronisation
	Pessimistische Synchronisation mit Sperren
		Sperrprotokolle
			2PL [deadlocks]
			Konservatives 2PL
			Striktes 2PL [deadlocks]
			Konservatives + Striktes 2PL
		Sperrverfahren
			RX
			RUX
			RAX
			RIX
			RAC
		Deadlocks
			Vermeiden [konservatives 2PL/precaiming]
			Erkennen
				Wartegraph
				Time-Out
					wound-wait
					wait-die
	Pessimistische Synchronisation mit Zeitstempeln
	Optimistische Synchronisation mit Zeitstempeln
		BOCC
		BOCC+
		FOCC

• Synchronisation

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

• Atomic (Wenn, dann wird man als ganzes abgebrochen)
• Consistency (Konsistenter Zystand → Konsistenter Zustand)
• Isolation (Man muss sich aleine fühlen)
• Durability (Abgeschlossene Transaktionen sind von dauer)

Spaltenweise von oben nach unten die $wr(x), rw(x), ww(x)$-Paare finden

Non-repeatable read mit Aggregiertem read

Eigenschaften eines Schedules:

Eigenschaften zwischen Schedules:

• Schlüssel-~
• Referenzielle ~
• Multiplititäten Constraints
• Allgemeine Constraints

Explizite Autorisierung:

Subjekt bekommt Zugriffsrecht auf Objekt

grant ... on ... to ...

Implizite Autorisierung:

• starke Autorisierung überschreibt schwache Autorisierung
• Es gibt positive und negative Autorisierung
• Subjekte, Objekte und Operationen haben eine Hierarchie

• Implizite Weitergabe positiver Autorisierung in die eine Richtung
• Implizite Weitergabe negativer Autorisierung in die andere Richtung

• Sicherheitsklassen für Subjekte und Objekte
• Objekte hochstufen
• Objekte runter stufen
• Zugriff wenn class(S) >= class(O)
• Angelegte Objekte class(S) =< class(O)

B+

• Directory/Index Seiten
• Datenseiten

• Sequenziell
  $t_\text{scan} = t_\text{seek} + f \cdot t_\text{transfer} + \lceil \frac{f}{c_\text{puffer}} \rceil \cdot t_\text{lat}$
• Wahlfrei
  $t_\text{random} = (t_\text{seek} + c_\text{index} \cdot t_\text{transfer} + t_\text{lat}) \cdot a$

• Logische Anfrageoptimierung
  Auswertungsplan umbauen
• Physische Anfrageoptimierung
  Algorithmen auswählen

• $R \bowtie S = S \bowtie S$
• $R \cup S = S \cup R$
• $R \cap S = S \cap R$
• $R \times S = S \times R$
• $(R \bowtie S) \bowtie T = R \bowtie (S \bowtie T)$
• $(R \cup S) \cup T = R \cup (S \cup T)$
• $(R \cap S) \cap T = R \cap (S \cap T)$
• $(R \times S) \times T = R \times (S \times T)$
• $\sigma_A(\sigma_B(R)) = \sigma_B(\sigma_A(R))$
• $\sigma_{A \wedge B}(R) = \sigma_A(\sigma_B(R))$
• $\pi_A(\pi_B(R)) = \pi_A(R) \text{ mit } A \subseteq B$
• $\pi_A(\sigma_B(R)) = \sigma_B(\pi_A(R)) \text{ mit attr}(B) \subseteq A$
• $\sigma_B(R \bowtie S) = \sigma_B(R) \bowtie S \text{ mit attr}(B) \subseteq \text{ attr}(R)$
• $\sigma_B(R \times S) = \sigma_B(R) \times S \text{ mit attr}(B) \subseteq \text{ attr}(R)$
• $\sigma_B(R \cup S) = \sigma_B(R) \cup \sigma_B(S)$
• $\sigma_B(R \cap S) = \sigma_B(R) \cap \sigma_B(S)$
• $\sigma_B(R \setminus S) = \sigma_B(R) \setminus \sigma_B(S)$
• $\pi_B(R \cup S) = \pi_B(R) \cup \pi_B(S)$
• $\sigma_{A=B}(R \times S) = R \bowtie_{A=B} S$

1. $\sigma$ splitten
2. $\sigma$ nach unten
3. $\sigma$ und $\times$ ⇒ $\bowtie$
4. $\pi$ einfügen, um auf minimum beschränken
5. $\pi$ nach unten
6. $\sigma$ mergen

• high-volume
• high-velocity
• high-variety

1. Map
   Data ⇒ KV-Pair
2. Shuffle
   Same key to same node
3. Reduce
   Marge Values per Key

$F = (1 - P(A) + x \cdot P(A)) \cdot \ldots$

Fakten in hierachischen Dimensionen

Faktentabelle in der Mitte

Eine Tabelle pro Hierachieebene pro Dimension

Eine Tabelle pro Dimension

• Transaktionsfehler ⇒ Rücksetzen
  • Lokales UNDO
• Systemfehler ⇒ Warmstart
  • Globales UNDO
  • Globales REDO
• Medienfehler ⇒ Geräte-Recovery
  • Globales REDO

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

Ringbuffer

• LSN (Fortlaufende Nummer)
• TA-ID (Welche Transaktion)
• Page-ID (Welche Seite)
• REDO
• UNDO
• PrevLSN

Log-Granularität $<=$ Sperrgranularität

• Direkt (NonAtomic, Update in-place) ⇒ UNDO nötig
• Indirektes Einbringen (Atomic) [“Daneben ablegen”] ⇒ Kein UNDO nötig

• No-Steal [Nach COMMIT] ⇒ Kein UNDO
• Steal [egal] ⇒ UNDO

WAL-Prinzip: UNDO muss vor Änderungen an DB im Log stehen

• Force [Vor COMMIT] ⇒ Kein REDO
• No-Force [egal] ⇒ REDO

COMMIT-Regel: REDO muss vor COMMIT im Log stehen

• TOC: Sicherung einer TA (entspricht Force)
• TCC: Alle Änderungen raus schreiben, derweil keine TA.
• ACC: Alle Änderungen raus schreiben, derweil keine Operation.

• Gewinner ⇒ COMMIT im log
• Verlierer ⇒ Rest