\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}
