Sumário Projecto de bases de dados relacionais Conceitos básicos Metodologia de normalização Gabriel David FEUP - Rua Dr. Roberto Frias, 4200-465 Porto - PORTUGAL Tel. 351-225081408 - Fax: 351-225081440 Email: [email protected] URL: http://www.fe.up.pt 1 Projecto de BD relacionais Esquema da BD = esquemas das relações + regras de integridade Identificar os elementos de informação relevantes, os atributos Como organizar os atributos em tabelas? Optar entre vários esquemas alternativos critérios de comparação Noções úteis também para BDOO e grandes aplicações tradicionais Projecto de BD - 2 BD Coop Esquema Sócios( nome, endereço, balanço ) Encomendas( nome, produto, quant ) Fornecedores( empresa, morada, produto, preço ) Sócios nome João Pedro Antónia Jaime endereço balanço Boavista, 45 530 Galvão, 61 200 Constituição, 5 -47 Breyner, 95 0 Encomendas nome produto João farinha João bolacha Antónia farinha Pedro batata quant 5 10 3 8 Projecto de BD - 3 Defeitos do esquema Redundância Fornecedores empresa morada Agro Massarelos, 80 Agro Massarelos, 80 Agro Massarelos, 80 Alimentar Industrial, 2 Alimentar Industrial, 2 Alimentar Industrial, 2 Nutriente Lordelo, 509 Nutriente Lordelo, 509 Nutriente Lordelo, 509 produto preço farinha 129 batata 89 bacalhau 540 massa 70 feijão 80 bolacha 125 batata 79 massa 79 bacalhau 570 anomalias de actualização valores nulos, chave? anomalias de apagamento inconsistência anomalias de inserção mesmo facto, vários registos dois factos, mesmo registo Vantagem dispensa a junção, eficiência segurança vs. eficiência Projecto de BD - 4 Esquema alternativo Forn empresa Agro Alimentar Nutriente Prod empresa Agro Agro Agro Alimentar Alimentar Alimentar Nutriente Nutriente Nutriente morada Massarelos, 80 Industrial, 2 Lordelo, 509 produto preço farinha 129 batata 89 bacalhau 540 massa 70 feijão 80 bolacha 125 batata 79 massa 79 bacalhau 570 Sócios( nome, endereço, balanço ) Encomendas(nome, produto, quant) Forn ( empresa, morada ) Prod( empresa, produto, preço ) sem deficiências um facto, um registo junção recupera Fornecedores maior esforço computacional conjuntos de dados menores Projecto de BD - 5 Restrições de integridade Relações representam classes e associações não basta garantir que possuem a aridade correcta e a compatibilidade de certos domínios Mais informação no modelo restrições de semântica dos elementos do domínio • validações restrições de igualdade ou desigualdade • interesse para o projecto se BI1=BI2 implica nome1=nome2 nome= f( BI ) BI nome BI1 nome1 BI2 nome2 [nome depende funcionalmente de BI] [BI determina funcionalmente nome] Projecto de BD - 6 Dependência funcional R( A1, A2, …, An ) X = AX1 AX2 … Y = AY1 AY2 … AXi, AYi A1 … An Se X Y então dois tuplos Ta e Tb em que Xa=Xb terão que satisfazer Ya=Yb Caso contrário a BD está num estado inconsistente, por violar a dependência funcional X Y Projecto de BD - 7 No exemplo Fornecedores Dependências no modelo declaradas pelo projectista empresa morada empresa produto preço significam que uma empresa só tem uma morada e que uma empresa tem um só preço para cada produto No 1º esquema é fácil violar a primeira dependência, por inserção ou actualização, devido à redundância No 2º esquema só existe uma morada, pelo que não pode haver inconsistência (quando muito incorrecção se a morada estiver errada) Projecto de BD - 8 De onde vêm as dependências Chave uma chave determina qualquer subconjunto de atributos da relação R( A, B, C, D, E ) A A B D D • ABA • ABCD • ABBDE Associação muitos-um R( A1, A2, B, C, D1, D2, E ) 1 2 Entidade 1 1 Ass 2 Entidade 2 C • A1 A2 D1 D2 e como D1 D2 é chave da Entidade 2 • A1 A2 A1 A2 ... C ... E • D1 D2 A1 A2 Cabe ao projectista decidir quais as chaves que existem Projecto de BD - 9 E Dependências implícitas R( A, B, C ) (F: dependências sobre a relação R) F= {A B, B C} implica A C F+= {A A, A B A, A B, A B B, A B, A B C, A A B, A B A B, A A C, A B A C, A B C, A B B C, A A B C, A B A B C, A , A B , B B, B C B, B B C, B C B C, C , B C A C A, A C B, A C C, A C A B, A C A C, A C B C, A C A B C, A C , B C, B , A B C A, A B C B, A B C C, A B C A B, A B C A C, A B C B C, A B C A B C, A B C , B C C, B C , Dependências dadas, triviais, derivadas Projecto de BD - 10 Fecho de um conjunto de dependências F+ (fecho de F) é o conjunto de todas as dependências implicadas logicamente por F Axiomas de Armstrong Reflexividade (triviais) Aumento Transitividade Reunião Pseudotransitividade Decomposição YXU XY X Y e Z U XZ YZ XYeYZ XZ X Y e X Z X YZ X Y e WY Z X W Z XYeZY XZ Projecto de BD - 11 Dependência derivada Cálculo de uma dependência derivada, a partir das dependências dadas e das regras de cálculo 1 (dada) F_nome Produto Preço 2 (dada) F_nome F_endereço 3 (2 + aumento) F_nome Produto F_endereço Produto 4 (3 + decomposição) F_nome Produto F_endereço 5 (4+1+reunião) F_nome Produto F_endereço Preço Projecto de BD - 12 Chave de uma relação Dados uma relação R( A1, A2, ..., An ) e um conjunto de dependências funcionais F X, subconjunto de A1, A2, ..., An é chave se 1. X A1, A2, ..., An pertence a F+ 2. Não se verifica Y A1, A2, ..., An pertencer a F+, com Y X. A chave determina todos os atributos e é mínima. Projecto de BD - 13 Exemplo das moradas Morada( cidade, rua, cod ) F = { cidade rua cod, cod cidade } cidade rua cidade rua cod rua cod cidade rua cod Só rua, só cod ou só cidade não determinam todos os atributos e portanto não são chaves {cidade rua} e {rua cod} são chaves alternativas, uma das quais pode ser escolhida para chave primária Projecto de BD - 14 Fecho de um conjunto de atributos Problema: algoritmo de cálculo de F+ (todas as dependências) é de ordem exponencial não praticável para casos de dimensão realista (X: conjunto de atributos) X+ (fecho de X) é o conjunto de todos os atributos funcionalmente dependentes de X Solução: X Y pertence a F+ sse Y X+ Algoritmo de cálculo de X+, relativamente a F 1. 2. 3. X(0) = X X(i+1) = X(i) {A | Y Z F, Y X(i), A Z} X+ = X(i), se X(i+1) = X(i) Projecto de BD - 15 Exemplo de cálculo de X+ R(A, B, C, D, E, F) F= {AB C F ED CA BE C BC F CD BF ACF B CE AD } Calcular o fecho de X = BF X(0)= BF X(1)= BDEF X(2)= BCDEF X(3)= ABCDEF = X+ = U B+= B F+= DEF U Logo, X= BF é chave Projecto de BD - 16 Conjuntos de dependências F e G – conjuntos de dependências dois conjuntos são equivalentes se os respectivos fechos forem iguais F G sse F+ = G+ Método de teste Para cada Y Z F testar se Y Z G+ • Calcular Y+|G • Verificar se Z Y+ Vice-versa, para as dependências em G. Projecto de BD - 17 Forma minimal Conjunto de dependências F numa forma minimal 1. 2. 3. Membro direito das dependências tem só 1 atributo Não existe X A F tal que F \ {X A} F Não existe X A F e Z X tal que F \ {X A} {Z A} F • • (2) impede redundância nas dependências (3) impede redundância nos atributos de uma dependência Entre os conjuntos de dependências equivalentes a F existe sempre pelo menos um que é minimal, isto é, que não se pode simplificar mais; mas pode existir mais do que um minimal, pelo que não se define o mínimo. Projecto de BD - 18 Determinação de forma minimal Determine uma forma minimal de F (pág. 16) Decompor as dependências com membro direito composto F= { AB C FE CD B CA FD CD F BC F BE C CE A ACF B CE D } Eliminar CE A (implicada por C A) Eliminar A em ACF B (porque B CF+|F) a) eliminar CD B (porque B CD+|F’) ou b) eliminar CF B (porque B CF+|F’’) e CD F (F CD+|F’’) Projecto de BD - 19 Duas formas minimais F’= { AB C CA BC F CF B FE FD BE C AB C CA BC F FE FD BE C CD F CE D } F’’= { CD B CE D } Neste caso, as duas formas minimais têm um número diferente de elementos Projecto de BD - 20 Decomposição Decomposição de R em R1 e R2 R1 e R2 obtêm-se de R por projecção e substituem-na todos os atributos de R se encontram em R1 ou R2 Para recuperar R, faz-se a junção natural de R1 e R2 Decomposição sem perdas se R = R1(R) ⋈ R2(R) Fornecedores = FORN ⋈ PROD Fornecedores ( empresa, morada, produto, preço ) Forn ( empresa, morada ) Prod ( empresa, produto, preço ) (ver pág. 3 e 4) Projecto de BD - 21 Decomposição com perdas FornProd empresa Agro Agro Agro Alimentar Alimentar Alimentar Nutriente Nutriente Nutriente produto farinha batata bacalhau massa feijão bolacha batata massa bacalhau MoraProd morada Massarelos, 80 Massarelos, 80 Massarelos, 80 Industrial, 2 Industrial, 2 Industrial, 2 Lordelo, 509 Lordelo, 509 Lordelo, 509 FornProd ⋈ MoraProd Fornecedores empresa morada produto preço Agro Massarelos, 80 farinha 129 Agro Massarelos, 80 batata 89 Agro Lordelo, 509 batata 79 … Nutriente Massarelos, 80 batata 89 Nutriente Lordelo, 509 batata 79 ... produto preço farinha 129 batata 89 bacalhau 540 massa 70 feijão 80 bolacha 125 batata 79 massa 79 bacalhau 570 Excesso de linhas Perda de informação Projecto de BD - 22 Decomposição sem perdas Algoritmo de teste R(A1, …, An), F (R1, …, Rk) relação inicial, dependências decomposição 1. Construir uma tabela k n coluna j atributo Aj linha i relação Ri 2. xij = aj se Aj em Ri xij = bij c.c. 3. Iterativamente, para cada XY em F, forçar linhas que coincidam em X a coincidir em Y mesmo aj ou, se não houver, mesmo bij 4. Decomposição é sem perdas se, no fim, houver uma linha só com a’s. Projecto de BD - 23 Aplicação do algoritmo Passo 1 Passo 2 empresa morada empresa produto preço 1º caso, sem perdas Fornecedores empresa morada produto preço Forn a1 a2 b13 b14 Prod a1 b22 a3 a4 Fornecedores empresa morada produto preço Forn a1 a2 b13 b14 Prod a1 a2 a3 a4 2º caso, com perdas Fornecedores empresa morada produto preço FornProd a1 b12 a3 b14 MoraProd b21 a2 a3 a4 Projecto de BD - 24 Vantagens da decomposição Trabalhar com conjuntos menores Redução das redundâncias Redução das perdas de informação Obriga a junções naturais método da normalização vai indicar regras orientadoras para a decomposição Projecto de BD - 25 Projecção das dependências A decomposição de uma relação R, sujeita ao conjunto de dependências F, num conjunto de relações (R1, ..., Rk) é acompanhada da projecção de F sobre cada uma das Ri Projecção de F sobre os atributos Z — conjunto de dependências X Y no fecho de F tal que XY Z X Y não precisa de estar em F, basta que esteja no fecho de F. Decomposição que preserva o conjunto de dependências F — quando a reunião das projecções de F sobre cada uma das relações da decomposição implica logicamente F. Se não se preservarem as dependências, aquilo que é admitido na decomposição pode não o ser na junção (nem no modelo...) Projecto de BD - 26 Falta de preservação F= {Cidade Rua Cod, Cod Cidade} MORADA(Cidade, Rua, Cod) decomposição: R1(Rua, Cod) F1= {} R2(Cidade, Cod) F2= {Cod Cidade} sem perdas: Cidade Rua R1 b11 a2 R2 a1 b22 Cod a3 a3 Cidade Rua R1 a1 a2 R2 a1 b22 Cod a3 a3 mas F1+F2 / F, i.e. não preserva as dependências R1 Rua Cod Cedofeita, 50 4000 Cedofeita, 50 4100 Conclusão: Cidade Rua Cod tem que ser verificada explicitamente R2 R1 ⋈ R2 Cidade Cod Porto 4000 Porto 4100 Cidade Rua Cod Porto Cedofeita, 50 4000 Porto Cedofeita, 50 4100 Projecto de BD - 27 Teste de preservação método inviável: calcular o fecho do conjunto de dependências F, projectá-lo sobre as relações da decomposição, fazer a respectiva exponencial união e verificar se este conjunto é equivalente a F. Algoritmo de teste da preservação das dependências Entrada: decomposição (R1,..., Rk) e dependências F Saída: decisão sobre a preservação de F. Método: para cada X Y em F fazer Z:= X enquanto ocorrerem alterações a Z fazer para i:= 1 até k fazer Z:= Z ((Z Ri)+ Ri) /*operação Ri, fecho relativo a F */ se Y Z então a dependência é preservada. Para saber se X Y em F está no fecho de G (a reunião das projecções) • calcular o fecho de X relativamente a G [G não é calculado] • truque: aplicar a operação-Ri até não haver mais alterações simula G Projecto de BD - 28 Aplicação do algoritmo Considerar R= { A B C D } decomposto em { AB, BC, CD } com as dependências F = { A B, B C, C D, D A }. À primeira vista, a projecção de F sobre AB, BC, CD parece não suportar D A. Acontece que, de facto, se projecta o fecho de F e portanto B C, C D, D A B A pelo que F1= { A B, B A}, F2= { B C, C B}, F3= { C D, D C} e F1 + F2 + F3 D A. Verificação deste resultado pelo algoritmo: • • começa-se com Z= {D}, mas {D} [({D} {A, B})+ {A, B}]= {D} idem para a operação-BC; relativamente à operação-CD temos Z= {D} [({D} {C, D})+ {C, D}]= {D} ({D}+ {C, D})= {D} ({A, B, C, D} {C, D})= {C, D} • na passagem seguinte obtém-se Z = {B, C, D} na operação-BC e a seguir Z= {A, B, C, D}, que contém A e logo D A está no fecho das dependências projectadas. Projecto de BD - 29 Método da normalização F - dependências funcionais (chave) F+ - fecho de um conjunto de dependências (axiomas) X+ - fecho de um conjunto de atributos relativamente a F (algoritmo) equivalência de conjuntos de dependências (algoritmo) forma minimal decomposição sem perdas (algoritmo de verificação) decomposição com preservação das dependências (algoritmo de verificação) algoritmo de decomposição sem perdas, para BCNF sem perdas e com preservação das dependências para 3NF Projecto de BD - 30 Primeira forma normal Relação normalizada (1NF) atributos simples ou compostos mas não relações não normalizada: Nr produto data qualidade dia mês ano 1 cebola 01 05 86 egipto 2 feijão 25 06 86 branco, vermelho, frade normalizar: passar a forma tabular, só com valores simples Atributo principal se pertencer a alguma chave candidata da relação Projecto de BD - 31 Segunda forma normal Uma relação é da 2NF, relativamente a F: se XA e A não está em X, então A é principal ou X não é um subconjunto estrito de uma chave não há dependências em partes da chave exemplo Fornecedores • empresa morada • chave: empresa produto • não é 2NF empresa morada produto preço Projecto de BD - 32 Terceira forma normal Uma relação é da 3NF, relativamente a F: se XA e A não está em X, então A é principal ou X contém uma chave Uma 3NF é 2NF e não tem dependências transitivas Exemplo Carros • Carro( matrícula, marca, potência, BI, nome, idade ) • F = {matrícula marca potência, BI nome idade, matrícula BI matrícula BI} • C+=? marca, nome, • Carro não é 3NF potência idade Projecto de BD - 33 Relações 3NF Evidenciam as dependências simples relativamente à chave meio de estruturar a informação mais simples para o utilizador semântica = esquemas + dependências: clarifica mais simples para o SGBD uma relação 3NF tende a representar uma entidadetipo/classe ou uma associação implementada pelo conceito de chave primária basta impedir chaves duplicadas dispensa efeitos colaterais nas inserções e actualizações Projecto de BD - 34 Forma normalizada Boyce-Codd Uma relação é da BCNF, relativamente a F: se XA e A não está em X, então X contém uma chave deixa cair a excepção de A ser principal dependências só na chave não há dependências inesperadas exemplo: relação MORADA não é BCNF e é 3NF todos os atributos são principais não é possível memorizar um código de uma dada cidade se não se conhecer uma rua dessa área MORADA(Cidade, Rua, Cod) F= {Cidade Rua Cod, Cod Cidade} chaves (Cidade, Rua) ou (Cod, Rua) Projecto de BD - 35 Decomposição para 3NF Algoritmo entrada: R e F (forma minimal) saída: decomposição 3NF com preservação das dependências método: • atributos que não apareçam nas dependências formam uma relação • uma associação muitosmuitos entre A e B, representa-se pela dependência artificial AB • decomposição nos esquemas (X,A) para cada XA em F • pares de relações entre cujos tuplos se possa estabelecer uma correspondência biunívoca são agrupados Projecto de BD - 36 Exemplo de decomposição 3NF Carro( matrícula, marca, potência, BI, nome, idade ) F = {matrícula marca potência, BI nome idade} associação muitos para muitos entre carros e pessoas Passo zero Carro( matrícula, marca, potência, BI, nome, idade ) F’ = {matrícula marca, matrícula potência, BI nome, BI idade, BI matrícula } Passo um Nome(BI, nome) Idade(BI, idade ) Marca( matrícula, marca) Potência( matrícula, potência) Proprietário( matrícula, BI) Projecto de BD - 37 Decomposição 3NF (cont.) Passo dois (recomposição) se cada carro tiver dono e um só dono Pessoa(BI, nome, idade ) Carro( matrícula, marca, potência) Proprietário( matrícula, BI) matrícula BI Proprietário ( matrícula, BI) Passo dois’ (recomposição) Pessoa(BI, nome, idade ) Carro( matrícula, marca, potência, BI) Projecto de BD - 38 Outra decomposição 3NF Decomposição Carro( matrícula, marca, potência) • F1 = {matrícula marca potência} Bilhete( matrícula, BI) • F2 = {matrícula BI} Dono(matrícula, nome, idade ) • F3 = {} sem preservação das dependências restrição BI nome idade passa a ser interrelações, não sendo suportada pelo método da normalização SGBD terá que a suportar através de triggers Projecto de BD - 39 Decomposição para BCNF Algoritmo entrada: R e F (forma minimal) saída: decomposição sem perdas em que cada esquema é BCNF relativamente à projecção de F sobre esse esquema método: • • • • • condição inicial: D0 = {R} em cada passo, decompõe-se uma relação que viole a BCNF: Di+1 = Di \ {S} {S1, S2} em que se verifica XA F, {X, A} S, S X+, A X sendo S1 = {X, A} e S2 = S \ {A} não garante a preservação das dependências Projecto de BD - 40 Dependências multívocas Origem das dependências multívocas Centro projecto internamentos programador Manuel António Isabel estatística Eduarda Miguel Centro horário 9-11 14-16 11-13 16-17 não normalizada projecto programador projecto horário (indissociáveis) projecto internamentos internamentos internamentos internamentos internamentos internamentos estatística estatística estatística estatística 1NF Chave trivial programador Manuel António Isabel Manuel António Isabel Eduarda Miguel Eduarda Miguel horário 9-11 9-11 9-11 14-16 14-16 14-16 11-13 11-13 16-17 16-17 Projecto de BD - 41 Efeito Se existem estatística Eduarda 11-13 estatística Miguel 16-17 a dependência multívoca obriga à existência de estatística Miguel 11-13 estatística Eduarda 16-17. Originada pela normalização de relações Manifestam-se pelo facto de a presença de alguns tuplos implicar a presença de outros Dependência multívoca A B em R(A,B,C) se e só se o conjunto de valores de B associados a um par (A,C) depender só de A e não de C Isto é, é o mesmo conjunto qualquer que seja C Projecto de BD - 42 Características Dependências multívocas generalizam dependências funcionais Complementação (U – universo dos atributos) X Y X Y X Y X U-X-Y uma relação só com dois atributos não pode violar a 4NF Junção sem perdas (revisitada) Seja D={R1, R2} uma decomposição de R e F um conjunto de dependências funcionais e multívocas Então D tem uma junção sem perdas relativamente a F se e só se R1 R2 R1 - R2 (ou R2-R1) Projecto de BD - 43 4NF Uma relação é da 4NF, relativamente a F, se para todas as XA então X contém uma chave (XYR). Método da decomposição Se em R(X,A,B), XA e X não contém uma chave, decompõe-se o esquema em R1(X,A) e R2(X,B). Programadores projecto internamentos internamentos internamentos estatística estatística programador Manuel António Isabel Eduarda Miguel Centro não é 4NF Horários projecto internamentos internamentos estatística estatística horário 9-11 14-16 11-13 16-17 Projecto de BD - 44 Conclusão Uma relação que obedeça a uma das formas mais restritivas obedece também às menos restritivas 1NF 2NF Nível de normalização é um problema de semântica e não de valores 3NF BCNF 4NF Não basta olhar para o conteúdo das várias relações para dizer se são 3NF, é preciso saber o significado dos dados e as dependências existentes A normalização é uma disciplina para captar a semântica da realidade. Projecto de BD - 45
Download
