Normalização
Motivação: anomalias
Por vezes, ao desenhar uma base de dados, as relações são definidas de maneira tal que a informação é guardada de maneira redundante. Vejamos o seguinte exemplo:
Dada a relação:
info_conta(num_conta, saldo, nome_cliente, cidade_cliente, nome_agencia, cidade_agencia)
Podemos construir a seguinte tabela de exemplo:
num_conta |
saldo |
nome_cliente |
cidade_cliente |
nome_agencia |
cidade_agencia |
---|---|---|---|---|---|
A-101 | 500 | Hayes | Harrison | Downtown | Brooklyn |
A-101 | 500 | Johnson | Palo Alto | Downtown | Brooklyn |
A-201 | 900 | Johnson | Palo Alto | Perryridge | Horseneck |
A-215 | 700 | Smith | Rye | Mianus | Horseneck |
A-444 | 625 | Smith | Rye | North Town | Rye |
Rapidamente percebemos que há informação repetida:
- a informação (num_conta, saldo) está repetida para cada cliente que participa nessa conta.
- a informação (nome_cliente, cidade_cliente) está repetida em cada conta em que ele participa.
- a informação (nome_agencia, cidade_agencia) está repetida para cada conta registada nessa agencia.
Esta repetição da mesma informação é propensa a erros, como iremos ver.
Tipos de anomalias
Podemos enquadrar as anomalias em vários tipos:
-
Anomalias de inserção, quando para inserir um novo item na base de dados temos que inserir outros items, que não deviam estar relacionados.
-
Anomalias de atualização, quando para atualizar um item temos de atualizar outros items, que não deviam estar relacionados.
-
Anomalias de remoção, quando para remover um item temos que remover outros itens que não deviam estar relacionados.
-
Anomalias de consulta: para operações mais demoradas que o suposto, vamos ter maior consumo de largura de banda e mais memória gasta.
Exemplo
No caso do exemplo anterior, podemos ver que existem as seguintes anomalias:
- quando se quer inserir uma conta para um cliente existente, temos que voltar a inserir a cidade do cliente.
- quando se quer alterar o saldo da conta A-101 tem que se atualizar em várias linhas.
- quando se quer apagar a conta A-101, também se vai estar a apagar o cliente Hayes (o que pode não ser desejado).
Estas anomalias são causadas pela redundância de informação na base de dados, que advém de falhas no seu desenho: a base de dados não está normalizada, portanto.
Teoria da Normalização
Os objetivos da normalização da informação passam por:
- reduzir a redundância de informação, evitando ter informação repetida na base de dados.
- guardar dados independentes de maneira independente, procurando não criar dependências desnecessárias nem apagar dependências que fazem sentido.
- garantir que os dados podem ser facilmente consultados, reduzindo a complexidade é reduzida ao mínimo.
Vamos abordar, entre outros conceitos da Teoria da Normalização, as dependências funcionais, as formas normais, e a decomposição de relações.
Dependências funcionais (FD)
Dada uma relação , em que e são subconjuntos de atributos, diz-se que determina Y, ou que é dependente de , se cada valor de está associado a um único valor de . Neste caso, dizemos que !
Propriedades das dependências
As dependências funcionais obedecem às propriedades esperadas:
- Refletividade: se , então .
- Aumentação: se , então .
- Transitividade: se e , então .
Destes axiomas, podemos ainda derivar mais propriedades:
- é, claro, universal.
- Decomposição: se , então e .
- União: se e , então .
- Composição: se e , então .
Fecho de Atributos
O fecho, , de um conjunto de atributos , corresponde ao conjunto de atributos que dependem de - isto é, .
Caso o fecho de inclua todos os elementos da relação, dizemos que é uma super-chave da mesma.
pode ser computado iterativamente, como mostrado abaixo:
Exemplo
A título de exemplo, considerando a seguinte relação:
r(A, B, C, G, H, I)
Com o seguinte conjunto de dependências:
, , , ,
O fecho de , , pode ser computado tal que:
- começamos com um fecho que corresponde ao próprio ;
- pegando em (porque ), podemos adicionar ao fecho, ficando então com o fecho ;
- pegando em (porque ), podemos adicionar ao fecho, ficando então com o fecho ;
- pegando em (porque ), podemos adicionar ao fecho, ficando então com o fecho ;
- pegando em (porque ), podemos adicionar ao fecho, ficando então com o fecho .
Chegámos agora a um ponto em que todos os atributos da relação estão no fecho do conjunto inicial, pelo que podemos afirmar que é uma super-chave.
É ainda interessante definir dependência total: dizemos que um conjunto de atributos é totalmente dependente de outro conjunto caso e não haja nenhum subconjunto de que também determine . Isto é:
Por fim, podemos agora definir chave candidata: corresponde a uma chave em que nenhum dos seus subconjuntos é uma chave - isto é, um subconjunto de atributos de uma relação tal que . Podendo haver mais que uma chave candidata, damos o nome de chave primária à chave candidata escolhida pelo designer da BD para identificar unicamente tuplos numa relação.
Formas Normais
Correspondem a formas estandardizadas de representar a informação na base de dados, por forma a evitar (tanto quanto possível) a redundância da mesma, procurando ainda manter a coerência dos dados. Baseiam-se na noção de dependência funcional explorada mais acima.
1ª Forma Normal
Dizemos que uma relação está na 1ª Forma Normal quando todos os atributos são valores atómicos: isto é, cada atributo da relação pode ter apenas um valor por tuplo. Esta é, aliás, uma das definições necessárias para estarmos na presença de uma relação, já que precisamos que o nosso modelo seja consultável.
Esta forma normal é a mais simples, e portanto também bastante limitada: não faz qualquer verificação quanto à (in)dependência dos atributos, por exemplo. É aqui que entra a 2ª forma normal.
2ª Forma Normal
Dizemos que uma relação está na 2ª Forma Normal caso esteja na 1ª Forma Normal, e cada atributo não-chave dependa de todos os atributos-chave da relação em que se encontra.
Se tivermos a relação:
maquina(modelo, id, voltagem)
Com as seguintes dependências:
,
Como a voltagem depende totalmente do modelo (não é preciso id para se saber qual o seu valor), então não está a respeitar a 2ª FN. Essa informação deveria estar representada noutra tabela.
Temos, contudo, que esta FN continua sem evitar por completo a redundância, dado que pode haver dependências entre atributos não chave. É aqui que entra a utilidade da 3ª Forma Normal.
3ª Forma Normal
Diz-se que uma relação está na 3ª Forma Normal quando está na 2ª Forma Normal, todos os atributos não-chave são independentes entre si.
Exemplo
Se alterarmos o exemplo anterior e passarmos a ter:
maquina(id, modelo, voltagem)
Com as mesmas dependências:
,
Neste caso já respeita a 2ª FN, pois tanto como , e portanto, por transitividade, - temos, assim, todos os atributos não-chave a depender de atributos chave.
No entanto, a voltagem não é independente do modelo (), pelo que esta relação não respeita a 3ª FN.
Forma Normal de Boyce-Codd
Chegámos, finalmente, a uma forma normal que evita qualquer tipo de redundâncias, a forma normal de Boyce-Codd. Diz-se que uma relação está na FNBC quando está na 3ª Forma Normal e todos os atributos (independentemente de serem ou não chaves) são totalmente dependentes de uma chave candidata.
Exemplo
Vamos considerar o caso de querermos guardar informação sobre alunos, disciplinas e professores. Neste caso, cada professor só pode estar associado a uma única disciplina.
Temos a relação:
aula(aluno, disciplina, professor)
As chaves candidatas são:
- (aluno, professor)
- (aluno, disciplina)
Temos ainda as seguintes dependências:
, ,
Esta relação está na 3ª FN, pois só há um atributo não-chave, e esse atributo depende de ambos os atributos-chave. No entanto, não está na FNBC, uma vez que disciplina é totalmente dependente de professor, e professor não é uma chave candidata.
A FNBC é diferente da 3ª FN sempre que:
- há mais que uma chave candidata;
- as chaves são formadas por múltiplos atributos.
A FNBC já garante que não há redundância de informação, logo previne anomalias.
Decomposição de relações
O objectivo da decomposição de relações é pegar numa ou várias relações que não estão na FNBC e subdividir noutras relações de maneira a que estas já estejam.
No entanto, decomposição de relações, se não for bem feita, pode gerar
perda de informação e/ou de dependências.
Dizemos que a decomposição de uma relação é lossless (sem
perdas) quando a relação original consegue ser obtida através do
NATURAL JOIN
das relações resultantes da decomposição.
Teorema de Heath
Dada uma relação , em que , , são conjuntos de atributos, a decomposição de em e diz-se lossless caso ou .
Podemos, caso se verifique o teorema de Heath, e dada uma relação onde é uma dependência que viola a FNBC, então, fazer o seguinte:
- Decompor em e ;
- Verificar se e estão na FNBC, e repetir o processo recursivamente até todas as "sub-relações" criadas estarem na FNBC.