Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

====== Zusammenfassung ======
Die Mega-Übersicht
<code>
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
</code>

  * [[Synchronisation]]

===== Grundbegriffe =====
==== Anforderungen (Codd) ====
  * **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)

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

==== ACID ====
  * 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)


==== Serialisierungs-Graph ====
^ x ^ y ^ z | <- Attribute |
|  $r_1$  |  $w_2$  |  $r_1$  | <- $\text{Operation}_\text{Transaktion}$ |
|  $r_2$  |  $r_3$  |  $w_1$  | ::: |
|  $w_2$  |  $w_3$  |  $r_4$  | ::: |
|         |         |  $w_3$  | ::: |

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

==== Anomalien ====
=== Lost update ===
^ t1 |  r(x)  |        |  w(x)  |
^ t2 |        |  w(x)  |        |

=== Dirty read/write ===
^ t1 |  w(x)  |        |  w(x)  |
^ t2 |        |  r(x)  |        |

=== Non-repeatable read ===
^ t1 |  r(x)  |        |  r(x)  |
^ t2 |        |  w(x)  |        |

=== Phantom-Problem ===
//Non-repeatable read// mit Aggregiertem read

==== Eigenschaften von Schedules ====
Eigenschaften eines Schedules:
^  Schedule ^ Beschreibung ^
| allgemein                     | Durcheinander                                              |
| seriell                       | Blockform                                                  |
| serialisierbar                | allgemein + seriell (Zyklenfrei)                           |
| rücksetzbar                   | ''commit'' erst nach ''commit'' von denen ich gelesen habe |
| ohne kaskadiertes \\ Rollback | Keine Daten einer laufenden TA lesen                       |
| strikt                        | Keine Daten einer laufenden TA lesen/schreiben             |


Eigenschaften zwischen Schedules:
^  Schedule ^ Beschreibung ^
| konfliktäquivalent | Gleiche Abhängigkeitsmengen |

===== Integrität =====
  * Schlüssel-~
  * Referenzielle ~
  * Multiplititäten Constraints
  * 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


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

xxxxxxxxxx
 
====== Zusammenfassung ======Die Mega-Übersicht<code>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</code>​  * [[Synchronisation]]​===== Grundbegriffe ========= Anforderungen (Codd) ====  * **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)​==== Ebenen ====|  Anwendungen (mehrere)                                       ||^         Externe Ebene | Views (mehrere)                       |^                       |  ↓↓ Logische Datenunabhängigkeit ↓↓   |^  Konzeptionelle Ebene |                                       |^                       |  ↓↓ Physische Datenunabhängigkeit ↓↓  |^         Interne Ebene | Speicherformat                        |​==== ACID ====  * 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)​​==== Serialisierungs-Graph ====^ x ^ y ^ z | <- Attribute ||  $r_1$  |  $w_2$  |  $r_1$  | <- $\text{Operation}_\text{Transaktion}$ ||  $r_2$  |  $r_3$  |  $w_1$  | ::: ||  $w_2$  |  $w_3$  |  $r_4$  | ::: ||         |         |  $w_3$  | ::: |​Spaltenweise von oben nach unten die $wr(x), rw(x), ww(x)$-Paare finden​==== Anomalien ======= Lost update ===^ t1 |  r(x)  |        |  w(x)  |^ t2 |        |  w(x)  |        |​=== Dirty read/write ===^ t1 |  w(x)  |        |  w(x)  |^ t2 |        |  r(x)  |        |​=== Non-repeatable read ===^ t1 |  r(x)  |        |  r(x)  |^ t2 |        |  w(x)  |        |​=== Phantom-Problem ===//Non-repeatable read// mit Aggregiertem read​==== Eigenschaften von Schedules ====Eigenschaften eines Schedules:^  Schedule ^ Beschreibung ^| allgemein                     | Durcheinander                                              || seriell                       | Blockform                                                  || serialisierbar                | allgemein + seriell (Zyklenfrei)                           || rücksetzbar                   | ''commit'' erst nach ''commit'' von denen ich gelesen habe || ohne kaskadiertes \\ Rollback | Keine Daten einer laufenden TA lesen                       || strikt                        | Keine Daten einer laufenden TA lesen/schreiben             |​​Eigenschaften zwischen Schedules:^  Schedule ^ Beschreibung ^| konfliktäquivalent | Gleiche Abhängigkeitsmengen |​===== Integrität =====  * Schlüssel-~  * Referenzielle ~  * Multiplititäten Constraints  * 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​​===== 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