Wiki

A universe of ideas

User Tools

Site Tools

You are here: A universe of ideas » Uni » 5. Semester » Datenbanksysteme I
Trace:
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-29 15:14] – [B+ Baum] 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 134: Line 192:
  
 === 1. NF === === 1. NF ===
 +Bedingung
 > Alle Attribute //atomar// > Alle Attribute //atomar//
  
Line 141: Line 200:
  
 === 2. NF === === 2. NF ===
 +Bedingung
 > //Jedes// Attribut entweder > //Jedes// Attribut entweder
 > voll funktional Abhängig von //jedem// Schlüsselkandidaten > voll funktional Abhängig von //jedem// Schlüsselkandidaten
Line 149: Line 209:
  
 Sonst: Vom Schlüssel nicht voll funktional Abhängige Attribute werden herausgelöst, in eigene Tabelle 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 246: Line 359:
  
 ===== Speicher Stukturen ===== ===== 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 ==== ==== B+ Baum ====
 {{http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Bplustree.png/800px-Bplustree.png?400}} {{http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Bplustree.png/800px-Bplustree.png?400}}
Line 256: Line 385:
   * Wurzel: //1// ... //2m// Kinder   * Wurzel: //1// ... //2m// Kinder
   * Knoten: //m// ... //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 =====
 Elemente: Elemente:
Line 452: Line 605:
 CREATE INDEX name ON t (a1, a2, ...); CREATE INDEX name ON t (a1, a2, ...);
 DROP INDEX name; 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.1391004892.txt.gz · Last modified: (external edit)