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}