\documentstyle[11pt]{article}
\begin{document}
\begin{center}
{\bf CSE 233 $~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ $ $~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ $ Spring, 2018} \\
\vspace{4mm}
{\Large Problem Set \#1 } \\
{\bf Due on Thursday , April 19}
\end{center}
\vspace{6mm}
Please typeset your answer (latex recommended).
\vspace{4mm}
\noindent
{\bf 1.} The movie database consists of the following two
relations
\vspace{4mm}
\begin{tabular}{ll}
\begin{tabular}{l|lll}
movie & title & director & actor \\ \hline
& & &
\end{tabular}
&
\begin{tabular}{l|ll}
schedule & theater & title \\ \hline
& & \\
\end{tabular}
\end{tabular}
\vspace{4mm}
The first relation provides titles, directors, and actors of various movies.
Assume a movie is uniquely identified by its title. Do not assume that a movie has a unique director
(so a movie by Hitchcock is one for which {\em one of the directors} is Hitchcock).
The second relation provides the titles of currently playing movies and the theaters where they
are being shown. Express the following queries in relational calculus and relational algebra.
\begin{itemize}
\item [(a)] $(1 ~point)$ List the theaters showing some movie by Hitchcock.
\item [(b)] $(3 ~points)$ List the theaters showing only movies by Hitchcock.
\end{itemize}
\vspace{4mm}
\noindent
{\bf 2.} The {\em division} binary operator $\div$ on relations is defined as follows.
Given relations $P$ and $Q$ for which $att(Q) \subset att(P)$,
$P \div Q$ is a relation with attributes $att(P) - att(Q)$ containing the tuples $t$ for which $\{t\} \Join Q \subseteq P$.
For example, if $att(P) = \{A,B\}$ and $att(Q) = \{B\}$, $P \div Q$ is the relation with attribute $\{A\}$ containing
the tuples $\langle a \rangle$ for which $\langle a,b \rangle \in P$ for every tuple $\langle b \rangle \in Q$.
Intuitively, $\div$ is a direct implementation of universal quantification.
\begin{itemize}
\item [(i)] $(2 ~points)$ Use $\div$ (and standard algebra operators) to express the query
``List the theaters showing {\em every} movie by Hitchcock".
\item [(ii)] $(4 ~points)$ Show how $P \div Q$ can be expressed using the standard relational algebra operators
(you can assume, for simplicity, that $att(P) = \{A,B\}$ and $att(Q) = \{B\}$).
\end{itemize}
\newpage
\noindent
{\bf 3.} Consider the following query on the above {\em schedule} relation:
\begin{center}
{\em Find the theaters showing more than one title}
\end{center}
\begin{itemize}
\item [(i)] $(2 ~points)$ Express this query in relational calculus and relational algebra.
\item [(ii)] $(6 ~points)$ Prove that every relational algebra expression defining the above query {\em must} use the attribute
renaming operator $\delta$.
\end{itemize}
\vspace{4mm}
\noindent
{\bf 4.} (Automorphisms)
\begin{itemize}
\item [(i)] $(5 ~points)$ Let $\sigma$ be a database schema and $I$ an instance of $\sigma$.
A one-to-one mapping $f:$ {\bf dom} $\rightarrow$ {\bf dom} is an automorphism of $I$ iff $f(I) = I$ ($f$ is applied to tuples componentwise). For example, if $I$ is the binary relation instance
$$\begin{array}{l|ll}
& & \\
\hline
& a & c \\
& b & c \\
& c & d \\
\end{array}
$$
then the mapping given by the table
$$
\begin{array}{l|lll}
f & & \\ \hline
& a & \rightarrow & b \\
& b & \rightarrow & a \\
& c & \rightarrow & c \\
& d & \rightarrow & d
\end{array}
$$
is an automorphism of $I$ but the mapping
$$
\begin{array}{l|lll}
f & & \\ \hline
& a & \rightarrow & a \\
& b & \rightarrow & b \\
& c & \rightarrow & d \\
& d & \rightarrow & c
\end{array}
$$
is not.
Show that CALC queries without constants are invariant under automorphisms. In other words, if $Q$
is a CALC query without constants over schema $\sigma$,
then for every instance $I$ over $\sigma$, if $f$ is an automorphism of $I$ then $f$ is also an automorphism of $Q(I)$. \\
{\bf Hint:} Assume without loss of generality that the CALC formula $\varphi$ defining $Q$
uses only $\wedge, \exists, \neg$, and use structural induction on the formula.
\item[(ii)] $(2 ~points)$ Let $\sigma$ consist of a binary relation $R$. Using (i), show that there is no CALC query
without constants which on input
$$\begin{array}{l|ll}
R & & \\
\hline
& a & b \\
& b & c \\
& c & d \\
& d & a
\end{array}$$
produces as answer
$$\begin{array}{l|ll}
& & \\
\hline
& a & c \\
& b & d \\
\end{array}$$
\end{itemize}
\end{document}