\documentclass[11pt]{article}
\usepackage{amsmath, alltt, amssymb, xspace, times, epsfig, color}

\setlength{\evensidemargin}{0in} \setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in} \setlength{\textheight}{8.5in}
\setlength{\topmargin}{0in} \setlength{\headheight}{0in}



\begin{document}
\begin{center}
 \textbf{CS3431:  B-Term, 2013} \\
\textbf{Homework 3: Functional Dependency and Normalization} \\
\end{center}

\noindent
\textbf{Due Date:} Dec. 16, 2013 (3:00 PM)\\


\subsection*{Problem 1 [15 Points]}
Consider a relation with schema {\em R(A, B, C, D)} and FD's: $AB \rightarrow  C$,  $C \rightarrow D$, and  $D \rightarrow A$.

\begin{enumerate}
\item \textbf{(5 Points)} Report \textbf{five} nontrivial FD's that can be derived from the given FD's.

\item \textbf{(5 Points)} Find the attribute closure for the following attribute sets: \{AD\},  \{C\},  \{AB\}

\item \textbf{(5 Points)} What are all the candidate keys of {\em R}? 

\end{enumerate}


%--------------------------------------------------------------------------

\subsection*{Problem 2 [50 Points]}

For each relational schema given below and its corresponding functional dependencies (FDs):

\begin{itemize}
\item $R(A,B,C,D)$: $AB \rightarrow C, C \rightarrow D$ and $D \rightarrow A$

\item $R(A,B,C,D)$: $AB \rightarrow C, BC \rightarrow D$ and $CD \rightarrow A$ and
	$AD \rightarrow B$

\item $R(A,B,C,D,E)$: $AB \rightarrow C, C \rightarrow D, D \rightarrow B$ and $D \rightarrow E$
\end{itemize}

answer the following questions (for each of the above three cases separately):
\begin{enumerate}
\item \textbf{(10 Points)} find all candidate keys of the relation.
\item \textbf{(10 Points)} Given the keys you defined in the previous step, find the functional dependencies (from the given ones) that violate BCNF.
\item \textbf{(10 Points)} Decompose the relations to satisfy BCNF. Specify which FD is used to make the decomposition. If there is multi-step decomposition, then indicate each step along with which FD used for the decomposition.
\item \textbf{(10 Points)} Given the keys you defined in Step 1, find the functional dependencies (from the given ones) that violate 3NF.
\item \textbf{(10 Points)} Decompose the relations to satisfy 3NF. Specify which FD is used to make the decomposition. If there is multi-step decomposition, then indicate each step along with which FD used for the decomposition.
\end{enumerate}



\newpage


\subsection*{Problem 3 [25 Points]}

\begin{table*}[t]
\begin{center}
{
\begin{tabular}{|l|l|l|l|}
\hline
Department       &  Surname          & FirstName               & Address\\
\hline
Sales            &  Eastland         & Fred                    & 6 High Street\\
Purchasing       &  Eastland         & Fred                    & 6 High Street\\
Accounts         &  Watson           & Ethel                   & 27 Acacia Avenue\\
Personnel        &  Eastland         & Sydney                  & 27 Acacia Avenue\\
\hline
\end{tabular}
}
\caption{Relation for Problem 3}
\label{tab:re}
\end{center}
\end{table*}



Consider the relation in Table~\ref{tab:re}.

\begin{enumerate}
\item  \textbf{(10 Points)} Indicate whether each of the following decompositions is \textbf{Lossy} or \textbf{Lossless} and state why?
    \begin{itemize}
        \item {\em Department} and {\em Surname} are in one relation and {\em Surname}, {\em FirstName}, and {\em Address} are in another relation.
        \item {\em Department}, {\em FirstName},  and {\em Surname} are in one relation and {\em FirstName},  and {\em Address} are in another relation.
   %     \item {\em Department}, {\em FirstName},  and {\em Surname}  are in one relation and {\em Surname}, {\em FirstName}, and {\em Address} are in another relation.
    \end{itemize}

\item \textbf{(15 Points)} From the data in Table~\ref{tab:re}, identify the set of functional dependencies that hold. Then, specify which of the following decompositions preserve the dependencies and state why?
    \begin{itemize}
        \item {\em Department}, {\em FirstName},  and {\em Surname} are in one relation and {\em Surname},  and {\em Address} are in another relation.
        \item {\em Department}, {\em FirstName},  and {\em Surname}  are in one relation and {\em Surname}, {\em FirstName}, and {\em Address} are in another relation.
      %  \item {\em Department},  and {\em Address}  are in one relation and {\em Surname}, {\em FirstName}, and {\em Department} are in another relation.
    \end{itemize}
\end{enumerate}



\newpage
%==============================================



\noindent
\textbf{Grading}:\\
The maximum grade is 90 Points. Late submissions follow the rules stated on the website.\\\\


\noindent
\textbf{Deliverables}:\\ 
Each student should deliver a report containing the required solution.\\\\


\noindent
\textbf{Submission}:\\
Submit a hardcopy in the beginning of the class (3:00PM), or submit electronically via blackboard.wpi.edu website (Electronic submission is recommended).


\end{document}


%latex hw3; bibtex hw3; latex hw3; latex hw3; dvips hw3 -o hw3.ps; ps2pdf hw3.ps hw3.pdf


