LaTeX-examples/documents/musterloesung-db-2012-09-24/musterloesung-db-2012-09-24.tex

\documentclass[a4paper,9pt]{scrartcl}
\usepackage{amssymb, amsmath} % needed for math
\usepackage[utf8]{inputenc} % this is needed for umlauts
\usepackage[ngerman]{babel} % this is needed for umlauts
\usepackage[T1]{fontenc}    % this is needed for correct output of umlauts in pdf
\usepackage{pdfpages}       % Signatureinbingung und includepdf
\usepackage{geometry}       % [margin=2.5cm]layout
\usepackage{hyperref}       % links im text
\usepackage{color}
\usepackage{framed}
\usepackage{enumerate}      % for advanced numbering of lists
\usepackage{marvosym}       % checkedbox
\usepackage{wasysym}
\usepackage{braket}         % for \Set{}
\usepackage{pifont}% http://ctan.org/pkg/pifont
\usepackage{minted} % needed for the inclusion of source code
\usepackage{tikz}
\usetikzlibrary{arrows,positioning, calc,lindenmayersystems,decorations.pathmorphing,intersections} 
\tikzstyle{vertex}=[draw,
fill=yellow,
circle,minimum size=10pt,inner sep=0pt]

\newcommand{\cmark}{\ding{51}}%
\newcommand{\xmark}{\ding{55}}%

\hypersetup{ 
  pdfauthor   = {Martin Thoma}, 
  pdfkeywords = {Datenbanksysteme,KIT}, 
  pdftitle    = {Musterlösung: Datenbanksysteme} 
} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Begin document                                                    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\section{Aufgabe 1 - Funktionale Abhängigkeiten}
\subsection{Teilaufgabe a)}
  Gilt $F \Rightarrow f$?

  \begin{tabular}{clccl}
    & Funktionale Abhängigkeit $f$ &  & Begründung\\
    \hline\hline
    1 & $DI \rightarrow BCDEFI$         & \xmark &   kein F\\
    2 & $BDG \rightarrow ABCDEFHH$      & \cmark &\\
    3 & $DHI \rightarrow ACDGI$         & \xmark &   kein A\\
    4 & $BCDEGI \rightarrow ABCDEFGHI$  & \cmark &\\
    5 & $AF \rightarrow ABCEGH$         & \cmark &\\
    6 & $ABCDE \rightarrow ABCEFHI$     & \xmark &   kein I\\
    7 & $DI \rightarrow CFGI$           & \xmark &   kein C\\
    8 & $ADFI \rightarrow BCDEFGHI$     & \cmark &\\
    9 & $GI \rightarrow BDEFG$          & \xmark &   kein B\\
  \end{tabular}

\subsection{Teilaufgabe b)}
Schlüssel in R:
\begin{itemize}
    \item $\Set{I, A}$
    \item $\Set{I, B}$
    \item $\Set{I, C}$
\end{itemize}

Die Relation befindet sich nur in 1NF, da $I \rightarrow H$ eine 
partielle Abhängigkeit darstellt. Daher kann die Relation nicht in
2NF sein.

\subsection{Teilaufgabe c)}
\begin{align*}
F^{(2)} = \{  & A \rightarrow B,\\
    &AI \rightarrow \delta,\\
    & B \rightarrow C, B \rightarrow D,\\
    & C \rightarrow A,C \rightarrow D,C \rightarrow F,\\
    & D \rightarrow E,D \rightarrow F,D \rightarrow G,D \rightarrow H,D \rightarrow H,\\
    & F \rightarrow G,\\
    & I \rightarrow H 
\}
\end{align*}

\begin{align*}
F^{(3)} = \{  & A \rightarrow B,\\
    &AI \rightarrow \delta,\\
    & B \rightarrow C, B \rightarrow D,\\
    & C \rightarrow A,\\
    & D \rightarrow E,D \rightarrow F,D \rightarrow H,\\
    & F \rightarrow G,\\
    & I \rightarrow H 
\}
\end{align*}

aufgelöst wurden wie folgt:

  \begin{tabular}{l|l}
             & redundant durch\\
    \hline
    $C \rightarrow D$ & $C \rightarrow A \land A \rightarrow B \land B \rightarrow D$\\
    $C \rightarrow F$ & $C \rightarrow A \land A \rightarrow B \land B \rightarrow D \land D \rightarrow F$\\
    $D \rightarrow G$ & $D \rightarrow F \land F \rightarrow G$\\
  \end{tabular}

ergibt die Zerlegung 

\begin{align*}
    R = \{\\
            & (\Set{A, B, C, D}, \Set{\Set{A}, \Set{B}, \Set{C}}),\\
            &(\Set{A, I}, \Set{\Set{A, I}}),\\
            & (\Set{D, E, F, H},\Set{\Set{D}}),\\
            & (\Set{F, G}, \Set{\Set{F}}),\\
            & (\Set{I, H}, \Set{\Set{I}})\\
        \}
\end{align*}
\clearpage

\section{Aufgabe 2 - SQL}
\subsection{Teilaufgabe a)}
\begin{tikzpicture}  [scale=1.2]
  \node (a)[vertex] at (1,2) {1};
  \node (b)[vertex] at (2,2) {2};
  \node (c)[vertex] at (3,1) {3};
  \node (d)[vertex] at (2,0) {4};
  \node (e)[vertex] at (1,0) {5};
  \node (f)[vertex] at (0,1) {6};

  \foreach \from/\to in {a/b,a/c,a/d,b/c,b/d,c/d,d/e,e/f}
    \draw[line width=1.5pt] (\from) -- (\to);
\end{tikzpicture}

\subsection{Teilaufgabe b)}
\inputminted[linenos, numbersep=5pt, tabsize=4]{sql}{d2b.sql}

\subsection{Teilaufgabe c)}
\subsubsection{Version A}
\inputminted[linenos, numbersep=5pt, tabsize=4]{sql}{d2c1.sql}

\paragraph{Weitere Erklärungen:}
Ansatz:
\begin{enumerate}
    \item Suche alle Personenpaare, die beide <id> als Freund haben (wobei
   nur ungleiche paare gesucht sind, da man nicht mit sich selbst befreundet
   sein kann)
    \item Prüfe über die Menge dieser Paare, welche noch nicht befreundet sind
\end{enumerate}

Dazu:
\inputminted[linenos, numbersep=5pt, tabsize=4]{sql}{d2c1.2.sql}

Ein LEFT JOIN ergänzen, um zu ermitteln, welche Paare nicht tatsächlich
in FriendshipSymmetric stehen (diese werden NULL joinen). Daher nach NULL
selektieren


Beispielhaftes Ergebnis für gegebene Situation und id=4:
\begin{verbatim}
"1","5"
"2","5"
"3","5"
"5","1"
"5","2"
"5","3"
\end{verbatim}
 
\subsubsection{Version B}
\inputminted[linenos, numbersep=5pt, tabsize=4]{sql}{d2c2.sql}

\section{Aufgabe 3 - Histories}
\subsubsection{Teilaufgabe a)}
\begin{itemize}
\item[H1] Es gibt folgende Kanten:
    (12, xyz), (13, xy), (23, y), (32, y).\\
    Somit ist ein Zykel zwischen 2 und 3 $\Rightarrow$ nicht serialisierbar
\item[H2] (21, xyz), (23, y), (31, xy).\\
    Somit keine Zykel und serialisierbar
\end{itemize}

\subsubsection{Teilaufgabe b) und c)}
(Y = erfüllt, N = nicht erfüllt)
\begin{itemize}
\item[H1]
    \begin{itemize}
        \item T3 reads y from T2 NN
        \item T2 reads x from T3 YN
        \item T2 reads z from T1 YN
        \item T3 reads x from T1 YN
    \end{itemize}
\item[H2]
    \begin{itemize}
        \item T1 reads y from T3 YN
        \item H1 ist nicht rücksetzbar (also weder in RC, ACA oder ST)
        \item H2 ist in RC (also nicht in ACA oder ST)
    \end{itemize}
\end{itemize}
\end{document}