Differences

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

--- uni:5:dbs [2014-01-28 01:04] – [Normalisierung] skrupellos
+++ uni:5:dbs [2020-11-18 18:11] (current) – external edit 127.0.0.1
@@ Line 89: / Line 89: @@
   * **Kostenbasiert** \\ Iterativ Heuristiken ausprobieren und Kostenentwicklung beobachten
+===== Transaktionen =====
+  * **Atomicity**
+  * **Consistency**
+  * **Isolation**
+  * **Durability**
+==== Datensicherheit ====
+Technische Fehler
+^ Wann ^ Was ^ Undo ^ Redo ^
+| Transaktionsfehler | Rücksetzen | //Lokales Undo// \\ nicht abgeschlossene Transaktion rückgängig | |
+| Systemfehler | Warmstart | //Globales Undo// \\ nicht abgeschlossene Transaktionen rückgängig | //Globales Redo// \\ Alle abgeschlossenen Transaktionen nachholen |
+| Medienfehler | Kaltstart | \\ Backup einspielen | //Globales Redo// \\ Alle abgeschlossenen Transaktionen nachholen |
+==== Integrität ====
+  * **Statische Integrität** \\ Einschränkung der Datenbank//zustände//
+  * **Dynamische Integrität** \\ Einschränkung der //Zustandsübergänge//
+  * **Modellinhärente Integrität**
+    * //Typ//integrität
+    * //Schlüssel//integrität
+    * //Referentielle// Integrität
+==== Synchronisation ====
+=== 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
+=== Serialisierung ===
+^ allgemeiner Schedule | Durcheinander | <latex>\[\frac{(m_1 + m_2 + \dots){\color{red}!}}{m_1{\color{red}!} \cdot m_2{\color{red}!} \cdot \dots}\]</latex> |
+^ serialisierbarer (allgemeiner) Schedule | Durcheinander kann in Blockform gebracht werden |
+^ serieller Schedule | Blockform | <latex>\[n{\color{red}!}\]</latex> |
+Graph Zeichen
+  * Knoten: Transaktionen
+  * Kanten: Abhängigkeiten
+^ Übergang ^ Markierung ^
+| $w_i(x) \rightarrow r_j(x)$ | wr(x) |
+| $r_i(x) \rightarrow w_j(x)$ | rw(x) |
+| $w_i(x) \rightarrow w_j(x)$ | ww(x) |
+//Kein// rr(x)
+Zyklenfrei? => Serialisierbar durch topologisches sorieren
+=== Technicken ===
+  * Pessimistische Ablaufsteuerung (Locking)
+  * Optimistische Ablaufsteuerung (Zeitstempelverfahren) \\ Notfalls rollback
 ===== Anwendung =====
 ==== "MVC" Aufteilungen ====
@@ Line 108: / Line 166: @@
 Vorübersetzes SQL mit Platzhaltern
 ===== Mathe =====
-==== Normalisierung ====
+==== Funktionale Abhängigkeiten ====
-=== FD ===
+=== Arten ===
   * **Partielle funktionale Abhängigkeit**: $X \rightarrow Y$
   * **Volle funktionale Abhängigkeit**: $X \dot{\rightarrow} Y$ (Minimalität)
-=== Anomalien ===
-  * **Update~** \\ Nicht alles wird geupdatet
-  * **Insert~** \\ Inkonsistentes insert
-  * **Delete~** \\ Löschen der letzten Verwendung, löscht auch Objekt
 === Axiome ===
@@ Line 125: / Line 178: @@
 ^ Dekomposition |  ${\color{red}X} \rightarrow {\color{ForestGreen}Y}{\color{RoyalBlue}Z}$ | $\Longrightarrow$ | ${\color{red}X} \rightarrow {\color{ForestGreen}Y} \wedge {\color{red}X} \rightarrow {\color{RoyalBlue}Z}$ |
 ^ Pseudotransitivität |  ${\color{red}X} \rightarrow {\color{ForestGreen}Y} \wedge {\color{RoyalBlue}Z}{\color{ForestGreen}Y} \rightarrow V$ | $\Longrightarrow$ | ${\color{red}X}{\color{RoyalBlue}Z} \rightarrow V$ |
+=== Attributhülle ===
+//AttrHülle(F,X)// mit \\ //F// = FDs \\ //X// = Start Attributmenge
+Starte mit //X// und wende so lange F ab, bis nichts mehr geht. ("Schau wie weit du kommst")
+==== Normalisierung ====
+=== Anomalien ===
+  * **Update~** \\ Nicht alles wird geupdatet
+  * **Insert~** \\ Inkonsistentes insert
+  * **Delete~** \\ Löschen der letzten Verwendung, löscht auch Objekt
+=== 1. NF ===
+Bedingung
+> Alle Attribute //atomar//
+Attributwerte dürfen nicht ...
+  * Listen sein: {Telefon1, Telefon2, Telefon3, ...}
+  * Zusammengesetzt sein: (Hausnummer, PLZ, ...)
+=== 2. NF ===
+Bedingung
+> //Jedes// Attribut entweder
+> voll funktional Abhängig von //jedem// Schlüsselkandidaten
+> -- oder --
+> prim (teil eines Schlüsselkandidaten)
+Trivial: nur //ein einelementiger// Schlüsselkandidat => 2. NF
+Sonst: Vom Schlüssel nicht voll funktional Abhängige Attribute werden herausgelöst, in eigene Tabelle
+=== 3. NF ===
+Bedingung
+<WRAP help 60%>
+//Jede// FD $X \rightarrow Y$ ist mindestens eins:
+  * tivial
+  * X enthält Schlüsselkandidat
+  * $\forall a \in (Y-X)$ ist prim
+</WRAP>
+<WRAP info 60%>
+Keine (nicht trivialen) FDs unter Nicht-Schlüssel-Attributen
+</WRAP>
+  - **Kanonische Überdeckung**
+    - Linksreduktion  \\ Komme ich von //X-x// und //identischem FD// dennoch auf Y, dann streiche x aus X
+    - Rechtsreduktion \\ Komme ich von //X// und //FD ohne y// dennoch auf y in Y, dann streiche y aus Y
+    - $X \rightarrow \emptyset$ entfernen
+    - Gleiche X zusammenfassen
+  - **Relationsschema erzeugen und FDs zuweisen**
+    - Aus jedem FD erzeuge eine Relation mit X als Primärschlüssel und Y als Attribute
+    - Ordne jedes FD den Relationen zu, die alle seine "Buchstaben" enthält
+  - **Schlüsselkandidat rekonstruieren** \\ Stelle sicher, dass eine Relation einen ehemaligen Schlüsselkandidaten enthält, notfalls erzeuge eine neue mit leerem ohne zugeordnete FDs
+  - **Überflüssige Relationen eliminieren** \\ Lösche Relationen, die Teilmenge einer anderen sind.
+=== Boyce-Codee-Normalform ===
+Bedingung
+<WRAP help 60%>
+//Jede// FD $X \rightarrow Y$ ist mindestens eins:
+  * tivial
+  * X enthält Schlüsselkandidat
+</WRAP>
+<WRAP info 60%>
+Keine (nicht trivialen) FDs unter Schlüssel-Attributen
+</WRAP>
+=== 4. NF ===
+Wirkung
+> Nicht mehrere Tabellen in einer.
+Bedingung
+<WRAP help 60%>
+//Jede// MVD $X \twoheadrightarrow Y$ ist mindestens eins:
+  * tivial
+  * X enthält Schlüsselkandidat
+</WRAP>
+MVD (Multi Valued Dependency): //Mehre// Attribut//werte//, eines Attributs, sind von der linken Seite abhängig.
 ==== Begriffe ====
   * Domain
@@ Line 141: / Line 278: @@
 === Eigenschaften ===
   - Eindeutig \\ $t_1 \ne t_2 \Rightarrow \pi_S(t_1) \ne \pi_S(t_1)$ \\ Unterschiedliche Tupel ⇒ Unterschiedliche Schlüssel
-  - Minimal \\ $\text{Eindeutig} T \wedge T \subseteq S \Rightarrow T = S$ \\ Keine Teilmenge des Schlüssels erfüllt die 1. Eigenschaft
+  - Minimal \\ $\text{Eindeutig}(T) \wedge T \subseteq S \Rightarrow T = S$ \\ Keine Teilmenge des Schlüssels erfüllt die 1. Eigenschaft
-(Minimal bedeutet //nicht//: Die wenigsten Attribute
+(Minimal bedeutet //nicht//: Die wenigsten Attribute)
+Schlüssel und FD sind //semantische Eigenschaften// (nicht anhand von aktueller Ausprägung erkennbar)
 === Arten ===
-  * Superschlüssel: Nur 1. Eigenschaft erfüllt
+  * Superschlüssel: Nur 1. Eigenschaft erfüllt ($S \rightarrow R$)
-  * Schlüsselkandidat: 1. und 2. Eigenschaft erfüllt
+  * Schlüsselkandidat: 1. und 2. Eigenschaft erfüllt ($S \dot{\rightarrow} R$)
   * Primärschlüssel: Ein beliebiger aber fester Schlüsselkandidat
+Primes Attribut: Teil eines Schlüsselkandidaten
+=== Beweis ===
+Beispiel: Beweise das //S = (A, B)// Schlüsselkandidat ist.
+  - **Eindeutigkeit** \\ $S \rightarrow R$ herleiten
+  - **Minimalität** \\ Zeigen das weder $A \rightarrow R$ noch $B \rightarrow R$ gild
 ==== Relationsschemata ====
 === geordnet ===
@@ Line 211: / Line 355: @@
 | Schema(t) = Schema(Städte) \\ {t %%|%% Städte(t) ∧ (∃ u ∈ Länder)(u.Lname = t.Land ∧ u.Partei = CDU) } | $\{x_1 \mid \exists x_2, x_3, y_2 : (\text{Städte}(x_1, x_2, x_3) \wedge \text{Länder}(x_3, y_2, \text{CDU}))\}$ |
 ^ SPD alleinregierte Länder ^^
-| Schema(t) = SChema(Länder) \\ {t %%|%% Länder(t) ∧ (∀ u ∈ Länder)(u.LName = t.LName ⇒ u.Partei = SPD} | $\{x_1 \mid \exists x_2 : (\text{Länder}(x_1, x_2, \text{SPD}) \wedge \not \exists y_3 : \text{Länder}(x_1, x_2, y_3) \wedge y_3 \ne \text{SPD} \}$ |
+| Schema(t) = SChema(Länder) \\ {t %%|%% Länder(t) ∧ (∀ u ∈ Länder)(u.LName = t.LName ⇒ u.Partei = SPD} | $\{x_1 \mid \exists x_2 : (\text{Länder}(x_1, x_2, \text{SPD}) \wedge \neg \exists y_3 : \text{Länder}(x_1, x_2, y_3) \wedge y_3 \ne \text{SPD} \}$ |
 | Schema(t) = SChema(Länder) \\ {t %%|%% Länder(t) ∧ (∀ u ∈ Länder)(u.LName = t.LName ⇒ u.Partei = SPD} | |
+===== Speicher Stukturen =====
+Jeder zusätzlich Schlüssel wirkt sich negativ auf updates aus.
+  * **//Daten//organisierende Strukturen** \\ //Suchbaum//verfahren (B+-Baum)
+  * **//Raum//organisierende Strukturen** \\ dynamische //Hash//-Verfahren
+Seitenarten (für Daten- und Raumorganisierende Strukturen)
+  * **//Directory//seiten** \\ Verweis auf Datenseiten
+  * **//Daten//seiten** \\ Die eigentlichen Daten
+Schlüsselarten
+  * Primärschlüsselsuche
+    * B+-Baum
+    * Lineares Hashing
+  * Sekundärschlüsselsuche
+    * Invertierte Listen
+==== B+ Baum ====
+{{http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Bplustree.png/800px-Bplustree.png?400}}
+  * //Alle Daten// ausschließlich in den Blättern (Datenseiten)
+  * Schlüssel (Seperatoren) kommen mehrfach in Directoryseiten vor.
+  * Mit //rechtem// Bruder ausgleichen
+  * Ordnung //m//
+  * Wurzel: //1// ... //2m// Kinder
+  * Knoten: //m// ... //2m// Kinder
+==== Erweiterbares Hashing (Directory) ====
+{{http://pluto.ksi.edu/~cyh/cis501/f5-14.GIF?400}}
+   * Die Zahlen geben an, wie viele Bits "beachtet" werden müssen.
+   * Die Zahl des Diresctorys ist immer größer-gleich der Zahl der Datenseiten, ansonsten Directory Zahl inkrementieren & Directory verdoppeln
+   * Läuft eine Datenseite über => Split + Zahl inkrementieren
+==== Lineares Hashing (Ohne directory) ====
+$\text{Belegungsfaktor} = \frac{\text{Alle Schlüssel}}{\text{Kapazität in \textit{Primär}seite}} > 0.8 \Rightarrow \text{Expansion}$
+==== Invertierte Listen ====
+  * Alle Attribute einzeln indizieren
+  * einzeln suchen
+  * Schnittmenge der Ergebnislisten bilden
+==== Reverse pattern matching ====
+  * Für ''LIKE "Horst%"''
+==== Composite Indizes ====
+mehrere Attribute
+  * Attributwerte werden concatiniert sortiert gespeichert
+  * Reihenfolge wichtig
 ===== E/R-Modell =====
@@ Line 287: / Line 482: @@
 | ''//a// **=** //b//'' | ''//a// **<>** //b//'' | | |
 | ''//a// < //b//'' | ''//a// > //b//'' | ''//a// %%<=%% //b//'' | ''//a// >= //b//'' |
+| ''//x// BETWEEN //a// AND //b//'' | | | |
 | ''//a// IS NULL'' | ''//a// IS NOT NULL'' |
 | ''//a// IN (...)'' | | | |
@@ Line 399: / Line 595: @@
 ON
   t
-FROm
+FROM
   TU PUBLIC,
   userName
-[RESTRICT | CASCADE]  -- RESTRICT: Nur den user löschen | CASCADE: nehme die rechte auch denjenigen, die sie vom user bekommen haben
+[RESTRICT | CASCADE]  -- RESTRICT: Nur den user löschen
+                      -- CASCADE: nehme die rechte auch denjenigen, die sie vom user bekommen haben
+</code>
+<code sql>
+CREATE INDEX name ON t (a1, a2, ...);
+DROP INDEX name;
+</code>
+<code sql>
+-- Laut script kein START TRANSACTION
+SET TRANSACTION READ-ONLY  -- kein INSERT, UPDATE und DELETE. Dafür bessere Transaktionsplanung
+SET TRANSACTION READ-WRITE -- default
+SAVEPOINT name
+COMMIT
+ROLLBACK
+ROLLBACK TO name
 </code>
 ==== Join ====