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 para cada conta em que ele participa.
  • a informação (nome_agencia, cidade_agencia) está repetida para cada conta registada nessa agência.

Esta repetição de 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 forma 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 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 r(XY)r(XY), em que XX e YY são subconjuntos de atributos, diz-se que XX determina YY ou que YY é dependente de XX, se cada valor de XX está associado a um único valor de YY. Neste caso, dizemos que XYX \to Y.

Propriedades das dependências

As dependências funcionais obedecem às propriedades esperadas:

  • Refletividade: se YXY \subseteq X, então XYX \to Y.
  • Aumentação: se XYX \to Y, então XZYZ,ZXZ \to YZ, \forall{Z}.
  • Transitividade: se XYX \to Y e YZY \to Z, então XZX \to Z.

Destes axiomas, podemos ainda derivar mais propriedades:

  • XXX \to X é, claro, universal.
  • Decomposição: se XYZX \to YZ, então XYX \to Y e XZX \to Z.
  • União: se XYX \to Y e XZX \to Z, então XYZX \to YZ.
  • Composição: se XYX \to Y e ABA \to B, então XAYBXA \to YB.

Fecho de Atributos

O fecho, α+\alpha^+, de um conjunto de atributos α\alpha, corresponde ao conjunto de atributos β\beta que dependem de α\alpha - isto é, αβ\alpha \to \beta.

Caso o fecho de α\alpha inclua todos os elementos da relação, dizemos que α\alpha é uma super-chave da mesma.

α+\alpha^+ 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:

ABA \to B, ACA \to C, CGHCG \to H, CGICG \to I, BHB \to H

O fecho de AGAG, (AG)+(AG)^+, pode ser computado tal que:

  • começamos com um fecho que corresponde ao próprio AGAG;
  • pegando em ABA \to B (porque AAGA \subset AG), podemos adicionar BB ao fecho, ficando então com o fecho ABGABG;
  • pegando em ACA \to C (porque AAGA \subset AG), podemos adicionar CC ao fecho, ficando então com o fecho ABCGABCG;
  • pegando em CGHCG \to H (porque GAGG \subset AG), podemos adicionar HH ao fecho, ficando então com o fecho ABCGHABCGH;
  • pegando em CGICG \to I (porque GAGG \subset AG), podemos adicionar II ao fecho, ficando então com o fecho ABCGHIABCGHI.

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 AGAG é uma super-chave.

É ainda interessante definir dependência total: dizemos que um conjunto de atributos YY é totalmente dependente de outro conjunto XX caso XYX \to Y e não haja nenhum subconjunto de XX que também determine YY. Isto é:

SX:SY\nexists_{S \subset X}: S \to Y

Por fim, podemos agora definir chave candidata: corresponde a uma chave em que nenhum dos seus subconjuntos é uma chave - isto é, um subconjunto de atributos XX de uma relação RR tal que XRXX \to R - X. Podendo haver mais do que uma chave candidata, damos o nome de chave primária à chave candidata escolhida para identificar unicamente tuplos numa relação de uma base de dados.

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 tem 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:

idmodeloid \to modelo, modelovoltagemmodelo \to voltagem

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 e 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:

idmodeloid \to modelo, modelovoltagemmodelo \to voltagem

Neste caso, a relação já respeita a 2ª FN, pois tanto idmodeloid \to modelo como modelovoltagemmodelo \to voltagem, e portanto, por transitividade, idmodelovoltagemid \to modelo \to voltagem. Temos, assim, todos os atributos não-chave a depender de atributos chave.

No entanto, a voltagem não é independente do modelo (modelovoltagemmodelo \to voltagem), 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:

(aluno,professor)disciplina(aluno, professor) \to disciplina, (aluno,disciplina)professor(aluno, disciplina) \to professor, (professor)disciplina(professor) \to disciplina

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, que não é uma chave candidata.

A FNBC é diferente da 3ª FN sempre que:

  • há mais do 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 detetáveis por dependências funcionais, logo previne anomalias.

Decomposição de relações

O objetivo 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, a 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 r(XYZ)r(XYZ), em que XX, YY e ZZ são conjuntos de atributos, a decomposição de rr em r1(XY)r_1(XY) e r2(XZ)r_2(XZ) diz-se lossless caso XYX \to Y ou XZX \to Z.

Podemos, caso se verifique o Teorema de Heath e tivermos uma relação r(XYZ)r(XYZ) onde XYX \to Y é uma dependência que viola a FNBC, fazer o seguinte:

  1. Decompor r(XYZ)r(XYZ) em r1(XY)r_1(XY) e r2(XZ)r_2(XZ);
  2. Verificar se r1r_1 e r2r_2 estão na FNBC, repetindo o processo recursivamente até todas as "sub-relações" criadas estarem na FNBC.