446 lines
26 KiB
TeX
446 lines
26 KiB
TeX
\documentclass[11pt,a4paper]{scrartcl}
|
|
\usepackage[table]{xcolor}
|
|
\usepackage[a4paper,left=1.5cm,right=1.5cm,top=2.0cm,bottom=2.0cm]{geometry}
|
|
\usepackage[ngerman]{babel}
|
|
\usepackage{amssymb}
|
|
\usepackage{mathrsfs}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage{amsmath}
|
|
\usepackage{enumitem}
|
|
\usepackage{tikz-qtree}
|
|
\usepackage{mathtools}
|
|
\usepackage{latexsym}
|
|
\usepackage{algorithmicx}
|
|
\usepackage{csquotes}
|
|
\usepackage{pdfpages}
|
|
\usepackage{pgfplots}
|
|
\usepackage{hyperref}
|
|
\usepackage{listings}
|
|
\usepackage{pdflscape}
|
|
\usepackage{tikz}
|
|
\usetikzlibrary{positioning}
|
|
\usetikzlibrary{arrows}
|
|
\usetikzlibrary{automata}
|
|
\usetikzlibrary{shapes}
|
|
\usetikzlibrary{calc}
|
|
\usetikzlibrary{decorations.markings}
|
|
\usetikzlibrary{matrix}
|
|
\usepackage{commath}
|
|
|
|
\pdfminorversion=7 % Import-Unterstützung für PDFs bis Version 1.7
|
|
\pgfplotsset{compat=1.16} % verhindern, dass pgfplots im Rückwärtskompatibilitätsmodus arbeitet
|
|
|
|
\definecolor{fau_blau}{RGB}{26, 71, 115}
|
|
|
|
\newcommand{\begriff}[1]{\textcolor{fau_blau}{\emph{#1}}}
|
|
\newcommand{\wichtig}[1]{\emph{#1}}
|
|
|
|
\tikzset{rectangle state/.style={draw,rectangle}}
|
|
|
|
\title{Zusammenfassung IDB}
|
|
\author{Marco Ammon}
|
|
\date{\today}
|
|
|
|
\begin{document}
|
|
\maketitle
|
|
|
|
\section{Einführung}
|
|
\begin{itemize}
|
|
\item \begriff{Datenabstraktion} / \begriff{Datenunabhängigkeit}: persistentes Speichern und Wiedergewinnen (Auffinden und Aushändigen) von Daten \wichtig{unabhängig} von Details der Speicherung
|
|
\item \begriff{Schicht}: realisiert \begriff{Dienst} und stellt ihn per \begriff{Schnittstelle} zur Verfügung
|
|
\end{itemize}
|
|
|
|
\section{Dateiverwaltung}
|
|
\begin{itemize}
|
|
\item \begriff{physische} Speichergeräte (z.B. Festplatten) werden durch \begriff{logische} abstrahiert (z.B. Neueinlesen bei Checksum-Fehlern)
|
|
\item \begriff{Block} als kleinste Einheit der IO
|
|
\item \enquote{Adresse} eines Blocks: (Zylinder, Spur, Sektor)
|
|
\item \begriff{Dateien} als benannte Menge von Blöcken
|
|
\item \begriff{blockorientierte} Zugriffsmethode: verwendet eindeutige, fortlaufende Blockadressen innerhalb der Datei
|
|
\end{itemize}
|
|
|
|
\section{Sätze}
|
|
\begin{itemize}
|
|
\item \begriff{Satz} als zusammengehörende Daten eines Gegenstands der Anwendung (z.B. Tupel, Objekt) mit variabler oder fester Länge
|
|
\item \begriff{Satzdatei} als Sammlung von Sätzen, kann über verschiedene Blöcke verteilt sein
|
|
\item Ausprägungen: \begin{itemize}
|
|
\item \begriff{sequentiell}: \begin{itemize}
|
|
\item Reihenfolge der Abspeicherung und des Auslesens bereits mit Schreiben festgelegt
|
|
\item \wichtig{keine} Änderungen / Löschen möglich
|
|
\item kein wahlfreier Zugriff
|
|
\end{itemize}
|
|
\item \begriff{direkt}: \begin{itemize}
|
|
\item Verwendung sogenannter \begriff{Satzadressen} (hier als \begriff{TID}s realisiert; \wichtig{eindeutig} und \wichtig{unveränderlich}) als Adresstupel (Block, Index)
|
|
\item Abbildung von Index auf Offset innerhalb eines Blockes durch Array am Ende eines Blockes
|
|
\item erlaubt wahlfreien Zugriff
|
|
\item erlaubt Löschen von Sätzen: Index wird ungültig markiert, folgende Sätze nach vorne verschoben, Anpassung der Offsets
|
|
\item erlaubt Ändern von Sätzen: \begin{itemize}
|
|
\item \wichtig{ohne} Überlauf: Verschieben der folgenden Sätze, Anpassung der Offsets
|
|
\item \wichtig{mit} Überlauf: Satz wird in anderen Block verschoben, Verweis auf diesen wird angelegt, (evtl.) Anpassung der Offsets
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\section{Schlüssel}
|
|
\begin{itemize}
|
|
\item \begriff{Schlüsselwerte} als \enquote{inhaltsbezogene Adressen}
|
|
\item \begriff{Hashing}: \begin{itemize}
|
|
\item \begriff{Hash-Funktion} verteilt Schlüsselwert möglichst gleichmäßig auf verfügbare \begriff{Buckets} (Blöcke)
|
|
\item \begriff{Divisions-Rest-Verfahren}: $h(k) = (k \mod q)$ mit Schlüsselwert $k$ und Anzahl der Buckets $q$
|
|
\item Problem des \begriff{Überlaufs} mit verschiedenen Lösungsmöglichkeiten: \begin{itemize}
|
|
\item \begriff{Open Addressing}: Ausweichen auf Nachbarbuckets
|
|
\item spezielle \begriff{Overflow-Buckets}: Bucket verweist auf \enquote{\wichtig{seinen}} Overflow-Bucket
|
|
\end{itemize}
|
|
\item \begriff{virtuelles Hashing} zur konstanten Reorganisation: \begin{itemize}
|
|
\item Anzahl der Buckets $q$, Sätze pro Bucket $b$ $\Rightarrow$ Kapazität $\coloneqq q \cdot b$
|
|
\item Belegungsfaktor $\beta \coloneqq \frac{\text{Anzahl gespeicherter Sätze}\ N}{\text{Kapazität}}$
|
|
\item Wenn $\beta > \text{Schwellwert}\ \alpha$, Menge der Buckets vergrößern
|
|
\item als \begriff{VH1}: \begin{itemize}
|
|
\item Anzahl der Blöcke direkt verdoppeln
|
|
\item neue Hashfunktion $h_2$ einführen
|
|
\item Bitmaske um Verwendung der neuen Hashfunktion zu verwalten
|
|
\item bei \wichtig{Einfügen} eines Satzes in ein \enquote{altes} Bucket Neuverteilung dieses Buckets mittels $h_2$, Bit setzen
|
|
\end{itemize}
|
|
\item als \begriff{Lineares Hashing}: \begin{itemize}
|
|
\item Positionszeiger $p$
|
|
\item \wichtig{ein} neues Bucket anlegen
|
|
\item Bucket an Stelle $p$ mit $h_2$ aufteilen, $p$++
|
|
\item wenn $h_1(k) < p$, dann mittels $h_2$ verteilen
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item \begriff{Indizes} mittels \begriff{Bäumen}: \begin{itemize}
|
|
\item \begriff{B-Baum}: \begin{itemize}
|
|
\item jeder \begriff{Knoten} ist genau einen Block groß
|
|
\item \wichtig{balanciert}, alle Blätter außer Wurzel immer mindestens zur Hälfte gefüllt
|
|
\item Knoten: \begin{itemize}
|
|
\item Anzahl der verwendeten Einträge $n$, es gilt $k \leq n \leq 2k$
|
|
\item \begriff{Eintrag}: Tupel (Schlüsselwert, Datensatz, Blocknummer des Kindknotens)
|
|
\item Einträge nach Schlüsselwert \wichtig{sortiert}
|
|
\end{itemize}
|
|
\item Einfügen: wie Suchen; nur in Blattknoten; bei Überlauf \enquote{linke} und \enquote{rechte} Einträge als neue Knoten, \enquote{mittlerer} als \begriff{Diskriminator} in Eltern-Knoten einfügen
|
|
\item Löschen von Schlüssel $S$ im Blattknoten: \begin{itemize}
|
|
\item Entfernen und ggf. Unterlauf behandeln
|
|
\end{itemize}
|
|
\item Löschen von Schlüssel $S$ in innerem Knoten: \begin{itemize}
|
|
\item betrachte die Blattknoten mit direktem Vorgänger $S'$ und direktem Nachfolger $S''$ von $S$
|
|
\item wähle den größeren
|
|
\item ersetze $S$ je nach Wahl durch $S'$ bzw. $S''$
|
|
\item lösche entsprechenden Schlüssel $S'$ bzw. $S''$ und ggf. Unterlauf behandeln
|
|
\end{itemize}
|
|
\item Höhe: \begin{itemize}
|
|
\item obere Schranke: $h(n) = \log_{k+1}\left(\frac{n+1}{2}\right) + 1$
|
|
\item untere Schranke: $h(n) = \log_{2k+1}\left(n + 1 \right)$
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item \begriff{B*-Baum} / \begriff{B+-Baum}: \begin{itemize}
|
|
\item Sätze stehen \wichtig{ausschließlich} in Blattknoten
|
|
\item innerer Knoten: \begin{itemize}
|
|
\item Anzahl der verwendeten Einträge $n$
|
|
\item Eintrag: Tupel (Referenzschlüssel, Blocknummer des Kindknotens)
|
|
\end{itemize}
|
|
\item Blattknoten: \begin{itemize}
|
|
\item Anzahl der verwendeten Einträge $n$
|
|
\item Vorgänger-Zeiger, Nachfolger-Zeiger
|
|
\item Eintrag: Tupel (Schlüsselwert, Datensatz)
|
|
\end{itemize}
|
|
\item Löschen ohne Unterlauf: lösche Satz aus Blatt; Diskriminator muss \wichtig{nicht} geändert werden
|
|
\item Löschen mit Unterlauf:\begin{itemize}
|
|
\item Ist Anzahl der Einträge des Blatts und eines Nachbarknotens größer als 2k, verteile Sätze neu auf beide Knoten
|
|
\item ansonsten mische beide Blätter zu einem einzigen
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item \begriff{R-Baum}: \begin{itemize}
|
|
\item ähnlich zu B-Baum
|
|
\item multidimensional
|
|
\item arbeitet mit Rechtecken
|
|
\item beim Einfügen Rechteck nur möglichst gering vergrößern
|
|
\end{itemize}
|
|
\item Müssen nicht zwangsläufig zur \begriff{Primärorganisation} verwendet werden, können als \enquote{Sätze} z.B. auch nur Satzadressen enthalten
|
|
\end{itemize}
|
|
\item \begriff{Bitmap-Indizes}: eine Bitmap \wichtig{pro Schlüsselwert}
|
|
\end{itemize}
|
|
|
|
\section{Puffer}
|
|
\begin{itemize}
|
|
\item Hauptspeicherbereich, der Blöcke aufnehmen kann, um (Lese-/Schreibe-) Zugriffe zu \wichtig{beschleunigen}
|
|
\item \begriff{Ersetzungsstrategie}: \enquote{Welcher Block wird verdrängt?} \begin{itemize}
|
|
\item \begriff{first in, first out} (FIFO): \enquote{ältester} Block
|
|
\item \begriff{least frequently used} (LFU): am seltensten benutzter Block
|
|
\item \begriff{least recently used} (LRU): am längsten nicht mehr benutzter Block \begin{itemize}
|
|
\item Stacktiefenverteilung: \enquote{Wie tief liegen die referenzierten Seiten?}
|
|
\end{itemize}
|
|
\item \begriff{second chance} (CLOCK): Approximation von LRU mit einfacherer Implementierung: \begin{itemize}
|
|
\item Jeder Block im Puffer besitzt ein \begriff{Benutzt-Bit}
|
|
\item bei Verdrängung Suche mit Zeiger
|
|
\item falls Benutzt-Bit 1, auf 0 setzen und Zeiger weiterschieben
|
|
\item falls Benutzt-Bit 0, Block ersetzen
|
|
\end{itemize}
|
|
\item \begriff{Working Set Size} $\abs{W(t,w)}$: Anzahl der unterschiedlichen referenzierten Seiten in den letzten $w$ Zugriffen bis Zeitpunkt $t$
|
|
\item \begriff{aktuelle Lokalität}: $AL(t,w) = \frac{\abs{W(t,w)}}{w}$
|
|
\item \begriff{durchschnittliche Lokalität}: $L(w) = \frac{\sum_{t=w}^{n} AL(t,w)}{n - w + 1}$
|
|
\end{itemize}
|
|
\item Zustand im Fehlerfall hängt unter anderem von \begriff{Einbringstrategie} (siehe \hyperref[recovery]{Recovery}) und \begriff{Seitenzuordnung} ab
|
|
\item Seitenzuordnung: \enquote{Welche Blöcke (in einer Datei) gehören zu einer Seite (im Puffer)?} \begin{itemize}
|
|
\item \begriff{direkt}: aufeinander folgende Seiten werden auf aufeinander folgende Blöcke einer Datei abgebildet
|
|
\item \begriff{indirekt}: \begriff{Page Table} enthält zu jeder Seite eine Blocknummer
|
|
\end{itemize}
|
|
\item Seiteneinbringung: \begin{itemize}
|
|
\item \begriff{direkt}: Bei Verdrängung aus Puffer wird genau der Block überschrieben, aus dem ursprünglich eingelagert wurde (\enquote{update-in-place})
|
|
\item \begriff{indirekt}: Bei Verdrängung aus Puffer wird in einen freien Block geschrieben.
|
|
\end{itemize}
|
|
\item Problem der indirekten Seiteneinbringung: \enquote{Wann können alte Blöcke gelöscht werden?}; verschiedene Lösungsansätze: \begin{itemize}
|
|
\item \begriff{Schattenspeicher}: \begin{itemize}
|
|
\item Änderungen nur auf Kopien, die periodisch dann mit \enquote{gesicherter} Version vertauscht wird
|
|
\end{itemize}
|
|
\item \begriff{Twin Slots}: \begin{itemize}
|
|
\item jede Seite hat zwei Blöcke
|
|
\item immer beide lesen, bei Änderungen älteren überschreiben
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\section{Programmzugriff}
|
|
\begin{itemize}
|
|
\item \begriff{Precompiler} übersetzt SQL-Anweisungen (mittels \texttt{EXEC SQL} gekennzeichnet) zur \wichtig{Compile-Zeit} in die verwendete Programmiersprache \begin{itemize}
|
|
\item Deklaration der verwendeten Variablen am Anfang mittels \texttt{DECLARE SECTION}
|
|
\item Fehlermeldungen und ähnliches werden über die sogenannte \begriff{SQL communication area} verwaltet (\texttt{INCLUDE SQLCA} am Anfang)
|
|
\item Mengen-orientes Paradigma des DBVS oft nicht mit Programmiersprache vereinbar $\Rightarrow$ Einrichtung eines \begriff{Cursors} zum tupelweisen Durchlaufen der Ergebnismenge
|
|
\item Beispielablauf: \texttt{DECLARE CURSOR} $\rightarrow$ \texttt{OPEN} $\rightarrow$ (mehrfach) \texttt{FETCH} bis Fehlercode $== 100$ $\rightarrow$ \texttt{CLOSE}
|
|
\item kann durch Präprozessor direkt als \hyperref[stored-procedure]{\begriff{stored procedure}} angelegt werden
|
|
\end{itemize}
|
|
\item \begriff{Unterprogrammaufruf} (\begriff{Call-Level-Interface}): \begin{itemize}
|
|
\item Übergabe der SQL-Anweisungen zur \wichtig{Laufzeit}
|
|
\item Beispiel JDBC \begin{itemize}
|
|
\item \texttt{Connection con = DriverManager.getConnection(URL, USER, PASSWORD);}
|
|
\item \texttt{Statement anweisung = con.createStatement();\\
|
|
ResultSet ergebnis = anweisung.execureQuery(ANFRAGE);}\\
|
|
außerdem: \texttt{int executeUpdate(String sql)}, \texttt{boolean execute(String sql)}
|
|
\item \texttt{while (ergebnis.next()) int pnr = ergebnis.getInt(1);}
|
|
\end{itemize}
|
|
\item Bei mehrfacher Ausführung der gleichen Abfrage mit unterschiedlichen Werten \begriff{prepared statements} sinnvoll: \begin{itemize}
|
|
\item Anfrage enthält Platzhalter für Werte
|
|
\item Analyse, Ausführungsplanerstellung und weiteres wird sofort durchgeführte
|
|
\item JDBC: \begin{itemize}
|
|
\item \texttt{PreparedStatement prep =\\con.prepareStatement("{}INSERT INTO ... VALUES (?,?)"{})}
|
|
\item Setzen der Werte mittels \texttt{void setDATENTYP(int paramId, DATENTYP val)}
|
|
\item Ausführung mit \texttt{prep.executeUpdate()}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item bei stored-procedures nur noch einmaliges Analysieren, etc. zur Compile-Zeit erforderlich: \label{stored-procedure} \begin{itemize}
|
|
\item Prozedur in DBVS bekommt \enquote{Namen}, über den sie mit Werten als Parametern aufrufbar ist
|
|
\item JDBC:\begin{itemize}
|
|
\item \texttt{CallableStatement call = con.prepareCall("\{ call PROZEDUR \}");}
|
|
\item Eingabe-Parameter analog zu prepared statements
|
|
\item Ausgabe-Parameter mittels \texttt{registerOutParameter(int paramId, int type)}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item \begriff{O/R-Mapping} bildet Objekte der Programmiersprace (meist durch Annotationen) auf Tupel der relationalen DB ab
|
|
\end{itemize}
|
|
|
|
\section{Transaktionen}
|
|
\begin{itemize}
|
|
\item sinnvoll für \wichtig{nebenläufigen} Zugriff
|
|
\item erleichtern Umgang mit \begriff{Fehlern} und Ausfällen (siehe \hyperref[recovery]{Recovery}
|
|
\item \begriff{Transaktion} als \begriff{logische Einheit} einer Folge von DB-Operationen (von einem logisch konsistenten Zustand zum nächsten): \begin{itemize}
|
|
\item bei Fehler vor Ende: Rückgängigmachen der bisher durchgeführten Änderungen
|
|
\item bei Fehler nach Ende: kein Problem
|
|
\item Anfang meist implizit (oder \begriff{begin})
|
|
\item Ende durch \begriff{commit} (Änderungen sollen durchgeführt werden) bzw. \begriff{abort}/\begriff{rollback} (Änderungen sollen verworfen werden)
|
|
\end{itemize}
|
|
\item \begriff{ACID}-Eigenschaften einer Transaktion: \begin{itemize}
|
|
\item \begriff{Atomarität} (\enquote{alles oder nichts} wird ausgeführt)
|
|
\item \begriff{Konsistenz}
|
|
\item \begriff{Isolation} (gegenüber anderen Zugriffen auf DB)
|
|
\item \begriff{Dauerhaftigkeit} (auch nach Fehler bleiben erfolgreiche Transaktionen bestehen)
|
|
\end{itemize}
|
|
\item \enquote{Lebenszyklus} einer Transaktion\\
|
|
\input{fig/zustandsuebergangsdiagramm.tex}
|
|
\item \begriff{Anomalien} im \begriff{Mehrbenutzerbetrieb}: \begin{itemize}
|
|
\item \begriff{dirty read}: Lesen von nicht freigegeben Änderungen: $w_1[x], r_2[x]$, erst danach Commit / Rollback
|
|
\item \begriff{dirty write}: Überschreiben von nicht freigegebenen Änderungen: $w_1[x], w_2[x]$, erst danach Commit / Rollback
|
|
\item \begriff{non-repeatable read}: Änderung nachdem gelesen wurde: $r_1[x], w_2[x]$, erst danach Commit / Rollback
|
|
\item \begriff{Phantom-Problem}: Ändern/Anlegen eines Tupels, das gelesenes Prädikat $P$ erfüllt: $r_1[P], w_1[y\in P]$, erst danach Commit/Rollback
|
|
\end{itemize}
|
|
\item \begriff{Serialisierbarkeitstheorie}: \begin{itemize}
|
|
\item Ablauf ist \begriff{serialisierbar}, wenn es einen \begriff{äquivalenten} \wichtig{seriellen} Ablauf seiner Transaktionen gibt
|
|
\item Äquivalenz von Abläufen $G$, $H$, wenn für jedes Datenobjekt $A$ gilt ($<$ $\widehat{=}$ \enquote{vor}):
|
|
\begin{align*}
|
|
r_i[A] <_H w_j[A] &\Leftrightarrow r_i[A] <_G w_j[A]\\
|
|
w_i[A] <_H r_j[A] &\Leftrightarrow w_i[A] <_G r_j[A]\\
|
|
w_i[A] <_H w_j[A] &\Leftrightarrow w_i[A] <_G w_j[A]
|
|
\end{align*}
|
|
\item \begriff{Abhängigkeitsgraph} hat \wichtig{keine} Zyklen $\Rightarrow$ Ablauf serialisierbar
|
|
\end{itemize}
|
|
\item \begriff{Sperrverfahren} mittels \begriff{Sperrtabelle}: \begin{itemize}
|
|
\item Sperrung muss \wichtig{vor} Zugriff erfolgen
|
|
\item Transaktionen fordern Sperre nicht erneut an
|
|
\item Sperren müssen beachtet werden
|
|
\item erst am Ende einer Transaktion dürfen Sperren freigegeben werden
|
|
\item \begriff{X-Sperre}: exklusiv, für Änderungen notwendig
|
|
\item \begriff{S-Sperre}: geteilt, für Lesen notwendig
|
|
\item \begriff{IX-Sperre}: exklusiv, zeigt Sperren auf feingranularerer Ebene an
|
|
\item \begriff{IS-Sperre}: geteilt, zeigt Sperren auf feingranularerer Ebene an
|
|
\item \begriff{SIX-Sperre}: S + IX, wenn alle Tupel gelesen, aber nur einige geändert werden
|
|
\item \begriff{Top-Down}-Erwerb, \begriff{Bottom-Up}-Freigabe der Sperren
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\section{Speicherung}
|
|
\begin{itemize}
|
|
\item Speicherung der Tupel in Sätzen: \begin{itemize}
|
|
\item zusammengesetzt aus Feldern mit Namen, Typ und Länge (maximal oder variabel)
|
|
\item \begriff{Metadaten} in \begriff{Systemkatalog} gespeichert
|
|
\item \begriff{Satztyp}: Menge von Sätzen gleicher Struktur (z.B. Tupel einer Relation)
|
|
\end{itemize}
|
|
\item verschiedene \begriff{Speicherungsstrukturen} in Sätzen: \begin{itemize}
|
|
\item mit \begriff{eingebetteten Längenfeldern}: Gesamtlänge $GL$, Inhalt fester Länge $F$, zu jedem Inhalt variabler Länge $V$ vorher die Länge $L$ $\Rightarrow$ satzinterne Adresse kann \wichtig{nicht} direkt aus Katalogdaten berechnet werden\\
|
|
\input{fig/eingebettete-laengenfelder.tex}
|
|
\item eingebettete Längenfelder mit \begriff{Zeigern}: Länge des festen Strukturteils $FL$, Zeiger auf variable Bereiche $\Rightarrow$ satzinterne Adresse kann aus Katalogdaten berechnet werden\\
|
|
\input{fig/zeiger.tex}
|
|
\end{itemize}
|
|
\item \begriff{spaltenweises} Abspeichern mittels \begriff{C-Store}: \begin{itemize}
|
|
\item vor allem auf das Lesen optimiert
|
|
\item Änderungen durch Löschen und Einfügen
|
|
\item \begriff{Projektion}: \begin{itemize}
|
|
\item eine oder mehrere Spalten einer Tabelle (und ggf. anderer, über Fremdschlüssel erreichbare Tabellen) nach einem Attribut sortiert
|
|
\item Speicherschlüssel (\begriff{Storage Keys}, \begriff{SK}) für jedes Tupel, aus Position berechenbar
|
|
\item \begriff{Verbund-Indizes} (\begriff{Join Indices}): Seien T1 und T2 Projektionen der Tabelle T, dann ist ein Join-Index von T1 zu T2 eine Liste von Tupeln aus T2 um den jeweiligen SK aus T1 ergänzt.
|
|
\end{itemize}
|
|
\item verschiedene \begriff{Komprimierungen} abhängig von Sortierung und Anzahl der verschiedenen Werte: \begin{itemize}
|
|
\item sortiert, wenige verschiedene Werte: Tripel (Wert, Position des ersten Auftretens, Anzahl des gleichen Werts) in B-Baum
|
|
\item unsortiert, wenige verschiedene Werte: lauflängenkodierte Bitmaps pro Wert mit B-Baum zum Auffinden der richtigen Bitmap
|
|
\item sortiert, viele verschiedene Werte: Delta-Kodierung (DIffertenz zum Vorgänger) mit B-Baum als Primärorganisation
|
|
\item unsortiert, viele verschiedene Werte: unkomprimiert, bei Zeichenketten \begriff{Dictionary}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\section{Anfrageverarbeitung}
|
|
\begin{itemize}
|
|
\item Abbildung von mengenorientierten Operatoren auf interne Satzschnittstelle
|
|
\item \begriff{Anfrageverarbeitung} erstellt einen \begriff{Anfrageausführungsplan}: \begin{itemize}
|
|
\item Analyse: lexikalische und syntaktische Prüfung, semantische Prüfung, Zugriffskontrolle, Integritätskontrolle
|
|
\item Optimierung: \begin{itemize}
|
|
\item \begriff{Standardisierung} und Vereinfachung
|
|
\item \begriff{algebraische} Verbesserung
|
|
\item \begriff{nicht-algebraische} Verbesserung: Berücksichtigung der Kosten der \begriff{Planoperatoren}
|
|
\end{itemize}
|
|
\item Code-Generierung
|
|
\item Ausführungskontrolle
|
|
\end{itemize}
|
|
\item \begriff{logische Operatoren} mit Relationen $R$, $S$ und Prädikat $P$: \begin{itemize}
|
|
\item \begriff{Selektion} $\text{SEL}(R, P)$
|
|
\item \begriff{Projektion} $\text{PROJ}(R, L)$ mit $L = (A_1, \dots, A_k)$
|
|
\item \begriff{Kreuzprodukt} $\text{CROSS}(R,S)$
|
|
\item \begriff{Verbund} $\text{JOIN}(R,S,P(R_{Ai}, S_{Aj}))$
|
|
\item \begriff{Vereinigung} $\text{UNION(R;S)}$
|
|
\item \begriff{Schnitt} $\text{INTERSECT(R,S)}$
|
|
\item \begriff{Ausschluss} $\text{EXCEPT(R,S)}$
|
|
\item analoge Operationen auf \begriff{Multimengen}
|
|
\item \begriff{Umbenennung} $\text{RENAME}(R, R_\text{neu}, ((A_i, A_{i,\text{neu}}), \dots))$
|
|
\item \begriff{Duplikat-Eliminierung} $\text{DUP-ELIM}(R)$
|
|
\item \begriff{Aggregation} $\text{SUM}(R, A_i)$, $\text{AVG}(R, A_i)$, $\text{MIN}(R, A_i)$, $\text{MAX}(R, A_i)$, $\text{COUNT}(R)$
|
|
\item \begriff{Gruppierung} $\text{GROUP}(R, L, G)$ mit $G = ((\text{AGG}_1, (A_i), \text{name}_1), \dots)$
|
|
\item \begriff{erweiterte Projektion} $\text{G-PROJ}(R, L)$ mit $L = (\text{name}_1 = \text{expr}_1, \dots)$
|
|
\item \begriff{Sortierung} $\text{SORT}(R, L)$ mit $L = (A_i, A_j, \dots)$
|
|
\item \begriff{äußerer Verbund} $\text{OUTER-JOIN}(R,S,P,c)$ mit $c \in \{\text{left}, \text{right}, \text{full}\}$
|
|
\end{itemize}
|
|
\item allgemeine Vorgehensweise bei Restrukturierung: \begin{itemize}
|
|
\item komplexe Verbünde, Selektionen in binäre aufteilen
|
|
\item Selektion möglichst \enquote{weit unten} ausführen
|
|
\item Selektion und Kreuzprodukt zu Verbund gruppieren
|
|
\item aufeinander folgende Selektionen der selben Relation zusammenfassen
|
|
\item Projektionen möglichst \enquote{weit unten} ausführen (aber Duplikat-Eliminierung vermeiden)
|
|
\end{itemize}
|
|
\item Planoperatoren (können durch \begriff{Pipelining} beschleunigt werden): \begin{itemize}
|
|
\item Selektion (\begriff{Scan}): \begin{itemize}
|
|
\item Kosten: $C(R)$
|
|
\item Relationen-Scan (Table-Scan): sequentielles Lesen\\
|
|
Kosten: $B(R)$
|
|
\item Index-Scan: Verwendung eines Index\\
|
|
Kosten: $a\cdot \left\lceil B(R) \cdot \text{Selektivitätsfaktor}\right\rceil$
|
|
\end{itemize}
|
|
\item Projektion: in andere Planoperatoren integriert\\
|
|
Kosten: $C(R)$
|
|
\item Sortierung
|
|
\item Join mit Relationen $R$, $S$: \begin{itemize}
|
|
\item Nested-Loop-Join (für \begriff{Gleichverbund} mit Index-Zugriff verbesserbar)\\
|
|
Kosten: $C(R) + B(R) \cdot C(S)$
|
|
\item Sorted-Merge-Join (nur für Gleichverbund): sortiere $R$, $S$; \begriff{schritthaltender} Scan\\
|
|
Kosten: $C(R) + C(S) + 2 \cdot \left(B(R) + B(T)\right)$
|
|
\item Hash-Join (nur für Gleichverbund): kleinere Relation hashen (bei zu großer Relation mehrere Teile); über größere sequentiellen Scan\\
|
|
Kosten: $C(R) + C(S)$
|
|
\end{itemize}
|
|
\item Duplikat-Eliminierung
|
|
\item Gruppierung
|
|
\end{itemize}
|
|
\item je nach System/Anwendung Optimierung auf niedrige CPU-/IO-Last
|
|
\item \begriff{Statistiken} für Wahl des Planoperators sinnvoll (Verteilung der Tupel, Selektivität, \dots)
|
|
\end{itemize}
|
|
|
|
\section{Recovery}
|
|
\label{recovery}
|
|
\begin{itemize}
|
|
\item \begriff{Programmfehler}: Absturz des Datenbank-Anwendungsprogramms $\Rightarrow$ Daten im Puffer und auf Festplatte in undefiniertem Zustand
|
|
\item \begriff{Systemfehler}: DBVS oder BS fällt aus, Hardware-Fehler, \textellipsis $\Rightarrow$ Daten im Puffer verloren, auf Festplatte in undefiniertem Zustand
|
|
\item \begriff{Gerätefehler}: Festplattenausfall $\Rightarrow$ Daten auf Festplatte sind verloren
|
|
\item \begriff{Transaktionsfehler}: z.B. \begriff{Deadlock}, falsche Operationen, Aufruf von \texttt{rollback} bzw. \texttt{abort}
|
|
\item \begriff{physische Konsistenz}: \begin{itemize}
|
|
\item Korrektheit der Speicherungsstrukturen, Verweise und Adressen
|
|
\item alle Indizes sind vollständig und stimmen mit Primärdaten überein
|
|
\end{itemize}
|
|
\item \begriff{logische Konsistenz}: \begin{itemize}
|
|
\item Korrektheit der Inhalte
|
|
\item Referentielle Integrität, Primärschlüsseleigenschaft und eigene Assertions sind erfüllt
|
|
\item erfordert physische Konsistenz
|
|
\end{itemize}
|
|
\item Nach Fehler soll ein logisch konsistenter Zustand erreicht werden: \begin{itemize}
|
|
\item der Zustand vor Beginn der unvollständigen Änderungen durch \begriff{Rückgängigmachen} dieser (\begriff{undo}) \begin{itemize}
|
|
\item \begriff{partial}: nach Transaktionsfehler Zurücksetzen der fehlgeschlagenen Transaktion
|
|
\item \begriff{global}: nach Systemfehler mit Verlust des Hauptspeicherinhalts Zurücksetzen aller unvollständigen Transaktion
|
|
\item Logging-Informationen müssen \wichtig{vor} dem Einbringen gespeichert werden (\begriff{write-ahead log}, WAL)
|
|
\end{itemize}
|
|
\item der Zustand nach Abschluss aller Änderungen durch \begriff{Vervollständigung} bzw. \begriff{Wiederholung} der unvollständigen Änderungen (\begriff{redo}) \begin{itemize}
|
|
\item \begriff{partial}: nach Systemfehler mit Verlust des Hauptspeicherinhalts Wiederholen aller verlorengegangen Änderungen von abgeschlossenen Transaktionen
|
|
\item \begriff{global}: nach Gerätefehler Einspielen des Backups und Nachvollziehen aller danach erfolgreichen Transaktionen
|
|
\item Logging-Informationen müssen \wichtig{vor} dem Melden des erfolgreichen Abschlusses geschrieben werden
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item \begriff{Sicherung} und \begriff{Protokollierung} (\begriff{Logging}) \wichtig{immer} notwendig
|
|
\item auch Einbringstrategie von Bedeutung: \begin{itemize}
|
|
\item \enquote{Wann \wichtig{darf} geänderte Seite auf die Festplatte geschrieben werden?} \begin{itemize}
|
|
\item \begriff{Steal}: auch schon vor Ende der Transaktion bei Verdrängung aus dem Puffer
|
|
\item \begriff{NoSteal}: erst am Ende der erfolgreichen Transaktion
|
|
\end{itemize}
|
|
\item \enquote{Wann \wichtig{muss} geänderte Seite auf die Festplatte geschrieben werden?} \begin{itemize}
|
|
\item \begriff{NoForce}: erst bei Verdrängung aus dem Puffer (also auch nach Ende einer Transaktion)
|
|
\item \begriff{Force}: spätestens am Ende der erfolgreichen Transaktion
|
|
\end{itemize}
|
|
\item \enquote{Wie werden geänderte Seiten auf die Festplatte geschrieben?} \begin{itemize}
|
|
\item \begriff{NotAtomic}: direktes Einbringen, in-place
|
|
\item \begriff{Atomic}: indirektes Einbringen, \enquote{Umschalten} von altem auf neuen Zustand
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item Protokollverfahren: \begin{itemize}
|
|
\item \begriff{physisch}: \begin{itemize}
|
|
\item \begriff{Zustandprotokollierung}: \begriff{before-image} für undo, \begriff{after-image} für redo, auf Ebene von Seiten oder Sätzen
|
|
\item \begriff{Seitenprotokollierung}: für jede geänderte Seite before-image und after-image sichern
|
|
\item \begriff{Eintragsprotokollierung}:nur geänderte Teile einer Seite
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\item Begrenzung des Recovery-Aufwands durch \begriff{Sicherungspunkte} (\begriff{checkpoints}): \begin{itemize}
|
|
\item \begriff{transaction-oriented checkpoint}: Einbringung mittels Force
|
|
\item \begriff{transaction-consistent checkpoint}: Beginn neuer Transaktionen verhindern, auf Abschluss der laufenden warten, dann sichern
|
|
\item \begriff{action-consistent checkpoint}: keine Änderungs\wichtig{operation} darf aktiv sein, dann sichern; da aber Transaktionen laufen nur Begrenzung von Redo-Recovery
|
|
\end{itemize}
|
|
\item \begriff{Wiederherstellungsprozedur}: \begin{itemize}
|
|
\item Analyse von letztem Checkpoint bis zum Log-Ende
|
|
\item erfolgreiche Transaktionen gegebenenfalls wiederholen
|
|
\item fehlgeschlagene Transaktionen von \enquote{neu nach alt} rückgängig machen
|
|
\end{itemize}
|
|
\end{itemize}
|
|
\end{document}
|