George Hamilton

Slide Title

Asterio K. Tanaka

BANCO DE DADOSDependências funcionais e Normalização de

Bancos de Dados Relacionais

(Material complementar aos Capítulos 14-15 de Elmasri-Navathe 2000)

Asterio K. Tanakahttp://www.uniriotec.br/~tanaka

tanaka@rjnet.com.br

Utilização por terceiros autorizada com citação da fonte.

George Hamilton

Slide Title

Asterio K. Tanaka

Projeto de Bancos de Dados

Requisitos de Dados

ProjetoConceitual

ProjetoLógico

ProjetoFísico

Esquema Conceitual

Esquema Físico

Esquema Lógico

Modelagem dos requisitos de dados através de diagramas de Entidades e Relacionamentos (DER) ou de Classes e Objetos (DCO)

Mapeamento do esquema conceitual para o modelo de dados do SGBD escolhido, através de diagrama de estruturas de dados (DED)

Mapeamento do esquema lógico para os tipos de dados e restrições de integridade do SGBD escolhido; criação de visões e índices.

George Hamilton

Slide Title

Asterio K. Tanaka

Normalização

• Normalização de dados : processo de decomposição de esquemas para evitar anomalias de atualização (na inserção, exclusão, modificação de dados).

• “Bom design” evita redundância de dados e anomalias de atualização.

• Mecanismo formal para analisar esquemas de relações baseado nas suas chaves e nas dependências funcionais entre seus atributos.

• Antes da modelagem conceitual, normalização era um método de projeto de relações, a partir de uma RELAÇÃO UNIVERSAL.

• Uma modelagem conceitual bem feita resulta naturalmente em esquemas normalizados, portanto normalização é conseqüência, ou seja, um “bom design” é conseqüência de uma boa modelagem.

George Hamilton

Slide Title

Asterio K. Tanaka

Redundância de Dados e Anomalias de Atualização

CPF Nome-Func

Data-Nasc

Endereço

Num-Dept Nome-Dept Gerente-Dept

CPF Num-Proj Horas Nome-Func

Nome-Proj

Local-Proj

• Redundância nas tuplas: Num-Dept, Nome-Dept, Gerente-Dept são repetidos para todo funcionário que trabalha naquele departamento. Idem para Nome-Func, Nome-Proj, Local-Proj para cada funcionário alocado em determinado projeto.

• Anomalias de atualização:

• Inserção: incluir um novo funcionário implica em incluir dados de departamento our deixar nulos; como incluir um novo departamento, se CPF é chave primária

• Exclusão: ao excluir um funcinário que seja o único funcinário de um departamento, estaremos perdendo dados sobre o departamento

• Modificação: ao mudarmos um dado de um departamento (por exemplo, o gerente), todas as tuplas de funcionários daquele departamento terão que ser modificadas.

FUNC-DEPT

FUNC-PROJ

George Hamilton

Slide Title

Asterio K. Tanaka

Projeto de BD por Normalização

CPF Nome Emp Num Dept Nome Dept

Num Proj Nome Proj

Horas

CPF Nome Emp Num Dept

CPF Num Proj Horas

Num Dept Nome Dept

Num Proj Nome Proj

Normalização

Esquema com relações normalizadas

relação universal (“tabelão” com todos os dados)

George Hamilton

Slide Title

Asterio K. Tanaka

Primeira Forma Normal (1FN)

• É parte da definição formal de uma relação; foi definida para não permitir atributos multivalorados, atributos compostos e suas combinações. A 1FN garante a propriedade de fechamento da Álgebra Relacional.

Uma relação está em 1FN se e somente se todos os seus atributos contêm apenas valores atômicos (simples, indivisíveis).

George Hamilton

Slide Title

Asterio K. Tanaka

Nome Núm Gerente Data-Inicio

DEPARTAMENTO

PesqAdmSede

541

333445555987654321888665555

22Mai8801Jan9219Jun91

Lins, Bauru, SantosCampinasSantos

Localização

Relação que não está em 1FN

Num-Dept Localização

LOCAL_DEPT

14555

SantosCampinasLinsBauruSantos

Nome Núm Gerente Data-Inicio

DEPARTAMENTO

PesqAdmSede

541

333445555987654321888665555

22Mai8801Jan9219Jun91

Relações em 1FNsem redundância

atributo multivalorado

George Hamilton

Slide Title

Asterio K. Tanaka

CPF-Emp Num-Proj Horas

TRABALHA_EM

123456789123456789666884444453453453453453453333445555333445555333445555333445555999887777999887777987987987987987987987654321987654321888665555

1231223102030101030302020

32,5 7,540,020,020,010,010,010,010,030,010,035,05,020,015,0nulo

Relação em 1FN

CPF-Emp Projetos

Num-Proj Horas

TRABALHA_EM

123456789 666884444453453453 333445555 999887777 987987987 987654321 888665555

1231223102030101030302020

32,5 7,540,020,020,010,010,010,010,030,010,035,05,020,015,0nulo

Relação que não está em 1FN

atributo composto

George Hamilton

Slide Title

Asterio K. Tanaka

Dependência Funcional

CPF Num-Proj Horas Nome-Emp Nome-Proj Local-Proj

EMP-PROJ

df1

df2

df3

df1 : {CPF, Num-Proj} {Horas}df2 : {CPF} {Nome-Emp}df3 : {Num-Proj} {Nome-Proj, Local-Proj}

DF deve ser explicitamente definida por alguém que conheça a semântica dos atributos de uma relação. Não basta deduzir a DF pelas instâncias.

X YOs valores dos atributos do conjunto X determinam os valores dos atributos do conjunto Y ou, inversamente, os valores dos atributos do conjunto Y dependem funcionalmente dos valores dos atributos do conjunto X.

George Hamilton

Slide Title

Asterio K. Tanaka

Regras de Inferência para Dependências Funcionais

Regra reflexiva : Se X Y, então X Y.

Regra de aumento : {XY} XZ Y.

Regra transitiva : {X Y, Y Z} X Z.

Regra projetiva ou de decomposição : {X YZ} X Y.

Regra aditiva ou de união : {X Y, X Z} X YZ.

Regra pseudo-transitiva : {X Y, WY Z} WX Z.

George Hamilton

Slide Title

Asterio K. Tanaka

Segunda Forma Normal (2FN)

Uma relação está em 2FN se e somente se estiver em 1FN e todo atributo não-primo (isto é, que não seja membro de uma chave) for totalmente dependente de qualquer chave.

George Hamilton

Slide Title

Asterio K. Tanaka

CPF Num-Proj Horas

CPF Nome-Emp

Num-Proj Nome-Proj Local-Proj

df1

TRABALHA_EM

EMPREGADO

PROJETO

df2

df3

Relaçõesem 2FN

CPF Num-Proj Horas Nome-Emp Nome-Proj Local-Proj

EMP-PROJ

df1

df2

df3

Relação em 1FN que não está em 2FN

George Hamilton

Slide Title

Asterio K. Tanaka

Terceira Forma Normal (3FN)

Uma relação está em 3FN se e somente se estiver em 2FN e nenhum atributo não-primo (isto é, que não seja membro de uma chave) for transitivamente dependente da chave primária.

Em outras palavras, para toda df X A, uma das duas condições seguintes devem valer:

• X é uma superchave ou

• A é membro de uma chave candidata

George Hamilton

Slide Title

Asterio K. Tanaka

CPF Nome-Emp Data-Nasc Endereço Num-Dept Nome-Dept Ger-Dept

EMP-DEPT

Relação em 2FN que não está em 3FN

df1

df2

CPF Nome-Emp Data-Nasc Endereço Num-Dept

df1

Num-Dept Nome-Dept Ger-Dept

df2

EMPREGADO

DEPARTAMENTO

Relaçõesem 3FN

George Hamilton

Slide Title

Asterio K. Tanaka

Forma Normal de Boyce-Codd (FNBC)

• É uma forma mais restritiva de 3FN, isto é toda relação em FNBC está também em 3FN; entretanto, uma relação em 3FN não está necessariamente em FNBC.

Uma relação está em FNBC se para toda DF X Z, X é uma super-chave.

George Hamilton

Slide Title

Asterio K. Tanaka

Aluno Disciplina Professor

df1

df2

Aluno Disciplina Professor

Carlos Química AnaCarlos Física AntonioMarta Química AnaMarta Português MariaJoão Português Manoel

Relação em 3FN que não está em FNBC

Anomalia de exclusão : Se Carlos sair da aula de Física, não teremos nenhum registro de que Antonio leciona Física.

AULA

AULA

df2 : {Professor} Disciplina} {Professor} não é uma superchave.

George Hamilton

Slide Title

Asterio K. Tanaka

Carlos AnaCarlos AntonioMarta AnaMarta MariaJoão Manoel

Relações em FNBC

Note, entretanto, que a dependência funcional

df1 : {Aluno, Disciplina} Professor

foi perdida na decomposição.

Considere, por exemplo, a inserção de (Marta, Manoel) em R1.

Aluno Professor

Ana QuímicaAntonio FísicaMaria PortuguêsManoel Português

Professor Disciplina R1 R2

George Hamilton

Slide Title

Asterio K. Tanaka

• Conclusão: alguns esquemas não podem ser normalizados em FNBC e ao mesmo tempo preservar todas as dfs.

• Solução: redundância parcial.

Decomposição/Junção sem Perda

Aluno Disciplina Professor

Carlos Química AnaCarlos Física AntonioMarta Química AnaMarta Português MariaJoão Português Manoel

AULA

Ana QuímicaAntonio FísicaMaria PortuguêsManoel Português

Professor Disciplina

R2

Relações em FNBC, com redundância parciale todas as dependências funcionais preservadas

George Hamilton

Slide Title

Asterio K. Tanaka

Quarta Forma Normal

• Baseada em dependências multivaloradas (DMVs)

Quarta forma normal (4FN)

Uma relação R está em 4FN se e somente se estiver em FNBC e, caso exista alguma DMV

X --->> Y,

a DMV é trivial (i.e., Y X ou X Y = R)

ou

X é uma superchave de R.

George Hamilton

Slide Title

Asterio K. Tanaka

Nome-Emp Nome-Proj Nome-Depend

Prado X JoãoPrado Y AnaPrado X AnaPrado Y JoãoBorba W JoséBorba X JoséBorba Y JoséBorba Z JoséBorba W JoanaBorba X JoanaBorba Y JoanaBorba Z JoanaBorba W BetoBorba X BetoBorba Y BetoBorba Z Beto

EMPREGADO

Relação EMPREGADO não estáem 4FN.2 DMVs não triviais:Nome-Emp --->> Nome-ProjNome-Emp --->> Nome-Depend

Nome-Emp Nome-Proj Nome-Emp Nome-Depend

Prado XPrado YBorba WBorba XBorba YBorba Z

Prado JoãoPrado AnaBorba JoséBorba JoanaBorba Beto

EMP-PROJ EMP-DEP

As relações EMP-PROJ e EMP-DEP estão em 4FN

George Hamilton

Slide Title

Asterio K. Tanaka

Outras Formas Normais

• Tipos adicionais de dependências.

• dependências de junção e de inclusão, que levam a formas normais mais restritas (Quinta Forma Normal, Forma Normal de Domínio-Chave).

• A utilidade prática destas formas normais é limitada, porque num banco de dados real com muitos atributos, é muito difícil (e praticamente irrelevante) descobrir tais dependências e restrições.

George Hamilton

Slide Title

Asterio K. Tanaka

Normalização como Ferramenta para Validação da Qualidade de um Esquema

• As formas normais até FNBC são baseadas em dependências funcionais, exceto a 1FN, que faz parte da definição do modelo relacional.

• O design conceitual baseado nos modelos ER ou OO tende naturalmente a produzir esquemas normalizados, a menos da 1FN.

• A separação de conceitos é o resultado natural do design conceitual bem feito.

• Na prática, esquemas que violam a normalização são exemplos de esquemas mal projetados.