\frametitle{Functional Dependencies}

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

  %   \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}  
    The \emph{functional dependency (FD)}
    A_1, \dots A_n \to B_1, \dots B_m
    \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}
                  & 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