Projeto de Bancos de Dados v2 - dcc.ufrj.brdcc.ufrj.br/~pedro/Arquivos/ProjetoBDv2.pdf · Projeto de Bancos de Dados RelacionaisProjeto de Bancos de Dados Relacionais Bancos de Dados

DCC/UFRJ Bancos de Dados IPedro Manoel da Silveira

PMS v2Bancos de Dados Relacionais 1

Bancos de Dados I

Bancos de Dados Relacionais

Projeto de Bancos de Dados RelacionaisProjeto de Bancos de Dados Relacionais

Bancos de Dados I

Projeto de BD Relacionais

Problema:Como distribuir os dados de um sistema em um esquema relacional que seja o mais eficiente possível.

Teoria baseada nas dependências funcionais, buscando-se algoritmos automatizados para verificar a adequação de esquemas relacionais. Muitos resultados importantes publicados nas décadas de 70 e 80.

Bancos de Dados I

Objetivos do Projeto de BD

1. Decomposição sem perdatodos os estados que podem ser representados pelo conjunto de atributos podem ser recuperados a partir do esquema relacional escolhido.



Bancos de Dados I


2. Normalizaçãoo esquema relacional escolhido observa as formas normais.

Bancos de Dados I


3. Preservação das dependências funcionaistodas as dependências funcionais são preservadas no esquema relacional escolhido, isto é, não pode haver uma dependência funcional que possa violada em qualquer das tabelas.

Bancos de Dados I

Anomalias num Projeto de BD

Problemas acarretados por um esquema relacional inadequado:

Redundância de dados, quando a mesma informação é registrada mais de uma vez;

Inconsistência, quando a mesma informações tem mais um versão registrada;

Dificuldades para inserção/remoção de dados, quando o esquema exige que essas operações envolvam mais dados que o necessário.



Bancos de Dados I

Normalização

Problema: Dada uma lista de itens de dados a representar no computador, como decidir quais as relações que vão existir e quais os seus atributosConceitos envolvidos:

Dependências funcionaisFormas normaisRelação universal Normalização ajuda,

mas não resolve!

Bancos de Dados I

Dependências funcionais

Definição: Dada uma relação R, o atributo Y de R éfuncionalmente dependente de um atributo X de R se e somente se, sempre que duas tuplas de R têm o mesmo valor para X têm também o mesmo valor para Y. Diz-se também que “X determina Y”.

Notação:X → Y

A definição também vale para conjuntos de atributos:X, Y, W → Z

Bancos de Dados I


Exemplo: Considere um banco de dados com dados pessoais, composto pelos atributos CPF, Nome, Endereço. Sabendo-se que no Brasil há cada CPF corresponde a uma única pessoa, e que há somente um endereço por pessoa no banco de dados, pode-se concluir que:CPF → NomeCPF → EndereçoPor outro lado, não é verdade que:Nome → CPFNome → Endereço



Bancos de Dados I


Dependência parcial e total:

X → Y, então Y é totalmente dependente de X

X,Z → Y, então Y é parcialmente dependente de X

Bancos de Dados I

Atributos e suas dependências funcionais (1)

Considerando os atributos:

CodVôo, CodEmp, NomeEmp, TelefoneData,H_Saída, H_Chegada, H_Saída_Real, H_Chegada_Real,CodAvião, Tipo, CapacidadeOrigem, Destino, Distância

Bancos de Dados I

Atributos e suas dependências funcionais (2)

CodEmp

Data

Telefone NomeEmp

H_Saída

CodAviãoCodVôo

OrigemDestino

H_Chegada

H_Saída_RealH_Chegada_Real

Capacidade

Distância



Bancos de Dados I

Derivando dependências funcionais

Axiomas de Armstrong permitam a derivação de novas dependências funcionais a partir de um conjunto inicial. Há três axiomas básicos:

A1. Reflexividade: Se Y ⊆ X ⊆ U então X → YDá as dependências triviais, que não dependem de F.

A2. Aumento: Se X → Y e Z ⊆ U então XZ → YZX, Y e Z são conjuntos de atributos e X → Y pode estar em F ou ter sido derivada pelos axiomas.

A3. Transitividade: Se X →Y e Y →Z então X →Z

Bancos de Dados I

Derivando dependências funcionais

Axiomas de Armstrong inferidos a partir dos axiomas básicos:

A4. União: Se X → Y e X → Z então X → YZDá as dependências triviais, que não dependem de F.

A5. Pseudotransitividade:Se X → Y e WY → Z então XW → Z

A6. Decomposição: Se X → Y e Z ⊆ Y então X → ZUma consequência importante da decomposição:Se A1,...,An são atributos então X → A1,...,An verifica-se se

e somente se X → Ai para cada i

Bancos de Dados I

Proposições

Os axiomas de Armstrong são robustos e completos (sound and complete).



Bancos de Dados I

Formas normais

Verificam as relações escolhidasEvitam problemas de atualização ineficientesHá 4 formas normais usualmente empregadas

Bancos de Dados I

Exemplo de projeto pobre

Gol Linhas AéreasGOL102

American AirlinesAA905

Transportes Aéreos Marília

TAM751

Gol Linhas AéreasGOL101

NomeEmpCodEmpCodVoo

Bancos de Dados I

Anomalias

RedundânciaO nome da empresa aparece mais de uma vez

InconsistênciaO nome da empresa poderia aparecer com valores diferentes para o mesmo código de empresa

InserçãoNão é possível inserir uma empresa sem que haja vôos

RemoçãoRemover todos os vôos significa remover a empresa



Bancos de Dados I

Primeira forma normal

Todos os atributos têm valores atômicos

Exemplo de relação transgressora

Problema: vários telefones na mesma colunaSolução: desmembrar em mais de uma relação

EmpresaCodEmp NomeEmp Telefones

VRGTAMTBR

VARIGTrans A Marília

Transbrasil

2345678 3456789 45678992345677

9876543 3674530

Bancos de Dados I

Primeira forma normal

Desmembramento

EmpresaCodEmp NomeEmp

VRGTAMTBR

VarigTransp A Marília

Transbrasil

TelefoneNumTelefone CodEmp

234567834567894567899234567798765433674530

VRGVRGVRGTAMTBRTBR

Bancos de Dados I

Para cada chave de uma tabela, todo atributo que não é parte dessa chave deve ser totalmente dependente dos atributos que a compõem


Problema: O atributo CodAvião não faz parte da chave CodVôo e dela não depende

Solução: desmembrar em mais de uma relação

Segunda forma normal

VôoCodVôo CodEmp CodAvião



Bancos de Dados I

Segunda forma normal

Desmembramento

Solução: O atributo CodAvião deve ser movido para outra tabela

VôoCodVôo CodEmp

Bancos de Dados I

Terceira forma normal

A tabela deve estar na segunda forma normal e, para cada chave da tabela, todo atributo que não é parte dessa chave não é transitivamente dependente dos atributos que a compõem através de um atributo que não faz parte da chave.


Problema: O atributo NomeEmp é transitivamente dependente de CodVôoatravés do atributo CodEmp.

V ô oC o d V ô o C o d E m p N o m e E m p

1 0 17 5 12 3 03 2 1

V R GT A MT B RV R G

V a r igT r a n s A M a r í l iaT r a n s b ra s ilV a r ig

Bancos de Dados I


Desmembramento

VôoCodVôo CodEmp

101751230321

VRGTAMTBRVRG

EmpresaCodEmp NomeEmp

VRGTAMTBR

VarigTrans A Marília

Transbrasil



Bancos de Dados I

Forma normal Boyce-Codd

Para cada dependência funcional não trivial, se todos os atributos que compõem a dependência aparecem numa tabela, então o conjunto de atributos que formam o determinante dessa dependência deve, necessariamente, incluir uma super-chave da tabela.


Problema: Os atributos CodVôo, Origem, Destino formam um determinante para o atributo H_Saída

Solução: desmembrar em mais de uma relação (ou, em alguns casos, introduzir uma chave)

ViagemCodVôo Origem Destino Data H_Saída H_Saída_Real H_Chegada_Real

Bancos de Dados I

Chaves

Se R é um esquema relacional com atributos A1,...,An e dependências funcionais F e X é um subconjunto de A1,...,An, diz-se que X é uma chave de Rse:

1. X→ A1,...,An está em F2. não existe um subconjunto Y⊆X tal

que Y → A1,...,An esteja em F

Bancos de Dados I

Exemplo

Esquema R(Cidade, Rua, Número, CEP)

DependênciasCidade Rua Número → CEPCEP → Cidade

As combinações de atributos abaixo podem ser definidas como chaves?

{Cidade, Rua, Número} {CEP, Rua, Número}



Bancos de Dados I

Aplicando axiomas

CEP → Cidade (dado)CEP Rua Número → Cidade Rua Número (aumento)Cidade Rua Número → CEP (dado)Cidade Rua Número → CEP Cidade Rua Número (aumento)CEP Rua Número → CEP Cidade Rua Número (transitividade)

logo

{Cidade, Rua, Número} {CEP, Rua, Número}

são chaves.

Bancos de Dados I

Terceira forma normal melhorada

Uma relação R está na terceira forma normalse não existe uma chave X em R, um conjunto de atributos Y⊆R e um atributo não chave A, disjunto de X e Y, tal que:

1. X → Y verifica-se em R;2. Y → A verifica-se em R;3. Y → X não se verifica em R.

Bancos de Dados I


Supondo que CPF →DRE e DRE → Nome, a relação abaixo não passaria na primeira definição da 3ª. FN

Aluno

João903103

Maria901102

Paulo901101

NomeDRECPF



Bancos de Dados I

Formas normais

Uma relação é dita na Forma normal Boyce-Codd se sempre que X → A se verifica em R, e A não está em X, então X inclui uma chave de R.

Proposição: Se uma relação R está nesta forma normal então está também na terceira forma normal.

Bancos de Dados I

Formas normais

Uma relação está na Forma normal Boyce-Codd se para toda dependência da forma X → Y, uma das condições éverdadeira:

a) X → Y é uma dependência trivial, isto é, Y ⊆ X

b) X é uma superchave para R.

Bancos de Dados I

Superchave

Se para todos os pares de tuplas t1, t2 em r, se t1 # t2 então t1[K] # t2[K], então K éuma superchave.

Por que super? Porque esta definição engloba o caso

R(A,B,C) ⇒ R(A,B,C) ⇒ R(A,B,C)



Bancos de Dados I

Formas normais e decomposição

Qualquer relação tem uma decomposição sem perda na FNBC.Qualquer relação tem uma decomposição sem perda na 3FN que preserva as dependências funcionais.

Bancos de Dados I

Dependências multivaloradas

X multidetermina Y, ou X →→ Y, se para valores dos atributos X há um conjunto de zero, um ou mais valores associados dos atributos Y, e esse conjunto de valores não está associado aos valores dos atributos R - X - Y.

Bancos de Dados I


Diz-se que X →→Y verifica-se em R se sempre que existirem t1 e t2 na instância de R, com t1[X]=t2[X], então existem também as u1 e u2, onde

1. u1[X] = u2[X] = t1[X] = t2[X]2. u1[Y] = t1[Y] e u1[R - X - Y] = t2[R - X - Y]3. u2[Y] = t2[Y] e u2[R - X - Y] = t1[R - X - Y]



Bancos de Dados I


ExemploCodVôo Origem Destino H_Saída Data

101 Rio BHZ 14:15 2/7/02

101 BHZ BSB 15:20 2/7/02

101 Rio BHZ 14:15 3/7/02

101 BHZ BSB 15:20 3/7/02

101 Rio BHZ 14:15 4/7/02

101 BHZ BSB 15:20 4/7/02

Bancos de Dados I


Testando CodVôo →→ Origem, Destino, H_Saída

CodVôo Origem Destino H_Saída Data

101 Rio BHZ 14:15 2/7/02 t1

101 BHZ BSB 15:20 2/7/02 u2

101 Rio BHZ 14:15 3/7/02 u1

101 BHZ BSB 15:20 3/7/02 t2

101 Rio BHZ 14:15 4/7/02

101 BHZ BSB 15:20 4/7/02

Bancos de Dados I

Quarta forma normal

Uma relação R está na Quarta forma normal se sempre que houver uma dependência multivalorada X →→ Y, onde Y não é vazio nem subconjunto de X, e XY não inclui todos os atributos de R, então X inclui alguma chave de R.



Bancos de Dados I

Axiomas para D.F. e D.M.

A1. Reflexividade: Se Y ⊆ X ⊆ U então X → YA2. Aumento: Se X → Y e Z ⊆ U então XZ → YZA3. Transitividade: Se X →Y e Y →Z então X →ZA4. Complemento: Se X →→ Y então X →→ U - X - YA5. Aumento: Se X →→ Y e V ⊆ W então WX →→ VYA6. Transitividade: Se X →→ Y e Y →→ Z então X →→ Z - YA7. Se X → Y então X →→ YA8. Se X →→ Y , Z ⊆ Y e

para algum W disjunto de Ytem-se que W→ Z,

então X→ Z

Bancos de Dados I

Proposições sobre 4FN

Se D inclui apenas dependências funcionais então sempre que R estiver na 4FN estará na FNBC.É possível encontrar uma decomposição sem perda tal que cada relação produzida esteja na 4FN.O algoritmo que determina quando uma decomposição é ou não sem perda pode ser adaptado para dependências multivaloradas.

Bancos de Dados I

Derivação lógica

Seja F um conjunto de dependências funcionais, R um esquema relacional e X→Y uma dependência funcional. Diz-se que X→Y deriva logicamente de F se toda relação r que satisfaz as dependências em F também satisfaz X→Y.



Bancos de Dados I

Cobertura de dependências

Seja F +, a cobertura (closure) de F, o conjunto de dependências funcionais derivadas de F. Se

F + = Fdiz-se que F é uma família completa de

dependências.

Bancos de Dados I

Calculando coberturas

Seja F um conjunto de dependências funcionais num conjunto de atributos U, e seja X um subconjunto de U. X+, a cobertura (closure) de X em relação a F, é o conjunto de atributos A tal que X→Apode ser deduzido de F pelos axiomas de Armstrong.

Bancos de Dados I


Cálculo da cobertura de um conjunto de atributos em relação a um conjunto de dependências funcionaisEntrada: Conjunto de atributos U, F sobre U e um conjunto X⊆USaída: X+, a cobertura de X em relação a F



Bancos de Dados I


Método: 1. X(0) é X2. X(i+1) é X mais o conjunto de atributos A tal que exista uma dependência Y→Z em F, A em Z, e Y⊆ X(i).Uma vez que X=X(0) ⊆ ... ⊆ X(i) ⊆ ... ⊆ U, e U é finito, épossível alcançar X(i) =X(i+1) =X(i+2) =...X+ é X(i).

Bancos de Dados I


ExemploAB→C D→ EGC→ A BE→ CBC→ D CG→ BDACD→ B CE→ AG

X(0) = {BD} X(1) = {BDEG}X(2) = {BCDEG} X(3) = {ABCDEG}X(4) = {ABCDEG} X(5) = ...

Bancos de Dados I


Proposições sobre o algoritmo para X+

1. O algoritmo pode executar em tempo proporcional ao comprimento das dependências.2. O algoritmo calcula corretamente.



Bancos de Dados I

Ainda coberturas...

Sejam F e G dois conjuntos de dependências. F e G são ditos equivalentes se F+ = G+

Diz-se que G cobre F , e vice-versa.

Bancos de Dados I

Mais ainda!

Um conjunto de dependências é mínimo se:1. todos os lados direitos em F têm somente um atributo2. para nenhum X→ A em F o conjunto F - {X→ A} éequivalente a F3. para nenhum X→ A em F , e subconjunto Z de X, o conjunto F - {X→ A} ∪ {Z→ A} é equivalente a F

Qualquer conjunto de dependências éequivalente a um conjunto que é mínimo!

Bancos de Dados I

Equivalência

Equivalência de dois conjuntos de dependências F e G: para cada dependência X→Y em F, testar se X→Z está em G+, calculando Y+ e testando se Z⊆Y+.



Bancos de Dados I

Decomposição de esquemas

A decomposição de um esquema relacional R={A1,...,An} é sua substituição por uma coleção ρ={R1,...,Rk} de subconjuntos de R tal que R1∪...∪Rk = R.

Bancos de Dados I

Decomposição de esquemas

Junção sem perda (lossless join)Se R é um esquema relacional decomposto nos esquemas R1,...,Rk e D é um conjunto de dependências, diz-se que a decomposição é sem perda em relação a D se, para cada relação r para R, que satisfaz D

r = π R1 (r) ⌧ ... ⌧ π Rk (r) isto é, r é a junção natural de suas projeções em Ri

Bancos de Dados I

Decomposição

Algoritmo para testar propriedade sem perda

Entrada: Um esquema relacional R={A1,...,An}, um conjunto de dependências F e uma decomposição ρ={R1,...,Rk}

Saída: Decisão sobre a propriedade sem perda



Bancos de Dados I

Decomposição

Método: Construir uma tabela com n linhas (esquema Ri) e k colunas (atributo Aj). Na posição (i,j) coloca-se aj se o atributo Aj pertence ao esquema Ri; caso contrário coloca-se bij.Repetidamente, considera-se cada dependência X→Y em F. Se há um par de linhas que coincidem nos atributos de X, equacionam-se os atributos de Y, assim:se um é aj, faça-se o outro aj; se os dois são bij e bji, façam-se os dois bij ou bji, arbitrariamente;

se há uma linha com a1,...,ak a decomposição é sem perda

Bancos de Dados I

Decomposição

Considere-se o esquemaFornecimento(Nome, Endereço, Item, Preço)

com a decomposiçãoR1(Nome, Endereço)R2(Nome, Item, Preço)

e as dependênciasNome → EndereçoNome Item → Preço

Bancos de Dados I

Decomposição

Tabela resultante

N E I Pa1 a2 b13 b14a1 b22 a3 a4

N E I Pa1 a2 b13 b14a1 a2 a3 a4



Bancos de Dados I

Formas normais

Uma relação R está na terceira forma normal se não existe uma chave X em R, um conjunto de atributos Y⊆R e um atributo não chave A, disjunto de X e Y, tal que:

1. X → Y verifica-se em R;2. Y → A verifica-se em R;3. Y → X não verifica-se em R.

Se R satisfaz as condições acima sempre que Y⊆X então diz-se que R está na segunda forma normal.

Bancos de Dados I

Super-chave

• Se para qualquer par de tuplas t1 e t2, na instância de uma relação R, t1[K]≠ t2[K]sempre que t1 ≠ t2 , então diz-se que K éuma super-chave de R.

Note que esta definição engloba o casoR(A, B, C) R(A, B, C) R(A, B, C)

Bancos de Dados I

Formas normais

• Uma relação R está na forma normal Boyce-Codd, com respeito a um conjunto de dependências funcionais F, se para toda dependência X → Y, X⊆R e Y⊆R, uma das condições a seguir éverdadeira:

1. X → Y é uma dependência trivial, isto é, Y⊆X ;2. X é uma super-chave para R.



Bancos de Dados I

Formas normais

Um relação é dita na Forma normal Boyce-Codd se sempre que X → A se verifica em R, e A não está em X, então X inclui uma chave de R.

Proposição: Se uma relação R está nesta forma normal então está também na terceira forma normal.

Bancos de Dados I

Formas normais e decomposição

ProposiçõesQualquer relação tem um decomposição sem perda na FNBC.Qualquer relação tem uma decomposição sem perda na 3FN que preserva as dependências funcionais.

Documents

Projeto de Bancos de Dados v2 - dcc.ufrj.brdcc.ufrj.br/~pedro/Arquivos/ProjetoBDv2.pdf · Projeto de Bancos de Dados RelacionaisProjeto de Bancos de Dados Relacionais Bancos de Dados