% This is an example of a LaTeX document, intended for teaching purposes only.
% Author: Ramona C. Truta
% Date: over the period of 2004 - 2005

% this is the documentstyle in use
\documentstyle{article}

% this is a comment
% the following are just settings
\setlength{\headheight}{0pt}
\setlength{\footheight}{0pt}
\setlength{\topmargin}{-.7in}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5truein}
\setlength{\textheight}{25cm}
\setlength{\parindent}{0 in}
% this is just a def of a new command, you don't have to worry about it.
% we can use the new command in this document, by simply \la
\newcommand{\la}{\leftarrow}
\newcommand{\ra}{\rightarrow}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\renewcommand{\i}{\item}
\newcommand{\sit}{\subitem}
\newcommand{\bv}{\begin{verbatim}}
\newcommand{\ev}{\end{verbatim}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}

% end of settings

% every document starts with this
% end ends with \end{document}
\begin{document}

This is an example of a simple text.

% the use of items (by default, they are bullets; if you want smth else,
% use \item [what you want] ([--] for instance))
\begin{itemize}
  \item \verb+C+ we refer to the \verb+Component+ relation;
  \item \verb+M+ we refer to the \verb+Manufacturer+ relation;
  \item \verb+S+ we refer to the \verb+Store+ relation;
  \item \verb+L+ we refer to the \verb+Sells+ relation.
\end{itemize}

% this is an example of an equation

% if you want your equation to be numbered, eliminate the '*'
% now, use

% \pi, for the pi symbol
% \sigma, for the sigma symbol
% \rho, for the rho symbol (renaming operator)
% \times, for the cartesian prod symbol
% \bowtie, for the natural join

% _ for subscripts
% ^ for superscripts

% \wedge for the logical conjunction
% \vee for the logical disjunction
% \neg for negation

% if you want  a space in a formula, use \ \

% \exists, for the existential quantifier
% \forall, for the universal quantifier

% \neq, for not equal
% \leq, for less than equal
% \geq, for greater than equal


{\bf RA:}

% \bf for bolding

% if you want your equation inside a line with text, just enclose it in between
% 2 dollar signs $ your equation $.
$a \ \geq \ b$

% by default, this will display your equation on a new line, and it's centered
\begin{eqnarray*}
  \pi_{sName, sLocation}(\sigma_{mLocation = sLocation}(S \bowtie L \bowtie M))
\end{eqnarray*}

{\bf SQL:}
\begin{verbatim}
SELECT S.sName, S.sLocation
FROM Store S, Sells L, Manufacturer M
WHERE S.sName = L.sName AND M.mName = L.sName AND S.sLocation = M.mLocation
\end{verbatim}


{\bf 2.} Find stores selling at least 3 different components of the same
manufacturer.

{\bf RA:}
\begin{eqnarray*}
  \pi_{sName, sLocation}(\sigma_{cName1 \neq cName2\ \wedge\ cName1 \neq cName3
   \wedge\ cName2 \neq cName3 }
  (\rho_{cName1 \la cName, price1 \la price}(L) \bowtie \\
  \rho_{cName2 \la cName, price2 \la price}(L) \bowtie
  \rho_{cName3 \la cName, price3 \la price}(L) \bowtie S)))
\end{eqnarray*}

% When you have a long expression to write it as a subscript, it is usefull to
% split it along several lines. For that, the tabular mode is needed.

\begin{eqnarray*}
  \pi_{sName, sLocation}
  &&(\sigma_{\begin{small} % to write the subscripts with smaller chars
             \begin{tabular}{l} % align at left; r for right; c for center
               $cName1 \neq cName2 \wedge$ \\
               $cName1 \neq cName3 \wedge$ \\
               $cName2 \neq cName3$
             \end{tabular}
             \end{small}}
      (\rho_{\begin{small}
             \begin{tabular}{l}
               $cName1 \la cName,$ \\
               $price1 \la price$
              \end{tabular}
              \end{small}} (L) \bowtie
       \rho_{\begin{small}
             \begin{tabular}{l}
               $cName2 \la cName,$ \\
               $price2 \la price$
              \end{tabular}
              \end{small}} (L) \bowtie \\
   &&  \rho_{\begin{small}
             \begin{tabular}{l}
               $cName3 \la cName,$ \\
               $price3 \la price$
              \end{tabular}
              \end{small}} (L) \bowtie S)))
\end{eqnarray*}

% to start a new page use

\newpage

{\bf SQL:}
\begin{verbatim}
SELECT S.sName, S.sLocation
FROM Store S, Sells L1, Sells L2, Sells L3
WHERE S.sName = L1.sName AND S.sName = L2.sName AND S.sName = L3.sName
      AND L1.mName = L2.mName AND L2.mName = L3.mName
      AND L1.cName <> L2.cName AND L1.cName <> L3.cName
      AND L2.cName <> L3.cName
\end{verbatim}

{\bf RC:}

% here is an example of a multiline equation

% you need to align your lines of this equations; use & &

% if you want a special symbol to be treated as a regular
% caracter, use the avoidance char (\)
% in this example, we have to enclose the RC in between {};
% this is why we use \{ and \}

% break the line and go to the next line  is \\

\begin{eqnarray*}
\{
   \ (sName,\ sLocation) & | & \exists\ mName1,\ mName2,\ mName3,\ price1,
                               \ price2,\ price3,\ cName\\
                         & &   L(sName,cName,mName1,price1)\ \wedge
                               L(sName,cName,mName2,price2)\ \wedge \\
                         & &   L(sName,cName,mName3,price3) \wedge
                               S(sName,sLocation) \wedge \\
                         & &   (mName1 \neq mName2)\ \wedge\
                               (mName2 \neq mName3) \wedge
                               (mName1 \neq mName3)
\}
\end{eqnarray*}

% if you want to change the fonts in an equation use:
% tt font
% $\mathtt{enclose equation here}$ or
% \begin{eqnarray*}
%     \mathtt{equation}
% \end{eqnarray*}

% rm font
% $\mathrm{enclose equation here}$ or
% \begin{eqnarray*}
%     \mathtrm{equation}
% \end{eqnarray*}

% see examples below:

This is an example of how to change the fonts in an equation:
\begin{eqnarray*}
  \mathtt{\{ \ (sName,\ sLocation)\ | \ \exists\ mName1,\ mName2, \cdots \} }
\end{eqnarray*}

Notice the difference now:
\begin{eqnarray*}
  \mathrm{\{ \ (sName,\ sLocation)\ | \ \exists\ mName1,\ mName2, \cdots \} }
\end{eqnarray*}


% below is an example on how to edit a BCNF decomposition,
% provided that you do NOT want to draw the tree of the decomposition

% notice the change of the size of the characters: large
\large {\bf Example on how to itemize/enumerate in LaTex}

% introduce a vertical space of 0.5cm
\vspace{0.5cm}

Given a relation $\mathrm{\ R (U, \cal{F})}$, where
$\mathrm{\ U = \{A, B, C, D, E, F \} }$,  and \\
$\mathrm{{\cal F} = \{ F \to B (FD1), C \to D (FD2), D \to E (FD3)\}}$.

Compute a BCNF decomposition of this relation.

FD1, FD2 and FD3 violate BCNF.

% if you want a bullet-like enumeration list, use the ``itemize'' mode
% \begin{itemize}
%  \item here comes your text
%  \item blah
% \end{itemize}
% by default, the bullet is a black circle; if you want to change its format
% use \item [here's the symbol you want your bullet to look like]
% use \item [] if you want no symbol

% if you want a numbered enumeration list, use the ``enumerate'' mode
% \begin{enumerate}
%  \item here comes your text
% \end{itemize}

% notice in the example below we've changed the format of the bullet.

{\bf using itemize}

\begin{itemize}
  \item [--] Start decomposing using FD1. We obtain R1 = ($BF, FD1$), and
    R2 = ($ACDEF, \{FD2, FD3\}$). R1 is in BCNF, and R2 is not in BCNF.
  \item [--] For R2, FD2 and FD3 violate BCNF. Continue
    decomposing R2, using FD3. We obtain R3 = ($DE, FD3$) and
    R4 = ($ACDF, \ FD2\}$). R3 is in BCNF, and R4 is not in BCNF.
  \item [--] For R4, FD2 violates BCNF. Continue
    decomposing R4, using FD2. We obtain R5 = ($CD, FD2$), and
    R6 = ($ACF, \emptyset$). Both R5 and R6 are in BCNF.
\end{itemize}

% example of enumerate

{\bf using enumerate}

\begin{enumerate}
  \item Start decomposing using FD1. We obtain R1 = ($BF, FD1$), and
    R2 = ($ACDEF, \{FD2, FD3\}$). R1 is in BCNF, and R2 is not in BCNF.
  \item For R2, FD2 and FD3 violate BCNF. Continue
    decomposing R2, using FD3. We obtain R3 = ($DE, FD3$) and
    R4 = ($ACDF, \ FD2\}$). R3 is in BCNF, and R4 is not in BCNF.
  \item For R4, FD2 violates BCNF. Continue
    decomposing R4, using FD2. We obtain R5 = ($CD, FD2$), and
    R6 = ($ACF, \emptyset$). Both R5 and R6 are in BCNF.
\end{enumerate}

\newpage

{\bf This is an example of the 3NF Synthesis Algorithm}

Consider a relation $R$ with attributes ${\cal U} = \{ A, B, C, D, E, G, H, K \} $ and
the set of functional dependencies
\begin{eqnarray*}
  {\cal F} =  \{ ABH \ra CK, A \ra D, C \ra E, BGH \ra L,
                 L \ra AD, E \ra L, BH \ra E \}
\end{eqnarray*}


% please note all the new commands defined and used: \bi, \ei, \be, \ee, \i

{\bf a)} Find a minimal cover of the relation $R$.
\be
  \i {\bf Step 1}
  {\em Decompose all FDs of the form $X \ra A$, where $A$ is a single
  attribute.}

  $\cal G = \{$

  \i {\bf Step 2} {\em Eliminate redundant attributes from LHS.}

   {\bf Algorithm}: \\
    If FD $XB \ra A \in {\cal F}$  (where $B$ is a single attribute) and
    $X \ra A$ is entailed by $\cal F$, then $B$ was unnecessary
   \bi
     \i[--] Can an attribute be eliminated from $ABH \ra C$?
       \sit $(AB)^+ = $
       \sit $(AH)^+ = $
       \sit $(BH)^+ = $
       \sit Answer:
     \i[--] Can an attribute be eliminated from $ABH \ra K$?
       \sit $(AB)^+ = $
       \sit $(AH)^+ = $
       \sit $(BH)^+ = $
       \sit Answer:
     \i[--] Can an attribute be eliminated from $BGH \ra L$?
       \sit $(BG)^+ = $
       \sit $(BH)^+ = $
       \sit $(GH)^+ = $
       \sit Answer:
     \i[--] Can an attribute be eliminated from $BH \ra E$?
       \sit $(B)^+ = $
       \sit $(H)^+ = $
       \sit Answer:
   \ei

   $\cal G = \{$
  \i {\bf Step 3} {\em Delete redundant FDs from $\cal G$.}

  {\bf Algorithm}:  \\
   If ${\cal G}-\{f\}$ entails $f$, then  $f$ is redundant:
   If  $f$ is $X \ra A$ then check if $A \in X^+_{{\cal G}-\{f\}}$
   \bi
     \i[--] Can $BH \to C$ be eliminated from $\cal G$?
       \sit $(BH)^+_{{\cal G}-\{BH \to C\}} = $ \\
     \i[--] Can $BH \to K$ be eliminated from $\cal G$?
       \sit $(BH)^+_{{\cal G}-\{BH \to K\}} = $ \\
     \i[--] Can $A \to D$ be eliminated from $\cal G$?
       \sit $(A)^+_{{\cal G}-\{A \to D\}} = $ \\
     \i[--] Can $C \to E$ be eliminated from $\cal G$?
       \sit $(C)^+_{{\cal G}-\{C \to E\}} = $ \\
     \i[--] Can $BH \to L$ be eliminated from $\cal G$?
       \sit $(BH)^+_{{\cal G}-\{BH \to L\}} = $ \\
     \i[--] Can $L \to A$ be eliminated from $\cal G$?
       \sit $(L)^+_{{\cal G}-\{L \to A\}} = $ \\
     \i[--] Can $L \to D$ be eliminated from $\cal G$?
       \sit $(L)^+_{{\cal G}-\{L \to D\}} = $ \\
     \i[--] Can $E \to L$ be eliminated from $\cal G$?
       \sit $(E)^+_{{\cal G}-\{E \to L\}} = $ \\
     \i[--] Can $BH \to E$ be eliminated from $\cal G$?
       \sit $(BH)^+_{{\cal G}-\{BH \to E\}} = $
   \ei

  $\cal G = \{$

\ee

{\bf b)} Produce a 3NF decomposition of the relation $R$.

\be
  \i {\bf Step 1} {\em Compute a minimal cover $\cal G$.}

  $\cal G = \{ $

  \i {\bf Step 2} {\em Partition $\cal G$ into sets
  ${\cal G}_1, {\cal G}_2, \cdots, {\cal G}_n$
  such that the LHS of all elements of ${\cal G}_i$ are the same.}

%  \vspace{6cm}
  \i {\bf Step 3} {\em For each ${\cal G}_i$ form schema
  $R_i = ({\cal U}_i,{\cal G}_i)$, where ${\cal U}_i$ is the set
  of all attributes mentioned in ${\cal G}_i$.}

%  \vspace{6cm}
  \i {\bf Step 4} {\em If no $R_i$ is a superkey of $R$, add schema
  $R_0 = ({\cal U}_0,\{\})$, where ${\cal U}_0$ is a key of $R$.}
\ee


\end{document}






