Differences

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

--- uni:5:dbs [2014-01-26 01:47] – [Bla] skrupellos
+++ uni:5:dbs [2020-11-18 18:11] (current) – external edit 127.0.0.1
@@ Line 52: / Line 52: @@
   * DSL
+===== Optimierung =====
+|  %%|%% \\ Anfrage (deklarativ) \\ ↓  |
+^  Scanner/Parser/View-Erzeuger  ^
+|  %%|%% \\ algebraischer Ausdruck \\ ↓  |
+^  Anfrageoptimierung  ^
+|  %%|%% \\ Auswertungsplan (prozedural) \\ ↓  |
+^  Ausführung  ^
+==== Kanonischer Auswertungsplan ====
+Query in Funktionsbaum übersetzten
+  * Kaskadierter Kartesische Produkte (//nur 2 Eingänge//)
+  * Jede ''WHERE'' Bedingung //einzeln//
+Beispiel
+<code sql>
+SELECT A1, A2
+FROM R1, R2, R3
+WHERE B1, B2
+</code>
+Ergibt $\pi_{A_1, A_2}(\sigma_{B_1}(\sigma_{B_2}(R_1 \times (R_2 \times R_3))))$
+Optimierung: Filter so früh wie möglich
+==== Wo kann optimiert werden ====
+  * **Logische Anfrageoptimierung** \\ Auswertungsplan umbauen
+  * **Physische Anfrageoptimierung**
+    * Join Strategie
+      * **Nested Loop** \\ Kartesisches Produkt Filtern
+      * **Sort Merge** \\ Vorher Sortieren, dann mergen
+      * **Indexed Loop** \\ Tabelle 1 abarbeiten, Tabelle 2 über Index mergen
+    * Index Verwenden?
+==== Wie kann optimiert werden ====
+  * **Regelbasiert** \\ Heuristiken
+  * **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 ====
+^ ^  Thin client  ^  Fat client  ^  Stored procedure  ^  Web Application  ^  Application Server  ^
+^  Client |  GUI  |  GUI \\ Logik  |  GUI \\ Hauptprogramm  |  Browser  |  GUI  |
+^  Application \\ Server | | | | |  Logik  |
+^  DB-Server |  \\ Logik \\ DB-Schnittstelle \\ DB  |  \\ \\ DB-Schnittstelle \\ DB  |  \\ Prozeduren \\ DB-Schnittstelle \\ DB  |  Webserver \\ Logik \\ DB-Schnittstelle \\ DB  |  \\ \\ DB-Schnittstelle \\ DB  |
+==== Interaktion ====
+  * Call-Level-Schnittstelle (library)
+  * Embedded SQL
+==== Cursor ====
+  - **Declaration** \\ SQL eingeben
+  - **Open** \\ Ausführen
+  - **Fetch** loop
+  - **Close**
+Vorübersetzes SQL mit Platzhaltern
 ===== Mathe =====
+==== Funktionale Abhängigkeiten ====
+=== Arten ===
+  * **Partielle funktionale Abhängigkeit**: $X \rightarrow Y$
+  * **Volle funktionale Abhängigkeit**: $X \dot{\rightarrow} Y$ (Minimalität)
+=== Axiome ===
+^ Reflexivität |  ${\color{ForestGreen}Y} \subseteq {\color{red}X}$ | $\Longrightarrow$ | ${\color{red}X} \rightarrow {\color{ForestGreen}Y}$  |
+^ Verstärkung |  ${\color{red}X} \rightarrow {\color{ForestGreen}Y}$ | $\Longrightarrow$ | ${\color{red}X}{\color{RoyalBlue}Z} \rightarrow {\color{ForestGreen}Y}{\color{RoyalBlue}Z}$ |
+^ Transistivität |  ${\color{red}X} \rightarrow {\color{ForestGreen}Y} \wedge {\color{ForestGreen}Y} \rightarrow {\color{RoyalBlue}Z}$ | $\Longrightarrow$ | ${\color{red}X} \rightarrow {\color{RoyalBlue}Z}$ |
+^ Vereinigung |  ${\color{red}X} \rightarrow {\color{ForestGreen}Y} \wedge {\color{red}X} \rightarrow {\color{RoyalBlue}Z}$ | $\Longrightarrow$ | ${\color{red}X} \rightarrow {\color{ForestGreen}Y}{\color{RoyalBlue}Z}$ |
+^ 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 69: / 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 139: / 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 =====
+Elemente:
+  * Entitie (eckig)
+  * Relationship (raute)
+    * Können Attribute haben
+  * Attribute (oval)
+    * Primärschlüssel unterstreichen
+  * (strich)
+    * Können Rollen haben
+    * Pfeil = 1-KArdinalität
+    * Voller Kringel: 1.. / NOT NULL
+    * Hohler Kringel: 0.. / NULL
+  * Vererbung (Pyramide)
+    * Text: "isa"
+Umsetzen:
+  * Vererbung
+    * Eine gemeinsame Tabelle \\ -- ODER --
+    * "isa" in einzelne Relationen auflösen
+  * 1:1 Relation
+    - Beide Relationen zusamenfassen
+    - Nur //einer// der alten Primärschlüssel wird der neue Primärschlüssel
 ===== SQL =====
 ==== Typen ====
@@ Line 190: / 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 274: / Line 567: @@
 </code>
+<code sql>
+GRANT
+  ALL
+  ALL PRIVILEGES
+  SELECT
+  INSERT
+  DELETE
+  UPDATE
+  UPDATE(a, b)
+ON
+  t
+TO
+  TU PUBLIC,
+  userName
+[WIDTH GRANT OPTION]
+</code>
+<code sql>
+REVOKE
+  ALL
+  ALL PRIVILEGES
+  SELECT
+  INSERT
+  DELETE
+  UPDATE
+  UPDATE(a, b)
+ON
+  t
+FROM
+  TU PUBLIC,
+  userName
+[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 ====
 | ''**NATURAL JOIN** t''       | Natural Join |  $A \bowtie B$                         | Vergleich //aller// gleichbenannten |
@@ Line 368: / Line 709: @@
   * Datenschutz
+=== Normaler View ===
 <code sql>
 CREATE [OR REPLACE] VIEW v AS SELECT ...
@@ Line 375: / Line 717: @@
 Nicht erlaubt in //Basisrelation//:
   * ''ORDER BY''
+=== Materialisierter View ===
+<code sql>
+INSERT INTO mv (SELECT ...)
+</code>
 === Effekt-Konformität ===
-<quote>Kein merkbarer unterschied zwischen View und Relation</quote>
+> Kein merkbarer unterschied zwischen View und Relation
+^ Teil im \\ View ^ Angewendete \\ Operation ^ Problembeschreibung ^
+| ''SELECT'' | ''INSERT'' | Default (''NULL'') für wegprojezierte Attribute |
+| ::: | ''INSER''T \\ ''UPDATE'' \\ ''DELETE'' | Nicht möglich, wenn //''DISTINCT''// oder //arithmetische Ausdrücke// |
+| ''WHERE'' | ''INSERT'' \\ ''UPDATE'' | //Tupel-Migration//: Tupel verschwindet, da nicht von ''WHERE'' erfasst \\ Abhilfe: ''WHERE ... WITH CHECK OPTION'' |
+| ''JOIN'' \\ ''GROUP BY'' | ''INSERT'' \\ ''UPDATE'' \\ ''DELETE'' | Nicht möglich |
+| Subquerry | ''INSERT'' \\ ''UPDATE'' \\ ''DELETE'' | Nicht möglich, wenn //Selbstbezug// |