Databases
Normalização
P. Serendero, 2011-13
(Todos os exercícios do aeroporto e marina são nossos)
Normalização
Uma Base de Dados, para ser um modelo que bem represente a realidade,
precisa de de ser depurada de anomalias e outros problemas que se
presentam quando operamos nela:
Nas operações de: inserir, apagar, modificar, interrogar
As bases de dados são normalizadas igualmente para evitar redundâncias,
para proteger a integridade dos dados
Normalização
Utilizamos a Teoria da Normalização para fazer esta depuração.
Este processo utiliza
as dependências funcionais e
o conceito de chaves para “normalizar” uma base de dados no momento
da sua conceição
Vamos agora utilizar as dependências funcionais e outras restrições do
modelo para normalizar a base de dados
Normalização
O processo de depurar as relações dum dado esquema de BD relacional de maneira de eliminar anomalias, redundância e outros problemas.
Neste processo são utilizadas as dependências funcionais e as chaves primárias e estrangeiras para se certificar que um dado esquema de BD está numa determinada forma normal.
Existem pelo menos 6 Formas Normais, denominadas primeira forma normal, segunda forma normal,.., etc e que normalmente escrevemos como 1FN, 2FN, 3FN, 3FNBC, 4FN, 5FN.
Alguns autores identificam mais formas normais.
Normalização
1FN: Uma relação está na 1FN se e só se (see)
todos os seus atributos são atómicos
Portanto, não são permitidos grupos repetitivos (atributos com
multi valores). Cada coluna na tabela deve ter apenas 1 atributo
com 1 valor atribuído
Exemplo: pretendemos as seguintes relações
r1 (a1, a2, a3, {a4-a, a5, a6)
a4-b,
a4-c},
folha-de-voo (num, data, hora-saída, {tripulantes} , ..)
aluno(matricula, nome, curso, {disciplina, nota}, ...)
Normalização
Resolvemos esta anomalia particionando a relação com grupos repetitivos,
em duas relações onde os atributos são todos atómicos
Partilhamos a r1 por exemplo assim:
r1 (a1, a2, a3, a5, a6)
r2( a1, a4-valor)
(logo veremos como é a chave primária para r2)
Podemos agora inserir múltiplas valores para a4 respeitando a 1FN
A escolha de outra chave primária em r2 é possível, e depende dos
objetivos do domínio, mas a condição de manter a relação definida no
modelo gráfico DER
Normalização
Exemplo. Voltemos ao aeroporto. Tínhamos:
folha­de­voo (num, data, destino, hora­saída, {tripulantes} …)
Aplicando a 1FN, fazemos a descomposição da relação original: folha­de­voo (num,data, destino, hora­saída, data­chegada,...)
tripulantes_voo(num­folha­voo, id_tripulante, cargo)
Como se pode ver, fazendo a projeção da relação original em relações apropriadas, conseguimos obter relações normalizadas no respeitante a 1FN
As relações obtidas são equivalentes a relação original, no sentido que esta sempre se poderá recuperar mediante a união (natural) de essas projeções, de maneira de não perder informação com a redução
E como fazíamos na relação aluno ? (fazer como exercício)
Normalização
Chaves, atributos-chave, atributos não-chave
Um ou mais atributos {A1, A2, ...An } constituem uma chave numa
relação R, se:
1) Determinam funcionalmente todos os outros atributos na relação.
2) Nenhum subconjunto em {A1, A2, ...An } determina funcionalmente
todos os outros atributos da relação R. Isto é, uma chave deve ser
mínima na sua composição.
A esta denomina-se chave principal ou primária
Chaves candidatas: todos os conjuntos de 1 ou mais atributos que
qualificam como chave primária numa relação
Atributo-chave : aquele que participa numa chave candidata
Atributo não-chave: atributos que não estão presentes nas chaves
Também conhecidos como atributos primários e não primários
Normalização
Segunda Formal Normal (2FN)
Uma relação está na 2FN sse está na 1FN e todos os atributos não-chaves
são completa e funcionalmente dependentes de
toda a chave primária
Utiliza os conceptos de DFs, chave primária e atributo primário
Atributo primário – atributo membro da chave primária
Dependência funcional completa – uma DF Y  Z onde a remoção de qualquer atributo em Y, faz com que a DF já não é verdadeira
Portanto, no caso de chaves primárias múltiplas (super key), os atributos não­chave não podem depender parcialmente de um subconjunto da super key
Normalização
Segunda Formal Normal (2FN)
Utiliza o conceito de atributo principal e atributos não-chave
Exemplo:
A seguinte relação está na 1FN. Mas, está na 2FN?
folha-voo(id, data, destino, voo, id-capitão, nome-capitão,
telemóvel, num-tripulantes, hora-saída)
Quais atributos não-chave não dependem completamente da chave
principal?
Normalização
Tínhamos:
folha-voo(id, voo, data, destino, id-tripulante, nome-tripulante,
telemóvel, num-tripulantes, hora-saída)
Fizemos as projeções:
folha-voo(id, voo, data, destino, num-tripulantes, hora-saída)
tripulante(id-tripulante, nome, telemóvel, cargo)
tripulante-voo(id-folha-voo , id-tripulante)
Repare a chave composta da relação tripulante-voo
A projeção da relação original em 3 relações, normaliza a relação
original conforme a 1FN
Se fizermos a união destas 3 relações, voltávamos a informação
original. O processo é -deve ser- reversível
Normalização
Agora verifiquemos a 2FN. Tinhamos estas relações na 1FN:
folha-voo(id, voo, data, destino, num-tripulantes, hora-saída)
tripulante(id-tripulante, nome, telemóvel, cargo)
tripulante-voo(id-folha-voo, id-tripulante)
Existem as seguintes DF : voo → destino, num_tripulantes
Isto é, existem atributos não-chave que não dependem da chave primária.
Portanto, esta relação não está ainda na 2FN.
Projectando:
folha-voo(id, voo, data, num-tripulantes, hora-saída)
voo (id_voo, destino, num-tripulantes, data-prevista, altura-de-voo)
Normalização
Assim teríamos,
tripulante(id-tripulante, nome, telemóvel, cargo)
tripulantes-voo(id-folha-voo , id-tripulante)
folha-voo(id, id-voo, data, num-tripulantes, hora-saída)
voo (id_voo, destino, num-tripulantes, data-prevista, altura-de-voo)
Mas, como este voo se faz x vezes por semana, data-prevista não é um
atributo atómico e temos que normalizar ainda:
voo (id_voo, destino, num-tripulantes, altura-de-voo)
data-voo(id-voo,data-prevista)
Normalização
Assim temos finalmente:
tripulante(id-tripulante, nome, telemóvel, cargo)
tripulantes-voo(id-folha-voo , id-tripulante)
folha-voo(id, id-voo, data, num-tripulantes, hora-saída)
voo (id_voo, destino, num-tripulantes, altura-de-voo, duração)
data-voo(id-voo, data-prevista)
As relações estão todas na 2FN (e portanto na 1FN).
Todos os atributos não-chave dependem funcionalmente da chave
primária
Normalização
Lembrando os Diagramas de Entidade-Associação:
As relações anterior podem ser expressadas gráficamente no seguinte DEA:
voo
1
*
tem
data­prevista
realiza
folha­voo
1
id­folha­voo
tem
*
tripulante
id­tripulante
Normalização
Alternativamente:
id­voo
voo
1
data­prevista
realiza
bi
*
folha­voo
1
tem
*
tripulante
num
id­folha­voo
id­tripulante
Normalização
Dependências funcionais e preservação da informação
A normalização utiliza projeção para eliminar dependências funcionais
complexas (em SQL, corresponde em geral a instrução SELECT, com a excepção que
o query pode devolver tuplos duplicados)
A recomposição e feita mediante operações de JOIN (uniões)
A descomposição duma relação R1,..Rn é “nonloss” se
R = a união de R1,..Rn
Isto é, se não há perda de informação
As normalização pode ser vista como o processo de eliminar
dependências funcionais que não se originam nas chaves candidatas
Normalização
O que quer dizer na 2FN : “... de toda a chave primária”
O que quer dizer isto? O caso das chave primárias compostas
Ex.: A dependência funcional (A, B) → C
neste caso exige que C seja totalmente dependente de TODA a chave primária
(super key) A e B.
Caso contrário a dependência funcional não existe e a relação não esta na
2FN
Portanto uma consequência desta definição de 2FN é que
(AB) → C deve ser verdadeira, porque pode ser o caso que alguma das
dependências A → C ou B → C não sejam DFs nesta relação
Outra consequência é que uma relação na 2FN com 1 atributo como chave
primária está assegurada de não ter outras dependências indesejadas
Normalização
Exemplo:
Imagine que data-voo do exemplo anterior era assim:
data-voo(id-voo, data-prevista, hora, dia-semana)
Onde a chave primária é {id-voo + data-prevista}
Nesta relação existe a DF: data-prevista → dia-semana
Existe dependência parcial de dia-semana a com uma parte do
determinante.
A 2FN NÃO aceita esta situação: os atributos não-chave devem
depender total e funcionalmente de TODA a super key
Normalização
Exemplo: Normalizemos a seguinte relação
campeões-ténis(torneio, ano, pais, campeão, superficie, data_final, idade)
DF
torneio, ano → campeao
torneio, ano → superficie
torneio, ano → data_final
torneio → pais torneio → superficie
campeão → idade
Imagine que temos escolhido (torneio + ano) como chave candidata.
Existem nesta relação dependências parciais e dependências transitivas
Parciais: superficie depende apenas do torneo
Transitivas: a idade depende do campeão o qual pela sua vez depende de
torneio e ano.
Normalização
Ex. campeões-ténis(torneio, ano, pais, campeão, superficie, data_final, idade)
DF
torneio, ano → campeao
torneio, ano → superficie
torneio, ano → data_final
torneio → pais
torneio → superficie
campeão → idade
Podíamos fazer as seguintes projeções para eliminar dependências indesejadas:
campeões-ténis(torneio, ano, campeão, data-final)
torneio(torneio-id, superficie, pais)
campeão( campeão, idade, nacionalidade)
As Rs estão na 2FN
(Ainda podíamos considerar campião-id ou nome como chaves candidatas
na relação campeão)
Normalização
Nem todas as relações nas quais os atributos não chave não mostram
dependências parciais estão na 2FN
Os atributos não-chaves (ou não primários) também não devem ter
dependências parciais com qualquer atributo de outras chaves candidatas
existentes na mesma relação
Múltiplas chaves candidatas acontecem por exemplo na seguinte relação de
tipos de barcos:
tipos-barcos(nome-completo-modelo, construtor, modelo, pais-constructor)
chaves candidatas: (nome-completo-modelo), (construtor, modelo)
Existe a seguinte DF: construtor → pais-constructor
O que seria preciso fazer neste caso para ter esta r em 2FN?
Normalização
Tínhamos
tipos-barco(nome-completo-modelo, construtor, modelo, pais-construtor)
DFs:
construtor → pais-construtor
nome-completo-modelo → modelo
nome-completo-modelo → construtor
construtor → nome-completo-modelo
modelo, construtor → nome-completo-modelo
Projectando:
r1(construtor, pais-construtor)
r2( nome-completo-modelo, modelo, construtor)
chaves candidatas?
Normalização
Anomalias na 2FN: Voltemos as relações obtidas no domínio do
aeroporto
folha-voo(id, voo, data, destino, num-tripulantes, hora-saída)
tripulante(id-tripulante, nome, telemóvel, cargo)
tripulantes-voo(id-folha-voo + id-tripulante)
Na relação folha-voo, o atributo não primário 'destino' não depende
da chave primária id.
Ele é um atributo que depende funcionalmente de voo que pela sua
vez é parcialmente uma chave candidata (voo+data)
Estes são problemas resolvidos na 3FN
Normalização
Terceira Formal Normal (3FN)
Uma relação está na 3FN see:
a) está na 2FN
b) todos os atributos não-chaves não são transitivamente dependentes da
chave primária. (Date)
Dependência transitiva:
Uma dependência funcional na qual X → Z indiretamente no caso quando
X → Y, Y → Z sempre que não se der a dependência funcional Y → X
Por transitividade, X → Z
Ex: item-factura(num-factura, id-produto, preço-unit, quantidade, total-linha)
Existem as DF: (num_factura,id-produto) → preço-unitario, quantidade
preço-unitario, quantidade → total-linha
Repare que na 3FN estamos lidando com dependências transitivas de atributos
não-chave (não primários)
Normalização
Dependência transitiva:
Repare que uma relação em 3NF com mais que uma chave candidata,
terá nitidamente dependências transitivas do tipo:
chave primária → outra chave candidata
outra chave candidata → qualquer atributo não chave
Relações com apenas 1 chave candidata, estão na 3FN sse os atributos não
chave são mutualmente independentes e são completamente dependentes da
chave principal
Atributos mutualmente independentes: acontece entre dois o mais atributos que
não são funcionalmente dependentes entre eles
Normalização
Normalizando para a 3FN as relações do aeroporto teríamos:
voo(código-voo, co-aérea, destino, tipo-avião, data, hora-saída, duração-voo,
hora-chegada)
tripulante(id-tripulante, nome, co-aerea, telemóvel, cargo)
folha-voo(id, codigo-voo, data-real-voo, num-tripulantes, hora-saída-real)
(repare que aqui a chave primária podia tb ser: codigo-voo + data-real-voo)
tripulantes-voo(id-folha_voo, id-tripulante)
A 3FN está formada por uma chave primária que identifica a entidade, e um ou
mais atributos não-chaves na 2FN e sem dependências transitivas.
Normalização
3FN. Outro exemplo:
embarcação(matricula, nome, cod-proprietario, cod-modelo, boca, comprimento)
Existem (entre outras) as DF: matricula → cod-modelo
cod-modelo → boca, comprimento
Portanto temos uma dependência transitiva. matrícula → boca, comprimento
Projectando para conformar as relações com a 3FN:
embarcação (matricula, nome, cod-proprietario, cod-modelo)
modelo(cod-modelo, boca, comprimento)
Todos os atributos não-chave são mutuamente independentes e todos eles
dependem completamente da chave principal
Normalização
Terceira Forma Normal Boyce-Codd conhecida como “BCNF”
Uma relação está na BCNF see cada determinante nela é uma chave candidata
A BCNF se ocupa da descomposição em relações onde existem várias chaves
candidatas compostas e ainda justapostas
Justapostas: duas chaves candidatas compostas partilham pelo menos 1
atributo em comum. A,B e B,C são candidatas justapostas por ex.
Isto é, na FNBC todas as chaves candidatas são determinantes
(Determinante: um(uns) atributo(s) do qual dependem funcionalmente
(completamente) todos os outros atributos numa relação
Mais informalmente, todos os lados esquerdos das DF existentes na relação
são chaves candidatas
Normalização
Identificando uma relação na BCNF
Considere a seguinte relação R e dadas as seguintes DFs
R(A,B,C,D) com DFs:
1) (A,C) → B, D
2) (A,D) → B
A primeira DF indica-nos que poder-íamos ter AC como determinante. Todos
os outros atributos em R seriam determinados pela chave primária
Só que a segunda DF indica que AD determina B, mas AD não determina
todos os atributos na relação, nomeadamente C.
A,D não pode ser o determinante.
Neste caso a primeira DF (determinante) é uma chave candidata mas não a
segunda. Pelo tanto esta relação não está na BCNF (está sim na 3FN)
BCNF vs 3NF
Geralmente uma relação na 3FN está também na BCNF.
A BCNF é considerada um caso especial da 3FN
Uma tabela pode estar na 3FN e não na BCNF quando um atributo
não chave (C) é determinante dum atributo que faz parte duma
chave(B)
A
B
C
D
É dificil na prática de encontrar relações que tenham todas as
características da BCNF:
varias chaves candidatas,
elas são compostas e
algumas delas superpostas (tem pelo menos 1 atributo comum)
BCNF exemplo
num-cliente
data-marcação
hora-marcação
id-medico
gabinete
M-012
13-10-13
10:00
pmartins
2.43
P-018
13-10-13
11:00
pmartins
2.43
A-290
15-10-13
10:30
jduarte
1.24
P-018
15-10-13
10:00
pmartins
1.24
Dependências funcionais existentes:
1) num-cliente, data-marcação → hora-marcação, id-medico, gabinete
2) id-medico, data-marcação, hora-marcação → num-cliente
3) gabinete, data-marcação, hora-marcação → num-cliente, id-medico
4) data-marcação, hora-marcação → gabinete BCNF exemplo
Para remover as anomalias poderíamos projetar a relação em duas:
Existiriam ainda anomalias após fazer o seguinte?
r1) entrevista(num-cliente, data-marcação, hora-marcação, id-medico)
r2) gabinete-ocupação(id-medico, data-marcação, hora-marcação, gabinete)
Estão normalizadas
estas projeções?
num-cliente
data-marcação hora-marcação id-medico
M-012
P-018
A-290
13-10-13
13-10-13
15-10-13
10:00
11:00
10:30
pmartins
pmartins
jduarte
P-018
15-10-13
10:00
pmartins
id-medico
data-marcação
hora-marcação
gabinete
pmartins
13-10-13
10:00
2.43
pmartins
13-10-13
11:00
2.43
jduarte
15-10-13
10:30
1.24
pmartins
15-10-13
10:00
1.24
Como faziamos para
simplificar estas
relações?
Normalização
Terceira Forma Normal Boyce-Codd: FNBC
Cada FN é uma definição mais estrita que a anterior:
Cada relação tem que estar na 1FN
Cada relação na 2FN tem que estar na 1FN
Cada relação na 3FN tem que estar na 2FN
Existem relações em 3FN que não estão na BCNF
Os objectivos (standard) da normalização são que as relações estejam
na BCNF ou minimamente na 3NF.
Isto é o que se considera uma relação normalizada
Normalização: exemplo BCNF
Imaginemos uma R(fornecedor)
fornecedor(número, nome, nível, cidade)
O número do fornecedor, o seu nome, um nível de qualificação deste fornecedor e a cidade
onde fica. Assume-se que o nome dos fornecedores é único e que cada um fica só numa
cidade
numero
f1
nome
Ramos
nivel
20
cidade
Faro
f2
Lopes
10
Porto
f3
Garrãio
30
Lisboa
f4
Gonçalves
10
Guimarães
Claves candidatas: número e nome (portanto estes valores são únicos)
Os atributos 'nível' e 'cidade' são independentes entre eles.
número
nível
Diagrama de DF's
nome
cidade
Fonte: C.J.Date
BCNF ?
Normalização: exemplo BCNF
Imaginemos uma R onde as chaves se justapõem: cada uma tem dois ou mais
atributos e pelo menos um destes é comum
f1
numerof
f2
nome
Ramos
num-peça
P1
quantidade
300
Lopes
P1
250
f3
Garrãio
134
4
f4
Gonçalves
P14
10
Claves candidatas: (número-f, num-peça) e (nome, num-peça)
BCNF ?
Não, porque tem dois determinantes: número-f e nome que não são claves candidatas
Eles são determinantes porque cada um determina o outro
Esta tabela tem redundâncias que dificultam as atualizações: por ex. Mudar o
nome do fornecedor
A tabela está na 3FN: um atributo, se faz parte de uma chave candidata não
precisa de depender de toda a chave primária: nome não depende
completamente de (número, num-peca) Fonte: C.J.Date
Normalização: exemplo BCNF
Solução para esta relação?
Podíamos descompor nas projeções:
fornecedor (número, nome, nível) e
peça( num-peça, nome, quantidade)
Alternativamente:
e assumindo nome como chave candidata
fornecedor(número, nome, nível)
peças(nome, num-peça, quantidade)
Fonte: C.J.Date
Normalização
Quarta Forma Normal 4FN
(Fagin, 1977)
Uma tabela está na 4FN sse, para cada uma das suas dependências multi-valor
(multivalued) X -->> Y, X é uma super chave,
Isto é, X é uma chave candidata o um super conjunto dela.
imagine 3 grupos disjuntos de atributos X,Y e Z numa tabela, e os valores x,y,z
num tuplo qualquer.
Se computamos num tuplo qualquer o valor de x, e compilamos todos os
valores possíveis xyz que aparecem na tabela, encontraremos que o valor x está
associado com o mesmo valor de y, independentemente do valor de z
A esto chamamos a dependência multi-valor X -->> Y
Normalização
Quarta Forma Normal 4FN
Esta forma normal não está directamente associada com DFs mas com dependências
multi-valor. Um tipo de redundância que se pode apresentar.
Acontece quando apresentamos na mesma relação dois ou mais conjuntos
multi-valor X -->> Y
disciplina
professor
livro
fisica
paulo
Mecanica I
Disciplina leccionada por qualquer professor. Podem ser vários. fisica
paulo
Optica
fisica
luisa
Mecanica I
fisica
luisa
optica
Utiliza os livros indicados
matemáticas
paulo
vectores
matemáticas
pedro
trigonometria
matemáticas
pedro
Analise vectorial
Exemplo (redundância!)
Professores e textos são independentes entre sim
Professores e livros podem se associar com qualquer disciplina
Normalização: 4FN
Esta relação mesmo com problemas, está na BCNF: é só chaves
Para adicionar um novo docente de Matemáticas teriamos que adicionar mais 3 tuplas
uma para cada livro de texto.
O problema aqui é que os professores e livros são independentes entre eles. A situação
podería melhorar se projetáva a relação em duas:
disciplina-Professor( disciplina, professor)
e
disciplina-Livro( disciplina, livro)
disciplina
professor
disciplina
livro
fisica
paulo
fisica
paulo
fisica
luisa
fisica
luisa
matemáticas
paulo
fisica
fisica
fisica
fisica
matemáticas
Mecanica I
Optica
Mecanica I
optica
vectores
matemáticas
pedro
matemáticas
trigonometria
matemáticas
pedro
matemáticas
Analise vectorial
Estas relações estão na BCNF. Mas não podem se fazer baseadas em DF. Se podem fazer baseadas em dependências multi­valor (DMV)
Normalização
Quarta Forma Normal 4FN: baseadas em DMV
DMV: dada uma relação R, ela é DMV X →>> Y
se quando fixamos o valor dos atributos em X, os valores nos atributos em Y são independentes dos restantes atributos da relação
Formalmente, uma R é DMV se:
Para cada par de tuplos de R, t e u, que tenham os mesmos valores para os componentes dos atributos X, pode existir um outro tuplo z em R tal que:
­ z tem os mesmos componentes que t e u nos atributos X
­ z tem os mesmos componentes que t nos atributos Y ­ z tem os mesmos componentes que u nos restantes atributos de R(atrib(R) – X – Y) Normalização
Quarta Forma Normal 4FN: baseadas em DMV
Dados 2 tuplos que tenham os mesmos componentes em X, podemos trocar os componentes em Y e obtemos um tuplo que tem que existir em R
X
Y
Tomado dos apontamentos do Prof. Lobo
outros
Normalização 4FN
disciplina
professor
Livro
Fisica
Paulo
Mecánica I
Fisica
Paulo
Optica
Fisica
Luisa
Mecánica I
Fisica
Luisa
Optica
Matemática
Paulo
Mecánica I
Matemática
Paulo
Análise vectorial
Matemática
Paulo
Trigonometría
DMV’: disciplina ­­>> professor | livro , porque
Dada R(D,P,L) a DMV D ­­>> P se cumpre see também
se cumpre a DMV D ­­>> L.
As DMV só podem existir em R com pelo menos 3 atributos
Normalização 4FN
Quarta Forma Normal 4FN
Uma relação R está na 4FN se sempre que existir uma
DMV X -->> Y não trivial, X for a superchave de R
Uma dada relação R que esteja na 4FN, também está em
BCNF
porque uma violação da BCNF é também uma violação da
4FN
Normalização
Resumindo e concluindo,
Para estar em 1FN uma relação deve conter só valores atómicos
Para estar em 2FN uma R tem todos os atributos não chave dependentes total
e funcionalmente da chave primária, e não contem qualquer DF parcial
no caso de superchaves
Para estar na 3FN, uma R está na 2FN e não tem DF transitivas entre
atributos não chaves
Para estar na 3FNBC cada determinante deve ser uma chave candidata
Para estar na 4FN todas as relações DMV devem ser de facto DF’s
O processo de normalização
Remover
atributos
não atómicos
tabelas
Remover
dependências
transitivas
1FN
2FN
3FN
Todos os determinantes são
chaves candidatas
3FNBC
4FN
Remover
dependências
parciais
Remover anomalias
de dependências
não funcionais
Normalização
Fim Normalização