Wiki

A universe of ideas

User Tools

Site Tools


uni:5:dbs

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
uni:5:dbs [2014-01-28 01:10] – [Schlüssel] skrupellosuni: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//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 ===== ===== Anwendung =====
 ==== "MVC" Aufteilungen ==== ==== "MVC" Aufteilungen ====
Line 108: Line 166:
 Vorübersetzes SQL mit Platzhaltern Vorübersetzes SQL mit Platzhaltern
 ===== Mathe ===== ===== Mathe =====
-==== Normalisierung ==== +==== Funktionale Abhängigkeiten ==== 
-=== FD ===+=== Arten ===
   * **Partielle funktionale Abhängigkeit**: $X \rightarrow Y$   * **Partielle funktionale Abhängigkeit**: $X \rightarrow Y$
   * **Volle funktionale Abhängigkeit**: $X \dot{\rightarrow} Y$ (Minimalität)   * **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 === === 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}$ | ^ 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$ | ^ 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 ==== ==== Begriffe ====
   * Domain   * Domain
Line 151: Line 288:
   * Primärschlüssel: Ein beliebiger aber fester Schlüsselkandidat   * 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 ==== ==== Relationsschemata ====
 === geordnet === === geordnet ===
Line 212: 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}))\}$ | | 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 ^^ ^ 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} | | | 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 ===== ===== E/R-Modell =====
Line 288: Line 482:
 | ''//a// **=** //b//'' | ''//a// **<>** //b//'' | | | | ''//a// **=** //b//'' | ''//a// **<>** //b//'' | | |
 | ''//a// < //b//'' | ''//a// > //b//'' | ''//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// IS NULL'' | ''//a// IS NOT NULL'' |
 | ''//a// IN (...)'' | | | | | ''//a// IN (...)'' | | | |
Line 400: Line 595:
 ON ON
   t   t
-FROm+FROM
   TU PUBLIC,   TU PUBLIC,
   userName   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> </code>
 ==== Join ==== ==== Join ====
uni/5/dbs.1390867840.txt.gz · Last modified: (external edit)