\documentclass[12pt]{article}
\usepackage{amsfonts, amssymb, amsmath, comment}
\usepackage{times}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage{url}
\usepackage{listings}
\usepackage[normalem]{ulem}
\usepackage{tikz}
\usetikzlibrary{shapes,shapes.geometric,er,positioning,calc,arrows,decorations.markings,backgrounds}
\lstset{language=SQL}
%\usepackage{xypic}
\usepackage{epsf}
\usepackage{epsfig}
\usepackage{enumitem}
%\usepackage{comment}

\setlist[itemize]{nosep}
\setlist[enumerate]{nosep}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.0in}
\setlength{\topmargin}{-0.5in}
\setlength{\headheight}{0in}
\parskip12pt
\parindent0pt
\pagestyle{fancy}
\lhead{CS 338 - Spring 2026}
\chead{CM A04}
\rhead{Due Wednesday, August 5, 11:59 PM EST}
\cfoot{\normalfont\medskip Copyright \copyright 2026}

\newcommand{\rmp}{\reversemarginpar\marginpar}

\providecommand{\SolutionOne}{}
\providecommand{\SolutionTwo}{}
\providecommand{\SolutionThree}{}
\providecommand{\SolutionFour}{}
\providecommand{\SolutionFive}{}
\providecommand{\SolutionSix}{}
\providecommand{\SolutionSeven}{}
\providecommand{\SolutionEight}{}
\providecommand{\SolutionNine}{}
\providecommand{\SolutionTen}{}

%\input xy
%\xyoption{all}

\begin{document}

\begin{itemize}
\item{
\textbf{Topics:} Normalization
}
\item{
Assignments must be completed individually.
}
\item{
No late assignments will be accepted.
}
\item{
Submit your completed solutions to \textbf{Crowdmark}.
}
\item{
\textbf{Rubric:}
Each question is worth 5 points, and will be graded according to the following rubric:
\begin{itemize}
\item{
5 points: Excellent (no mistake, or only a very small mistake)
}
\item{
4 points: Good (some mistakes)
}
\item{
3 points: OK (lots of mistakes)
}
\item{
2 points: Unsatisfactory (mostly wrong but has some merit)
}
\item{
1 point: Poor (mostly wrong but has one good idea)
}
\item{
0 points: Wrong (totally off, or no answer)
}
\end{itemize}
}
\end{itemize}

\newpage

\begin{enumerate}

\item \label{QuestionOne}
Consider the relation $R(ABCDEFG)$.
\begin{enumerate}
\item{
If $FD = \{ B \rightarrow CDF, AF \rightarrow G, G \rightarrow AC \}$, then what are the CK(s) in $R$?
}
\item{
If $FD = \{ A \rightarrow C, BE \rightarrow D, AG \rightarrow BF \}$, then what are the CK(s) in $R$?
}
\item{
If $FD = \{ E \rightarrow CG, F \rightarrow AD, C \rightarrow EF, G \rightarrow ABF \}$, then what are the CK(s) in $R$?
}
\end{enumerate}
\SolutionOne

\newpage

\item \label{QuestionTwo}
Determine whether each of the following relations is in BCNF:
\begin{enumerate}
\item{
$R1=(ABCD)$, $\{C \rightarrow BD, A \rightarrow BC\}$, and $A$ is the only candidate key.
}
\item{
$R2=(ABCD)$, $\{D \rightarrow B, CD \rightarrow AC\}$, and $CD$ is the only candidate key.
}
\item{
$R3=(ABCD)$, $\{A \rightarrow B, BC \rightarrow AD\}$, and $A$ and $B$ are the only two candidate keys.
}
\end{enumerate}
\SolutionTwo

\newpage

\item \label{QuestionThree}
Consider the relation $R = (ABCEFX)$, with the following set of functional dependencies:
\begin{eqnarray*}
X & \rightarrow & AB \\
A & \rightarrow & CX \\
E & \rightarrow & A \\
F & \rightarrow & EX .
\end{eqnarray*}
\begin{enumerate}
\item{
What are the candidate keys of R?
\textbf{Hint:} Consider the attribute closure.
}
\item{
Is R in BCNF?
}
\end{enumerate}
\SolutionThree

\newpage

\item \label{QuestionFour}
When \rmp{[5]}designing database in practice, the user and client sometimes cannot properly explain the functional dependencies.
They can only show how data is recorded in file and then they will have to fish out the necessary information themselves, as in this question.
Note that the actual semantics of the data is irrelevant.
So here we mask everything with just letters and numbers.
Note that a functional dependency $A \rightarrow B$ is analogous to a function $B=f(A)$, where every value in $A$ corresponds to one and only one value in $B$.

\begin{tabular}{|c|c|c|c|c|}
\hline
\textbf{J} & \textbf{E} & \textbf{C} & \textbf{M} & \textbf{D} \\
\hline
11 & 15 & 216 & 7 & 14 \\
11 & 7 & 216 & 7 & 17 \\
20 & 11 & 216 & 3 & 9 \\
1 & 7 & 7 & 4 & 17 \\
121 & 22 & 130 & 1 & 11 \\
1 & 7 & 8 & 9 & 110 \\
\hline
\end{tabular}

\begin{enumerate}
\item{
Identify the proper functional dependencies in the table given above.
To keep it simple, let's focus on the FDs between individual attributes.
}
\item{
Based on the FDs from (a), find the candidate keys.
}
\item{
Decompose the table $R(JECMD)$ into BCNF.
}
\end{enumerate}
\SolutionFour

\newpage

\item \label{QuestionFive}
Consider \rmp{[5]}the following relation, R, and Functional Dependencies:
\begin{displaymath}
R(ABCDE)
\end{displaymath}

\noindent
\textbf{FDs:}
\begin{eqnarray*}
AC & \rightarrow & DE\\
D & \rightarrow & B\\
CD & \rightarrow & E
\end{eqnarray*}
Decompose R into BCNF.
Check whether your decomposition is lossless, and preserves all functional dependencies.
\SolutionFive

\newpage

\item \label{QuestionSix}
Consider \rmp{[5]}the following relation, R, and Functional Dependencies:
\begin{displaymath}
R(CDMXY)
\end{displaymath}

\noindent
\textbf{FDs:}
\begin{eqnarray*}
M & \rightarrow & D\\
XY & \rightarrow & M\\
C & \rightarrow & MY
\end{eqnarray*}
Decompose R into BCNF.
Check whether your decomposition is lossless, and preserves all functional dependencies.
\SolutionSix

\newpage

\item \label{QuestionSeven}
Departments, \rmp{[5]}identified by ID, operate a variety of printers, each located in a particular room in a particular building.
Printers are supplied by a number of suppliers, identified by name, with each supplier charging a different price for a given printer, but also providing different delivery delays, measured in days.
A given room can have any number of printers, including none.

\noindent
The following relation is used to record printing services information.
\begin{eqnarray*}
PrintingService & & (DID, Printer\#, Room\#, Building\#, SupplierName,\\
 & & SupplierAddress, Delay, Cost)
\end{eqnarray*}

\noindent
\textbf{FDs:}
\begin{eqnarray*}
Printer\# & \rightarrow & DID, Room\#, Building\#, SupplierName\\
(Room\#, Building\#) & \rightarrow & DID\\
(SupplierName, Printer\#) & \rightarrow & Delay, Cost\\
SupplierName & \rightarrow & SupplierAddress\\
\end{eqnarray*}
\begin{enumerate}
\item{
Find all the candidate keys for the relation.
}
\item{
Indicate which FD(s) violates BCNF.
}
\item{
Find a BCNF decomposition for the given relation.
}
\item{
Is your decomposition lossless?
}
\item{
Does your decomposition preserve all functional dependencies?
}
\end{enumerate}
\SolutionSeven

\newpage

\item \label{QuestionEight}
The \rmp{[5]}following relation is used to record student information.
\begin{eqnarray*}
Student & & (SName, SID, College, StartDate, EndDate, Degree, \\
 & & CollegeAddress, Month, Year, ClassID, Grade)
\end{eqnarray*}

\noindent
\textbf{FDs:}
\begin{eqnarray*}
(SID, StartDate) & \rightarrow & College, CollegeAddress, EndDate, Degree, Month, Year\\
(SID, ClassID ) & \rightarrow & Grade\\
SID & \rightarrow & SName\\
College & \rightarrow & CollegeAddress\\
ClassID & \rightarrow & College, CollegeAddress\\
\end{eqnarray*}
Decompose the Student table into BCNF.
Make sure to show the steps.
Check whether it is lossless and FD preserving.

\noindent
\textbf{Hint:} Find all the CKs first.
\SolutionEight

\end{enumerate}

\end{document}