uni:5:dbs
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
uni:5:dbs [2014-01-27 03:32] – [Optimierung] 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 | * **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// | ||
+ | * **Dynamische Integrität** \\ Einschränkung der // | ||
+ | * **Modellinhärente 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 == | ||
+ | // | ||
+ | |||
+ | === Serialisierung === | ||
+ | ^ allgemeiner Schedule | Durcheinander | < | ||
+ | ^ serialisierbarer (allgemeiner) Schedule | Durcheinander kann in Blockform gebracht werden | | ||
+ | ^ serieller Schedule | Blockform | < | ||
+ | |||
+ | 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 ===== | ===== Anwendung ===== | ||
+ | ==== " | ||
^ ^ Thin client | ^ ^ Thin client | ||
^ Client | GUI | GUI \\ Logik | GUI \\ Hauptprogramm | ^ Client | GUI | GUI \\ Logik | GUI \\ Hauptprogramm | ||
^ Application \\ Server | | | | | Logik | | ^ Application \\ Server | | | | | Logik | | ||
^ DB-Server | \\ Logik \\ DB-Schnittstelle \\ DB | \\ \\ DB-Schnittstelle \\ DB | \\ Prozeduren \\ DB-Schnittstelle \\ DB | Webserver \\ Logik \\ DB-Schnittstelle \\ DB | \\ \\ DB-Schnittstelle \\ DB | | ^ 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 ===== | ===== Mathe ===== | ||
+ | ==== Funktionale Abhängigkeiten ==== | ||
+ | === Arten === | ||
+ | * **Partielle funktionale Abhängigkeit**: | ||
+ | * **Volle funktionale Abhängigkeit**: | ||
+ | |||
+ | === 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 === | ||
+ | // | ||
+ | |||
+ | Starte mit //X// und wende so lange F ab, bis nichts mehr geht. (" | ||
+ | |||
+ | ==== 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, | ||
+ | |||
+ | === 2. NF === | ||
+ | Bedingung | ||
+ | > //Jedes// Attribut entweder | ||
+ | > voll funktional Abhängig von //jedem// Schlüsselkandidaten | ||
+ | > -- oder -- | ||
+ | > prim (teil eines Schlüsselkandidaten) | ||
+ | |||
+ | Trivial: nur //ein einelementiger// | ||
+ | |||
+ | Sonst: Vom Schlüssel nicht voll funktional Abhängige Attribute werden herausgelöst, | ||
+ | |||
+ | === 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 info 60%> | ||
+ | Keine (nicht trivialen) FDs unter Nicht-Schlüssel-Attributen | ||
+ | </ | ||
+ | |||
+ | - **Kanonische Überdeckung** | ||
+ | - Linksreduktion | ||
+ | - 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 " | ||
+ | - **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 info 60%> | ||
+ | Keine (nicht trivialen) FDs unter Schlüssel-Attributen | ||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | === 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 | ||
+ | </ | ||
+ | |||
+ | MVD (Multi Valued Dependency): | ||
+ | |||
+ | |||
==== Begriffe ==== | ==== Begriffe ==== | ||
* Domain | * Domain | ||
Line 111: | Line 278: | ||
=== Eigenschaften === | === Eigenschaften === | ||
- Eindeutig \\ $t_1 \ne t_2 \Rightarrow \pi_S(t_1) \ne \pi_S(t_1)$ \\ Unterschiedliche Tupel ⇒ Unterschiedliche Schlüssel | - 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 // | ||
=== Arten === | === Arten === | ||
- | * Superschlüssel: | + | * Superschlüssel: |
- | * Schlüsselkandidat: | + | * Schlüsselkandidat: |
* Primärschlüssel: | * Primärschlüssel: | ||
+ | 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 ==== | ==== Relationsschemata ==== | ||
=== geordnet === | === geordnet === | ||
Line 181: | 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, | | 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, | ||
^ SPD alleinregierte Länder ^^ | ^ 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, | + | | 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, |
| Schema(t) = SChema(Länder) \\ {t %%|%% Länder(t) ∧ (∀ u ∈ Länder)(u.LName = t.LName ⇒ u.Partei = 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. | ||
+ | |||
+ | * **// | ||
+ | * **// | ||
+ | |||
+ | Seitenarten (für Daten- und Raumorganisierende Strukturen) | ||
+ | * **// | ||
+ | * **// | ||
+ | |||
+ | Schlüsselarten | ||
+ | * Primärschlüsselsuche | ||
+ | * B+-Baum | ||
+ | * Lineares Hashing | ||
+ | * Sekundärschlüsselsuche | ||
+ | * Invertierte Listen | ||
+ | |||
+ | ==== B+ Baum ==== | ||
+ | {{http:// | ||
+ | |||
+ | * //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:// | ||
+ | |||
+ | * Die Zahlen geben an, wie viele Bits " | ||
+ | * Die Zahl des Diresctorys ist immer größer-gleich der Zahl der Datenseiten, | ||
+ | * 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 '' | ||
+ | |||
+ | ==== Composite Indizes ==== | ||
+ | mehrere Attribute | ||
+ | * Attributwerte werden concatiniert sortiert gespeichert | ||
+ | * Reihenfolge wichtig | ||
===== E/R-Modell ===== | ===== E/R-Modell ===== | ||
Line 257: | Line 482: | ||
| ''// | | ''// | ||
| ''// | | ''// | ||
+ | | ''// | ||
| ''// | | ''// | ||
| ''// | | ''// | ||
Line 369: | Line 595: | ||
ON | ON | ||
t | t | ||
- | FROm | + | FROM |
TU PUBLIC, | TU PUBLIC, | ||
userName | userName | ||
- | [RESTRICT | CASCADE] | + | [RESTRICT | CASCADE] |
+ | -- CASCADE: nehme die rechte auch denjenigen, die sie vom user bekommen haben | ||
+ | </ | ||
+ | |||
+ | <code sql> | ||
+ | CREATE INDEX name ON t (a1, a2, ...); | ||
+ | DROP INDEX name; | ||
+ | </ | ||
+ | |||
+ | <code sql> | ||
+ | -- Laut script kein START TRANSACTION | ||
+ | SET TRANSACTION READ-ONLY | ||
+ | SET TRANSACTION READ-WRITE -- default | ||
+ | SAVEPOINT name | ||
+ | COMMIT | ||
+ | ROLLBACK | ||
+ | ROLLBACK TO name | ||
</ | </ | ||
==== Join ==== | ==== Join ==== |
uni/5/dbs.1390789936.txt.gz · Last modified: (external edit)