36/296
\begin{frame}
  \frametitle{Functional Dependencies}

  \begin{goal}{}
    In general, an \emph{functional dependencies} take the form
    \begin{talign}
    A_1, \dots, A_n \to B_1, \dots, B_m 
    \end{talign}
  \end{goal}
  
  \begin{itemize}
  \pause
  \item sequence of attributes is unimportant
  \pause
  \item both sides formally are sets of attributes
    \begin{talign}
    \{ A_1, \dots, A_n \} \to \{ B_1, \dots, B_m \}
    \end{talign}
  \end{itemize}
  \pause

  %   \begin{block}{}
  %     We discuss functional dependencies for a \emph{single relation} $R$.  
  %     \begin{itemize}
  %       \item all $A_i, B_j$ are attributes of the same relation $R$
  %     \end{itemize}
  %   \end{block}  
  
  \begin{block}{}
    The \emph{functional dependency (FD)}
    \begin{talign}
    A_1, \dots A_n \to B_1, \dots B_m
    \end{talign}
    \emph{holds for a relation $R$} in a database state $I$ if and only if for
    all tuples $t,u \in I(R)$:\vspace{-1ex}
    $$
    \begin{array}{cl}
                  & t.A_1 = u.A_1 \wedge \cdots \wedge t.A_n = u.A_n \\
      \Rightarrow & t.B_1 = u.B_1 \wedge \cdots \wedge t.B_m = u.B_m 
    \end{array}
    $$
  \end{block}  
\end{frame}