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 a coerência da
informação.
 Fundamenta-se nas dependências entre os atributos das
relações
 Foi extensivamente usado como critério de desenho de
sistemas de informação.
 Ao nível do modelo Relacional, deve ser usado para detectar
eventuais problemas associados à da redundância e coerência
da informação.
 Ao nível do modelo Entidade Associação, pode ser usado para
identificar 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, perdese 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
Definições Elementares
 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.
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
•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 à chave
primária da Relação (ou ao identificador da Entidade)
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 relação (ou entidade ) 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 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 não têm as anomalias !
Formas Normais
Pedro Sousa
15
A 1 Forma Normal e os Modelos Conceptuais
 Qual o 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
começa pela 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.
 Todos as entidades ou associaçõ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
Exemplos
Consideremos a 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
Estudante
Nº
2ª Forma Normal
Exemplos
Estudante
Nº
Professor
Exame
Cadeira
Nota
Exame
Nome
Cadeira
Nota
Professor
Nome
Exame não está na 2FN
Exame está na 2FN
Atributos da Associação Exame:
Nº -Estudante,Nome-Cadeira, Professor,Nota
Identificador da Associação Exame: Nº -Estudante,Nome-Cadeira
Dependências da associaçã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
Exemplos
 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.
Preço Total
Quantidade
 Por exemplo, a informação
sobre o preço de cada peça.
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
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 entidades 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 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, Nº Departamento
Nº Projecto
Orçamento
Orçamento, Nº Horas, Nº Projecto
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ão está na 3FN, porque Projecto determina Orçamento e não é chave
Formas Normais
Pedro Sousa
26
Problemas com a 3ª Forma Normal
Seja a Entidade/Relação X
com os seguintes atributos
e identificadores
a1
X
a2
a3
a4
 Os problemas da 3FN surgem
quando:
 Existem dependências entre os
atributos dos identificadores, por
exemplo:
a3
a1
a3
 Existem vários identificadores
compostos, com pelo menos um
atributo comum, por exemplo:
a1,a2
a3,a2
X(a1, a2, a3, a4)
Formas Normais
a1
Pedro Sousa
a3,a4
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 Cood
(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:
 Existem 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 existem na 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 :
Aulas (Disciplina,Professor,Aluno)
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 perca de
informação.
O Problema da Perca de Informação
 Entre as decomposições que não implicam a perca
de informação, importa decidir sobre a mais correcta.
O Problema da Perca 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! (ou seja, R´1
tem mais tuplos do que R1)
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
Uniã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
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, YZ-> X
R3:
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
Uniã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
 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
 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
1
N
Da
Encomenda
Data
NrCliente
Quantidade
NomeCliente
Detalhe(NrItem, NrEncomenda,PreçoUnitário, Quantidade)
Encomenda(NrEncomenda,Data,NrCliente,NomeCliente)
Formas Normais
Pedro Sousa
39
Exemplo
 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
1
N
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
 Este esquema está na 3FN
Quantidade
Item
NrEncomenda
1
N
Detalhe
Encomenda
Data
N
PreçoUnitário
Do
NrItem
N
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
Formas Normais: Exercício 1
A
B
C
D
E1
A
B
C
D
E2
B
D
AB
C
AB
CE
E
AB
C
Qual o Identificador ?
Em que FN está ?
Qual o Identificador ?
Em que FN está ?
D
E
Formas Normais
Pedro Sousa
42
Formas Normais: Exercício 2
E3
E4
Formas Normais
A
B
C
D
A
B
C
D
B
D
D
B
ABD
C
A
BCD
B
ACD
CD
AB
Pedro Sousa
Qual o Identificador ?
Em que FN está ?
Qual o Identificador ?
Em que FN está ?
43
Exercício 3
Considere a relação R(a,b,c,d,e), em que {a,b} é a chave
primária e d->e .
- Indique todas as dependências da relação R.
- Qual a forma normal da relação R?
- Assuma agora que a chave primária R é {a,b,d}. Em que
forma normal a relação R passa a estar?
Formas Normais
Pedro Sousa
44
Exercício 4
Considere a relação R(a,b,c,d), em que {a,b} é a chave
primária.
- Indique uma dependência funcional entre os atributos de R
de forma a que R não esteja na 2ª forma normal.
- Indique uma dependência funcional entre os atributos de R
de forma a que R esteja na 2ª forma normal mas não
esteja na 3ª forma normal.
- Indique uma dependência funcional entre os atributos de R
de forma a que R esteja na 3ª forma normal mas não
esteja
na Boyce Codd.
Pedro Sousa
Formas Normais
45
Exercício 5
 Considere a relação R (a,b,c) e a sua decomposição
nas relações R1(b,c) e R2(a,c).
- Qual ou quais as dependências que têm
necessariamente que existir entre os atributos a, b e
c para que a decomposição de R em R1 e R2 não
represente perda de informação?
- Assumindo a existência da ou das dependências
anteriores, escreva uma expressão em álgebra
relacional que permita reconstituir R a partir de R1 e
R2 ?
Formas Normais
Pedro Sousa
46