Differences

This shows you the differences between two versions of the page.

--- uni:8:dbs2:zusammenfassung [2015-07-17 18:13] – skrupellos
+++ uni:8:dbs2:zusammenfassung [2020-11-18 18:11] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
 ====== Zusammenfassung ======
+Die Mega-Übersicht
+<code>
+Synchronisation
+	Pessimistische Synchronisation mit Sperren
+		Sperrprotokolle
+PL [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
+</code>
+  * [[Synchronisation]]
 ===== Grundbegriffe =====
 ==== Anforderungen (Codd) ====
@@ Line 25: / Line 56: @@
   * Durability (Abgeschlossene Transaktionen sind von dauer)
-===== Synchronisation =====
 ==== Serialisierungs-Graph ====
 ^ x ^ y ^ z | <- Attribute |
@@ Line 66: / Line 97: @@
 | konfliktäquivalent | Gleiche Abhängigkeitsmengen |
-===== Locking =====
+===== Integrität =====
-==== Verfahren ====
+  * Schlüssel-~
-=== (Voll) ===
+  * Referenzielle ~
-^    ^   X   ^
+  * Multiplititäten Constraints
-^  X |  (-)  |
+  * Allgemeine Constraints
+===== Datenschutz =====
+==== Discretionary Access Controll (DAC) ====
+Explizite Autorisierung:
+<blockquote>//Subjekt// bekommt //Zugriffsrecht// auf //Objekt//</blockquote>
+  grant ... on ... to ...
+==== Verfeinertes DAC ====
+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
+==== Mandatory Access Control (MAC) ====
+  * Sicherheitsklassen für //Subjekte// und //Objekte//
+  * Objekte hochstufen (V)
+  * Objekte runter stufen (X)
+  * Zugriff wenn ''class(S) >= class(O)''
+  * Angelegte Objekte ''class(S) =< class(O)''
+===== HW =====
+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$
+===== Anfrageoptimierung =====
+==== Arten ====
+  * **Logische Anfrageoptimierung** \\ Auswertungsplan umbauen
+  * **Physische Anfrageoptimierung** \\ Algorithmen auswählen
+==== Logische Anfrageoptimierung ====
+=== Umformungsregeln ===
+  *  $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$
+=== Algo ===
+  -  $\sigma$  splitten
+  -  $\sigma$  nach unten
+  -  $\sigma$  und  $\times$  =>  $\bowtie$
+  -  $\pi$  einfügen, um auf minimum beschränken
+  -  $\pi$  nach unten
+  -  $\sigma$  mergen
+===== Big Data =====
+  * high-**volume**
+  * high-**velocity**
+  * high-**variety**
+==== Map-Reduce ====
+  - **Map** \\ Data => KV-Pair
+  - **Shuffle** \\ Same key to same node
+  - **Reduce** \\ Marge Values per Key
+==== Zählanfrage auf unsicheren Daten ====
+ $F = (1 - P(A) + x \cdot P(A)) \cdot \ldots$
+==== Data Warehouse ====
+| OLTP                          | OLAP                         |
+| Online Transaction Processing | Online Analytical Processing |
+| Detail                        | Nur relevante                |
+| Aktuelle                      | Historische                  |
+| Ist eine quelle               | Hat viele quellen            |
+| Veränderbar                   | Nur hinzufügen               |
+<blockquote>//Fakten// in //hierachischen// //Dimensionen//</blockquote>
+=== Relationales mapping ===
+Faktentabelle in der Mitte
+== Snowflake ==
+Eine Tabelle pro Hierachieebene pro Dimension
+== Star ==
+Eine Tabelle pro Dimension
-=== RX ===
+===== Recovery =====
-^    ^   R   ^   X   ^
+==== Fehlerarten ====
-^  R |  (+)  |  (-)  |
+  * Transaktionsfehler => Rücksetzen
-^  X |  (-)  |  (-)  |
+    * Lokales UNDO
+  * Systemfehler => Warmstart
+    * Globales UNDO
+    * Globales REDO
+  * Medienfehler => Geräte-Recovery
+    * Globales REDO
-=== RUX ===
+==== Logging ====
-  * U: update/lesen
+  * Physisch [Bit-Blöcke]
-^    ^   R   ^   U   ^   X   ^
+    * Übergangslogging [XOR]
-^  R |  (+)  |  (-)  |  (-)  |
+    * Zustandslogging [Volle ...]
-^  U |  (+)  |  (-)  |  (-)  |
+      * Seiten-Logging [... Seiten]
-^  X |  (-)  |  (-)  |  (-)  |
+      * Eintrags-Logging [... Einträge]
+  * Logisches Logging [Befehle/Parameter loggen]
+  * Physiologisches Logging [Befehle/Parameter pro Seite]
-Übergänge:
+=== Aufbau Log-File ===
-  * U -> X: Möchte jetzt schreiben
+Ringbuffer
+  * LSN (Fortlaufende Nummer)
+  * TA-ID (Welche Transaktion)
+  * Page-ID (Welche Seite)
+  * REDO
+  * UNDO
+  * PrevLSN
-=== RAX ===
+Log-Granularität $<=$ Sperrgranularität
-  * A: = U (update/lesen)
-^    ^   R   ^   A   ^   X   ^
+=== Einbringungsstrategie (wo in DB) ===
-^  R |  (+)  |  (+)  |  (-)  |
+  * Direkt (NonAtomic, Update in-place) => UNDO nötig
-^  A |  (+)  |  (-)  |  (-)  |
+  * Indirektes Einbringen (Atomic) ["Daneben ablegen"] => Kein UNDO nötig
-^  X |  (-)  |  (-)  |  (-)  |
-Übergänge:
+=== Verdrängungsstrategien (wann frühestens Puffer -> DB) ===
-  * A -> X: Möchte jetzt schreiben
+  * No-Steal [Nach COMMIT] => Kein UNDO
-=== RIX ===
+  * Steal [egal] => UNDO
-Auf oberer Ebene (Tabelle):
-^      ^   R   ^   X   ^   IR  ^   IX  ^  RIX  ^
-^    R |  (+)  |  (-)  |  (+)  |  (-)  |  (-)  |
-^    X |  (-)  |  (-)  |  (-)  |  (-)  |  (-)  |
-^   IR |  (+)  |  (-)  |  (+)  ^  (+)  ^  (+)  |
-^   IX |  (-)  |  (-)  ^  (+)  ^  (+)  |  (-)  |
-^  RIX |  (-)  |  (-)  ^  (+)  |  (-)  |  (-)  |
-^ Überprüfung auf unterer Ebene nötig  ^
+WAL-Prinzip: UNDO muss vor Änderungen an DB im Log stehen
-  * Obere Ebene hat ...
+=== Ausschreibungsstrategie (wann spätestens Puffer -> DB) ===
-    * **R**
+  * Force [Vor COMMIT] => Kein REDO
-    * **X**
+  * No-Force [egal] => REDO
-  * Untere Ebene hat ...
-    * R => **IR**
-    * X => **IX**
-  * Obere Ebene hat //R//, untere Ebene hat //X// ...
-    * **RIX** (mix aus //R// und //IX//)
+COMMIT-Regel: REDO muss vor COMMIT im Log stehen
-Auf unterer Ebene (Tupel): RX/RUX/RAX
+==== Sicherungen ====
-=== RAC ===
+=== Arten ===
-  * **A** Änderung  $V_\text{neu}$  im cache
+  * TOC: Sicherung //einer// TA (entspricht Force)
-  * **C**  $V_\text{alt}$  wird noch von alten Lesern gelesen
+  * TCC: Alle Änderungen raus schreiben, derweil keine //TA//.
+  * ACC: Alle Änderungen raus schreiben, derweil keine //Operation//.
-^    ^   R   ^   A   ^   C   ^
+=== Ablauf ===
-^  R |  (+)  |  (+)  |  (+)  |
+| 1. Analyse   | Gewinner/Verlierer Bestimmen                    ||
-^  A |  (+)  |  (-)  |  (-)  |
+| 2. REDO      | Vollständiges REDO          | Gewinner REDO      |
-^  C |  (+)  |  (-)  |  (-)  |
+| 3. UNDO      | UNDO (damals) laufender TAs | UNDO verlierer TA  |
+| 4. Abschluss | Sicherungspunkt erstellen                       ||
-Übergänge:
+  * Gewinner => COMMIT im log
-  * A -> C: Bei commit
+  * Verlierer => Rest
-==== Eigenschaften ====
-^ Verfahren ^ Kein Verhungern ^ Deadlockfrei \\ selbes Obj.  ^ Deadlockfrei \\ anderes Obj.  ^ Schedule ^ Bemerkung ^
-|   RX | (X) | (X) |  (X) | kaskadierte freies rücksetzen | Parallele Leser |
-|  RUX | (V) | (V) |  (X) |  | Parallele Leser |
-|  RAX | (X) | (V) |  (X) |  | Zwar nach kein verklemmen, dafür verhungern für mehr Parallelität  |