Normalização de dados

Origem: Wikipédia, a enciclopédia livre.

Este artigo encontra-se parcialmente em língua estrangeira. Ajude e colabore com a tradução.

A normalização de dados é uma série de passos que se segue no desenho de uma base de dados que permite um armazenamento consistente e um eficiente acesso aos dados em uma base de dados relacional. Esses passos reduzem a redundância de dados e as chances dos dados se tornarem insconsistentes.

No entanto, muitas DBMSs relacionais não têm separação suficiente entre o design lógico da base de dados e a implementação física do armazém de dados (data store), e isso tem como consequência que as consultas feitas a uma base de dados totalmente normalizada têm um mau desempenho. Nestes casos, usa-se por vezes a denormalização para melhorar o desempenho, com o custo de menores garantias de consistência.

[editar] Panorâmica informal

Diz-se que uma tabela numa base de dados relacional está numa certa forma normal se satisfaz certas condições. O trabalho original de Edgar F. Codd definiu três dessas formas, mas existem hoje outras formas normais geralmente aceitas. Damos aqui uma curta panorâmica informal das mais comuns. Cada forma normal listada abaixo representa uma condição mais forte que a que a precede na lista. Para a maioria dos efeitos práticos, considera-se que as bases de dados estão normalizadas se aderirem à terceira forma normal.

Primeira Forma Normal (ou 1FN) requer que todos os valores de colunas em uma tabela, sejam atômicos (ex., um número é um átomo, enquanto uma lista ou um conjunto não o são).Por exemplo, a normalização elimina grupos repetidos pondo-os cada um em uma tabela separada, conectando-os com uma chave primária ou estrangeira.

Segunda Forma Normal (ou 2FN) requer que não haja dependência funcional não-trivial de um atributo que não seja a chave, em parte da chave candidata.

Terceira Forma Normal (ou 3FN) requer não haver dependências funcionais não-triviais de atributos que não sejam chave, em qualquer coisa exceto um superconjunto de uma chave candidata.

Forma Normal de Boyce-Codd (ou BCNF)

requer que não exista nenhuma dependência funcional não-trivial de atributos em algo mais do que um superconjunto de uma chave candidata. Neste estágio, todos os atributos são dependentes de uma chave, de uma chave inteira e de nada mais que uma chave (excluindo dependências triviais, como A->A).

Quarta Forma Normal (or 4NF) requer que não exista nenhuma dependência multi-valorada não-trivial de conjuntos de atributo em algo mais de que um superconjunto de uma chave candidata.

Quinta Forma Normal (ou 5NF ou PJ/NF) requer que não exista dependências de joins não triviais que não venham de key constraints.

Domain-Key Normal Form (or DK/NF) requer que todas as constraints sigam os domínios e key constraints.

[editar] Visão Formal

Antes de falar sobre normalização, é necessário utilizar alguns termos a partir do modelo relacional e defini-los na teoria de conjuntos. Estas definições muitas vezes serão simplificações de seus significados originais, uma vez que somente alguns aspectos do modelo relacional são levados em consideração na normalização.

As Notações Básicas utilizadas no modelo relacional são nomes de relacionamentos e nomes de atributos. Representaremos estas cadeias de caracteres tais como Pessoas e Nomes e geralmente usaremos variáveis como r, s, t, ... e a, b, c para o conjunto dados definido sobre eles. Outra notação básica é o conjunto de valores atômicos que contém valores tais como números e cadeias de caracteres.

Nossa primeira definição que nos interessa é a noção de tupla a qual formaliza a noção de linha ou registro em uma tabela:

Def. Uma tupla é uma função parcial de nomes de atributos para valores atômicos.

Def. Um cabeçalho é um conjunto finito de nomes de atributos.

Def. A projeção de uma tupla t em um conjunto finito de atributos A é t[A] = { (a, v) : (a, v) ∈ t, a ∈ A }.

A próxima definição é a de relação na qual formaliza-se o teor de uma tabela como ele é definido no modelo relacional.

Def. Uma relação é uma tupla (H, B) sendo H, o cabeçalho, um cabeçalho e B, o corpo, um conjunto de tuplas em que possuem todas o domínio H.

Como uma relação corresponde definitivamente com aquela que é usualmente chamada de extensão de um predicado em lógica de primeira ordem exceto que aqui nós identificamos os locais no predicado com nomes de atributos. Geralmente no modelo relacional um esquema de banco de dados é dito consistir-se de um conjunto de nomes relação, os cabeçalhos que são associados com esses nomes e as constraints que devem manter toda instancia do esquema de banco de dados. Para normalização nós nos concentraremos nas constraints que indicam relações individuais, isto é, as constraints relacionais. O propósito destas constraints é descrever o universo relacional, ou seja, o conjunto de todas as relações que são permitidas para serem associadas com certos nomes relação.

Def. Um universo relacional U sobre um cabeçalho H é um conjunto não vazio de relações com o cabeçalho H.

Def. Um esquema relacional (H, C) consiste de um cabeçalho H e um predicado C(R) que é definido por todas as relações R com o cabeçalho H.

Def. Uma relação satisfaz o esquema relacional (H, C) se possuir o cabeçalho H e satisfizer C.

[editar] Constraints Chave e Dependencias Funcionais

Um dos mais simples e mais importantes tipos de constraints relacionais é a constraint chave. Ela nos informa que em cada instância de um certo esquema relacinal as tuplas podem ser identificadas por seus valores por certos atributos.

Def. Uma superchave é escrita como um conjunto finito de nomes de atributos.

Def. Uma superchave K indica numa relação (H, B) se K ⊆ H e que não existem duas tuplas distintas t₁ e t₂ em B tais que t₁[K] = t₂[K].

Def. Uma superchave K indica num universo relacional U sob um cabeçalho H se ela indica em toda relação de U.

Def. Uma superchave K é indicada como uma chave candidata para um universo relacional U sobre H se ela é indicada como uma superchave para U e se não existe subconjunto próprio de K que também seja indicada como uma superchave para U.

Def. Uma dependência funcional (ou DF para abreviar) é escrita como X->Y com X e Y conjuntos finitos de nomes de atributos.

Este artigo encontra-se parcialmente em língua estrangeira. Ajude e colabore com a tradução.

Def. A functional dependency X->Y holds in a relation (H, B) if X and Y are subsets of H and for all tuples t₁ and t₂ in B it holds that if t₁[X] = t₂[X] then t₁[Y] = t₂[Y]

Def. A functional dependency X->Y holds in a relation universe U over a header H if it holds in all relations in U.

Def. A functional dependency is trivial under a header H if it holds in all relation universes over H.

Theorem A FD X->Y is trivial under a header H iff Y ⊆ X ⊆ H.

Theorem A superkey K holds in a relation universe U over H iff K ⊆ H and K->H holds in U.

Def. (Armstrong's rules) Let S be a set of FDs then the closure of S under a header H, written as S⁺, is the smallest superset of S such that:

(reflexivity) if Y ⊆ X ⊆ H then X->Y in S⁺

(transitivity) if X->Y in S⁺ and Y->Z in S⁺ then X->Z in S⁺

(augmentation) if X->Y in S⁺ and Z ⊆ H then X∪Z -> Y∪Z in S⁺

Theorem Armstrong's rules are sound and complete, i.e., given a header H and a set S of FDs that only contain subsets of H then the FD X->Y is in S⁺ iff it holds in all relation universes over H in which all FDs in S hold.

Def. If X is a finite set of attributes and S a finite set of FDs then the completion of X under S, written as X⁺, is the smallest superset of X such that:

if Y->Z in S and Y ⊆ X⁺ then Z ⊆ X⁺

The completion of an attribute set can be used to compute if a certain dependency is in the closure of a set of FDs.

Theorem Given a header H and a set S of FDs that only contain subsets of H it holds that X->Y is in S⁺ iff Y ⊆ X⁺.

Algorithm (deriving candidate keys from FDs)

      INPUT: a set S of FDs that contain only subsets of a header H
      OUTPUT: the set C of superkeys that hold as candidate keys in
              all relation universes over H in which all FDs in S hold
      begin
        C := ∅;          // found candidate keys
        Q := { H };      // superkeys that contain candidate keys
        while Q <> ∅ do
          let K be some element from Q;
          Q := Q - { K };  
          minimal := true;
          for each X->Y in S do 
            K' := (K - Y) ∪ X;   // derive new superkey
            if K' ⊂ K
            then
              minimal := false;
              Q := Q ∪ { K' };
            fi
          od
          if minimal and there is not a subset of K in C
          then
            remove all supersets of K from C;
            C := C ∪ { K };
          fi
        od
      end

Def. Given a header H and a set of FDs S that only contain subsets of H an irreducible cover of S is a a set T of FDs such that

1. S⁺ = T⁺
2. there is no proper subset U of T such that S⁺ = U⁺,
3. if X->Y in T then Y is a singleton set and
4. if X->Y in T and Z a proper subset of X then Z->Y is not in S⁺.

[editar] EXEMPLO

[editar] Tabela não normalizada

Atributos não atômicos ou contém tabelas aninhadas

Exemplo: Tabela de alocação de funcionários a projetos

Código do Projeto: 1 Tipo: Desenvolvimento

Descrição: Vagas

Código do Projeto: 2 Tipo: Administrativo

Descrição: Marketing

A seguinte tabela descreveria os dados acima apresentados: Projetos(codp, tipo, descrição, empregados(code, nome, categ, salário,data_início, tempo_aloc))

Tabela não normalizada empregados é um atributo não atômico.

[editar] Primeira Forma Normal

Definição (note que relacionamentos como são definidos acima são necessariamente na 1NF)

  "Uma tabela está na 1FN, se e somente se, não contiver tabelas aninhadas."

Definir relações NFNF

• como transformar relações NFNF (também chamadas relações UNF) em relações 1NF
  • como transformar as restrições chave de relações aninhadas
  • como transformar as dependências funcionais de relações aninhadas

Passagem à 1FN:

• Gerar uma única tabela com colunas simples
• Chave primária : id de cada tabela aninhada

Exemplo: Projetos(codp, tipo, descrição, code, nome, categ, salário, data_início, tempo_aloc)

Problemas:

• Redundância
• Anomalias de Atualização

[editar] Segunda Forma Normal

Definição:

   Uma relação está na 2FN se, e somente se, estiver na 1FN e cada atributo não-chave for dependente da chave primária inteira, isto é, cada atributo não-chave não poderá ser dependente de apenas parte da chave.

Passagem à 2FN:

• Geração de novas tabelas com DFs completas
• Análise de DFs:

  * tipo e descrição - DF de codp
  * nome, categ e salário - DF de code
  * data_início e  tempo_aloc - DF de toda a chave

Resultado:

• Projetos(codp, tipo, descrição)
• Empregados(code, nome, categ, salário)
• ProjEmp(codp, code, data_início, tempo_aloc)

Conclusões:

• Maior independência de dados (não há mais repetição de empregados por projeto, por exemplo)
• Redundâncias + Anomalias - DF indiretas

[editar] Terceira Forma Normal

• definição

“Uma tabela está na 3FN, se e somente se, estiver na 2FN e todo atributo não chave depende funcionalmente diretamente da  chave primária, ou seja, não há dependências entre atributos não chave”

Passagem à 3FN:

• Geração de novas tabelas com DF diretas

• Análise de DFs entre atributos não chave:

  - salário - DF de categ

Resultado:

• Projetos(codp, tipo, descrição)

• Empregados(code, nome, categ)

• Categorias(categ, salário)

• ProjEmp(codp, code, data_início, tempo_aloc)

Conclusões:

• Maior independência de dados

• 3FN gera representações lógicas finais na maioria das vezes

• Redundâncias + Anomalias - DF multivaloradas

[editar] Terceira Forma Normal - Boyce-Codde

• definição

Deve estar na 3º forma normal e não deve apresentar subconjuntos da chave candidata

• exemplo
• Como transformar da 3NF para BCNF
• Nem sempre pode ser alcançada preservando a dependência.

[editar] Multi-valued and Join Dependencies

• def multi-value dependencies
• exemplo
  • trivial multi-value dependency (X->>Y is trivial if X+Y contains all attributes or Y is a subset of X)
• reasoning rules for MVDs

• def join dependency
• example
• reasoning rules for JDs
• when is join dependency implied by key constraints?
• relacionamento entre JDs e MVDs

[editar] Quarta Forma Normal

Definição

   “Uma tabela está na 4FN, se e somente se, estiver na 3FN e não existirem dependências multivaloradas”.

Exemplo: Dados sobre livros

Relação não normalizada: Livros(nrol, (autor), título, (assunto), editora, cid_edit, ano_public)

1FN:        Livros(nrol, autor, assunto, título, editora, cid_edit, ano_public)
2FN:     Livros(nrol,título, editora, cid-edit, ano_public)
        AutAssLiv(nrol, autor, assunto)
3FN:     Livros(nrol, título, editora, ano_public)
        Editoras(editora, cid-edit)
        AutAssLiv(nrol, autor, assunto)

• Redundância para representar todas as informações
• Evitar todas as combinações: representação não-uniforme (repete alguns elementos ou posições nulas)

Passagem à 4FN:

• Geração de novas tabelas, eliminando Dependências Multivaloradas
• Análise de Dependências Multivaloradas entre atributos:
• autor, assunto  Dependência multivalorada de nrol

Resultado:

4FN: Livros(nrol, título, editora, ano_public)

       Editoras(editora, cid-edit)
       AutLiv(nrol, autor)
       AssLiv(nrol, assunto)

[editar] Quinta Forma Normal

• definição da 5NF

Está ligada a noção de dependência de junção. • Se uma relação é decomposta em várias relações e a reconstrução não é possível pela junção das outras relações, dizemos que existe uma dependência de junção. • Existem tabelas na 4FN que não podem ser divididas em duas relações sem que se altere os dados originais. • Exemplo: Seja as relações R1(CodEmp, CodPrj) e R2(CodEmp, Papel) a decomposição da relação ProjetoRecuro(CodEmp, CodPrj, Papel).

• exemplo
• Da 4FN para a 5NF
• Explanação de que a última forma norma pode ser alcançada com projeções

[editar] Forma Normal Chave-Domínio

• def de FNCD
• ultimate normal form
• degride normal form

[editar] Outras dependencias

• dependências encapsuladas
• dependencias como blocos em lógica de primeira ordem

This article was originally based on material from the Free On-line Dictionary of Computing, used with permission. Update as needed.