\begin{frame} \frametitle{Canonical Set of Functional Dependencies} \begin{block}{Computing a Canonical Set of Functional Dependencies} Let a set of FDs $\mathcal{F}$ be given. Determine a \emph{minimal} (\emph{canonical}) set of FDs that is equivalent to $\mathcal{F}$ by transforming $\mathcal{F}$ as follows: \begin{enumerate} \pause\smallskip \item \emph{Make the right-hand sides singular}\\[1ex] Replace every FD $\alpha \to B_1, \dots, B_m$ by $\alpha \to B_i$, $1 \leqslant i \leqslant m$. \pause\medskip \item \emph{Minimise left-hand sides}\\[1ex] For each FD $\alpha \to B$ and attribute $A \in \alpha$:\\[.5ex] If $B \in (\alpha - \{\, A \,\})_{\mathcal{F}}^+$, replace $\alpha \to B$ by $(\alpha - \{\, A \,\}) \to B$ in $\mathcal{F}$. % For each $A_1, \dots, A_n \to B$ and each $i = 1,\dots,n$: % \begin{itemize} % \item If the cover $\{A_1,\dots,A_{i-1},A_{i+1},\dots,A_n\}^+_{\mathcal{F}}$ contains $B$, then % \begin{itemize} % \item drop \;\;$A_1,\dots,A_n \to B$\;\; from $\mathcal{F}$, and % \item add \;\;$A_1,\dots,A_{i-1},A_{i+1},\dots,A_n \to B$\;\; to $\mathcal{F}$. % \end{itemize} % \end{itemize} \pause\medskip \item \emph{Remove implied FDs}\\[1ex] For each FD $\alpha \to B$:\\[.5ex] If $B \in \alpha^+_{\mathcal{G}}$ for $\mathcal{G} = \mathcal{F} - \{ \alpha \to B \}$, then drop $\alpha \to B$ from $\mathcal{F}$. \pause\medskip \end{enumerate} Repeat steps 2 and 3 until nothing can be removed. \end{block} \end{frame}