%Copyright 2013 Dirk Winkel
%This file is free software: you can redistribute it and/or modify
%it under the terms of the GNU Affero General Public License as
%published by the Free Software Foundation, either version 3 of the 
%License, or (at your option) any later version.

%This program is distributed in the hope that it will be useful,
%but WITHOUT ANY WARRANTY; without even the implied warranty of
%MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%GNU Affero General Public License for more details.

%You should have received a copy of the GNU Affero General Public 
%License along with GradeMan.  If not, see 
%<http://www.gnu.org/licenses/>.
\documentclass[12pt,a4paper,oneside]{article}
% -----------------------------------------------------------------------------------------
\usepackage[latin1]{inputenc}
\usepackage[centertags]{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{newlfont}
\usepackage{amsxtra}
\usepackage{amstext}
\usepackage[german]{babel}
\usepackage{latexsym}
\usepackage{geometry}
\usepackage{pifont}
\usepackage{ulem}
\usepackage{color}
\usepackage{marvosym}
\usepackage[T1]{fontenc}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{array}
\usepackage{booktabs}
\usepackage{dcolumn}
\usepackage{units}
\usepackage{rotating}
\usepackage{hyperref}
\usepackage{floatflt}
%\usepackage{makeidx}
%\usepackage[usenames,dvipsnames]{pstricks}
%\usepackage{epsfig}
%\usepackage{pst-grad} % For gradients
%\usepackage{pst-plot} % For axes
%\usepackage{qtree}

\usepackage{a4wide}
\usepackage{textcomp}
\usepackage{tikz}
\usetikzlibrary{automata}
\usepackage{mdframed}
\usepackage{listings}

\textheight25cm
% -----------------------------------------------------------------------------------------
\begin{document}
% -----------------------------------------------------------------------------------------
%	 Titel
% -----------------------------------------------------------------------------------------
\headheight0cm\headsep0cm\topskip0cm\footskip0cm
\begin{floatingfigure}[l]{3cm}
 \includegraphics[width=2.8cm, height=2.8cm, angle=270]{siegel}
\end{floatingfigure}
\begin{small}
Philipps-Universität Marburg

Fachbereich 12 Informatik

VL Datenbanken

Prof. Seeger

Sommersemester 2013

Zusammengefasst von: Dirk Winkel

\end{small}
\begin{center}
{\LARGE \textbf{Zusammenfassung Skript}}
\end{center}
% -----------------------------------------------------------------------------------------
%	Hauptext
% -----------------------------------------------------------------------------------------
\tableofcontents

\section{Einführung}
\begin{itemize}
 \item Datenbanksysteme (DBS) zur Verwaltung großer, persistent zu verwaltender Datenbestände
 \item DBS bestehen aus Datenbankverwaltungssystem (DBMS) und Datenbank (DB)
 \item Anwendungen: Zahlreich > Big Data, zentralisierung von Daten
 \item Probleme Anwendungsprogramme (AWP): Datenaustausch, Inkonsistenzen, Aufwändig, Mehrbenutzerbetrieb, Datenverluste, Datenverknüpfung, ...
 \item Anforderungen: Gemeinstame Datenbasis, Mehrbenutzerbetrieb, Kontrollierte Datenredundanz, Sicherstellung der Datenqualität, Schutz, Benutzerschnittstellen, Unterstützung bei AWP-Entwicklung, Leistungsfähigkeit
 \item Abstraktionsstufen: Externe (Sichten), Logische (Datenbeziehungen), Physische (Speicherstrukturen)
 \item Datenmodell: Strukturbeschreibung (Datendefinitionssprache, DDL), Datenmanipulationssprache (DML)
 \item Arten: physisch (speicherorientiert), logisch (benutzerorientiert)
 \item Logische: relationales Modell, objektorientiertes Modell, XML, JSON, HDF, ...
\end{itemize}

\section{Das relationale Datenmodell}
\begin{itemize}
 \item Entwicklung 1970 durch Edgar Codd
 \item Verwendung: Oracle, SQL Server, mySQL, PostgreSQL, Sybase, IBM DB2, ...
 \item Eigenschaften: Einfach (Relation>Tabelle, wenige Grundoperationen), Mengenorientierte Verarbeitung, formal fundiert
\end{itemize}

\subsection{Relationen}
\begin{itemize}
 \item Relation (r) = Tabelle
 \item Relationenname = Tabellenname
 \item Relationenschema (RS) = ``Spaltenbeschriftung'' (Tabellenaufbau), REL(RS) = Menge aller Relationen über RS
 \item Tupel (t) = Tabellenzeile
 \item Formal: A: Attribut (Spaltenbeschriftung) mit dom(A) als Wertebereich, U: Menge aller Attribute
 \item t[X] = T eingeschränkt auf X (mit z.B. X=\{A\})
 \item Integritätsbedingung: Einschränkung für Werte
 \item Schlüssel: Eindeutig (, Minimal); in jedem Relationenschema mindestens einer vorhanden
 \item Primärschlüssel: Maximal einer pro RS, Stellvertreter für Datensatz, im Schema unterstrichen, kann z.B. auch aus mehreren Fremdschlüsseln bestehen
 \item Konsistenz (von r): Alle lokalen Integritätsbedingungen sind erfüllt
 \item Datenbankschema (DS): Menge von Relationenschemata
 \item Datenbank (d): Menge von Relationen
\end{itemize}

\subsection{Die relationale Algebra}
\begin{itemize}
 \item Ziel: Definition einer DML (> SQL)
 \item Anforderungen: Ausdrucksstärke (Berechenbarkeit), Effizienz (Komplexitätsklassen O), Einfachkeit (minimale Anzahl d. Operatoren)
 \item Algebra: Menge von Ankern N (z.B. Zahlen oder Boolean), Menge von Operatoren
 \item Relationale Algebra: Anker = Relationen, 6 Operatoren: $\sigma, \pi, \cup, \times, -, \rho$
 \item Projektion $\pi$: Filtern von Spalten einer Relation, Ausgabe ist temporäre Relation:\\
  $\pi_X(r)=s=\{t[X] | t \in r\}$
 \item Selektion $\sigma$: Filtern von Zeilen aus einer Relation mit boolscher Funktion F:\\
  $\sigma_F(r)=\{t|F(t) \wedge t \in r\}$
 \item Umbenennung $\rho$: Erzeugt neue Relation mit anderem RS:\\
  $\rho_{X\leftarrow A}(r) = s$ mit A als altem und X als neuem Bezeichner
 \item Vereinigung $\cup$: vereinigt zwei Relationen mit gleichem Relationnschemata:\\
  $r_1 \cup r_2 = s = \{t | t \in r_1 \vee t \in r_2 \}$
 \item Differenz $-$: Mengendifferenz:\\
  $r_1 - r_2 = \{t | t \in r_1 \wedge t \notin r_2 \}$
 \item Kartesisches Produkt $\times$: ``Kreuzprodukt'' (ergibt n*m Tupel):\\
  $r_1 \times r_2 = \{t | t[RS_1] \in r_1 \wedge t[RS_2] \in r_2 \}$
 \item Höherwertige Operatoren: lassen sich aus Grundoperatoren erzeugen: $\Join, \cap, \div, \Join_\Theta, \ltimes$
 \item Einfacher Verbund $\Join$ (natural join): Vereinigung bei gleichen Inhalten gleicher Attribute:\\
  $r_1 \Join r_2 = \{t | t[RS_1] \in r_1 \wedge t[RS_2] \in r_2 \}$
 \item Schnitt $\cap$: Nur gemeinsame Elemente:\\
  $r_1 \cap r_2 = r_1 - (r_1-r_2) $
 \item Division $\div$: Ermittlung der Tupel mit Beziehung zu Tupeln anderer Relation:\\
  $r_1 \div r_2 = \{t | \forall u\in r_2 \exists v \in r_1 : t=v[RS_1-RS_2]\}$
 \item Theta Join $\Join_\Theta$: Verknüpfung bzgl. eines Prädikates $\Theta$:\\
  $r_1 \Join_\Theta r_2 = \sigma_\Theta (r_1 \times r_2)$
 \item Semi-Join $\ltimes$: Joinbeteiligte von nur einer Seite:\\
  $r_1 \ltimes r_2 = \pi_{RS_1}(r_1 \Join r_2)$
\end{itemize}

\subsection{Das Relationenkalkül}
\begin{itemize}
 \item Ziel: Deklarative Beschreibung der Ergebnisrelation
 \item Syntax: r(t) (r Relation, t Tupelvariable), r[A]=u[B] (A, B Attribute)
 \item Formeln können zusammengesetzt werden mit $\wedge, \vee, \neg, \forall t:f(t), \exists t:f(t)$
 \item Freie Variable: uneingeschränkt, gebundene: Durch Formel eingeschränkt
 \item Ausdruck des Tupelkalküls: \{t | f(t)\} mit t als einzig freie Variable
 \item Substitution in Formeln: Schrittweises Auflösen einer Formel mit ``wahr'' und ``falsch''
 \item Wert eines Ausdruckes \{t | f(t)\} = alle Tupel, die sich zu ``wahr'' auflösen
 \item Kurzschreibweisen: \\
  $\exists t: r(f(t)) := \exists r(t) \wedge f(t)$\\
  $\forall t: r(f(t)) := \forall t: \neg r(t) \vee g(t)$\\
  $f \Rightarrow g := \neg f \vee g$
 \item Das Tüpelkalkül ist ausdrucksstärker als die RA (unendliche Ergebnismengen möglich)
 \item Sichere Ausdrücke: Eingeschränkt auf endliche > gleiche Mächtigkeit wie RA
\end{itemize}

\subsection{Erweiterung der relationalen Algebra}
\begin{itemize}
 \item Probleme: Mengensemantik hat keine Ordnung, Verdichten nicht möglich, Duplikate werden nicht erhalten
 \item M-Relationen (Multimengen-R.), mit speicherung der Vielfachheit, MREL(RS) = Mende aller M-Relationen über RS
 \item berücksichtigung im kartesischen Produkt, Summenvereinigung, Projektion
 \item Aggregation: Berechnung von Kennzahlen wie Summe (sum), Durchschnitt (avg), Anzahl (count), min/max:\\
  z.B. $avg_A(r)$ liefert numerischen Wert
 \item Gruppierung $\gamma_X$: Relation mit gleichem Schema wie M-Relation\\
  z.B. $gamma_{X, A1 \leftarrow count} (r)$ mit Anzahl der Tupel mit X 
\end{itemize}

\section{SQL - Die Abfragesprache für relationale Datenbanken}
\lstset{language=sql}
\subsection{Allgemeines}
\begin{itemize}
 \item SQL: structured query language, seit 1974
 \item Marktbeherrschend, mischung aus TK und RA, unterstützt (Multi-)Mengensemantik, Aggregation, Gruppieren und Sortieren
 \item Grade der Standardisierung: Entry, Intermediate, Full
 \item Rekursion, Prozeduren, XML, ...
 \item beinhaltet DDL und DML
 \item unterstützung aus Java, C++, C\#, Scala, ...
 \item nicht case-sensitiv, Befehle enden mit Semikolon, Kommentare mit --
 \item DDL: \lstinline$create view <name>$, \lstinline$create table <name>$,\\
  \lstinline$create index <name>$, \lstinline$create database <name>$\\
  Beispiel: \lstinline$create table Name(nummer int primary key, mname varchar(19));$ (primary key ist Integritätsbedingung)\\
  Fremdschlüssel: \lstinline$attribut int references Name(nummer)$\\
  Weitere Integritätsbedingungen: \lstinline$not null$, \lstinline$default 'Wert'$
 \item Primärschlüssel aus mehreren Attributen: \lstinline$constraint primkey primary key (a1, a2)$
 \item Löschen: \lstinline$drop table xname>$, Ändern: \lstinline$alter table <name> add <komponente>$
 \item DML-Beispiel: \lstinline$insert into <name> [(<a1>, <a2>)] values (<k1>, <k2>), (<l1>, <l2>)$
\end{itemize}

\subsection{Anfragen in SQL}
\begin{itemize}
 \item Grundschema:\\
  \lstinline$select <Liste von AttrNamen> from <Liste von RelNamen> [where <Bedingung>]$
 \item input: mehrere Relationen, output: eine temporäre Relation
\end{itemize}
\subsubsection{Operatoren der relationalen Algebra in SQL}
\begin{itemize}
 \item Ausgabe einer Relation: \lstinline$select * from <name>;$
 \item Projektion: \lstinline$select distinct <a> from <r>;$ wobei \lstinline$disdinct$ Duplikate verhindert
 \item Selektion: \lstinline$select * from <name> where <Bedingung>;$\\
  Bedingungen: \lstinline$<, >, =, in, not in, exists, any, some, all, and, or, not, ...)$
 \item Kartesisches Produkt: \lstinline$select * from <name1>, <name2>;$
 \item Vereinigung: \lstinline$select <a1> from <name1> union select <a2> from <name2>;$, mit Duplikaten: \lstinline$union all$
 \item Differenz:  \lstinline$select <a1> from <name1> except select <a2> from <name2>;$, mit Duplikaten: \lstinline$except all$
 \item Umbenennung: \lstinline$select <a1> as <neu1>, <a2> als <neu2> from <name>;$
 \item SWF-Anfrage: bestehend aus \lstinline$select, from, where$,\\
  Umsetzungsreihenfolge: \lstinline$from, where, select$
\end{itemize}

\subsubsection{Joins}
\begin{itemize}
 \item Durch kartesisches Produkt und Selektion ausdrücken
 \item \emph{Equi-Join}: \lstinline$select * from r, s where r.A = s.B$
 \item \emph{Semi-Join}: \lstinline$select r.* from r, s where r.A = s.B$
 \item Das Datenbanksystem vermeidet dabei die Bildung des kartesischen Produktes
 \item \emph{Kartesisches Produkt}: \lstinline$from r cross join s$
 \item \emph{Innerer Theta-Join}: \lstinline$from inner join s on r.A > s.B$ wobei \lstinline$inner$ jeweis optional ist
 \item \emph{Innerer Equi-Join}: \lstinline$from r inner join s using (A)$
 \item \emph{Natural Join}: \lstinline$from r natural inner join s$
 \item \emph{Outer Join}: Ergebnisse des inneren Joins mit denen ohne Join-Partner, fehlende Werte werden \lstinline$null$\\
  Beispiel: \lstinline$from r left outer join on r.A = s.B$
 \item \emph{NULL-Werte}: Kein Wert bekannt, eigentlich nicht Bestandteil des relationalen Modells
 \item automatische Eintragung verhindern: \lstinline$not null$ (Integritätsbedingung)
 \item Prüfen: \lstinline$is null$
 \item erfordert dreiwertige Logik: true, false, unknown
\end{itemize}

\subsubsection{Where-Klausel}
\begin{itemize}
 \item \emph{Ehere-Klausel} entspricht im Wesentlichen der Formel des TK: ``A <operator> B''
 \item \emph{between-Operator}: \lstinline$A between B and C$
 \item \emph{like-Operator}: \lstinline$A like B$ Vergleich mit Wildcards: \%: bel. viele Zeichen, \_: genau ein Zeichen\\
  Beispiel: \lstinline$select A from r where B like 'M\%g_t'$
 \item \emph{in-Operator}: \lstinline$A in (b, c, ..)$ (A: Ausdruck; b, c, ..: Konstanten)
\end{itemize}

\subsubsection{select-Klausel}
\begin{itemize}
 \item \emph{Duplikate beseitigen}: \lstinline$select distinct * from r, s where ...$
 \item \emph{Umbenennung}: \lstinline$select A as X, B*C as Y, abs(D) as Z from r;$ (vgl. Map-OP der RA)
\end{itemize}

\subsubsection{Aggregate}
\begin{itemize}
 \item Numerische: \lstinline$count, sum, avg, min, max$
 \item statistische: \lstinline$variance, corr, stddev, regr slope$
 \item logische: \lstinline$exists, every, any, some$
 \item \emph{Group-by-Klausel}: ggf. alternative zu Aggregat, $\gamma$-Operator der RA\\
  Beispiel: \lstinline$select <nummer>, cout(*) from r group by <nummer>$
 \item \emph{Having-Klausel}: Filtert Gruppen mit einem Boolean-Ausdruck\\
  Beispiel: \lstinline$select <nummer>, avg(zahl) from r group by <nummer> having count(*)>2;$ (Nur Relationen mit mehr als 2 Tupeln)
\end{itemize}

\subsubsection{Sortierte Ausgabe}
\begin{itemize}
 \item \lstinline$order by <a1>, <a2> asc nulls last limit 3$ sortiert aufsteigend erst nach a1, dann nach a2, Ausgabe auf 3 beschränkt
\end{itemize}

\subsection{Geschachtelte Anfragen}
\begin{itemize}
 \item Anstelle von persistenten Relationen können auch temporäre verwendet werden (Abfragen)
 \item Anstelle von Werten können Attribute temporärer Relationen verwendet werden
 \item \emph{Tupelvariablen}: Werden in \lstinline$from$-Klausel deklariert und binden an eine (temporäre) Relation an
  Beispiel: \lstinline$select a1.nummer, a2.nummer from r a1$
\end{itemize}

\subsubsection{from-Klausel}
\begin{itemize}
 \item Beispiel: \lstinline$select v.nr1 from (select nr1, nr2 from where nr3<100)v where v.nr2 < 3;$
\end{itemize}

\subsubsection{select-Klausel}
\begin{itemize}
 \item Bsb: \lstinline$select B.nr1, (select count(*) from r A where a.nr1 = B.nr1 and nr2 < 5) from r B;$
 \item Es lässt sich damit eine group-by-klausel nachbauen (aber ausdrucksstärker)
\end{itemize}

\subsubsection{where-Klausel}
\begin{itemize}
 \item Beispiel: \lstinline$select nr1 from r where nr2 = 67 and nr3 < (select avg(nr3) from r);$
\end{itemize}

\begin{itemize}
 \item Unteranfragen mit \lstinline$exists$ sind möglich
 \item Tupelvariablen sind in Unteranfragen gültig, werden aber darin bei neudeklaration überdeckt
 \item korrelierte Unteranfragen lassen sich oft in gewöhnliche Anfragen transformieren
 \item \emph{rekursive Anfragen}: umsetzung nur rudimentär, Anfragen über with-klausel
 \item \emph{with-Klausel}: temporäre Relation kann in darauffolgenden SQL-Befehlen genutzt werden
  Beispiel: \lstinline$with r(nr1, nr2) as (select nr1, avg(nr3) from s group by nr1)$
  \lstinline$select nr1 from r where ...$
 \item \emph{with recursive}: \lstinline$with recursive gauss(n) as (values (1) union select n+1 from gauss$ 
  \\\lstinline$where n<100)$\\
  \lstinline$ select sum(n) from gauss;$
 \item auswertung rek. Anfragen: nicht-rekursiver Teil: temporäre Arbeitsrelation bei auswertung des nicht-rekursiven Teils, dann der rekursive Term in eine temporäre Relation
 \item ggf. limit oder union all zwecks Abbruck einfügen
 \item \emph{konstante Relation}: \lstinline$values (<k1>, <inhalt>, ..),(..)$ erzeugt eine konstante Relation
\end{itemize}

\subsection{Einfügen, Löschen, Ändern}
\begin{itemize}
 \item \emph{Einfügen}: \lstinline$insert into r [<Attribute>] values (<Konstanten>)$ (ggf. statt \lstinline$values$ eine SQL-Anfrage)
 \item \emph{Löschen}: \lstinline$delete from r [where <bedingung>]$
 \item \emph{Ändern}: \lstinline$update r set a = a-1 [where ...]$
 \item \emph{Loading}: Einfügen beispielsweise aus csv-Datei, Spezialfunktionalität des DBMS
\end{itemize}

\subsection{Anlegen von Datenstrukturen}
\begin{itemize}
 \item \emph{Index} verbessert Antwortzeiten O(log n) statt O(n); Anlegen mit:\\
  \lstinline$creat [unique] indes <IndexName> on <Relation>(<Attribut>[<Ordnung>][,..])$\\
  mehrere Indexe auf eine Relation möglich (unabhängig von Speicherorganisation)
 \item \emph{Sichten}: Benutzerspezifische temporäre Ausschnitte der DB, logisch unabhängig\\
  \lstinline$create view <Sichtname> [(Attribut>[, ..]] as <Subquery> [with check option]$\\
  \lstinline$with check option$: Nur Datensätze, die auch wiedergefunden werden (zwecks änderung/einfügung > an Relation weiterreichen!)
 \item \emph{Namensraum}: zur Vermeidung von Namenskonflikten\\
  \lstinline$create schema <Name> [authorization <Benutzer>] [schema_element]*$
 \item \emph{Wertebereich}: Einschränkung durch Integritätsbedingungen:\\
  \lstinline$create domain <Name> [as] <Datentyp> [..]$
 \item \emph{Datentypen}: (Beispiele)\\
  \lstinline$bigint, bit, bit varying, char, character varying, date, time, xml, ...$
\end{itemize}

\subsection{Integritätsbedingungen}
\begin{itemize}
 \item statisch: beschreibt Datenbankzustand, dynamisch: DB-Änderungen
 \item \emph{Primärschlüssel}: Ein einziger, eindeutiger Schlüssel in einer Relation: \lstinline$primary key$
 \item weitere eindeutige Attribute: \lstinline$unique$ (null ist erlaubt, auch mehrfach!) Beide erstellen automatisch ein Index
 \item \emph{Fremdschlüssel}: Schlüssel in einer anderen Relation (oder null)\\
  \lstinline$create table <Name>(<> int references R(r), ..)$\\
  Referentielle Integrität wird eingehalten, löschen bei Fremdbezug nur durch Kaskadierendes Löschen: \lstinline$on delete cascade on update set null$ (alle abhängigen Werte werden auf null gesetzt)
 \item Integritätsbedingungen können z.B. zu bestimmten Zeitpunkten überprüft werden. \lstinline$not deferrabe$: sofortige überprüfung, \lstinline$deferrable initially deferred$: am Ende der Transaktion, \lstinline$.. immediate$: vor Änderung. Ändern mit \lstinline$set ..$
 \item \emph{Bedingung} für Relation: \lstinline$check(note > 0 and note < 7)$, hinzufügen mit:\\
  \lstinline$alter table r add constraint v check(..)$
 \item \emph{Assertion}: Eigenständiges Objekt für Bedingung:\\
  \lstinline$create assertion <name> check <Bedingung>$
\end{itemize}

\section{Anwendungsprogrammierung}
\lstset{language=java}
\begin{itemize}
 \item Aufteilung: Datenbank, problemspezifische Operationen, GUI; wobei nur die Datenbank in SQL ist, der Rest z.B. Java
 \item SQL: Deskriptive Anfragesprache, aber geringer Funktionalitätsumfang für alltägliche Programmierung
 \item \emph{Impedance Mismatch}: Mengenorientiert vs. Objektorientiert\\
  Kopplung über: Call-Schnittstelle wie JDBC, Vorübersetzer SQLJ, Frameworks Hibernate oder JPA, Erweiterungen PL/SQL ...
\end{itemize}

\subsection{CALL-Schnittstelle}
\begin{itemize}
 \item in Java: JDBC (Bestandteil von Java: Paket java.sql)
 \item SQL-Anfragen werden durch den Linker als Strings im Compilercode eingebunden
 \item Rückgabe als Cursor
 \item Nachteile: komplizierte Programmierung, fehleranfällig; Vorteil: sehr Flexibel
 \item \emph{Wichtige Klassen}: Connection, DriverManager, CallableStatement, PreparedStatement, Statement, ResultSet
 \item \emph{Client-Server-Kopplung}: Nach Anmeldung der Treiberklasse durch \\
  \lstinline$Class.forName(``oracle.jdbc.driver.OracleDriver'');$\\
  \lstinline$Connection con=DriverManager.getConnection(``<URL>'', ``<user>'', ``<passwort>'');$\\
  Connection-Objekt sendet Anweisungen an Server, empfängt Resultate etc.
 \item Ausführen von Anfragen durch z.B. \lstinline$ResultSet executeQuery (String sql)$
 \item \emph{PreparedStatement}: Muss bei Objekterzeugung bis auf Parameter (? im SQL-Befehl) fertig sein:\\
  \lstinline$PreparedStatemend stmt = con.prepareStatement(..);$\\
  Ausführen z.B. mit \lstinline$stmt(setInt(1,20);$
 \item \emph{Abfrageergebnisse} liegen als ResultSet, einem Cursor, vor. Methoden wie\\
 \lstinline$next(), findColumn(), getObject$. Neuere JDBC-Versionen unterstützen Änderungsoperationen, auch Batch-Updates sind möglich
 \item \emph{Metadaten}: Schnittstellen: ResultSetMetaData (Anzahl Spalten, Datentyp und Namen der Spalten) und DatabaseMetaData (Schema, also Namen der Relationen, und Eigenschaften des DBMS
 \item \emph{Ausnahmen}: SQLException, unkritisch: SQLWarning
 \item \emph{SQL-Typen}: Typen in unterschiedlichen DBMS ist unterschiedlich, in java.sql.Types finden sich einige generische Bezeichner\\
  bestimmten Typ auslesen mit getXXX, z.B. getInt (ebenso: setXXX)
\end{itemize}

\subsection{Einführung in Hibernate}
\begin{itemize}
 \item \emph{Ziel}: Objektrelationales Mapping (ORM): (Daten-)Objekte werden in der Datenbank persistent verwaltet.\\
  Vorteile: Indizierung, Konsistenzsicherung, hohe Verfügbarkeit, Mehrbenutzerbetrieb, integration voehandener Datenbestände, Performanz
 \item \emph{ORM-Architektur}: OR-Mapping zwischen OO Anwendung und DB
 \item Problem: Impedance Mismatch: Objekte vs. Mengen
 \item \emph{Himernate}: ORM für Java \& .Net, unterstützt gängige DBMS\\
  Vorgehen: Top-Down (DB-Schema aus Klassenmodell generiert), Bottom-Up: Klassen aus rel. DB-Schema generiert, Meet-In-The-Middle\\
  Keine spezifischen Erweiterungen im Java nötig
 \item \emph{Hibernate Query Language (HQL)}: Eigene Abfragesprache von Hibernate
 \item \emph{Konfiguration}: Enthält Verbindungsdaten zum DBMS, Einstellungen etc. und wird über XML-Datei hibernate.cfg.xml geladen.
 \item \emph{XML-Mapping}: Zuordnung (Abbildung) Java-Klassen <-> Relationen über XML-Datei, Problem: Schlüssel vs. \lstinline$equals()$
 \item \emph{POJO}: Java-Klassen müssen ``Plain Old Java Object'' sein (Default-Konstruktor, Getter- und Setter-Methoden für alle Felder)
 \item Klassen von Hibernate: SessionFactory; Session: Laden, Speichern, ...; Querry: Anfragen in HQL
 \item \emph{Beziehungen}: Fremdschlüssel vs. Assoziationen (Verweise)
 \item Unterschiedliche Implementierung Uni- und bidirektional
 \item n:m mit <many-to-many>-Tag möglich
 \item \emph{Is-A-Beziehung}: keine direkte Unterstützung in SQL\\
  Möglichkeiten: eine Tabelle je (konkrete) Klasse oder eine Tabelle je Klassenhierarchie
 \item \emph{Identität}: Objekt erhält Primärschlüssel Eigenschaft: \lstinline$objekt.getId()$, Hibernate garantiert Persistenz nur innerhalb einer session!
 \item \emph{Anfragesprachen}: HQL (Abfragen in SQL als vordefinierte Strings); Criteria API (Anfragen in Java), Problem: dynamische Erzeugung von Anfragen schwierig; Natives SQL per JDBC (kein ResultSet-Handling von Hibernate)
 \item Konkrete Umsetzung der Abbildungsdatei hier nicht dokumentiert!
\end{itemize}

\subsection{Prozedurale Erweiterung von SQL}
\lstset{language=sql}
\begin{itemize}
 \item \emph{SQL/PSM} (Persistent Stored Modules) Teil des SQL-Standart
 \item Zur Ausführung von Funktionen auf dem Server: unabhängig vom Client, Performant (keine Kommunikation), Zentral
 \item \emph{Vorgehen}: Implementierung, \\
  Installation auf Server: \lstinline$loadjava -user <> hello.class$\\
  Registrierung: \lstinline$create procedure <> return ...$ bzw. \lstinline$create function$\\
  Aufruf vom Client: \lstinline$CallableStatement <> = con-preparaCall(``{call ? HelloWorld()}''); ..$
\end{itemize}

\section{Datenbankentwurf}
\begin{itemize}
 \item Schritte: Anforderungsanalyse (Datenverarbeitung/Informationen); Konzeption; logischer Entwurf (DBMS berücksichtigen); Physischer Entwurf
 \item \emph{Anforderungsanalyse}: Informations(struktur)anforderungen (Objekte/Attribute, Beziehungen, wie viele?); Datenverarbeitungsanforderungen (typischen Prozesse, Reihenfolge, Priorität der Operationen)\\
 Dazu Pflichtenheft mit Benutzern erstellen
 \item \emph{Konzeptioneller Entwurf}: Datenbeschreibung in einer formalen Sprache (UML/ER-Modell)
 \item \emph{Logischer Entwurf}: Abbildung der Konzeption in Datenstrukturen des logischen Datenmodells (z.B. Transformation in relationales Modell), redundanz vermeiden!\\
 unabhängig vom physischer repräsentation/DBMS!
 \item \emph{Physischer Entwurf}: physische Umsetzung des logischen Entwurfes, Anlegen von Hilfsstrukturen wie Indexe etc., Hardwarestrukturen, ...
\end{itemize}

\subsection{Entity-Relationship Datenmodell}
\begin{itemize}
 \item \emph{ER-Modell}: Modellierung durch Abstraktion
 \item Beschreibung von Entitäten (Entities) mit Eigenschaften (Attributen) und Beziehungen (Relationships)
 \item \emph{Entitätstypen}: (Entitätsmengen) Sturukturgleiche Entitäten
 \item \emph{Schlüssel}: minimale Menge von Arrtibuten, die eine Entität eindeutig bestimmt
 \item \emph{Beziehungstyp}: Menge strukturgleicher Beziehungen von n>1 Entitätstypen (n = Grad des Beziehungstyps); Kann weitere Attribute haben (Beispiel: kannMaschineBedienen, Note:1-6)
 \item \emph{Funktionalität von Beziehungstypen}: 1:1; 1:M (eine aus E1 mit vielen aus E2, aber einer aus E2 nur mit einem aus E1); M:N (many-to-many)
 \item \emph{Graphische Repräsentation}: Entitätstyp: Rechteck; Attribut: Ellipse, Schlüssel wird unterstrichen; Beziehungstyp: Raute; Funktionalität an Verbindungslinien schreiben
 \item \emph{min-max-Notation}: min/maxanzahl der Beziehungen an Beziehungen schreiben (jeweils an die Entitätenseite!), * bedeutet beliebig viele, z.B.: (1,*)
 \item \emph{Id-Beziehungen}: Eine Entität (schwache E.) hängt von der anderen (starken) ab (schwache und Beziehung in Doppelrechteck/-raute)
 \item \emph{Is-A-Beziehung}: Eigenschaften werden vererbt (u.A. auch der Schlüssel)
\end{itemize}

\subsection{Abbildung des ER-Modells in ein relationales Datenmodell}
\begin{itemize}
 \item Einfache Umsetzung, dann Konsolidierung
 \item (fast) 1:1 Entitätstypen in Relationen umsetzen, Schlüssel wird Primärschlüssel
 \item Jeder Beziehungstyp wird zu Relation, daber bilden Primärschlüssel die Schlüssel der Relationen (Achtung: Einduetige Attributnamen!), Attribute der Relation aufnehmen
 \item \emph{Konsolidierung}: Vereinfachung des Datenbankschemas: Verschmelzen von Relationen mit 1:1, 1:N, N:1 (gleiche Primärschlüssel > outer-join)
\end{itemize}

\subsection{Entwurfstheorie relationaler Datenbanken}
\begin{itemize}
 \item \emph{Ziel}: Beurteilung der Güte eines DB-Schemas Vermeidung von Redundanzen und Anomalien, Informationsverlust, Effizienz
 \item \emph{Funktionale Abhängigkeiten (FD)}: statische Integritätsbedingungen, bei Anforderungsanalyse ermitteln\\
  Beispiel: \{ShopName, Ware\} -> \{Preis\} ShopName und Ware bestimmen eindeutig den Preis
 \item FD: $a \rightarrow B$ \textit{trivial} wenn $B \subseteq A$; \textit{voll} wenn keine echte Teilmenge C, sonst \textit{partiell}; \textit{transitiv} wenn nur über ein anderes Element.
 \item Ziel: Minimierung der FDs: Menge F von FDs zu einer (minimalen) äquivalenten Menge $F_c$ reduzieren
 \item \emph{$F^+$}: Menge aller gültigen FDs (Hülle), (3 Amstrong-)Axiome \& Regeln:
 \begin{itemize}
  \item \textit{reflexiv}: $B \subseteq A \Rightarrow A \rightarrow B$
  \item \textit{Verstärkung}: $A \rightarrow B \Rightarrow A \cup C \rightarrow B \cup C$
  \item \textit{Transitivität}: $A \rightarrow B \wedge B \rightarrow C \Rightarrow A \rightarrow C$
  \item \textit{Vereinigung}: $A \rightarrow B \wedge A \rightarrow C \Rightarrow A \rightarrow B \cup C$
  \item \textit{Dekomposition}: $A \rightarrow B \cup C \Rightarrow A \rightarrow B \wedge A \rightarrow C$
  \item \textit{Pseudotransitivität}: $A \rightarrow B \wedge C \cup B \rightarrow D \Rightarrow A \cup C \rightarrow D$
 \end{itemize}
 \item \textit{Membership-Problem}: Test ob eine Abhängigkeit $A \rightarrow B \subset F$ ist: Ermittlung der Hülle $A^+$ der Attributmenge bzgl. der Menge F! Dann: $ B \subseteq A^+ \Rightarrow A \rightarrow B \in F^+$ 
 \item \emph{$F_c$ Kanonische Überdeckung} von $F$ falls $F_c^+ = F^+$ und $\forall A \rightarrow B$ gibt es keine ``überflüssigen'' As \& Bs (${(F_c\setminus A)}^+ \notin F^+$)
 \item Algorithmus: Linksreduktion durchführen; Rechtsreduktion durchführen; alle $A \rightarrow \emptyset$ entfernen; alle $A \rightarrow B_1, ..$ ersetzen durch $A \rightarrow B_1 \cup ..$
 \item \emph{Zerlegung einer Relation} zur Beseitigung von Anomalien; kein Informationsverlust, FDs erhalten!\\
  \textit{Hüllentreue} zerlegung: $F^+ = (F_1 \cup ..)^+$
 \item \emph{Normalformen}:
 \begin{itemize}
  \item \textit{1. NF}: Alle Attribute nur atomare Werte
  \item \textit{2. NF}: jedes Attribut prim (Teil v. Schlüsselkandidat) oder voll FD (nur verletzt wenn Schlüsselkandidaten zusammengesetzt)\\
   (kein Nichtschlüsselattribut ist abhängig von einem Teilschlüssel)
  \item \textit{3. NF}: Alle Abhängigkeiten haben Schlüsselkandidaten oder abhängige Elemente sind prim\\
  (kein Nichtschlüsselattribut hängt transitiv von einem Schlüsselkanditaten ab)
 \end{itemize}
 \item \emph{Synthesealgorithmus}: \textit{Top-Down}: (Dekomposition: Universalrelation zerlegen bis alle in 3.NF; \textit{Bottom-Up}: 3.NFs verschmelzen solange sie in 3.NF bleiben.\\
  \textit{4 Schritte}: 1. Überdeckung der FDs ermitteln; 2. RS erzeugen aus FDs; 3. Falls kein Kandidatenschlüssel: RS mit K \& F ($\emptyset$) erzeugen; 4. anderweitig enthaltene RS entfernen
 \item \emph{Boyce-Codd Normalform} (BCNF): Alle ``echte'' (nicht-zirkuläre) Abhängigkeiten haben einen Schlüsselkandidaten (immer in 3.NF); Existiert zu jeder Menge von Attributen und FDs ohne Informationsverlust (aber nicht zwingend hüllentreu)
 \item \emph{Mehrwertige Abhängigkeiten} (MVD): $A \rightarrow \rightarrow B$ z.B. bei ISBN und Autor möglich; bei mehreren MVDs: Dekomposition! (verlustfrei!)
 \item \textit{4. NF}: (Verstärkung der BCNF) Jede nicht-triviale MVD enthält einen Schlüsselkandidaten ($A \rightarrow \rightarrow B$ \textit{trivial} $\Leftrightarrow B \subseteq A \vee B=RS-A$)
\end{itemize}

\subsection{Grenzen der Normalformen}
\begin{itemize}
 \item ggf. unpassend bei nur lesendem DB-Zugriff
 \item Beispiel: Star-Schema (z.B. ``Data-Warehouse'') liegt nicht in 3.NF vor (Star-Join)
\end{itemize}

\section{Transaktionen}
\begin{itemize}
 \item \emph{Transaktionen (TA)} müssen zahlreiche Bedingungen erfüllen (Konsistenz, Gleichzeitigkeit, Mehrbenutzer, Zuverlässigkeit auch bei Hardwareproblemen, ...)
 \item \emph{Elementaroperationen}: Mit Auswirkung auf DB: Lesen, Wertzuweisung
 \item \emph{Ablaufsteuerung}: Anfang einer Transaktion T: bot T.bot(); Ende: commit T.c(); Abbruch: abort T.a(); Ansonsten: T.r(), T.w() (lesen/schreiben)
 \item \emph{ACID-Bedingungen}: TA ist Atomate Ausführungseinheit; Consistenter Zustand; Isoliert gegen andere TA; Dauerhaft; (Aufgaben des Transaktionsmanagers)
 \item (Elementar-)Operationen in sequentieller Ordnung im Ausführungsplan (\& Historie)
 \item \emph{Probleme}:
  \begin{itemize}
   \item \textit{lost update}: Gleichzeitiger Zugriff läßt ersten Zugriff ungeschehen machen (DB bleibt konsistent)
   \item \textit{inkonsistente Sicht}: Durch verzahlnte Operationen sieht die Datenbank nur inkonsistent aus
   \item \textit{inkonsistente DB}: Verzahnte Zugriffe sorgen für Inkonsistenzen
   \item \textit{Phantom-Problem}: Ein zwischen Lesen und Schreiben aller Tupel eingefügter Datensatz erscheint beim Schreiben als Phantom
  \end{itemize}
\end{itemize}

\subsection{Serialisierung von TAs}
\begin{itemize}
 \item Bei zwei Transaktionen auf dem gleichen Datensatz entsteht ein \textit{Konflikt} wenn die Teiloperationen nicht vertauschbar sind. Wenn Ausführungpläne bei Konflikten identisch sind heißen sie \textit{äquivalent}.
 \item \emph{Sequentiell}: Transaktionen werden komplett nacheinander abgearbeitet
 \item \emph{Serialisierbar}: $\exists$ ein äquivalenter sequentieller Ausführungsplan (genau dann, wenn ein Gerichteter Serialisierbarkeitsgraph (1 Knopen pro T, Kanten = Konflikte) zyklenfrei ist)
\end{itemize}

\subsection{Syncronisationsverfahren}
\begin{itemize}
 \item Zwei Verfahren:
  \begin{itemize}
   \item \textit{verifizierend}: Ausführungsplan beobachten, bei nicht gegebener Serialisierbarkeit zurück
   \item \textit{präventiv:} nicht-serialisierbare Pläne verhindern (Sperrverfahren; Zeitstempel, Mehrversionen)
  \end{itemize}
 \item \emph{Sperrvarfahren}: Aktueller DB-Bereich wird gesperrt (Probleme mit Verklemmungen bei mehreren Sperren, Lösungen durch gemeinsames Sperren, alternativ: gemeinsames Entsperren)\\
 Auch nur Schreibsperren als Modus möglich
 \item \emph{Mehrbenutzersyncronisation}: Isolationslevel: Erhöhung der Parallelität, aber Gefahr der Inkonsistenzen\\
 read uncommited, read committed, repeatable reads, seializable
\end{itemize}

\subsection{Fehlerbehandlung}
\begin{itemize}
 \item Schutz vor Beeinträchtigung (User/system) durch Fehler oder Systemabsturz innerhalb einer TA, Lösung durch recovery-Komponente
 \item \emph{Fehlerklassen}: Transaktionsfehler (rücksetzen von TAs), Systemfehler (Alle TAs rücksetzen), Speicherfehler (HD) (Rekonstruktion der DB)
 \item \emph{Lese/Schreiboperation}: Lese Seite (Block), Fixiere Seite im Puffer, Sperre Datensatz, (TA), Zürückgeben der Sperre, Entsperren (Unfix)
 \item Bei Schreibpoerationen: DB kurzzeitig inkonsistent
 \item Varianten: (no-) steal: Freigabe vor (nach) dem commit; (no-)force: (nicht) schreiben bei commit\\
 Bei Inkonsistenz: REDO oder UNDO mit Protokoll\
 \item \emph{Logging}: Physisches (vorher- oder nachher-Zustand); Logisches (redo/undo); Physiologisches (beide)
 \item WAL (Write Ahead Logging): vor commit in Log-Datei schreiben!
 \item Nach Systemfehler: Analyse, Widerholung der Historie (Winner: schon committed), rückläufiges undo der Looser (uncommitted)
 \item redo ist idempotent (nach abbruch widerholbar), undo braucht Kompensationseinträge
 \item \emph{Sicherungspunkte}: Um Logs (und damit Recoverykosten) klein zu halten:
 \begin{itemize}
  \item \textit{Transaktionskonsistente}: Puffer schreiben, neue Protokolldatei bei keinen (gesprerrten) TAs
  \item \textit{Aktionsbasierte}: Min\_LSN aufnehmen (unfertige Änderungen zum Sicherungspunkt) ggf. schrittweises Weitersetzen des Sicherungspunktes\\
 \end{itemize}
 \item \emph{Verlust des externen Speichers}: Archivkopie mit Log-Datei!
\end{itemize}

\section{Konzepte der Implementierung von DBMS}
\begin{itemize}
 \item Speichersystem > Zugriffssystem > Tatensystem > SQL-Shell
\end{itemize}

\subsection{Speichersystem}
\begin{itemize}
 \item Zuordnung der Datenobjekte zu physischem Speicher
 \item Charakteristif von Festplatten: langsamer Direktzugriff, schneller Datentransfer > größere physische Einheiten (Seiten = Blöcke) (SQL: 8KB)
 \item Datei ist folge von Seiten, in PostgresSQL als Tablespace anzulegen; Speichersystem erlaubt Zugriff auf einzelne Seiten in Dateien
 \item Seitenzuordnung: Alles möglich zwischen statischer Datei-Zuordnung und dynamischer Block-Zuordnung (Adressierung über Tabelle)
 \item Beschleunigung durch Systempuffer
\end{itemize}

\subsection{Zugriffssystem}
\begin{itemize}
 \item \emph{Tuple-Identifyer} (TID, RowID oder RID): Seitenadresse und relative Adresse innerhalb der Seite; bei Migration in eine andere Seite: Stellvertreter-TID
 \item \emph{Recordmanager}: Verwalter von Datensätzen (Suche/Spiechern/Clustern)
 \item Zugriff auf Tupel: Entweder Relationen-Scan oder Index-Scan (vordefiniert)
\end{itemize}

\subsection{$B^+$-Bäume}
\begin{itemize}
 \item Gegensatz binärer Suchbaum: Für Externspeicher > viele Einträge in einem Knoten, Daten in Blattknoten, direkte Anpassung!
 \item Gegensatz: ISAM: statische Indexstruktur, periodische Reorganisation
 \item \emph{Binärer Suchbaum}: O(log n), Speicher O(n); bei vielen Daten nicht für Externspeicher geeignet
 \item \emph{$B^+$-Baum} Typ (b, c): Weg zum Blatt immer gleich; Knoten min 2, max 2b-1 Söhne, Blatt min c, max 2c-1 Einträge; Kosten O(h) (h=Höhe), h=O($log_b N$)
 \begin{itemize}
  \item \textit{Zwischenknoten}: Abwechselnd Zeiger auf Kindseite/Trennschlüssel
  \item \textit{Blattknoten}: Zeiger linkes Blatt | k | TID | .. | frei | Zeiger rechtes Blatt
 \end{itemize}
 \item Die Trennschlüssel geben den Maximalwert an, der unter dem Zeiger davor zu finden sein könnte
 \item \emph{Kosten}: Durch feste Höhe: O(h) mit h = Höhe des Baumes = konstant, Bereichssuche O(h+r/c) (r = Anz. der Antworten)
 \item \emph{Einfügen}: Blatt suchen, in Blatt einfügen; falls voll: Aufspalten in je die Hälfte \& Zeiger neu setzen (Elternknoten/Nachbarn)
 \item \emph{Löschen}: Löschen im Blatt; falls zu wenig im Blatt: rechts o. links vereinigen (Zeiger!);\\
  Ständiges Aufspalten/Verschmelzen unterbinden durch Verschmelzen bei erst 33\%
 \item \emph{Varianten} mit diversten Optimierungen (Präfix-Bäume, Cache-sensitiv, ...)
\end{itemize}

\subsection{Datensystem}
\begin{itemize}
 \item \emph{Schritte bei Anfrage-Bearbeitung}: Formulieren; Übersetzen in Operatorbaum (logisch) > RA-Ausdruck; Auswahl physischer Operatoren; Ausführung
 \item \emph{Logische Operatoren}: \textit{Algebra}: Selektieren, Projektion, Vereinigung, Differenz, Kartesisches Produkt und Joins, Umbenennung;\\
  Gruppieren, Aggregate, Allgemeine Map-Funktionen, Sortieren\\
  \textit{erw. rel. Algebra}: Multimengensemantig, Unterstützung von Duplikaten
 \item \textit{Logischer Operatorbaum}: Interne Repräsentation der Anfrage durch Operatorbaum (RA), Optimierung durch algebraische Umformungen (günstige zuerst)
 \item \emph{Physische Operatoren}: Implementierung der logischen, i.d.R. Vielzahl von Implementierungen (>100(0))
 \item \emph{Kopplungen} der Daten von einem zum nächsten Operator:
 \begin{itemize}
  \item \textit{Nativ}: vollst. Verarbeitung, speichern in temp-Relation
  \item \textit{Datengetrieben}: partielle Verarbeitung der Ausgabe > schneller, Datenstrom
  \item \textit{Anforderungsgetrieben}: partielle Verarbeitung der Eingabe, auf Anforderung der 2. Operation (Konsument) > Schnell, Ergebnisse schon bei unvollständiger Verarbeitung, Abbruch günstig, kein Zwischenspeichern (auf Externspeicher)
 \end{itemize}
 \item \emph{ONC-Schnittstelle}: Umsetzung der angetriebenen Kopplung; Iteratoren Open (Iterator öffnen), Next (nächstes Element), Close (Iterator)
 \item \emph{Implementierung von Operatoren}: Probleme: große Datenmengen, native zu teuer; Beispiele:
 \begin{itemize}
  \item \textit{Nested-Loops}: Duplikatbeseitigung: partielle Ergebnisse in Relation S Speichern, neues Tupel mit S vergleichen...
  \item \textit{Hashverfahren}: Für jeden Datensatz hash ermitteln und in Tabelle eintragen sofern noch nicht vorhanden (danach passen hoffentlich die Daten in den Hauptspeicher, sonst: z.B. rekursives Partitionieren)\\
  Kosten durch Partitionieren: O(n*N/B) (N: Datensätze, B: Seitenkapazität, n:Partitionen (die in Hauptspeicher passen))
  \item \textit{Sortieren}: Erst externes Sortierverfahren, dann lineares durchlaufen
 \end{itemize}

\end{itemize}


% -----------------------------------------------------------------------------------------
%	Literaturverzeichnis
% -----------------------------------------------------------------------------------------
%\include{Literatur}
\end{document}