\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}