Normalização e formas normais

Duas vendas do produto 11 guardam o seu nome atual em cada encomenda:

Encomenda	Nome
100	Rato
102	Rato

Mudar «Rato» para «Rato sem fios» exige corrigir as duas linhas. Se esta fosse a única tabela onde guardamos produtos, apagar as duas vendas apagaria também o nome do produto 11.

A normalização usa dependências entre atributos para identificar estas anomalias e separar factos. Podemos guardar o nome uma só vez, numa relação de produtos, e manter a quantidade de cada compra nas linhas da encomenda.

Dependências funcionais

Assumimos que cada produto tem um único nome atual. Assim, o produto 11 tem de se chamar Rato nas duas linhas, apesar de aparecer em encomendas diferentes. Escrevemos esta regra como:

$$\text{idProduto}\to\text{nomeProduto}.$$

Esta é uma dependência funcional, abreviada DF ou FD nos slides. Duas linhas com o mesmo idProduto têm de ter o mesmo nomeProduto. O mesmo produto pode aparecer em várias encomendas, como acontece com o 11. A dependência não exige uma única linha por produto.

Os restantes atributos podem variar. Na encomenda 100 foi vendida uma unidade do produto 11; na 102 foram vendidas três. O mesmo produto tem quantidades diferentes, por isso idProduto → qtd é falsa nestas vendas.

Em geral, $X\to Y$ significa que duas linhas iguais nos atributos de $X$ têm de ser iguais nos de $Y$. $X$ e $Y$ podem ser conjuntos de atributos. A regra deve valer em todas as instâncias válidas, incluindo dados futuros.

A tabela ilustra a regra sobre o nome. A justificação vem da condição de um único nome atual por produto.

A dependência inversa exige outra condição. Se produtos diferentes puderem chamar-se Rato, nomeProduto → idProduto não vale. Nomes distintos numa amostra não provam essa dependência; dois produtos de igual nome e ids diferentes refutam-na.

Dependências triviais

idProduto, nomeProduto → nomeProduto é uma dependência trivial. O lado direito já está incluído no esquerdo: $Y\subseteq X$. Duas linhas iguais no produto e no nome têm necessariamente o mesmo nome, sem precisarmos de impor outra regra ao domínio.

Em idProduto → idProduto, nomeProduto, a dependência completa não é trivial, mas só idProduto → nomeProduto acrescenta uma restrição. O atributo idProduto à direita pode ser retirado sem mudar o significado.

Inferir dependências

Os axiomas de Armstrong permitem obter todas as DFs implicadas por um conjunto inicial:

• Reflexividade: se $Y\subseteq X$, então $X\to Y$.
• Aumento: de $X\to Y$, obtemos $XZ\to YZ$.
• Transitividade: de $X\to Y$ e $Y\to Z$, obtemos $X\to Z$.

A justaposição representa união de conjuntos, não multiplicação. Por exemplo, $AB$ significa $\{A,B\}$.

Podemos separar e reunir atributos à direita: $A\to BC$ equivale a $A\to B$ e $A\to C$. Não podemos separar automaticamente a esquerda: $AB\to C$ não implica $A\to C$ nem $B\to C$.

Na loja, assumimos uma única linha por par encomenda/produto. Logo esse par determina a quantidade.

O produto sozinho não chega. Vimos que o produto 11 foi vendido em quantidades diferentes. A quantidade também pode variar entre os produtos de uma mesma encomenda. Por isso o id da encomenda sozinho não chega.

Fecho de um conjunto de atributos

O fecho $X^+$ contém todos os atributos determinados por $X$ segundo as DFs dadas. Para o calcular:

1. Começa com os atributos de $X$.
2. Se o lado esquerdo de uma DF já estiver todo no fecho, acrescenta o lado direito.
3. Repete até nenhuma DF acrescentar atributos.

O processo termina porque só acrescentamos atributos e o esquema tem um conjunto finito deles. Para testar $X\to Y$, verifica se $Y\subseteq X^+$.

Considera $R(A,B,C,D,E)$ com:

$$AB\to C,\qquad C\to D,\qquad D\to E.$$

Para calcular $(AB)^+$, aplica as DFs por rondas:

Ronda	DF usada	Fecho
0	nenhuma	$AB$
1	$AB\to C$	$ABC$
2	$C\to D$	$ABCD$
3	$D\to E$	$ABCDE$

Na ronda 2, $AB\to C$ já não acrescenta nada. O processo para quando nenhuma DF aumenta o fecho. Assim, $AB$ determina o esquema inteiro.

Já $A^+=A$ e $B^+=B$. Nenhum determina os outros atributos. Para $C$, começamos com $C$, acrescentamos $D$ e depois $E$, obtendo $CDE$. Não podemos usar $AB\to C$ ao contrário para obter $A$ ou $B$.

Chaves candidatas e atributos primos

$X$ é superchave quando $X^+$ contém todos os atributos de $R$. É chave candidata quando é superchave e nenhum subconjunto próprio o é. Portanto, um fecho completo prova superchave; a minimalidade exige outro passo.

No exemplo anterior, $AB$ é candidata porque o seu fecho é completo e nem $A$ nem $B$ chegam sozinhos.

É a única. Nenhum atributo consegue obter $A$ ou $B$ pelas DFs dadas, pois estes nunca aparecem à direita. Qualquer chave tem de conter ambos. Os supersets $ABC$ e $ABDE$ são superchaves, mas não candidatas.

Um atributo é primo se pertence a pelo menos uma chave candidata, não apenas à primária escolhida. Para encontrar todas as chaves, começa pelos atributos que não aparecem à direita de nenhuma DF não trivial. Testa extensões em ordem crescente e descarta supersets de candidatas já encontradas. Confirma sempre os fechos.

Por exemplo, em $S(A,B,C)$ com $AB\to C$ e $C\to B$, temos duas candidatas: $AB$ e $AC$. Ambas determinam o esquema; $A$, $B$ e $C$ isolados não. Todos os atributos são primos, mesmo que escolhamos $AB$ como primária.

Formas normais

A 1.ª forma normal, 1FN, usa valores atómicos dentro dos domínios escolhidos, sem grupos repetidos de atributos. Guardar produto1, produto2 e produto3 limita artificialmente uma encomenda. Guardar uma lista de ids numa célula dificulta referências e operações relacionais. Uma relação Item resolve estes problemas.

A atomicidade depende do modelo. Uma data pode ser um valor do domínio, mesmo que consigamos decompor o seu texto em ano, mês e dia. “Atómico” não significa “impossível de dividir de qualquer maneira”.

A 2FN exige 1FN e que cada atributo não primo dependa totalmente de cada chave candidata. Não pode depender de uma parte própria de uma candidata composta. Se todas as candidatas tiverem um único atributo, não há uma parte própria não vazia que crie a dependência parcial habitual.

A 3FN exige 1FN e, para cada DF não trivial $X\to A$ com um atributo à direita, que $X$ seja superchave ou que $A$ seja primo. A descrição “não haver dependências entre atributos não chave” ajuda em casos simples com uma candidata, mas não substitui esta definição.

A BCNF, forma normal de Boyce-Codd, exige 1FN e que o determinante $X$ de toda a DF não trivial seja superchave. Não há a exceção de atributo primo.

Forma	Condição que verificamos
2FN	Nenhum atributo não primo depende de parte própria de uma candidata.
3FN	Numa DF não trivial, o determinante é superchave ou o atributo determinado é primo.
BCNF	Numa DF não trivial, o determinante é superchave.

Uma relação em BCNF está em 3FN; uma relação em 3FN está em 2FN, assumindo o modelo em 1FN. A implicação inversa pode falhar.

Classificar uma relação

Em $R(A,B,C,D,E)$ com $AB\to C$, $C\to D$ e $D\to E$, a candidata é $AB$. Os atributos $C,D,E$ são não primos.

A relação está em 2FN: nem $A$ nem $B$ determinam atributos não primos. Falha 3FN por $C\to D$: $C^+=CDE$ não é o esquema completo, logo $C$ não é superchave; $D$ não é primo. $D\to E$ também viola 3FN. A forma mais alta é 2FN.

Agora considera $S(A,B,C)$ com $AB\to C$ e $C\to B$. As candidatas são $AB$ e $AC$, portanto $B$ é primo. A DF $C\to B$ não viola 3FN, embora $C$ não seja superchave. Viola BCNF. Esta relação está em 3FN e não em BCNF.

Precisamos de considerar as DFs implicadas, não apenas uma lista arbitrária de setas. Para BCNF, verificar os determinantes das DFs de uma base equivalente é suficiente quando o determinante de cada DF não trivial dessa base é superchave. Depois de decompor, a base original tem de ser projetada sobre cada esquema.

Dependência parcial e anomalias

Retomamos as duas vendas da abertura no esquema Venda(idEncomenda, idProduto, nomeProduto, qtd). Admitimos uma linha por par encomenda/produto e que cada produto tem um único nome atual. O par (idEncomenda, idProduto) é candidato a chave: determina o nome e a quantidade, enquanto nenhum dos ids isolados determina a venda completa.

Nos dados de abertura, (100,11) determina quantidade 1 e (102,11) determina quantidade 3. Já o produto 11 determina Rato nas duas linhas. O nome depende só de uma parte da candidata, violando 2FN. Cada compra volta a guardar o nome. Uma alteração exige várias atualizações; um produto ainda sem compras não tem um lugar independente; apagar a última compra apaga também a informação do nome.

As projeções separam as propriedades do produto das propriedades da compra:

Produto(idProduto, nomeProduto):

idProduto	nomeProduto
11	Rato

Item(idEncomenda, idProduto, qtd):

idEncomenda	idProduto	qtd
100	11	1
102	11	3

O nome tem agora um único lugar para mudar. As quantidades continuam ligadas a cada encomenda. A página de decomposição explica por que esta separação não inventa combinações ao reconstruir os dados.

O preço exige a mesma atenção ao significado do atributo. O preço atual depende do produto; o preço acordado numa venda pertence à linha da encomenda. Mesmo que coincidam hoje, mudar o primeiro não deve reescrever o segundo. Uma coincidência de preços entre vendas também não prova idProduto → precoPago.

Cobertura mínima

Uma cobertura mínima é um conjunto equivalente de DFs com um único atributo à direita, sem atributos dispensáveis à esquerda e sem DFs redundantes. Equivalente significa que os dois conjuntos implicam as mesmas dependências.

Considera $F=\{A\to BC,\ B\to C,\ AB\to D\}$.

1. Separa $A\to BC$ em $A\to B$ e $A\to C$.
2. Em $AB\to D$, o $B$ é dispensável: a partir de $A$ obtemos $B$, depois $D$. Podemos substituir por $A\to D$.
3. $A\to C$ é redundante, porque $A\to B$ e $B\to C$ já a implicam. Retira-a.

Fica $\{A\to B,\ B\to C,\ A\to D\}$. Confere cada remoção com fechos. Para testar se uma DF inteira é redundante, retira-a antes de calcular o fecho; caso contrário, ela própria prova o resultado que querias testar. A ordem das reduções pode produzir coberturas mínimas diferentes, mas equivalentes.

Confere o conjunto final: sem $A\to B$, $A^+=AD$ e $B$ perde-se; sem $B\to C$, $C$ perde-se; sem $A\to D$, $D$ perde-se. Nenhuma das três é redundante e nenhuma esquerda tem atributos dispensáveis.