Normalização e formas normais

Reconhecer uma DF

$X\to Y$ obriga quaisquer dois tuplos iguais em $X$ a serem iguais em $Y$, em todas as instâncias válidas, incluindo dados futuros.

• Uma amostra refuta uma DF com um contraexemplo; nunca a prova. Nomes distintos na tabela não provam nada; dois produtos “Rato” com ids diferentes refutam nomeProduto → idProduto.
• $Y\subseteq X$ torna-a trivial: Produto, Nome → Nome não restringe nada.
• A justaposição é união: $AB$ significa $\{A,B\}$.
• $A\to BC$ equivale a $A\to B$ e $A\to C$; a esquerda não se separa: $AB\to C$ não dá $A\to C$.

Armstrong: reflexividade ($Y\subseteq X\Rightarrow X\to Y$), aumento ($X\to Y\Rightarrow XZ\to YZ$) e transitividade.

Fecho e candidatas

Para $X^+$: começa em $X$ e acrescenta direitas de DFs cujas esquerdas já estejam no fecho, até estabilizar. $X\to Y$ vale se $Y\subseteq X^+$.

• Superchave: fecho igual a $R$. Candidata: superchave mínima por inclusão. Primo: pertence a alguma candidata.
• Atributos que nunca aparecem à direita de DFs não triviais pertencem a todas as candidatas; testa os seus fechos e extensões, descartando supersets de candidatas achadas.

Com $AB\to C$, $C\to D$, $D\to E$ em $R(A,B,C,D,E)$: $A^+=A$, $B^+=B$, $C^+=CDE$ e $(AB)^+=ABCDE$. $AB$ é a única candidata; $C,D,E$ são não primos.

Que forma normal

Assume 1FN: valores atómicos nos domínios escolhidos, sem grupos repetidos.

Forma	Teste para cada DF não trivial $X\to A$
2FN	Nenhum não primo depende de parte própria de candidata.
3FN	$X$ é superchave ou $A$ é primo.
BCNF	$X$ é superchave, sem exceção.

$\mathrm{BCNF}\Rightarrow\mathrm{3FN}\Rightarrow\mathrm{2FN}$. Verifica as DFs implicadas, não só as escritas.

• No exemplo acima, $C\to D$ viola 3FN ($C$ não é superchave, $D$ não é primo): está em 2FN.
• Com $AB\to C$ e $C\to B$ em $ABC$, as candidatas são $AB$ e $AC$ e $B$ é primo: $C\to B$ passa em 3FN mas viola BCNF.
• Em Venda(encomenda, produto, nomeProduto, qtd), o nome depende só do produto: dependência parcial que repete o nome e viola 2FN. Separa Produto de Item.

Reduzir a cobertura

1. Parte as direitas num atributo por DF.
2. Retira atributos dispensáveis à esquerda, confirmando por fechos.
3. Retira DFs redundantes, calculando o fecho sem a DF testada.

$\{A\to BC,B\to C,AB\to D\}$ dá $\{A\to B,B\to C,A\to D\}$: $B$ é dispensável em $AB\to D$ e $A\to C$ segue por transitividade. Ordens diferentes dão coberturas diferentes mas equivalentes.

Fechos e classificação desenvolvidos.