%% 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
\thispagestyle{empty}
\vspace*{0.2cm}\begin{center}
\large\bf
Klausur ``Semistructured Data and XML'' \\
Summer Term 2020 \\
Prof. Dr. Wolfgang May \\
21. August 2020, 10-12 Uhr \\
Working Time: planned 90 Minutes, then extended to 150 Min \\
(carried out as a computer-based ILIAS exam)
\end{center}
\vspace*{-0.2cm}
\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}
\end{tabular}
\end{center}
\vskip0.3cm
\textbf{Setting:} on the E-exam-computers, ILIAS was running,
Notepad++ as editor, and also saxon (with the aliases saxonValid,
saxonXQ, and saxonXSL defined as in the course) were installed.
In this exam basically all paper-based aids are allowed. For the exam,
it was recommended to have the printed slides, and a condensed
self-prepared ``cheat sheet'' (preparation of a cheat sheet is a very
effective way to work through the materials). Mobile phones must be
turned off.
Answers might be given in English or German (most answers are program
code anyway). In the text, the german translation is sometimes given in
parentheses.
Give \emph{all} answers via the ILIAS system.
Like in a ``paper exam'', also solutions that do maybe not work (or do
not work completely) can be delivered and will be graded with
appropriately partial points.
% Take this sheet with you to keep your result code:
% \fbox{\perscode}
% In case some answers are drawn/written on paper, use the
% \textbf{distributed} sheets for your answers. Write with black/blue
% ball-pen or ink pen.
% Auf dem letzten Blatt finden Sie ein XML-Dokument, das in allen
% Aufgaben verwendet wird. Trennen Sie es ggf.\ zur Bearbeitung der
% Aufgaben ab.
%\vskip0.2cm
For \textbf{passing} the exam, \textbf{50} points are sufficient.
%\vskip0.7cm
%\begin{tabular}{lp{15cm}}
% \fbox{\phantom{X}} & my grade should be published as soon as possible (without name)
% on the lecture's Web page \\
% \fbox{\phantom{X}} & my grade should not be published, I wait until it has been
% processed by the exam office.
%\end{tabular}
%
%\vskip0.7cm
\begin{center}
\theoremlisttype{punktliste}
\listtheorems{Aufgabe}
\end{center}
\vskip1cm
\textbf{Note:}
\nextone
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% 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 Points]}
% \begin{Aufgabe}[Administrative\punkte{1}\erwpunkte{15}]
% Check \emph{exactly} one of the below boxes according to your needs:
% \begin{itemize}
% \item[\raisebox{-0.3cm}{\fbox{\phantom{X}}}] my grade should be
% published as soon as possible anonymously by personal code number
% \fbox{\perscode} on the lecture's Web page.
% \item[\raisebox{-0.3cm}{\fbox{\phantom{X}}}] my grade should not be
% published, I wait until it has been processed by the exam office.
% \end{itemize}
% \end{Aufgabe}
\subsection*{Project: Housing Cooperative (german: 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
% }
All exercises are based on a common ``project'': the database of a
housing cooperative that owns houses with rental apartments in cities
all over Germany.
\thispagestyle{empty}
% \begin{itemize}
% \item Note: Exercise 1 deals with the XML design,
% \item Exercise 2 deals with DTD aspects, and there, parts of the XML structure
% are given that must used by the design.
% \end{itemize}
\begin{enumerate}
\item Assume that cities are uniquely identified by their name. Also,
every street name exists at most once in every city.
\item For each building that is owned by the cooperative, the address
(city, street, house number) is stored. It is also stored how many
apartments are in the building (assume that always all apartments in
the building are owned by the cooperative).
\begin{itemize}
\item The building \emph{Hauptstra"se 100} in \emph{G"ottingen}
consists of 80 apartments.
\item The building \emph{Rheinstra"se 53} in
\emph{K"oln} consists of 100 apartments.
\end{itemize}
\item Every apartment has a (unique) number in its building. For
each apartment, the number of rooms, the size (in square meters)
and the current monthly rent (=Kaltmiete) is stored.
\begin{itemize}
\item The apartment with the number 42 of the
building \emph{Hauptstra"se 100} in \emph{G"ottingen} has three
rooms, 82 m$^2$, for 850 EUR per month.
\item The apartment with the number 43 of the same
building has two rooms, 50 m$^2$, for 550 EUR per month.
\item The apartment with the number 17 of the
building \emph{Rheinstra"se 53} in \emph{K"oln} has three
rooms, 95 m$^2$, for 1300 EUR per month.
\end{itemize}
\item For being entitled to rent an apartment in a cooperative,
persons must buy a share and become \emph{members} of the
cooperative. For every person, the name, the (unique) membership
code (recall that XML IDs must start with a letter), the birthdate,
and the birth place (city name, country) are stored.
\begin{itemize}
\item John Doe is born on February 28th, 1995 in Boston, USA.
\item Markus Meier is born on July 10th, 1980 in G"ottingen, Germany.
\item Liese M"uller is born on October 1st, 1950 in K"oln, Germany.
\item Jan Jansen is born on August 10th, 1985 in Stockholm, Sweden.
\end{itemize}
\item For every individual rental agreement (=Mietvertrag) the name of
the tenant (=Mieter) is stored (assume that the agreement is always
made with a single person), together with the starting date, and
the contact address where the tenant lived when the contract was
signed. \\
Contracts always begin with the first day of a month, and end with
the last day of a month.\\
Additionally, it is stored whether the contract is terminated or
announced to be terminated, and for which date (=gek"undigt; in
Germany, a rental contract must be announced to be terminated three
months in advance -- e.g.\ today you could announce to terminate the
contract for your apartment for November 30th, 2020).
\begin{itemize}
\item \emph{John Doe} lives in the apartment nr.\ 42 of the building
\emph{Hauptstrasse 100} in \emph{G"ottingen} since April 1st,
2018. The contract is not announced to be terminated.
\item \emph{Markus Meier} lives in the apartment nr.\ 43 of the
building \emph{Hauptstrasse 100} in \emph{G"ottingen} since August
1st, 2011. He already announced to terminate the contract for
October 31st, 2020.
\item \emph{Liese M"uller} lives in the apartment nr.\ 17 of the
building \emph{Rheinstrasse 53} in K"oln since March 1st, 1990.
She announced to terminate the contract for August 31st, 2020.
\end{itemize}
\item When a new contract is signed, the (at this point current) address
of the tenant and the starting date of the contract is stored.
\begin{itemize}
\item The above-mentioned \emph{Markus Meier} has signed a contract
for the apartment nr.\ 17 of the building \emph{Rheinstrasse 53}
in \emph{K"oln}, beginning October 1st, 2020.
\item \emph{Jan Jansen}, who currently lives at the address
\emph{Hafenstrasse 10, Hamburg} (this apartment is not owned by
the cooperative), signed a contract for the apartment nr.\ 43 of
the building \emph{Hauptstrasse 100} in \emph{G"ottingen} from
December 1st, 2020 on.
\end{itemize}
\item If a tenant moves somewhere else (not necessarily to an
apartment of the cooperative), the new address is stored (e.g., to
send the final cost bills).
\begin{itemize}
\item The future address of \emph{Liese M"uller} is
\emph{M"uhlengasse 24, M"uhlhausen} in a building that does not
belong to the cooperative.
\end{itemize}
\item Data about older contracts is kept in the database, it
is \emph{not} deleted.
\end{enumerate}
\newpage
\begin{Aufgabe}[XML\punkte{20}\erwpunkte{15}]\label{ex-xml}
Design an XML structure (use the frame given in file \texttt{exam.xml}) and
fill it with some sample data (e.g.\ with some of the example data
given in the text). \\
(Information about handling dates in XML can be found in the
course's slides around Slide~300.)
Copy-and-paste the XML from the file \texttt{exam.xml} afterwards (at the end
of the exam, because it will be extended in later exercises) here:
\begin{loesung}
\begin{verbatimwrite}{exam.xml}
\end{verbatimwrite}
\prginput{exam.xml}
\end{loesung}
\end{Aufgabe}
\begin{Aufgabe}[DTD\punkte{15}\erwpunkte{10}]
Develop the DTD for your document developed in Exercise~\ref{ex-xml}, use the
file \texttt{exam.dtd}. \\
Use the saxon call
\begin{verbatim}
saxonValid.bat -s:exam.xml
\end{verbatim}
for validating it. \\
Copy-and-paste the DTD from the file \texttt{exam.dtd} afterwards here:
\begin{loesung}
\begin{verbatimwrite}{exam.dtd}
\end{verbatimwrite}
\prginput{exam.dtd}
\end{loesung}
\end{Aufgabe}
\begin{Aufgabe}[XPath (a) \punkte{2}\erwpunkte{2}]\label{ex-xpath1}
Use your \texttt{exam.xml} XML file as a basis for solving this and the following exercises. \\
None of the results should contain duplicates. \medskip
Give an XPath query or an XQuery query that returns the names of all
cities where the cooperative owns at least one apartment that
consists of \emph{exactly three} rooms.
Write the XPath query string in the file \texttt{query1.xq} and call it with
\begin{verbatim}
saxonXQ.bat -s:exam.xml query1.xq
\end{verbatim}
Copy-and-paste the query from query1.xq afterwards here:
\begin{loesung}
\begin{verbatimwrite}{query1.xq}
(: in my design where the buildings are nested in their cities, there is
no problem with duplicates - but care for .// :)
//city[.//apartment[@rooms=3]]/@name/string()
(: in other XML designs, it may be like
distinct-values(//building[apartment[@rooms=4]]/id(@city)/name) :)
\end{verbatimwrite}
\prginput{query1.xq}
\end{loesung}
\end{Aufgabe}
\begin{Aufgabe}[Appl.-semantic validation of query result\punkte{2}\erwpunkte{2}]
Add additional sample data to your XML designed in Exercise~\ref{ex-xml} to
test that your result does not return duplicates in case that there
are multiple such apartments in a city.
Paste your \emph{result} of evaluating the query from Exercise~\ref{ex-xpath1}
(XPath (a)) here:
\begin{loesung}
XML: just add another 3-room-apartment in the Göttingen-Hauptstrasse building.
result: should return the city where the mock apartment has been
added only once.
\end{loesung}
\end{Aufgabe}
\begin{Aufgabe}[XPath/XQuery (b) \punkte{4}\erwpunkte{3}]
Give an XPath query or an XQuery query that returns the names of all
persons who have \emph{currently} rented an apartment that
consists of exactly three rooms and costs less than 900 EUR. \\
(note: the current date can be obtained by the XPath function
current-date().)
Copy-and-paste the query from query2.xq afterwards here:
\begin{loesung}
\begin{verbatimwrite}{query2.xq}
(: distinct-values is again necessary, since a person on the move may
currently have two contracts :)
distinct-values(//apartment[@rooms = 3 and @rent < 900]/contract
[@from <= current-date() and not (@until < current-date())]
/id(@person)/@name)
distinct-values(//apartment[@rooms = 3 and @rent < 900]/contract
[@from <= current-date() and
(not(@until) or (@until >= current-date()))]
/id(@person)/@name)
(: alternative for second-last line:
(: note: explicit casting number(@rent) is not necessary because 900 is
parsed as a numeric constant.
note: saxon does not need a declaration of the xs:
namespace as it is predefined.
:)
\end{verbatimwrite}
\prginput{query2.xq}
\end{loesung}
\end{Aufgabe}
%\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}
\begin{Aufgabe}[XPath/XQuery (c) \punkte{6}\erwpunkte{4}]
Give an XPath query or an XQuery query which, for every city, yields
the total earnings of the cooperative in October 2020. The results
should be of the format
\begin{verbatim}
\end{verbatim}
Copy-and-paste the query from query3.xq afterwards here:
\begin{loesung}
\begin{verbatimwrite}{query3.xq}
for $c in //city
return
"2020-10-01")]]/@rent)}"/>
\end{verbatimwrite}%$
\prginput{query3.xq}
\end{loesung}
\end{Aufgabe}
\begin{Aufgabe}[XPath/XQuery (d) \punkte{5}\erwpunkte{2}]
Give an XPath query or an XQuery query that yields the names of all
persons who ever rented an apartment of the cooperative, but never
rented an apartment of the cooperative in K"oln.
Copy-and-paste the query from query4.xq afterwards here:
\begin{loesung}
\begin{verbatimwrite}{query4a.xq}
//person[not (./@id = //city[@name="Köln"]//apartment/contract/@person)]
/@name/string()
\end{verbatimwrite}
\prginput{query4a.xq}
\begin{verbatimwrite}{query4b.xq}
for $p in //person
where every $c in //contract[@person = $p/@id]
satisfies $c/ancestor::city/@name != 'Köln'
return $p/@name/string()
\end{verbatimwrite}
\prginput{query4b.xq}
Note that the comparison
\verb|contract[id(@person) = $p]| would apply string-comparison(!)
to empty(!) \ elements which always evaluates to ``true''. Then, one
must use
\verb|contract[id(@person) is $p]|.
There is also a --slightly awkward-- solution that uses
XQuery's --slightly awkward-- grouping semantics:
\begin{verbatimwrite}{query4c.xq}
for $c in //contract
group by $pid := $c/@person (: group-by always groups by string values! :)
where every $contract in $c (: $c now is the GROUP of all contracts of that person :)
satisfies $contract/ancestor::city/@name != 'Köln'
return id($pid)/@name/string()
\end{verbatimwrite}
%$
\prginput{query4c.xq}
\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}
% \end{loesung}
\begin{Aufgabe}[XPath/XQuery (e) \punkte{5}\erwpunkte{3}]
Give an XQuery query or an XPath query that returns the names of all
cities such that in \emph{every} building owned by the cooperative
in this city there is at least one apartment that has at least 100
square meters.
Copy-and-paste the query from query5.xq afterwards here:
\begin{loesung}
\begin{verbatimwrite}{query5.xq}
for $c in //city
where every $b in $c/building
satisfies $b/apartment[@size >= 100]
return $c/@name/string()
//city[not (building[not (apartment[@size >= 100])])]/@name/string()
\end{verbatimwrite} %$
\prginput{query5.xq}
\end{loesung}
\end{Aufgabe}
\begin{Aufgabe}[XPath/XQuery (f) \punkte{10}\erwpunkte{4}]
Give an XQuery query that returns information about all persons who
moved (or will move) from one apartment \emph{directly} to another (both owned by
the cooperative), and the second apartment is more expensive than
the one before (use the \emph{current rent}
for time-independent comparison of ``expensiveness'' of apartments). \\
The results should be of the format
\begin{verbatim}
\end{verbatim}
Copy-and-paste the query from query6.xq afterwards here:
\begin{loesung}
\begin{verbatimwrite}{query6a.xq}
for $c1 in //contract,
$c2 in //contract[@person=$c1/@person]
let $c2Addr := concat($c2/../../@street," ",$c2/../../@nr)
where $c1/afterAddr/@city = $c2/../../../@name
and $c1/afterAddr/@addr = $c2Addr
and number($c1/../@rent) < number($c2/../@rent)
return
\end{verbatimwrite} %$
\prginput{query6a.xq}
Another possibility is to use the termination date and the starting
date of subsequent contracts (usually, there is one or two months
overlap, or ``move overnight'')
\begin{verbatimwrite}{query6b.xq}
for $c1 in //contract,
$c2 in //contract[@person=$c1/@person]
let $c2Addr := concat($c2/../../@street," ",$c2/../../@nr),
$overlap := days-from-duration(xs:date($c1/@until) - xs:date($c2/@from))
where $overlap < 100 and $overlap > -3
and number($c1/../@rent) < number($c2/../@rent)
return
\end{verbatimwrite} %$
\prginput{query6b.xq}
\end{loesung}
\end{Aufgabe}
\begin{Aufgabe}[XPath/XQuery (g) \punkte{10}\erwpunkte{4}]
Give an XQuery query or an XSLT stylesheet that, for each city
``A'', gives a list of all cities ``B'' such that \emph{some} person
moved (or will move) \emph{directly} from an apartment in city ``A'' to an
apartment in ``B'', and both of the apartments belong to
the cooperative. \\
for each such city ``A'', the result should be of the form
\begin{verbatim}
name-of-city-B1 ... name-of-city-Bn
\end{verbatim}
(no duplicate B's, in any order, with arbitrary whitespaces)
Copy-and-paste the query from query7.xq afterwards here:
\begin{loesung}
\begin{verbatimwrite}{query7.xq}
for $c in //city
return
{ $c/@name,
let $followingcities :=
for $addr in $c//contract/afterAddr
let $aftercity := //city[@name = $addr/@city]
where $aftercity//building[concat(@street," ",@nr) = $addr/@addr]
return $aftercity/@name
return distinct-values($followingcities)
}
\end{verbatimwrite} %$
\prginput{query7.xq}
\end{loesung}
\end{Aufgabe}
% \begin{Aufgabe}[XQuery Updates \punkte{3}\erwpunkte{2}]
% Give an XQuery update statement for the following situation:
% John Doe informs the administration of the cooperative that he will
% terminate the contract for his apartment with December 31st,
% 2020. His future address is \emph{Willy-Brandt-Straße 1} in
% \emph{Berlin}.
% Note that XQuery updates cannot be executed with the saxonHE
% version installed in the E-exams room.
% Write the statements here:
% \begin{loesung}
% \begin{verbatimwrite}{queryX.xq}
% \end{verbatimwrite}
% \prginput{exam.xsl}
% \end{loesung}
% \end{Aufgabe}
\begin{Aufgabe}[XSLT \punkte{15}\erwpunkte{4}]
Extend the given XSL stylesheet frame \texttt{exam.xsl} to an XSLT
stylesheet that for each person returns the name in an h3-element,
followed by an HTML list that chronologically lists all apartments
(by address) that the person had rented from the cooperative. \\
(an HTML list consists of an ul-element with nested li-elements;
omit the surrounding HTML stuff, don't care too much for formatting)
Use the following call to execute it:
\begin{verbatim}
saxonXSL.bat -s:exam.xml exam.xsl
\end{verbatim}
Copy-and-paste the XSLT stylesheet from exam.xsl afterwards here:
\begin{loesung}
\begin{verbatimwrite}{exam.xsl}
:
-
\end{verbatimwrite}
\prginput{exam.xsl}
\end{loesung}
\end{Aufgabe}
\begin{Aufgabe}[Miscellaneous (a) \punkte{2}\erwpunkte{2}]
Describe (short and concisely) what ID and IDREF in XML, and primary
keys and foreign keys in relational databases both are used for:
\begin{loesung}
\begin{itemize}
\item ID/primary key: identification of a data item (element,
tuple),
\item IDREF/foreign key: reference to such an identifier.
\end{itemize}
\end{loesung}
\end{Aufgabe}
\begin{Aufgabe}[Miscellaneous (b) \punkte{4}\erwpunkte{2}]
Describe \textbf{two} aspects in which the ID/IDREF mechanism in the XML
world differs from the primary key/foreign key concept in relational
databases:
\begin{loesung}
There are many structural, ``small'' syntactical, and usage aspects:
\begin{itemize}
\item Primary keys are local to a table, IDs are global to the document \\
(e.g., in relational Mondial, ``AG'', ``C'' and ``NAM'' are both country
codes and abbreviations of organizations) \\
As a consequence of this, and by the design of the relational model,
foreign key references represent a certain relationship between
two classes/tables, while IDREFs attributes cannot be specified
in the DTD to point to elements of a certain type (e.g., to
could prevent a country/@capital attribute to the id of a lake).
XML Schema allows to specify constraints in the style of foreign key.
\item Primary keys may be composite (e.g., City(name, country,
province)), IDs are atomic.
\item Primary keys may contain whitespaces, IDs must be whitespace-free
(but, by this, a single IDREF can contain multiple targets).
\item IDREFs can be dereferenced in the query language (graph navigation
using the id() function),
PKs/FKs must be handled via joins (relational model).
\item XML model together with IDREFS's multivalued id(string$1^*$)
navigation functionality: 1:$n$ and $n$:$m$ relationships
can be expressed easily, while in the relational model this
requires an additional relationship table.
\item XML IDs must start with a letter. Primary keys may be numeric. \\
Note that numeric values for ID attributes would be problematic
since e.g.\ the number 1000 can be written as ``1000'' and as
``10E3'' or ``1.0E4''.
\end{itemize}
\end{loesung}
\end{Aufgabe}
\hrule
\vskip0.5cm
The following frames can be used:
\begin{itemize}
\item Frame for XML file \texttt{exam.xml}:
\begin{verbatim}
to be extended here
\end{verbatim}
\item Frame for XML stylesheet \texttt{exam.xsl}:
\begin{verbatim}
to be extended here
\end{verbatim}
\end{itemize}
% wenn die Musterloesung hier mit einer rechten Seite endet:
\ifloesung\cleardoublepage~\fi
% Local Variables:
% mode: latex
% TeX-master: "ssdklausur"
% TeX-PDF-mode: nil
% TeX-command-default: "LaTeX"
% End: