Dependências Funcionais
e
Formas Normais
Formas Normais
Pedro Sousa
1
Introdução
 As dependências funcionais e as formas normais estabelecem
critérios de qualidade de desenho no modelo Relacional.
 Permitem detectar e prevenir a redundância e garantir a coerência
da informação.
 Fundamenta-se nas dependências entre os atributos das relações
 Ao nível do modelo Relacional, deve ser usado para detectar
eventuais problemas associados à redundância e coerência da
informação.
 Ao nível do modelo Entidade Associação, deve ser usado para
identifcar entidades e determinar os seus atributos.
Formas Normais
Pedro Sousa
2
O problema da Redundância dos Dados
 A redundância dos dados tem implicações ao nível da coerência
e da completude da informação neles contidas
 São bem conhecidos os seguintes problemas, designados por
anomalias:
 Anomalia de inserção: quando os factos (conhecimento)
independentes não podem ser inseridos independentemente na
base de dados.
 Anomalia de eliminação: quando se elimina uma instância de um
facto, perde-se instâncias de outros factos independentes.
 Anomalia de actualização: quando a actualização de um facto
implica a alteração de uma série de instâncias de outros factos
independentes.
Formas Normais
Pedro Sousa
3
Exemplo Introdutório
Consideremos a seguinte Entidade /Relação
Encomenda
Quantidade
Nº Encomenda
Encomenda
NºEncomenda | Nº Peça | Quantidade| Preço Unitário
Nº da Peça
|
|
|
|
|
|
Preço Unitário
 Anomalia de inserção: Só podemos indicar o preço de cada
peça se existirem encomendas pendentes.
 Anomalia de eliminação: Ao eliminar uma encomenda, perde-se
a informação relativa ao preço de cada peça.
 Anomalia de actualização: A alteração do preço de uma peça
implica a alteração do mesmo em todas as encomendas
existentes.
Formas Normais
Pedro Sousa
4
Exemplo Introdutório
Dependências Funcionais
Encomenda
Quantidade
Nº Encomenda
Encomenda
NºEncomenda | Nº Peça | Quantidade| Preço Unitário
Nº da Peça
|
|
|
|
|
|
Preço Unitário
 O problema reside nas relações
de dependências entre os
atributos da Entidade/Relação:
 o Nº da encomenda determina
Nº da peça, a Quantidade e o
Preço Unitário.
 O Nº da peça determina o
Preço Unitário.
Formas Normais
Diagrama de Dependências Funcionais
Quantidade
Nº Encomenda
Preço Unitário
Nº Peça
Pedro Sousa
5
Diagrama de Dependências Funcionais
Outro Exemplo
Que informação está contida neste
Diagrama de Dependências Funcionais?
Nome-Director
Endereço-Armazém
Nome-Armazém
Peça Nº
Nome-Fornecedor
Data-Inventário
QuantidadeEntregue
QuantidadeExistente
Formas Normais
Pedro Sousa
Nº-Encomenda
De que modo essa informação
pode ser útil no desenvolvimento
de esquemas Relacionais ou
mesmo Conceptuais (ER)?
6
Dependência funcional
 Seja uma relação R com conjuntos de atributos X e Y:
Diz-se que X determina Y se para todo o valor
de X existe um só valor de Y.
 Por outras palavras, sempre que dois tuplos têm um valor de X
comum, têm também o valor de Y em comum.
 Diz-se também que X é determinante, e representa-se
graficamente por X-> Y.
 A dependência funcional é um questão semântica. Não pode ser
deduzida com base num conjunto de tuplos. Estes apenas podem
confirmar que determinada dependência não existe.
 X é uma super-chave se X->R, sendo R o conjunto de todos os
atributos da relação R
Formas Normais
Pedro Sousa
7
Propriedades das Dependências Funcionais
(regras de Armstrong)
 Reflexividade
 Se Y está contido em X, então X-> Y
 Incremento
 Se X -> Y, então X Z -> YZ
 Transitividade
 Se X -> Y e Y -> Z, então X-> Z
Formas Normais
Pedro Sousa
8
Regras Derivadas
 Auto-Reflexividade
 X -> X
 Decomposição
 Se X -> Y Z, então X-> Y e X -> Z
 União
 Se X-> Y e X -> Z então X -> YZ
 Composição
 Se X-> Y e A -> B então XA -> YB
Formas Normais
Pedro Sousa
9
Dependência total e atributos chaves
• Seja X um atributo e Y o conjunto de atributos { y1, y2, ...yn} tal
que {y1, y2, ...yn} determina X, i.e. {y1, y2, ...yn} -> X
•Dizemos que X é completamente dependente de Y, se qualquer
subconjunto dos elementos de Y não determina X.
•Dizemos que X é um atributo chave se pertence ao
identificador da Entidade ou à chave primária da Relação
Formas Normais
Pedro Sousa
10
As Formas Normais
1 Forma Normal
2 Forma Normal
3 Forma Normal
Forma Normal Boyce Codd
4 Forma Normal
5 Forma Normal
Formas Normais
Pedro Sousa
11
As Formas Normais
Seja uma entidade (ou associação) X com atributos
{i1,..,in, a1,...,am}
Seja {i1,..,in} os atributos que constituem a chave de X.
 A 1ª Forma Normal prende-se com a estrutura de cada
atributo de X.
 A 2ª Forma Normal prende-se com a dependência entre os
atributos {a1,...,am} e os atributos {i1,..,in}.
 A 3ª Forma Normal prende-se com as dependências
mútuas entre os atributos {a1,...,am}.
 A BCNF prende-se com a existência de várias chaves
Formas Normais
Pedro Sousa
12
1ª Forma Normal
Uma relação está na 1ª Forma normal se todos os
seus atributos são valores escalares.
 Todas as relações “normalizadas” estão na 1ª Forma Normal
“Relação” não Normalizada
Relação Normalizada
Pessoa
Residência
Pessoa
Cidade
João
Cidade Data
Lisboa 01-02-92
Faro 11-12-94
João
Lisboa
01-02-92
João
Faro
11-12-94
Zé
Lisboa
10-10-84
Zé
Formas Normais
Cidade Data
Lisboa 10-10-84
Pedro Sousa
Data
13
Problemas com a 1ª Forma Normal
Exemplo
 A 1ª FN não assegura a resolução do problema das anomalias!
ID_Pessoa
| Projecto | OrçamentoProjecto | TempoGastoProjecto
|
|
|
|
|
|
ID_Pessoa
Projecto
TempoGastoProjecto
OrçamentoProjecto
 Esta relação está na 1ª FN mas apresenta as anomalias de
inserção, de actualização e de eliminação!
Formas Normais
Pedro Sousa
14
Eliminação das Anomalias
do Exemplo Anterior
 A eliminação das anomalias implica a fragmentação da relação
inicial em duas novas relações
ID_Pessoa
| Projecto | TempoGastoProjecto
|
|
|
|
ID_Pessoa
Projecto
Projecto | OrçamentoProjecto
|
|
Projecto
OrçamentoProjecto
TempoGastoProjecto
 Estas relações já não têm as anomalias !
Formas Normais
Pedro Sousa
15
A 1ª Forma Normal e os Modelos Conceptuais
 Qual a relação entre os atributos multivalor, os atributos
compostos e a 1ª Forma Normal ?
Nº Encomenda
Nr-da-Peça
Identificação
Ano
Encomenda
 Em ambos os casos, os atributos Nr-da-Peça e identificação
não são atributos escalares!
 Esta é a razão pela qual a conversão ER para Relacional
implica a conversão dos atributos multivalor e compostos em
atributos simples
Formas Normais
Pedro Sousa
16
A 2ª Forma Normal
Uma Relação está na 2ª Forma normal se está na 1ª
Forma Normal e cada atributo não chave é
completamente dependente dos atributos chave.
 Ou seja, todos os atributos que não pertencem a nenhuma
chave são completamente dependentes de pelo menos uma
chave.
 Todas as relações na 1FN e com uma chave simples estão
necessariamente na 2FN.
 Nada se diz quanto às dependências mútuas entre os atributos
que pertencem às chaves.
 Nada se diz quanto às dependências mútuas entre os atributos
que não pertencem às chaves.
Formas Normais
Pedro Sousa
17
2ª Forma Normal
Exemplo 1
Consideremos a Relação R(A,B,C,D) e a dependência A -> D
(as dependências AB ->C e AB ->D são implícitas)
 Esta relação não está na 2ª FN.
 A decomposição da relação R com vista à 2ª FN passa por criar
as seguintes Relações:
 R1(A,B,C) com a dependência AB -> C
 R2(A,D) com a dependência A -> D
cada atributo não chave é completamente dependente
dos atributos chave
Formas Normais
Pedro Sousa
18
2ª Forma Normal - Exemplo 2
Estudante
Nº
Estudante
Nº
Professor
Exame
Cadeira
Nota
Exame
Nome
Cadeira
Nota
Professor
Nome
Exame não está na 2FN
Exame está na 2FN
Exame( Nº-Estudante,Nome-Cadeira, Professor,Nota)
Dependências da relação Exame:
Nº-Estudante, Nome-Cadeira
Professor,Nota
Nome-Cadeira
Professor
O atributo Professor não pode ser atributo de Exame!
Formas Normais
Pedro Sousa
19
2ª Forma Normal – Exemplo 3
 Cada encomenda refere-se apenas a uma quantidade de uma
única peça.Considere a Relação (ou Entidade) Encomenda.
Encomenda(NrEncomenda, NºPeça,PreçoUnitário,
Quantidade,PreçoTotal)
Quantidade
NrEncomenda
Encomenda
Preço Total
Nº da Peça
Preço Unitário
Quantidade
NrEncomenda
Preço Unitário
Preço Total
 Esta Entidade/Relação está na 2ª Forma Normal ?
Formas Normais
Pedro Sousa
Nº Peça
20
Problemas com a 2ª Forma Normal
 As 2ª Forma Normal não
garante a não redundância da
informação, sendo portanto
possível que os problemas das
anomalias existam também
nas relações na 2FN.
 Por exemplo, a informação
sobre o preço de cada peça.
Preço Total
Quantidade
NrEncomenda
Preço Unitário
 A redundância surge devido às
dependências entre os
atributos não chave.
Formas Normais
Nº Peça
Pedro Sousa
21
Eliminação das Anomalias
 A eliminação das anomalias implica a eliminação das dependências
entre os atributos não chave.
 Tal implica a decomposição da Entidade/Relação original em duas.
Preço Total
Preço Total
Quantidade
NrEncomenda
Quantidade
Nº Peça
NrEncomenda
Preço Unitário
Nº Peça
Nº Peça
Estão na 2FN
Está na 2FN
Formas Normais
Preço Unitário
Pedro Sousa
22
A 3ª Forma Normal
Uma Relação está na 3ª Forma normal
se todos os atributos não chave são completamente
dependentes dos atributos chave
e são independentes entre si.
 Ou seja, a 3FN implica a 2FN e que não existam dependências
entre os atributos não chave.
 Todas as relações que apenas têm um atributo não chave estão
na 3FN, se estiverem na 2FN.
 Nada se diz quanto às dependências mútuas entre os atributos
que pertencem às chaves.
Formas Normais
Pedro Sousa
23
3ª Forma Normal: Exemplo 1
Consideremos a Relação R(A,B,C) e a dependência B-> C
 Esta relação não está na 3ª FN.
 A decomposição da relação R com vista à 3ª FN passa por criar
as seguintes Relações:
 R1(B,C) com a dependência B -> C
 R2(A,B) com a dependência A -> B
cada atributo não chave é completamente independente
dos restantes atributos não chave
Formas Normais
Pedro Sousa
24
3ª Forma Normal: Exemplo 2
Nº Empregado
Empregado
Nome
Nome
Empregado
Nº Empregado
Do
v
Departamento
Departamento
Departamento
Divisão
Chefe
Da
Divisão
não está na 3FN
Nº Empregado
Divisão
Nome, Departamento, Divisão,Chefe
Departamento
Divisão
Chefe
está na 3FN
Divisão
Chefe
Formas Normais
Pedro Sousa
25
3ª Forma Normal: Exemplo 3
Nº Empregado
Empregado
Nome
Nº Horas
Trabalha
Nº Horas
Orçamento
Trabalha
Nº Projecto
Departamento
Nº Projecto
Projecto
Orçamento
Nº Departamento
Piso
Trabalha( Nº Empregado, Nº Departamento, Orçamento, Nº Horas, Nº Projecto)
Trabalha não está na 3FN, porque Projecto determina Orçamento e não é chave
Nº Empregado, Nº Departamento
Nº Projecto
Formas Normais
Orçamento, Nº Horas, Nº Projecto
Orçamento
Pedro Sousa
26
Problemas com a 3ª Forma Normal
Seja a Entidade/Relação X
com os seguintes atributos
e chaves
a1
X
a2
a3
a4
 Os problemas da 3FN surgem
quando:
 Existem dependências entre os
atributos das chaves, por exemplo:
a3
a1
a3
 Existem várias chaves compostas,
com pelo menos um atributo comum,
por exemplo:
X(a1, a2, a3, a4)
Formas Normais
a1
Pedro Sousa
a1,a2
a3,a4
a3,a2
a1,a4
27
Problemas com a 3ª Forma Normal: Exemplo
Relação Usa
Director
Projecto | Director | Peça | Quantidade
|
|
|
|
|
|
Peça
Quantidade
Projecto
Problemas:
 O director de cada projecto é armazenado
várias vezes
 O director de um projecto só é armazenado
quando o projecto encomendar peças
 Um projecto não pode ser armazenado
enquanto o seu director não for conhecido
 A mudança de um director de um projecto
implica a mudança de vários tuplos
Formas Normais
Pedro Sousa
Estes problemas resultam de:
• peça ser partilhada por
determinantes, e
• dependência entre Director e
Projecto
28
A Forma Boyce Codd
(BCNF)
Uma Relação está na BCNF quando todos os determinantes
são chave
 Não existem dependências entre os atributos não chave
 Não existem dependências entre sub-conjuntos dos atributos
das chaves.
 A BCNF só se distingue da 3FN quando:
 Existe mais do que uma chave
 As chaves são formadas por vários atributos
Formas Normais
Pedro Sousa
29
Exemplo -1
Chaves Disjuntas
 Seja a Relação Fornecedor :
F#
Estado
Nome
Cidade
Fornecedor (F#, Nome, Estado, Cidade)
 Em que FN esta Relação está ?
 Que anomalias são possíveis na relação Fornecedor ?
 Que inconvenientes resultam da existência de 2 chaves
candidatas ?
Formas Normais
Pedro Sousa
30
Exemplo - 2
Chaves Sobrepostas
 Seja a Relação Venda :
F#
Venda (F#, P#, Fnome,Quantidade)
P#
Quantidade
FNome
 Em que FN esta Relação está ?
 Que anomalias são possíveis na relação ?
 Quais são as decomposições mais convenientes ?
Formas Normais
Pedro Sousa
31
Exemplo -3
 Seja a Relação Aulas :
Aluno
Aulas (Disciplina,Professor,Aluno)
Professor
Disciplina
 Em que FN esta Relação está ?
 Que anomalias são possíveis na relação ?
 Quais são os inconvenientes das seguintes
decomposições ?
 V1 (Aluno,Professor) e V2 (Professor,Disciplina)
 V1 (Aluno,Disciplina) e V2 (Professor,Disciplina)
 V1 (Aluno,Disciplina) e V2 (Professor,Aluno)
Formas Normais
Pedro Sousa
32
Notas sobre a decomposição de
Relações/Entidades
 A decomposição de uma relação ou entidade com
vista à sua normalização pode implicar a perda de
informação.
O Problema da Perda de Informação
 Entre as decomposições que não implicam a perda
de informação, importa decidir sobre a mais correcta.
O Problema da Perda das Dependências
Formas Normais
Pedro Sousa
33
Decomposição com perdas de informação
 Seja R1(A,B,C), e A-> B e C-> B.
 Consideremos a decomposição de R1 em R2(A,B) e R3(B,C) ,e a
sua posterior restituição em R´1. Existe perda de informação!
R´1
R1
R3
A |B |C
a1 | b1 | c1
a3 | b1 | c2
a2 | b2 | c3
a4 | b2 | c4
b1 | c1
A |B
b1 | c2
a1 | b1
b2 | c3
a3 | b1
b2 | c4
a2 | b2
a1 | b1 | c2
a3 | b1 | c1
a3 | b1 | c2
a2 | b2 | c3
Junção
a2 | b2 | c4
a4 | b2 | c3
a4 | b2
Formas Normais
a1 | b1 | c1
B |C
Decomposição
R2
A |B |C
a4 | b2 | c4
Pedro Sousa
34
Decomposição sem perdas de informação
 A decomposição de uma relação diz-se sem perdas
(lossless-join decomposition) quando esta pode ser
obtida a partir do join natural das relações
resultantes da decomposição
 A decomposição de uma relação R(X,Y,Z) (em que X,
Y, Z são conjuntos de atributos) em R1(X,Y) e
R2(X,Z) é sem perdas se X->Y ou se X->Z. (Teorema
de Heath´s)
Formas Normais
Pedro Sousa
35
Decomposição sem perdas de Informação:
Exemplo
R1: X-> Y, X-> Z, YZ-> X
R3: X-> Z
X |Y |Z
x1 | y1 | z1
Decomposição
R´1
X |Z
x1 | z1
X |Y |Z
x2 | y2 | z2
R2: X-> Y
x3 | y2 | z1
X |Y
x2 | z2
x1 | y1 | z1
x4 | y1 | z2
x1 | y1
x3 | z1
x2 | y2 | z2
x2 | y2
x4 | z2
x3 | y2 | z1
Junção
x4 | y1 | z2
x3 | y2
x4 | y1
Formas Normais
Pedro Sousa
36
Exemplos de Decomposições
 Seja a Relação
Fornecedor (F#, Estado, Cidade).
 Decomposição 1
F1 (F#, Estado) e F2(F#,Cidade)
 Decomposição 2
F1 (F#, Estado) e F2(Cidade,Estado)
 A 1ª não implica perdas, enquanto na segunda perde-se
a dependência F# ->Cidade
Formas Normais
Pedro Sousa
37
Exemplo (1)
 Encomenda não está na 1FN.
 Porquê ?
 Quais são as anomalias que se podem verificar?
Codigo-Peça
Preço
Item
NrEncomenda
Quantidade
Encomenda
Data
NrCliente
NomeCliente
Formas Normais
Pedro Sousa
38
Exemplo (2)
 Este esquema está na 1FN, mas não está na 2FN.
 Porquê ?
 Quais são as anomalias que se podem verificar?
NrEncomenda
NrItem
PreçoUnitário
Detalhe
Da
Encomenda
Data
NrCliente
Quantidade
NomeCliente
Detalhe(NrItem, NrEncomenda,PreçoUnitário, Quantidade)
Encomenda(NrEncomenda,Data,NrCliente,NomeCliente)
Formas Normais
Pedro Sousa
39
Exemplo (3)
 Este esquema está na 2FN, mas não está na 3FN.
 Porquê ?
 Quais são as anomalias que se podem verificar?
Quantidade
Item
PreçoUnitário
NrEncomenda
Detalhe
Encomenda
Data
NrCliente
NrItem
NomeCliente
Detalhe(NrItem, NrEncomenda, Quantidade)
Item(NrItem, PreçoUnitário)
Encomenda(NrEncomenda,Data,NrCliente,NomeCliente)
Formas Normais
Pedro Sousa
40
Exemplo (4)
 Este esquema está na 3FN
Quantidade
Item
PreçoUnitário
NrEncomenda
Detalhe
Encomenda
Data
Do
NrItem
Cliente
NrCliente
Detalhe(NrItem, NrEncomenda,PreçoUnitário, Quantidade)
NomeCliente
Item(NrItem, PreçoUnitário)
Encomenda(NrEncomenda,Data,NrCliente)
Cliente(NrCliente,NomeCliente)
Formas Normais
Pedro Sousa
41