%\includeversion{english}
%\excludeversion{german}

%% Generate table with Exercises/points on the title page

\makeatletter\@ifundefined{vorname}
                  {\def\vorname{\underline{\hspace*{6cm}}}}{\relax}
\makeatother

\def\pageheader{%
Name: \hbox to 5cm{\ \ \vorname\ \name\hfill} \hfill 
MatNr.: \hbox to 5cm{\ \ \matrikel\hfill}\\
~
\hrule
\vskip1cm
}

\setcounter{page}{0}
\setcounter{Aufgabe}{0}
\setcounter{countpkte}{0}
\setcounter{countzpkte}{0}
\setcounter{erwpkte}{0}

\def\punkte#1{\global\pkt{#1}}
\def\zusatzpunkte#1{\global\zpkttrue\global\globalzpkttrue\global\zpkt{#1}}
\def\erwpunkte#1{\global\erwpkttrue\global\globalerwpkttrue\global\erwpkt{#1}}
\zpktfalse
\erwpktfalse
\globalzpktfalse
\globalerwpktfalse

\def\outerjoin
 {\mbox{$\,\,\raisebox{0.17ex}{$\scriptstyle\sqsupset$}
         \,\!\!\!\bowtie\!\!
        \raisebox{0.2ex}{$\scriptstyle\sqsubset$}\,\,$}}
\def\leftsemijoin{\mbox{\small$\,\,\rhd\!\!\!<\,\,$}}
\def\rightsemijoin{\mbox{\small$\,\,>\!\!\!\lhd\,\,\,$}}
\def\leftsemijoin{\mbox{\small$\,\,\rhd\!\!\!<\,\,$}}
\def\rightsemijoin{\mbox{\small$\,\,>\!\!\!\lhd\,\,\,$}}
\psset{nodesep=2pt, treesep=0.6cm, levelsep=1cm}

\thispagestyle{empty}
\vspace*{1.5cm}\begin{center}
\large\bf
  ILIAS-Beispielklausur  ``Einf"uhrung in Datenbanken'' \\
  Januar 2020 \\
  Basierend auf der Klausur von Wintersemester 2010/2011 \\
  Prof.\ Dr.\ Wolfgang May \\
  Gesch"atzte Bearbeitungszeit (auf Papier): 100 Minuten
\end{center}
\vskip1cm


\begin{german}
% \begin{center}\large
% %  \begin{tabular}{lc@{\underline{\hspace*{6cm}}}}
%   \begin{tabular}{ll}
%    \large Vorname: & \hbox to 6cm{\vorname} \\[0.5cm]
%    \large Nachname: & \hbox to 6cm{\name}\\[0.5cm]
%    \large Matrikelnummer: &\hbox to 6cm{\matrikel}\\[0.5cm]
%    \large Studiengang: &\hbox to 6cm{}\\
%   \end{tabular}
% \end{center}
\end{german}
\begin{english}
\begin{center}\large
%  \begin{tabular}{lc@{\underline{\hspace*{6cm}}}}
  \begin{tabular}{ll}
   \large Given Name: & \hbox to 6cm{\vorname} \\[0.5cm]
   \large Family Name: & \hbox to 6cm{\name}\\[0.5cm]
   \large Matrikel No.: &\hbox to 6cm{\matrikel}\\[0.5cm]
   \large Studies: &\hbox to 6cm{}\\
  \end{tabular}
\end{center}
\end{english}
\vskip1cm


% \begin{german}
%   Bei der Klausur sind \textbf{keine Hilfsmittel} (Skripten,
%   Taschenrechner, etc.) erlaubt.  Handies m"ussen ausgeschaltet sein.
%   Papier wird gestellt.  Benutzen Sie nur die \textbf{ausgeteilten},
%   zusammengehefteten \textbf{Bl"atter} f"ur Ihre Antworten.  Schreiben
%   Sie mit blauem/schwarzem Kugelschreiber, F"uller, etc.; Bleistift
%   ist nicht erlaubt.
% \end{german}
% \begin{english}
%   For this exam, no auxiliary materials (text, books, pocket
%   calculator etc.) are allowed. Mobile phones must be turned off.
%   Paper will be provided. Please use only the stapled, distributed
%   sheets for your answers. Write with blue/black pen, ball pen,
%   etc.; pencils are not allowed.
% \end{english}
% \vskip0.7cm


% \begin{german}
%   Auf dem letzten Blatt finden Sie eine Datenbasis, die in den
%   Aufgaben~1 und~2 verwendet wird. Trennen Sie es ggf.\ zur
%   Bearbeitung der Aufgaben ab.
% \end{german}
% \begin{english}
%   On the very last sheet, you find a database that is used in
%   Exercises~1 and ~2. You are encouraged to detach it.
% \end{english}
% \vskip0.5cm

% \begin{german}
% Zum \textbf{Bestehen} der Klausur sind \textbf{45} Punkte hinreichend.
% \end{german}
% \begin{english}
% For \textbf{passing} the exam, \textbf{45} points are sufficient.
% \end{english}
% \vskip0.7cm

% \begin{german}
% \begin{tabular}{lp{12cm}}
%  \fbox{\phantom{X}} & meine Note soll mit Matrikelnummer so bald wie
%    m"oglich auf der Vorlesungs-Webseite ver"offentlicht werden. \\
%  \fbox{\phantom{X}} & meine Note soll nicht ver"offentlicht werden;
%    ich erfahre sie dann aus FlexNever oder beim zust"andigen Pr"ufungsamt.
% \end{tabular}
% \end{german}
% \begin{english}
% \begin{tabular}{lp{12cm}}
%  \fbox{\phantom{X}} & my grade should be published as soon as possible
%    (using the matrikel number) on the lecture's Web Page.\\
%  \fbox{\phantom{X}} & my grade should not be published. Information
%    is then via Munopag/Wopag/FlexNever or via the responsible
%    exam office.
%  \end{tabular}
% \end{english}
\vskip0.7cm

Hinweise: \\
\begin{itemize}
\item Bearbeiten Sie zuerst Aufgabe 1 (ER-Diagramm), dann \emph{entweder}
  Aufgabe~2 (Tabellen in Textmode) oder Aufgabe~3 (Tabellen
  grafisch z.B. mit draw.io).
\item F"ur Ausdr"ucke der relationalen Algebra sind in dieser
  Probeklausur die einfachen Aufgaben im Textmodus angelegt (schreiben
  Sie einfach Klammerausdr"ucke mit ``pi'', ``sigma'', ``rho'',
  ``join'' f"ur die Operatoren), die komplexeren als pdf-upload
  (B"aume mit draw.io, oder sonstwas).
\end{itemize}

\begin{center}
\theoremlisttype{punktliste}
\listtheorems{Aufgabe}
\end{center}

\vskip1cm

\textbf{Note:}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% for output in headlines of exercises
%%note that these lines must stand *after* the table on the cover sheet!

\def\zusatzpunkte#1{+#1}
\def\punkte#1{ \ [#1 Punkte]}

\newpage
% besser stattdessen nextone, dann mit header
%\nextone

\subsection*{Themenstellung: Wohnungsgenossenschaft}

%  {
%  \makeatletter
%  \def\@listI{\leftmargin\leftmargini
%     \topsep0.2cm \parsep0.1cm \itemsep0.15cm}
%  \let\@listi\@listI
%  \def\@listii {\leftmargin\leftmarginii
%                \labelwidth\leftmarginii
%                \advance\labelwidth-\labelsep
%                \topsep0cm\itemsep0.05cm\parsep0.05cm}
%  \makeatother
%  }

Alle Klausuraufgaben basieren auf einem gemeinsamen ``Auftrag'': In
der Klausur soll eine Datenbank einer Wohnungsgenossenschaft, die
Mietwohnungen in Mehrfamilienh"ausern in verschiedenen St"adten in
ganz Deutschland besitzt, entworfen werden:
\thispagestyle{empty}\vskip-0.2cm

\begin{enumerate}
\item Es wird angenommen, dass St"adte durch ihren Namen eindeutig
  identifiziert sind.

\item Zu den einzelnen im Besitz der Genossenschaft befindlichen
  H"ausern sind Adresse (Strasse mit Hausnummer) und Stadt
  abgelegt. Ausserdem ist gespeichert, wieviele Wohnungen in dem Haus
  sind.

  \begin{enumerate}
  \item Das Geb"aude \emph{Hauptstrasse 100} in \emph{G"ottingen}
    besteht aus 50 Wohnungen.
  \item Das Geb"aude \emph{Rheinstrasse 53} in \emph{K"oln} besteht
    aus 83 Wohnungen.
  \end{enumerate}
  
\item Jede Wohnung hat eine Nummer innerhalb des Hauses.  Zu jeder
  Wohnung sind die Anzahl der Zimmer, die Quadratmeter und die monatliche
  (Kalt)Miete gespeichert.

  \begin{enumerate}
  \item Die Wohnung mit der Nummer \rnode{w42-1}{42} des Hauses
    \emph{Hauptstrasse 100} in \emph{G"ottingen} ist eine
    3-Zimmer-Wohnung mit 80qm f"ur 500 Euro im Monat.

  \item Die Wohnung mit der Nummer \rnode{w43-1}{43} desselben Hauses ist eine
    2-Zimmer-Wohnung mit 50qm f"ur 320 Euro im Monat.

  \item Die Wohnung mit der Nummer \rnode{rhein1}{17} des Hauses
    \emph{Rheinstrasse 53} in \emph{K"oln} ist ein 1-Zimmer-Apartment
    mit 36qm und kostet 400 Euro im Monat.
  \end{enumerate}

\item F"ur jeden Mietvertrag ist gespeichert, wer welche
  Wohnung (und seit wann) gemietet hat (es wird angenommen,
  dass immer auf eine einzige Person als Mieter auftritt, d.h.\ den
  Mietvertrag unterschrieben hat). Ausserdem ist abgelegt, ob und zu
  welchem Zeitpunkt das Mietverh"altnis gek"undigt ist.

  \begin{enumerate}
  \item \emph{Karl Napf} wohnt seit 1.4.2008 in der
    Wohnung Nummer \rnode{w42-2}{42} des Hauses
    \emph{Hauptstrasse 100} in \emph{G"ottingen}.  Das Mietverh"altnis
    ist nicht gek"undigt.\ncline{<-}{w42-1}{w42-2}

  \item \rnode{hdampf1}{\emph{Hans Dampf}} wohnt seit 1.8.2001 in der
    Wohnung Nummer \rnode{w43-2}{43} des Hauses \emph{Hauptstrasse
      100} in \emph{G"ottingen}. Er hat die Wohnung zum 30.4.2011
    gek"undigt.\ncline{<-}{w43-1}{w43-2}

  \item \emph{Lieschen M"uller} wohnt seit 1.3.1980 in der Wohnung
    \rnode{rhein2}{Wohnung Nr. 17} des Hauses \emph{Rheinstrasse 53}
    in K"oln.  Sie hat die Wohnung zum 28.2.2011
    gek"undigt.\ncline{<-}{rhein1}{rhein2}
  \end{enumerate}

\item Wenn ein neuer Mietvertrag abgeschlossen wird, wird dabei auch
  die (zu dem Zeitpunkt noch aktuelle) Adresse des Mieters sowie der
  Beginn des Mietverh"altnisses gespeichert.

  \begin{enumerate}
  \item \emph{Nils Pferd}, der zur Zeit in \emph{Im Stall 4,
      Hintertupfing} wohnt (die Wohnung geh"ort nicht der
    Wohnungsgenossenschaft), hat einen Mietvertrag f"ur die Wohnung
    Nummer \rnode{w43-3}{43} im Haus \emph{Hauptstrasse 100} in
    \emph{G"ottingen} ab 1.5.2011
    abgeschlossen.\ncline{<-}{w43-1}{w43-3}

  \item Der oben genannte \emph{\rnode{hdampf3}{Hans}
        Dampf}\ncline{<-}{hdampf1}{hdampf3}\/ hat einen am 1.4.2011
    beginnenden Mietvertrag f"ur die Wohnung \rnode{rhein3}{Nr. 17} im
    Haus \emph{Rheinstrasse 53} in \emph{K"oln}
    abgeschlossen.\ncline{<-}{rhein1}{rhein3}
  \end{enumerate}
\enlargethispage{1cm}
\item Wenn ein Mieter auszieht wird die neue Adresse gespeichert
  (z.B.\ f"ur die Neben\-kosten\-abrechnung des Auszugsjahres).

   \begin{enumerate}
   \item Die neue Adresse von \emph{Lieschen M"uller} ist
     \emph{M"uhlengasse 24, M"uhlhausen} in einem Haus, das nicht der
     Wohnungsgenossenschaft geh"ort.
   \end{enumerate}

\item Daten "uber alte Mietvertr"age werden nicht gel"oscht.   
\end{enumerate}

\newpage %% ER-Aufgabe auf der rechten Seite neben der Aufgabenstellung

\begin{Aufgabe}[ER-Modell\punkte{20}]

  Entwickeln Sie ein ER-Modell f"ur das Szenario.  Geben Sie darin
  die Schl"usselattribute sowie die Beziehungskardinalit"aten an.

  [File Upload: pdf oder sowas, empfohlen: draw.io]

\begin{loesung}
\begin{center}
\begin{tabular}{c@{\hspace*{1cm}}c@{\hspace*{1cm}}c}
  \entity{Stadt} \\[2.5cm]
  \entity[weak]{Gebaeude}[Haus=Adresse] & 
      ~~~~\relationship{AdrVorher} & \entity{Person} \\[1cm]
  & \relationship{AdrNachher}~~ \\[1cm]
  \entity[weak]{Wohnung} & & \entity[weak]{Mietvertrag} \\[0.6cm]~
\end{tabular}

\relationshipbetween[ident]{Wohnung}[\tiny$<1,1>$]{Gebaeude}[\tiny$<0,*>$]{in}
\relationshipbetween[ident]{Gebaeude}[\tiny$<1,1>$]{Stadt}[\tiny$<0,*>$]{in}
\relationshipbetween[ident]{Mietvertrag}[\tiny$<1,1>$]{Wohnung}[\tiny$<0,*>$]{fuer}
\relationshipbetween{Mietvertrag}[\tiny$<1,1>$]{Person}[\tiny$<0,*>$]{hat}
\inrelationship{Gebaeude}[\tiny$<0,*>$]{AdrVorher}
\ncline{Mietvertrag}{AdrVorher}\ncput*[npos=0.25]{\tiny$<1,1>$}
\inrelationship{Gebaeude}[\tiny$<0,*>$]{AdrNachher}
\inrelationship{Mietvertrag}[\tiny$<0,1>$]{AdrNachher}
\attributeof{Stadt}[1cm]{0}[key]{Name}
\attributeof{Gebaeude}[1.5cm]{150}[key]{Strasse}
\attributeof{Gebaeude}[2cm]{-180}[key]{Hausnr}
\attributeof{Gebaeude}[1.5cm]{-150}{Anz.Whgn.}
\attributeof{Wohnung}[1.5cm]{-180}[key]{Nr}
\attributeof{Wohnung}[0.8cm]{-120}{Miete}
\attributeof{Wohnung}[0.8cm]{-60}{Zimmer}
\attributeof{Person}[1.6cm]{0}[key]{name}
\attributeof{Mietvertrag}[1.3cm]{0}[key]{von}\
\attributeof{Mietvertrag}[1cm]{-45}{bis}
\end{center}

Hinweise:
\begin{itemize}
\item \emph{Stadt} bzw.\ \emph{Person} nur als Attribute zu
  \emph{Haus} und \emph{Mietvertrag} geht auch. 
\item \emph{Von} ist Schl"usselattribut von \emph{Mietvertrag}, um den
  Fall dass eine Person zweimal zu unterschiedlichen Zeitr"aumen in
  einer Wohnung wohnt, abbilden zu k"onnen (-1/2P). \\
  Damit mu"s die \emph{hat}-Beziehung nicht notwendigerweise als
  identifizierend ausgezeichnet werden, d.h. Wohnung +
  \emph{von}-Datum reicht als Schl"ussel aus.
  (Person und \emph{von}-Datum w"urden nur ausreichen, wenn man
  annimmt, dass eine Person nicht gleichzeitig zwei Mietvertr"age
  beginnt).
\item \emph{AdrVorher} und \emph{AdrNachher} k"onnen auch als
  Attribute zu \emph{Mietvertrag} gemacht werden (man verliert
  aber die in Aufgabe (3e) wertvolle Assoziation, dass dies 
  ja ggf.\ auf ein Haus der Genossenschaft verweisen kann).
  Sinnvoll ist auch dann eine Aufteilung in \emph{Stadt} und 
  \emph{Adresse}.
\item Anstatt der expliziten Verwendung des Entit"atstyps
  \emph{Mietvertrag} k"onnte man einfach eine Beziehung
  \emph{mietet(e)} zwischen \emph{Person} und \emph{Wohnung} mit den
  Attributen \emph{von} und \emph{bis} verwenden. \\
  Dieses w"urde das Konzept des Mietvertrages abdecken, es w"are aber
  dann nicht m"oglich, damit die vorher/nachher-Adressen zu verbinden
  (diese sind dann also nur Attribute zu \emph{mietet(e)}).
\item \emph{Ganz schlecht} ist es, \emph{AdrVorher} und
  \emph{AdrNachher} mit \emph{Person} zu assoziieren, da man so keinen
  (zeitlichen) Zusammenhang mit den einzelnen m"oglicherweise
  aufeinanderfolgenden Mietvertr"agen speichern kann.
\end{itemize}
\end{loesung}
\end{Aufgabe}

\begin{Aufgabe}[Transformation in das Rel.\ Modell (Textmode) \punkte{9}]

%  Geben Sie an, welche Tabellen (mit Attributen, Schl"usseln etc.)
%  Ihre Datenbank enth"alt (keine SQL \texttt{CREATE TABLE}-Statements,
%  sondern einfach grafisch).
%
%  Markieren Sie dabei auch Schl"ussel (durch
%  \underline{unterstreichen}) und Fremdschl"ussel (durch
%  $\overline{\mbox{"uberstreichen}}$).
%
%  Geben Sie die Tabellen mit jeweils mindestens zwei Beispieltupeln
%  (z.B.\ denen, die sich aus dem Aufgabentext ergeben, und weiteren
%  erfundenen) an.

  \textbf{Bearbeiten eine der Aufgaben: Textmode (diese) oder grafisch
    (die n"achste)}

  Geben Sie an, welche Tabellen (mit Attributen, Schl"usseln etc.)
  Ihre Datenbank enth"alt (keine SQL \texttt{CREATE TABLE}-Statements,
  sondern entsprechend ``ASCII-Art'' Pseudocode: (Empfehlung:
  editieren Sie es in einem lokalen File und mausen es am Ende ins
  Ilias, dann k"onnen Sie Ihr lokales File zur Bearbeitung der
  SQL-Aufgaben auch sehen).

  Geben Sie die Tabellen mit jeweils mindestens zwei Beispieltupeln
  (z.B.\ denen, die sich aus dem Aufgabentext ergeben, und weiteren
  erfundenen) an.

\begin{itemize}
\item Tabellenschemata:
\begin{verbatim}
  tabname(_attr1_,_attr2_,attr3,attr4)  
  ------------------------------------
           bsp11  bsp12   bsp13  bsp14  
           bsp21  bsp22   bsp23  bsp24  

  oder analog
  relname(attr1,attr2,attr3,attr4)  PK: (attr1,attr2)
\end{verbatim}
\item Angabe von Fremdschl"usselreferenzen: 
\begin{verbatim}
  rel1(A,B) -> rel2(X,Y) 
  bzw. bei einelementigen Fremdschluesseln einfach
  rel1.A -> rel2.B
\end{verbatim}
\end{itemize}

\begin{loesung}
\def\fkey#1{$\overline{\mbox{#1}}$}%

\begin{itemize}
\item Tabellen f"ur die Entit"atstypen ``Stadt'' und ``Person'' werden
  nicht unbedingt ben"otigt, da sie nur eine Spalte ``Name'' enthalten
  w"urden.
\end{itemize}

\begin{tabular}[t]{|l|l|l|}\hline
\multicolumn{3}{|c|}{\bf Haus}\\\hline\hline
  \underline{Adresse} & \underline{Stadt} & AnzWohnungen \\\hline
  Hauptstrasse 100 & G"ottingen & 50 \\
  Rheinstrasse 53  & K"oln      & 83 \\
   :               &  :         &  : \\\hline
\end{tabular}

(Strasse + Hausnummer in getrennten Spalten ist auch OK)

\begin{tabular}[t]{|l|l|l|l|l|l|}\hline
\multicolumn{6}{|c|}{\bf Wohnung}\\\hline\hline
  \fkey{\underline{Adresse}} & \fkey{\underline{Stadt}} 
       & \underline{WhgNr}
       & Zimmer & Fl"ache & Preis \\\hline
  Hauptstrasse 100 & G"ottingen & 42 & 3 & 80 & 500 \\
  Hauptstrasse 100 & G"ottingen & 43 & 2 & 50 & 320 \\
   :               &  :         &  : & : & :  &  :  \\
  Rheinstrasse 53  & K"oln      & 17 & 1 & 36 & 400 \\
   :               &  :         &  : & : & :  &  :  \\\hline
\end{tabular}
\medskip

\begin{tabular}[t]{|@{}l@{}|@{}l@{}|l|@{}l@{}|@{}l@{}|@{}l@{}|@{}l@{}|@{}l@{}|@{}l@{}|@{}l@{}|}\hline
\multicolumn{10}{|c|}{\bf Mietvertrag}\\\hline\hline
  \fkey{\underline{Adresse}} & \fkey{\underline{Stadt}} 
       & \fkey{\underline{WhgNr}} & \underline{von} 
       & Person & Adr.Alt & StadtAlt & bis & Adr.Neu & StadtNeu \\\hline
  Hauptstr.100 & G"ottingen & 42 & 1.4.2008 & Karl Napf 
       & null & null & null & null & null\\
  Hauptstr.100 & G"ottingen & 43 & 1.8.2001 & Hans Dampf 
       & null & null & 30.4.2011 & Rheinstr.53 & K"oln\\
  Rheinstr.53  & K"oln      & 17 & 1.3.1980 & L.M"uller  
       & null & null & 28.2.2011 & M"uhleng.24 & M"uhlh.\\
  Rheinstr.53  & K"oln      & 17 & 1.4.2011 & Hans Dampf
       & Hauptstr.100 & G"ottingen & null & null & null\\
  Hauptstr.100 & G"ottingen & 43 & 1.5.2011 & Nils Pferd
       & Im Stall 4 & H'tupfing  & null & null & null\\
       :&:&:&:&:&:&:&:&:&: \\\hline
\end{tabular}
\medskip

\begin{itemize}
\item Man kann auch aufteilen:\\
  \emph{PersonEinzug: \underline{Name,Adresse,Stadt}, \underline{Datum}, 
     StadtAlt, AdresseAlt} \\
  \emph{PersonAuszug: \underline{Name,Adresse,Stadt}, \underline{Datum}, 
     StadtNeu, AdresseNeu} \\
  Wichtig ist, dass Name und Datum dabei sind, wenn jemand nacheinander
  mehrere Wohnungen mietet (oder auch dieselbe einige Zeit sp"ater nochmal).
\item \emph{StadtAlt, AdresseAlt} und \emph{StadtNeu, AdresseNeu}
  sind keine Foreign Keys auf \emph{Haus(StadtAdresse)}, da sie nur dann
  Referenzen sind, wenn die betreffenden H"auser auch im Besitz der
  Genossenschaft sind.
\end{itemize}
\end{loesung}
\end{Aufgabe}

\begin{Aufgabe}[Transformation in das Rel.\ Modell (grafisch) \punkte{9}]

%  Geben Sie an, welche Tabellen (mit Attributen, Schl"usseln etc.)
%  Ihre Datenbank enth"alt (keine SQL \texttt{CREATE TABLE}-Statements,
%  sondern einfach grafisch).
%
%  Markieren Sie dabei auch Schl"ussel (durch
%  \underline{unterstreichen}) und Fremdschl"ussel (durch
%  $\overline{\mbox{"uberstreichen}}$).
%
%  Geben Sie die Tabellen mit jeweils mindestens zwei Beispieltupeln
%  (z.B.\ denen, die sich aus dem Aufgabentext ergeben, und weiteren
%  erfundenen) an.

  \textbf{Bearbeiten eine der Aufgaben: grafisch (diese) oder Textmode
    (die vorhergehende)}

  Geben Sie an, welche Tabellen (mit Attributen, Schl"usseln etc.)
  Ihre Datenbank enth"alt (keine SQL \texttt{CREATE TABLE}-Statements,
  sondern einfach grafisch.
  
  Markieren Sie dabei auch Schl"ussel (durch
  \underline{unterstreichen} -- das ist in draw.io ganz einfach) und
  Fremdschl"usselreferenzen (durch $\overline{\mbox{"uberstreichen}}$
  (frei malen)) oder durch Angabe von Fremdschl"usselreferenzen:
\begin{verbatim}
  rel1(A,B) -> rel2(X,Y) 
  bzw. bei einelementigen Fremdschluesseln einfach
  rel1.A -> rel2.B
\end{verbatim}
\end{Aufgabe}

\begin{Aufgabe}[Relationales Modell CREATE TABLE\punkte{7}]

  Geben Sie das \texttt{CREATE TABLE}-Statement f"ur diejenige Tabelle
  (bzw.\ die Tabellen), in der bei Ihnen die Daten "uber die Wohnungen
  abgespeichert sind, so vollst"andig wie m"oglich an.

\begin{loesung}
\begin{verbatim}                                         
  CREATE TABLE wohnung                                   Basis 4P
  ( adresse VARCHAR2(30),                 
    stadt   VARCHAR2(30),                 
    whgnr   NUMBER CHECK (whgnr > 0),                     
    zimmer  NUMBER NOT NULL CHECK (zimmer > 0),          1/2 Checks
    flaeche NUMBER NOT NULL CHECK (flaeche > 0),         1/2 NOT NULL
    preis   NUMBER NOT NULL CHECK (preis > 0),  
  CONSTRAINT whgkey PRIMARY KEY (adresse, stadt, whgnr),  1P PKEY
  CONSTRAINT whghaus FOREIGN KEY (adresse, stadt) 
                     REFERENCES haus(adresse,stadt) )     1P FKEY
\end{verbatim}
\end{loesung}
\end{Aufgabe}

\begin{Aufgabe}[SQL und Relationale Algebra (a1) \punkte{2}]
%           2+2 + 3+3+3 + 3 + 4 + 3+3 + 4 + 6
% erwartet: 3.5 + 2+2+1 + 2 + 2 + 1+1 + 3 + 2

  Verwenden Sie f"ur diese und die folgenden Aufgaben die von Ihnen
  entworfene relationale Datenbasis. Keine der Antworten soll
  Duplikate enthalten.  \medskip
    
  Geben Sie \textbf{eine SQL-Anfrage} an, die die Namen aller St"adte
  ausgibt, in denen die Genossenschaft mindestens eine
  4-Zimmer-Wohnung besitzt.
\begin{loesung}
  \begin{minipage}{0.5\linewidth}
   \begin{verbatim}
    select distinct stadt
    from wohnung
    where zimmer = 4;
   \end{verbatim}
  \end{minipage}
\end{loesung}
\end{Aufgabe}

\begin{Aufgabe}[SQL und Relationale Algebra (a2) \punkte{2}]
  Geben Sie \textbf{einen Algebra-Ausdruck} an, der die Namen aller
  St"adte ausgibt, in denen die Genossenschaft mindestens eine
  4-Zimmer-Wohnung besitzt.
\begin{loesung}
  \begin{minipage}{0.5\linewidth}
   \[ \psset{nodesep=2pt, treesep=0.6cm, levelsep=1cm}
      % 
      \pstree{\Tr{\pi[\mbox{stadt}]}}
         {\pstree{\Tr{\sigma[\mbox{zimmer=4}]}}
             {\Tr{\mbox{wohnung}}}}
   \]
 \end{minipage}
\end{loesung}
\end{Aufgabe}

% \begin{Aufgabe}[SQL und Relationale Algebra (b) \punkte{2}]

%   Geben Sie \textbf{einen Algebra-Ausdruck} an,
%   die die Namen aller St"adte ausgeben, in denen die Genossenschaft
%   mindestens eine 4-Zimmer-Wohnung besitzt
% \begin{loesung}
%   \begin{minipage}{0.5\linewidth}
%    \begin{verbatim}
%     select distinct stadt
%     from wohnung
%     where zimmer = 4;
%    \end{verbatim}
%   \end{minipage}
%   \begin{minipage}{0.5\linewidth}
%    \[ \psset{nodesep=2pt, treesep=0.6cm, levelsep=1cm}
%       % 
%       \pstree{\Tr{\pi[\mbox{stadt}]}}
%          {\pstree{\Tr{\sigma[\mbox{zimmer=4}]}}
%              {\Tr{\mbox{wohnung}}}}
%    \]
%  \end{minipage}
% \end{loesung}
% \end{Aufgabe}

\begin{Aufgabe}[SQL und Relationale Algebra (b1) \punkte{3}]

  Geben Sie \textbf{eine SQL-Anfrage} an, die die Namen aller Personen
  ausgibt, die gegenw"artig eine 4-Zimmer-Wohnung mit mindestens 100qm
  f"ur weniger als 600E gemietet haben.
\begin{loesung}
 \begin{verbatim}
  select distinct person
    -- distinct (-1/2P) ist wichtig, sonst sind alle Personen, die
    -- gerade umziehen, mehrfach dabei
  from mietvertrag mv, wohnung w
  where mv.adresse = w.adresse 
    and mv.stadt = w.stadt
    and mv.whgnr = w.whgnr 
    and w.zimmer = 4 and w.preis < 600 and w.flaeche >= 100
    and mv.von <= sysdate and not bis < sysdate;

  (beachten: bei gegenwaertigen Vertraegen ist "bis" NULL oder > dem
    aktuellen Datum, und "von" < dem aktuellen Datum (vgl.
    Vertrag mit Nils Pferd, der schon gespeichert ist, aber erst
    am 1.5. beginnt)    (-1/2 P wenn falsch)

  select distinct person  
  from mietvertrag
  where (adresse,stadt,whgnr) in 
               (select adresse, stadt, whgnr
                from wohnung
                where zimmer = 4 and preis < 600 and flaeche >= 100) 
    and von <= sysdate and not bis < sysdate;
    (oder "9.2.2011" direkt einsetzen)
  -- geht auch ganz aehnlich mit  ... where exists (... SFW ...)
 \end{verbatim}
 \end{loesung}
\end{Aufgabe}

\begin{Aufgabe}[SQL und Relationale Algebra (b2) \punkte{3}]

  Geben Sie \textbf{einen Algebra-Ausdruck} an, der die Namen
  aller Personen ausgibt, die gegenw"artig eine 4-Zimmer-Wohnung mit
  mindestens 100qm f"ur weniger als 600E gemietet haben.
\begin{loesung}
 Der Algebra-Ausdruck entspricht der ersten L"osung der vorhergehenden Aufgabe:
   \[ \psset{nodesep=2pt, treesep=0.6cm, levelsep=1cm}
      % 
      \pstree{\Tr{\pi[\mbox{person}]}}
         {\pstree{\Tr{\bowtie}}
           {\pstree{\Tr{\sigma[\mbox{zimmer=4 $\land$ preis $<$ 600 $\land$ flaeche $\ge$100}]}}
             {\Tr{\mbox{wohnung}}}
            \pstree{\Tr{\sigma[\mbox{von $\le$ sysdate $\land$ $\neg$ bis $<$ sysdate}]}}
             {\Tr{\mbox{mietvertrag}}}}}
   \]
 \end{loesung}
\end{Aufgabe}

% \begin{Aufgabe}[SQL und Relationale Algebra (b3) \punkte{3}]
%  Geben Sie auch einen soweit wie m"oglich
%   (auf algebraischer Ebene) optimierten Algebra-Ausdruck f"ur (b1) an.
% \begin{loesung}
%    Optimiert: 
%    \[ \psset{nodesep=2pt, treesep=0.6cm, levelsep=1cm}
%       \pstree{\Tr{\pi[\mbox{person}]}}
%          {\pstree{\Tr{\rightsemijoin}}
%            {\pstree{\Tr{\pi[\mbox{adresse,stadt,whgnr}]}}
%              {\pstree{\Tr{\sigma[\mbox{zimmer=4 $\land$ preis $<$ 600 $\land$ flaeche $\ge$100}]}}
%                {\Tr{\mbox{wohnung}}}}
%             \pstree{\Tr{\pi[\mbox{adresse,stadt,whgnr,person}]}}
%              {\pstree{\Tr{\sigma[\mbox{von $\le$ sysdate $\land$  $\neg$ bis $<$ sysdate}]}}
%                {\Tr{\mbox{mietvertrag}}}}}}
%    \]
%  \end{loesung}

% \item[b)] Ein Mietinteressent will ab 1.5.2011 (oder auch schon
%   fr"uher) eine 4-Zimmer-Wohnung in Frankfurt f"ur h"ochstens 500E
%   Kaltmiete mieten.

%   Geben Sie \textbf{eine SQL-Anfrage und einen Algebra-Ausdruck} an,
%   der die Adressen aller in Frage kommenden Wohnungen angibt.

% \begin{loesung}
%  \begin{verbatim}
%   SELECT adresse
%   FROM wohnung
%   WHERE stadt = 'Frankfurt'
%     AND zimmer = 4 and preis <= 500 
%     AND NOT (Adresse, Stadt, WhgNr) IN
%         (SELECT Adresse, Stadt, WhgNr
%          FROM mietvertrag
%          WHERE bis IS NULL or bis > '31.4.2011');
% \end{verbatim}
% \end{loesung}
%\end{Aufgabe}


\begin{Aufgabe}[SQL und Relationale Algebra (c) \punkte{2}]
  Geben Sie \textbf{eine SQL-Anfrage} an, die f"ur jede Stadt ausgibt,
  wieviel Miete die Genossenschaft insgesamt monatlich in dieser Stadt
  bekommen kann.
\begin{loesung}
 \begin{verbatim}
  select stadt, sum(miete)
  from wohnung
  group by stadt;
 \end{verbatim}
\end{loesung}  
\end{Aufgabe}

\begin{Aufgabe}[SQL und Relationale Algebra (d1) \punkte{3}]
  Geben Sie \textbf{eine SQL-Anfrage} an, die die Namen aller Personen
  ausgibt, die irgendwann in einer der Wohnungen der
  Wohnungsgenossenschaft gewohnt haben, und die aber nie in K"oln in
  einer Wohnung der Wohnungsgenossenschaft gewohnt haben.

\begin{loesung}
 \begin{verbatim}
  (select person              select person
   from mietvertrag           from mietvertrag m1
   where von < sysdate)       where von < sysdate     
  minus                         and not exists
  (select person                 (select *
   from mietvertrag               from mietvertrag m2
   where Stadt = 'Koeln'          where von < sysdate     
     and von < sysdate)           and m1.person=m2.person
                                    and m2.stadt = 'Koeln')
 
                              -- analog auch mit
                              -- where person not in (...)

  -- das "von < sysdate" hatte fast niemand, gab ggf. +1/2 Punkt.
\end{verbatim}       
\end{loesung}
\end{Aufgabe}

\begin{Aufgabe}[SQL und Relationale Algebra (d2) \punkte{3}]
  Geben Sie \textbf{einen Algebra-Ausdruck oder -Baum} an, der die Namen aller
  Personen ausgibt, die irgendwann in einer der Wohnungen der
  Wohnungsgenossenschaft gewohnt haben, und die aber nie in K"oln in
  einer Wohnung der Wohnungsgenossenschaft gewohnt haben.

\begin{loesung}
   \[ \psset{nodesep=2pt, treesep=0.6cm, levelsep=1cm}
      \hspace*{-2cm}
      % 
      \begin{array}{c}
      \pstree{\Tr{\setminus}}
       {\pstree{\Tr{\pi[\mbox{Person}]}}
        {\pstree{\Tr{\sigma[\mbox{von $<$ sysdate}]}}
         {\Tr{\mbox{Mietvertrag}}}}
        \pstree{\Tr{\pi[\mbox{Person}]}}
        {\pstree{\Tr{\sigma[\mbox{Stadt='K\"oln'} \land \mbox{von $<$ sysdate}]}}
         {\Tr{\mbox{Mietvertrag}}}}}
     \end{array}\]
\end{loesung}
\end{Aufgabe}


% \item[e)] Geben Sie \textbf{eine SQL-Anfrage ODER einen
%     Algebra-Ausdruck} an, die alle Personen ausgeben, die irgendwann
%   gleichzeitig mit Karl Napf in einem Haus der Wohnungsgenossenschaft
%   gewohnt haben. (4~P)

% \begin{loesung}
%  \begin{verbatim}
%   select distinct m1.person
%   from mietvertrag m1, mietvertrag m2
%   where m2.person = "Karl Napf"
%     and m1.adresse = m2.adresse and m1.stadt = m2.stadt
%     and (   (m1.von <= m2.von and not m1.bis < m2.von)   
%               -- napf nach p2 eingezogen und gleichzeitig
%          or (m1.von >= m2.von and not m2.bis < m1.von)); 
%               -- napf vor p2 eingezogen und gleichzeitig.
%  \end{verbatim}
%    \[ \psset{nodesep=2pt, treesep=0.6cm, levelsep=1cm}
%       \hspace*{-2cm}
%       \pstree{\Tr{\pi[\mbox{person}]}}
%        {\pstree{\Tr{\bowtie[\mbox{adresse=a1 and stadt=s1 and
%                ((v1$<=$von and not b1$<$von) or 
%                 (v1$>=$von and not bis$<$v1)}]}}
%         {\pstree{\Tr{\rho[\mbox{adresse$\to$a1, stadt$\to$s1, von$\to$v1, bis$\to$b1}]}}
%          {\pstree{\Tr{\pi[\mbox{adresse,stadt,von,bis,person}]}}
%           {\Tr{\mbox{mietvertrag}}}}
%          \pstree{\Tr{\pi[\mbox{adresse,stadt,von,bis}]}}
%          {\pstree{\Tr{\sigma[\mbox{person='Karl Napf'}]}}
%           {\Tr{\mbox{mietvertrag}}}}}}
%   \]  
% \end{loesung}

% \begin{Aufgabe}[SQL und Relationale Algebra (f1) \punkte{4}]
%   Geben Sie \textbf{eine SQL-Anfrage} an, die die Namen aller Personen
%   ausgibt, die mindestens einmal nach dem Auszug aus einer der
%   Genossenschaft geh"orenden Wohnung direkt in eine andere, auch der
%   Genossenschaft geh"orende Wohnung gezogen sind.

% \begin{loesung}
% \begin{verbatim}
%   select distinct m.person
%   from mietvertrag m1, mietvertrag m2
%   where m.AdrNeu = m2.Adr
%     and m.StadtNeu = m2.Stadt
%     and m2.von < sysdate  -- oder m1.bis < sysdate;
%   -- den Test auf sysdate (Umzug schon geschehen) hatte niemand;
%   --  haette auch hier wieder +1/2P gegeben;
%   -- haus anstatt mietvertrag.m2 war daher auch OK.
% \end{verbatim}
% \end{loesung}
% \end{Aufgabe}

% \begin{Aufgabe}[SQL und Relationale Algebra (f2) \punkte{4}]
%   Geben Sie \textbf{einen Algebra-Ausdruck} an, der die Namen aller
%   Personen ausgibt, die mindestens einmal nach dem Auszug aus einer
%   der Genossenschaft geh"orenden Wohnung direkt in eine andere, auch
%   der Genossenschaft geh"orende Wohnung gezogen sind.

% \begin{loesung}
%    \[ \psset{nodesep=2pt, treesep=0.6cm, levelsep=1cm}
%       \hspace*{-2cm}
%       % 
%       \begin{array}{c}
%       \pstree{\Tr{\pi[\mbox{Person}]}}
%        {\pstree{\Tr{\rightsemijoin}}
%          {\pstree{\Tr{\sigma[\mbox{von $<$ sysdate}]}}
%             {\Tr{\mbox{Mietvertrag}}}
%           \pstree{\Tr{\rho[\mbox{AdrNeu$\to$Adresse,StadtNeu$\to$Stadt}]}}
%             {\pstree{\Tr{\pi[\mbox{Person,AdrNeu,StrasseNeu}]}}
%              {\Tr{\mbox{Mietvertrag}}}}}}
%      \end{array}\]
%    \end{loesung}
% \end{Aufgabe}

% \item[e)] Geben Sie \textbf{eine SQL-Anfrage ODER einen
%     Algebra-Ausdruck} an, die alle Personen ausgeben, die irgendwann
%   gleichzeitig mit Karl Napf in einem Haus der Wohnungsgenossenschaft
%   gewohnt haben. (4~P)

\begin{Aufgabe}[SQL und Relationale Algebra (e) \punkte{7}]
  Geben Sie eine Aufgabenstellung (Textaufgabe) an, deren L"osung eine
  relationale Division erfordert. (Wenn ihnen nichts sinnvolles
  einf"allt, k"onnen Sie dazu auch eine weiteres Attribut zu einer der
  Tabellen, bzw. eine neue Tabelle hinzuf"ugen).

  Geben Sie dazu eine SQL-Anfrage \textbf{oder} einen Algebra-Ausdruck an.

\begin{loesung}
  Ein einfaches Beispiel ist ``diejenigen Personen, die schon in allen
  St"adten eine Wohnung gemietet hatten, in denen Lieschen M"uller
  eine Wohnung gemietet hatte''.

 ~~~~  $\pi$[Person,Stadt](Mietvertrag) div 
       ($\pi$[stadt]($\sigma$[name='L.M.'](Mietvertrag)))

\begin{verbatim}
  select x.Person
  from (select distinct person from mietvertrag) x
  where not exists (select * 
                    from mietvertrag m
                    where name='Lieschen Mueller'
                      and not (x.Person, m.stadt) IN 
                           (select Person,stadt
                            from mietvertrag))
\end{verbatim}

  Oder: Der Entit"atstyp bzw.\ die Tabelle Stadt (die man bei dieser
  L"osung noch hinzuf"ugen muss) bekommt ein Attribut ``Population'',
  und man fragt dann an ``welche Personen hatten in jeder Stadt mit
  mehr als einer Million Einwohnern einen Mietvertrag bei dieser
  Wohnungsgenossenschaft'':

 ~~~~  $\pi$[Person,Stadt](Mietvertrag) div 
       $\rho$[name$\to$Stadt]($\pi$[name]($\sigma$[pop$>$1000000](Stadt)))
\begin{verbatim}
  select x.Person
  from (select distinct person from mietvertrag) x
  where not exists (select * 
                    from stadt 
                    where population > 1000000
                      and not (x.Person, stadt.name) IN 
                           (select Person,stadt
                            from mietvertrag))
\end{verbatim}
\end{loesung}
\end{Aufgabe}

\begin{Aufgabe}[SQL und Relationale Algebra (f) \punkte{6}]
  Gibt es eine M"oglichkeit, mit SQL aus der Datenbasis alle Personen
  herauszufinden, die seit ihrem erstmaligen Einzug ausschliesslich,
  ggf.\ aber beliebig oft, von einer der Genossenschaft geh"orenden
  Wohnung direkt in eine andere, auch der Genossenschaft geh"orende
  Wohnung gezogen sind?

   Falls ja, geben Sie eine solche Anfrage (SQL oder Algebra)
   an. Falls nein, begr"unden Sie Ihre Antwort.

\begin{loesung}
   Ja. Alle, die nie in eine nicht der Genossenschaft gehoerende Wohnung
   umgezogen sind (also einschliesslich derer, die bisher noch nie ausgezogen 
   sind).

  \begin{verbatim}
   SELECT DISTINCT person 
   FROM mietvertrag m1  -- um alle bekannten Personen zu betrachten
   WHERE m1.von < sysdate
   WHERE NOT EXISTS -- Mietvertrag dieser Person, aus der diese Person
                    -- in eine nicht der G. gehoerende Whg gezogen ist
    (SELECT * 
     FROM mietvertrag m2
     WHERE m1.Person = m2.Person
       AND m2.von < sysdate
       AND bis IS NOT NULL 
       AND -- Nachfolgewohnung gehoert nicht der Genossenschaft
           (AdrNeu, StadtNeu) NOT IN
             (SELECT Adresse, Stadt
              FROM Wohnung))

   (SELECT person 
    FROM mietvertrag
    WHERE m1.von < sysdate)
   MINUS
   (SELECT person
    FROM mietvertrag
    WHERE von < sysdate
      AND bis IS NOT NULL 
      AND -- Nachfolgewohnung gehoert nicht der Genossenschaft
          (AdrNeu, StadtNeu) NOT IN
            (SELECT Adresse, Stadt
             FROM Wohnung))
  \end{verbatim}
   \[ \psset{nodesep=2pt, treesep=0.6cm, levelsep=1cm}
      \hspace*{-2cm}
      % 
      \begin{array}{c}
      \pstree{\Tr{\setminus}}
       {\pstree{\Tr{\pi[\mbox{Person}]}}
        {\pstree{\Tr{\sigma[\mbox{von $<$ sysdate}]}}
         {\Tr{\mbox{Mietvertrag}}}}
        \pstree{\Tr{\pi[\mbox{Person}]}}
        {\pstree{\Tr{\bowtie}}
         {\pstree{\Tr{\setminus}}
          {\pstree{\Tr{\rho[\mbox{AdrNeu$\to$Adresse,StadtNeu$\to$Stadt}]}}
           {\pstree{\Tr{\pi[\mbox{AdresseNeu,StadtNeu}]}}
            {\pstree{\Tr{\sigma[\mbox{von $<$ sysdate}]}}
             {\Tr{\mbox{Mietvertrag}}}}
            \pstree{\Tr{\pi[\mbox{Adresse,Stadt}]}}
            {\Tr{\mbox{Wohnung}}}}}}}}
     \end{array}\]
\end{loesung}
\end{Aufgabe}

\begin{Aufgabe}[SQL und Relationale Algebra (f2-upload) \punkte{6}]
  Falls Sie zu der vorhergehenden Aufgabe (f) einen Algebra-Ausdruck
  oder -Baum als Grafik-pdf hochladen wollen, k"onnen Sie dies hier tun:

% \item[g)] 
%   \begin{itemize}
%   \item[1)] Welche Updates (SQL) m"ussen Sie an Ihrer Datenbank
%     vornehmen, wenn Karl Napf sein in der Aufgabenstellung Punkt (4a)
%     beschriebenes Mietverh"altnis zum 31.5.2011 k"undigt und als neue
%     Adresse \emph{Hafenstrasse 3} in \emph{Hamburg} angibt? (3~P)
%   \item[2)] Welche Updates (SQL) m"ussen Sie am 1.3. in Ihrer Datenbank
%     vornehmen, um das Ende des Mietvertrages von Lieschen M"uller 
%     (vgl. Aufgabenstellung Punkt (4c)) abzubilden? (2~P)
%   \end{itemize}
%   \begin{loesung}
%   \begin{itemize}
%   \item[1)]
%     \begin{verbatim}
%  UPDATE Mietvertrag
%  SET bis = '31.5.2011', StadtNeu = 'Hamburg', AdrNeu = 'Hafenstrasse 3'
%  WHERE Name = 'Karl Napf' 
%    AND Adresse = 'Hauptstrasse 100' AND Stadt = 'Goettingen'
%    AND bis IS NULL;
%     \end{verbatim}
%   \item[2)] In der gegebenen Musterl"osung keine. Wenn jemand in seiner
%     Modellierung zwischen laufenden und ehemaligen Mietvertr"agen 
%     unterscheidet, muss jedoch einiges gemacht werden (Fehlerquelle in
%     einer realen Anwendung).
%   \end{itemize}
%   \end{loesung}
\end{Aufgabe}

\begin{Aufgabe}[Abstrakt: SQL und Algebra \punkte{5}]
  Gegeben sind zwei Relationen
  $R(A,B,C,D)$ und $S(E,F,G,H)$.  Die Attribute $R.C$ und $S.G$ sind
  numerisch, alle anderen sind Strings.

   Geben Sie einen \textbf{Algebra-Ausdruck oder -Baum} an, der
   "aquivalent zu der folgenden SQL-Anfrage ist:

\begin{verbatim}
   SELECT A,C
   FROM R
   WHERE (A,B) IN (SELECT E,F
                   FROM S
                   WHERE G < C)
\end{verbatim}

  \begin{loesung}
   Alle Subqueries werden in Joins umgewandelt. Hier:
         
   \[ \psset{nodesep=2pt, treesep=0.6cm, levelsep=1cm}
      \hspace*{-2cm}
      % 
      \begin{array}{c}
       \pstree{\Tr{\pi[A,C]}}
        {\pstree{\Tr{\bowtie[A=E \land B=F \land C>G]}}
         {\Tr{\mbox{R}}
          \Tr{\mbox{S}}}}
     \end{array}
%
     \begin{array}{c}
       \pstree{\Tr{\pi[A,C]}}
        {\pstree{\Tr{\sigma[C>G]}}
         {\pstree{\Tr{\bowtie}}
          {\Tr{\mbox{R}}
           \pstree{\Tr{\rho[E\to A, F\to B]}}
           {\Tr{\mbox{S}}}}}}
     \end{array}\]
   \end{loesung}
\end{Aufgabe}

\begin{Aufgabe}[Theorie-Aufgabe \punkte{5}]

  Seien $R$ und $S$ zwei Relationen.

  Geben Sie an, ob, und ggf.\ unter welchen Bedingungen bzgl.\ $R$ und
  $S$ die beiden untenstehenden Ausdr"ucke der relationalen Algebra
  "aquivalent sind. \\
  Begr"unden Sie Ihre Aussage. \\
  Beschreiben Sie ggf.\ auch, bzw.\ geben Sie ein Gegenbeispiel an, wo
  die beiden Ausdr"ucke nicht "aquivalent sind.
  \begin{enumerate}
  \item $R \cup S$ 
  \item $R \outerjoin S$
  \end{enumerate}
  
  \begin{loesung}
  (1) ist erlaubt, wenn $R$ und $S$ dasselbe Format, d.h. dieselben Attribute haben.
     Unter diesen Bedingungen ist $R \bowtie S = R\cap S$ 
     und $R\setminus (R\leftsemijoin S) = R\setminus (R\cap S) = R\setminus S$
     (analog auch symmetrisch). \\
     
     Und $R\outerjoin S 
     = R \bowtie S \cup 
            ((R\setminus (R\leftsemijoin S)) \times \{\})
            \cup ((S\setminus (S\leftsemijoin R)) \times \{\}) = 
       R \cap S \cup (R\setminus S) \cup (S\setminus R) = R \cup S$, \\
    wobei $\{\}$ hier das null-spaltige Tupel mit Nullwerten f"ur die
    (nicht vorhandenen) Attribute in $R$ aber nicht in $S$ (und umgekehrt)
    beschreibt. 

  Wenn $R$ und $S$ nicht dasselbe Format haben, ist (1) nicht erlaubt, aber (2)
  durchaus und (2) ist ein sinnvoller Ausdruck, der dann eben nicht zu (1)
  "aquivalent ist.  
  \end{loesung}
\end{Aufgabe}


\begin{Aufgabe}[Algebra-Anfrageb"aume/Multiple-Choice \punkte{8}]

Diese Aufgabe benutzt das Mondial-Schema:
\begin{verbatim}
  country(name,code,capital,province,area,population)
      (code,capital,province) geben den Landescode+Stadtname+Provinz der Hauptstadt an
  organization(abbreviation,name,city,country,province,established)  
      (city,country,province) geben die Stadt an, in der die Organisation ihren Sitz hat
  city(name,country,province,population,latitude,longitude,elevation)
  ismember(country,organization,type)
\end{verbatim}
Welche der folgenden Algebra-B"aume beantworten die Anfrage ``die
Namen aller St"adte, die die Hauptstadt eines Landes sind, und in
denen eine Organisation ihren Sitz hat'' korrekt? \\
(es k"onnen mehrere B"aume richtig sein)
\begin{enumerate}

\item \begin{minipage}[t]{.45\textwidth}\sf
  %% 1: falsch: hqs minus caps
 \pstree{\Tr{$\pi$[city]}}
  {\pstree{\Tr{$\setminus$}}
    {\pstree{\Tr{$\pi$[city,province,country]}}
      {\Tr{organization}}
     \pstree{\Tr{$\rho$[capital$\to$city]}}
      {\pstree{\Tr{$\pi$[capital,province,country]}}
          {\pstree{\Tr{$\rho$[code$\to$country]}}
             {\Tr{country}}}}}}
  \end{minipage}

\item \begin{minipage}[t]{.45\textwidth}\sf
  %% 2: richtig: join, wobei city unnötig ist
 \pstree{\Tr{$\pi$[city]}}
  {\pstree{\Tr{$\bowtie$}}
    {\pstree{\Tr{$\pi$[abbrev,city,country,province]}}
       {\Tr{organization}}
     \pstree{\Tr{$\bowtie$}}
      {\pstree{\Tr{$\rho$[name$\to$city]}}
        {\pstree{\Tr{$\pi$[name,country,province]}}
             {\Tr{city}}}
       \pstree{\Tr{$\rho$[code$\to$country,capital$\to$city]}}
             {\Tr{country}}}}}
  \end{minipage}
\item \begin{minipage}[t]{.45\textwidth}\sf
  %% 3: falsch: join, wobei city unnoetig ist, aber es joint über org.name=country.name und city.pop=country.pop!
 \pstree{\Tr{$\pi$[city]}}
  {\pstree{\Tr{$\bowtie$}}
    {\Tr{organization}
     \pstree{\Tr{$\bowtie$}}
      {\pstree{\Tr{$\rho$[name$\to$city]}}
             {\Tr{city}}
       \pstree{\Tr{$\rho$[code$\to$country,capital$\to$city]}}
             {\Tr{country}}}}}
  \end{minipage}
\item \begin{minipage}[t]{.45\textwidth}\sf
  %% 4: falsch: join ueber org.country(hq)=ismember, was nicht erwartet wird. Hq darf in einem nichtmember sein, 
  %% country.name=org.name ist auch noch implizit dabei
 \pstree{\Tr{$\pi$[city]}}
  {\pstree{\Tr{$\bowtie$}}
    {\pstree{\Tr{$\bowtie$}}
      {\Tr{organization}
       \Tr{isMember}}
     \pstree{\Tr{$\rho$[code$\to$country,capital$\to$city]}}
            {\Tr{country}}}}
  \end{minipage}
\item \begin{minipage}[t]{.45\textwidth}\sf
 %% 5: richtig: hq <semi-rightjoin< caps
 \pstree{\Tr{$\pi$[city]}}
  {\pstree{\Tr{$\rightsemijoin$}}
    {\Tr{organization}
     \pstree{\Tr{$\rho$[capital$\to$city]}}
      {\pstree{\Tr{$\pi$[capital,province,country]}}
          {\pstree{\Tr{$\rho$[code$\to$country]}}
             {\Tr{country}}}}}}
  \end{minipage}
\item \begin{minipage}[t]{.45\textwidth}\sf
  %% 6: falsch union+count geht so nicht
 \pstree{\Tr{$\pi$[city]}}
 {\pstree{\Tr{$\sigma$[anzahl $>$ 2]}}
  {\pstree{\Tr{$\cup$}}
    {\pstree{\Tr{$\pi$[city,province,country]}}
      {\Tr{organization}}
     \pstree{\Tr{$\rho$[capital$\to$city]}}
      {\pstree{\Tr{$\pi$[capital,province,country]}}
          {\pstree{\Tr{$\rho$[code$\to$country]}}
             {\Tr{country}}}}}}}
  \end{minipage}

\item \begin{minipage}[t]{.45\textwidth}\sf
 %% 7: richtig: hq cap caps
 \pstree{\Tr{$\pi$[city]}}
  {\pstree{\Tr{$\cap$}}
    {\pstree{\Tr{$\pi$[city,province,country]}}
      {\Tr{organization}}
     \pstree{\Tr{$\rho$[capital$\to$city]}}
      {\pstree{\Tr{$\pi$[capital,province,country]}}
          {\pstree{\Tr{$\rho$[code$\to$country]}}
             {\Tr{country}}}}}}
  \end{minipage}
\item \begin{minipage}[t]{.45\textwidth}\sf
 %% 7: richtig: full outer join
 \pstree{\Tr{$\pi$[city]}}
  {\pstree{\Tr{$\sigma$[abbrev is not null $\land$ name is not null]}}
  {\pstree{\Tr{$\outerjoin$}}
    {\pstree{\Tr{$\pi$[abbrev,city,province,country]}}
      {\Tr{organization}}
     \pstree{\Tr{$\rho$[capital$\to$city]}}
      {\pstree{\Tr{$\pi$[name,capital,province,country]}}
          {\pstree{\Tr{$\rho$[code$\to$country]}}
             {\Tr{country}}}}}}}
  \end{minipage}
\end{enumerate}

\begin{loesung}
\begin{enumerate}
\item falsch: Das g"abe alle St"adte, in denen eine Organisation ihren
  Sitz hat, die aber keine Hauptstadt sind.
\item richtig: join, wobei die Tabelle city nicht wirklich ben"otigt wird
\item falsch: join ist OK; city ist unn"otig (aber nicht falsch), aber
  es joint "uber org.name=country.name und city.pop=country.pop!
\item falsch: joint "uber
  org.country(hq)=ismember.country=ismember.country=country.code($\to$country)
  , was nicht erwartet wird. Der Sitz darf in einem
  nicht-Mitgliedsland sein.  Und country.name=org.name ist auch noch
  implizit dabei, was es wirklich richtig falsch macht.
\item richtig: Die Hauptst"adte werden im rechten Baum berechnet, scharf
  auf die ben"otigten Attribute projiziert, passend renamed, und  
  per Semijoin geschaut, ob es Sitze von Organisationen sind. \\
  Man k"onnte das Semijoin auch umdrehen, h"atte dasselbe Ergebnis.
\item falsch union+count geht so in der Algebra nicht.  Sie hat kein
  group-by, ``anzahl'' w"urde als Spaltenname interpretiert (deutsch
  k"onnte sie sowieso nicht). Die Idee ist auch insofern falsch, dass
  wenn eine Nicht-Hauptstadt Sitz zweier Organisationen w"are, sie
  auch reink"ame. \\
  In  SQL w"are folgendes korrekt, aber "ubelster Code:
  \begin{verbatim}
  select DISTINCT city
  FROM
    ((select DISTINCT city, country, province
      from organization)
     UNION ALL
     (select capital as city, code as country, province
      from country)
  GROUP BY city, country, province
  HAVING count(*) >= 2
  -- UNION ALL: do not remove duplicates
  \end{verbatim}
\item richtig: Schnittmenge aus headquarters und capitals. \\
  Im Prinzip das, was die o.g. Semijoin-L"osung auch tut.
\item richtig: outer join, und alle Paare, die eine Organisation und ein Land 
  ``haben'', ergeben eine L"osung.
\end{enumerate}
\end{loesung}
\end{Aufgabe}


\begin{Aufgabe}[Schemaentwurf/Multiple-Choice \punkte{4}]
Gegeben seien Relationen
\begin{verbatim}
 R(_a1_, a2),   
 S(_b1_, b2),
 T(_c1_, c2), und
 X(a,b,c)   
\end{verbatim}
 $X$ ist offensichtlich eine dreistellige Beziehung. F"ur $X$ seien sowohl 
 $A$, als auch $B$, als auch $C$ (einzeln!) Schl"usselkandidaten. \\
 ("Uberlegen Sie sich, was man daraus schlie"sen kann) \\
 Es gelten die Fremdschl"usselbeziehungen \verb|X.a->R.a1, X.b->S.b1, X.c->T.c1|.

 Welche der Aussagen ist/sind zutreffend (offensichtliche sich aus den
 Namen ergebende Fremdschl"usselbedingungen jeweils nicht explizit
 angegeben):

 \begin{itemize}
 \item[\fbox{\phantom{X}}] Das angegebene Schema ist redundanzfrei (d.h.\ formal in 3.\ Normalform).
 \item[\fbox{\phantom{X}}] Das Schema \\
   \verb| R(_a1_, a2, b, c), S(_b1_, b2), T(_c1_, c2) | \\
  ist "aquivalent, redundanzfrei und verlustfrei. 
 \item[\fbox{\phantom{X}}] Das Schema
   \verb| R(_a1_, a2, b, c), S(_b1_, b2, a, c), T(_c1_, c2, a, b) | \\
  ist "aquivalent, redundanzfrei und verlustfrei.
 \item[\fbox{\phantom{X}}] Das Schema \\
   \verb| R(_a1_, a2), S(_b1_, b2), T(_c1_, c2), X(_a_,b), Y(_b_,c), Z(_c_,a) | \\
  ist "aquivalent, redundanzfrei und verlustfrei. 
 \item[\fbox{\phantom{X}}] Das Schema \\
   \verb| R(_a1_, a2), S(_b1_, b2), T(_c1_, c2), X(_a_,b), Z(_c_,a)| \\
  ist "aquivalent, redundanzfrei und verlustfrei.
 \item[\fbox{\phantom{X}}] Das Schema \\
   \verb| R(_a1_, a2, b), S(_b1_, b2, c), T(_c1_, c2, a, b)| \\
  ist "aquivalent, redundanzfrei und verlustfrei. 
\item[\fbox{\phantom{X}}] Es gibt kein anderes Schema, das "aquivalent zu dem gegebenen
  Schema, redundanzfrei und verlustfrei ist.
\item[\fbox{\phantom{X}}] Es gibt noch weitere Schemata, die "aquivalent zu dem gegebenen
  Schema, redundanzfrei und verlustfrei sind.
\end{itemize}

  \begin{loesung}
  Dass alle drei Attribute Schl"usselattribute sind, bedeutet, dass jedes $a$, $b$, $c$
  h"ochstens einer Kombination der beiden anderen Attribute zugeordnet wird (wobei dann beide
  ungleich \emph{null} sein m"ussen, da sie ja auch Schl"usselkandidaten sind).
  Es kann aber auch $a_1$, $b_1$ und $c_1$-Werte in $R$, $S$ bzw.\ $T$ geben, die 
  keine solche Zuordnung haben.  \\
  (Intutiv: man hat drei K"orbe, und kann jeweils a-b-c-Tripel ``rausnehmen'' und eint"uten.) 
  
    \begin{enumerate}
    \item Das Schema ist redundanzfrei: Eine Zerlegung in untergeordnete Zusammenh"ange w"are
      h"ochstens bei der Tabelle $X$ m"oglich. Da aber jede Spalte Schl"ussel ist, kann es
      keine Redundanzen geben.
    \item Ja. Da $a$ Schl"ussel in $X$ ist, kann man die Eintr"age f"ur $b$ und $c$ mit 
      nach $R$ reinziehen. 
    \item ist redundant (und damit Fehleintrags-anf"allig). Einmal
      reinziehen gen"ugt.
    \item ist redundant/riskant. Man k"onnte $X(1,2)$, $Y(2,3)$, $Z(3,4)$ bilden und damit
      Widerspr"uche erzeugen. (Siehe auch n"achste Variante)
    \item Auch das nicht: Es ist immerhin widerspruchsfrei: man legt
      in $X$ ab, welches $b$ zum $a$ geh"ort, und in $Z$, welches $c$
      zu beiden. Man k"onnte aber $X(1,2)$ haben, ohne einen Eintrag
      in $Z$, der $Z$ dazu, womit es kein $c$ dazu g"abe.
    \item Auch das nicht: kombiniert die Probleme aus (4) und (5).
    \item Offensichtlich gibt es eines.
    \item Ja. Analog zu (2) k"onnte man die Beziehung auch in \emph{eine} der 
      Tabellen $S$ oder $R$ reinziehen. Man w"urde sie ggf.\ in diejenige Tabelle
      reinziehen, die die wenigsten Tupel enth"alt. Evtl.\ g"abe es in einer
      realen Anwendung eine, aus der alle Elemente zugeordnet werden.
    \end{enumerate}

    Man kann also die Zordnung (a,b,c) \emph{zusammen} in \emph{eine}
    der Tabellen reinziehen.  Wenn man sie aufspaltet oder mehrmals
    reinzieht, geht jeweils irgendetwas kaputt.
  \end{loesung}
\end{Aufgabe}


\begin{Aufgabe}[Ausdruckskraft - (Umordnungs-Beispiel) \punkte{4}]
Ordnen Sie die folgenden Klassen von Sprachen nach ihrer Ausdruckskraft (st"arkste zuerst):
  \begin{itemize}
  \item Konjunktive Anfragen (Selektion/Projektion/Join/Renaming)
    ``SPJR-Algebra''
  \item Turing-vollst"andige Programmiersprachen
  \item Relationale Algebra
  \item SQL-Anfragen
  \item nachweisbar terminierende Java-Programme
  \end{itemize}
  \begin{loesung}
    Von oben nach unten:
    \begin{itemize}
    \item Turing-vollst"andige Programmiersprachen: ``(fast) alles''
    \item nachweisbar terminierende Java-Programme: es gibt
      Einschr"ankungen g"angiger Programmiersprachen, mit denen
      partielle (=Programm terminiert) und totale (=Programm erf"ullt
      logische Zusicherungen) -meistens mit interaktiven Beweisern-
      nachgewiesen werden kann. 
    \item SQL-Anfragen: Relationale Algebra plus Datentypen und 
      GROUP BY und Aggregationsoperatoren.
    \item Relationale Algebra.
    \item Konjunktive Anfragen (Selektion/Projektion/Join/Renaming)
      ``SPJR-Algebra'' -- ein wichtiges Fragment der relationalen
      Algebra aus Sicht der effizienten Auswertbarkeit.
    \item eine weitere wichtige Sprachfamilie ist Datalog (Vorlesung
      ``Deductive Databases'') mit Well-Founded und Stable
      Semantics. Liegt "uber der Relationalen Algebra
      (z.B. erm"oglichen schon einfache rekursive Datalog-Regeln die
      Berechnung der transitiven H"ulle; Well-founded und Stable
      Semantics gehen dar"uber weit hinaus, Stable Semantics kann z.B.
      Sudokus l"osen).  Datalog als Theorie-Sprache liegt ist aber
      unvergleichbar zu SQL, da es keine Datentypen und kein GROUP BY
      hat. Implementierungen (z.B. XSB) enthalten das aber auch und
      liegen damit oberhalb von SQL-Anfragen.
    \end{itemize}
  \end{loesung}
\end{Aufgabe}

\begin{Aufgabe}[Transaktionen \punkte{6}]
  \begin{itemize}
  \item[1)] Was bedeutet die Eigenschaft \emph{Durability
      (Dauerhaftigkeit)} von Transaktionen? 
  \item[2)] Welche Ma"snahmen werden in kommerziell eingesetzten
    Datenbanksystemen eingesetzt, um dies zu gew"ahrleisten? 
  \end{itemize}
  \begin{loesung}
  \begin{itemize}
  \item[1)] Der Effekt einer \emph{erfolgreich} beendeten
    Transaktion (z.B. die Best"atigung, dass eine "Uberweisung
    durchgef"uhrt wurde) ist dauerhaft, d.h., (1) es wird nicht mehr
    durch ein Rollback oder "ahnliches ungeschehen gemacht, und (2)
    auch im Fall eines Software- oder Hardware-Absturzes kann es 
    nicht mehr verloren gehen.
  \item[2)] Redundanz (wenn eine der Instanzen crasht, bleibt die 
    andere bestehen), regelm"a"sige Backup-Kopien (Snapshots
    sichern), logfiles der ausgef"uhrten Transaktionen und Aktionen
    (um auf einem Snapshot bzw.\ dem Absturzzustand aufbauend wieder
    einen konsistenten Zustand zu erreichen).
  \end{itemize}    
  \end{loesung}
\end{Aufgabe}

\begin{Aufgabe}[Abb. ER-Modell auf Relationales Modell (a) \punkte{2}]
  Nehmen Sie an, dass Sie ein gutes ER-Diagramm entwickelt haben, und
  dabei sind, dies in ein relationales Modell umzusetzen.

  In welchen Situationen ben"otigt man f"ur einen Entit"atstyp mehrere
  Relationen, um seine Informationen abzulegen?
  \begin{loesung}
    Wenn er ein oder  mehrere mehrwertige Attribute hat. \\
    (Antworten, die auf die Definitionen der 2.\ und 3.\ Normalform
    eingehen sind auch richtig, allerdings kann man diese Situationen
    durch ein wirklich gut durchdachtes ER-Modell in den allermeisten
    F"allen verhindern).
  \end{loesung}
\end{Aufgabe}

\begin{Aufgabe}[Abb. ER-Modell auf Relationales Modell (b) \punkte{6}]
  Gegeben sei folgendes ER-Diagramm:
  \vskip1cm

    \hspace*{2cm}\entity{A}\hspace*{5cm}\entity{B}
    \relationshipbetween{A}[\tiny$<0,*>$]{B}[\tiny$<0,x>$]{R}
    \attributeof{A}[0.6cm]{-180}[key]{a$_1$}[a1]
    \attributeof{A}[0.6cm]{-90}{a$_2$}[a2]
    \attributeof{B}[0.6cm]{0}[key]{b$_1$}[b1]
    \attributeof{B}[0.6cm]{-90}{b$_2$}[b2]
    \attributeof{R}[0.6cm]{90}{bla}
  \vskip1.5cm

    Geben Sie das Tabellenschema der Tabelle zur Speicherung von
    $R$ im relationalen Modell an. (2~P) \\
    Welche Attribute sind (u.a.\ in Abh"angigkeit von $x$ in der
    Kardinalit"at von $B$ bzgl. $R$) Schl"usselattribute dieser
    Relation? (4~P)
    \begin{loesung}
  Die Relation $R$ hat die Attribute $a_1$, $b_1$, $bla$
     (oder als  $A$, $B$, $bla$ benannt). \\
     $x=1$: nur $b_1$. \\
     Wenn $x>1$ und jedes $B$ zu jedem $A$ nur einmal in dieser
     Beziehung stehen kann, bilden $a_1$ und $b_1$ den Schl"ussel. \\
     Wenn $x>1$ und ein $B$ zu einem $A$ auch mehrmals mit
     verschiedenen Werten von $bla$ in Beziehung stehen kann, bilden
     $a_1$, $b_1$ und $bla$ den Schl"ussel. \\\relax 
     [Bewertung: eine
     Antwort gab 2P, jede weitere 1.5P; insgesamt konnten also 5P
     erreicht werden]
  \end{loesung}
\end{Aufgabe}

% wenn die Musterloesung hier mit einer rechten Seite endet:
\ifloesung\cleardoublepage~\fi

% Local Variables: 
% mode: latex
% TeX-master: "dbklausur"
% TeX-command-default: "LaTeX"
% TeX-PDF-mode: nil
% End:

