Formas Normais – Parte 2 PDF

Bases de Dados FORMAS NORMAIS – PARTE 2 ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 1 Sudarschan  Forma Normal de Boyce-Codd ▪Uma relação R está na forma BCNF em relação a um conjunto F de dependências funcionais se para todas as dependência...

Bases de Dados FORMAS NORMAIS – PARTE 2 ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 1 Sudarschan  Forma Normal de Boyce-Codd ▪Uma relação R está na forma BCNF em relação a um conjunto F de dependências funcionais se para todas as dependências funcionais em F + da forma → onde   R e   R , pelo menos uma das seguintes situações é válida: ◦  →  é trivial (ou seja,    ) ◦  é uma superchave para R ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 2 Sudarschan  Forma normal de Boyce-Codd (continuação) ▪Exemplo de esquema que não está na forma BCNF: in_dep (ID, name, salary, dept_name, building, budget ) porque : ◦ dept_name→ building, budget ◦ verifica-se em in_dep ◦ mas dept_name não é uma superchave ▪Quando se decompõe in_dept em instrutor e department ◦ instrutor está na BCNF ◦ departament está na BCNF ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 3 Sudarschan  Decompondo um esquema para BCNF ▪Seja R um esquema que não está na BCNF. Seja  →  a dependência funcional que causa uma violação do BCNF. ▪Decompomos R em: (U) (R-(-)) ▪No emplo anterior in_dep , ◦  = dept_name ◦  = building, budget ▪Então, in_dep (ID, name, salary, dept_name, building, budget) deve ser decomposto em: ◦ (  U  ) = (dept_name, building, budget) ◦ ( R - (  -  ) ) = (ID, name, dept_name, salary ) ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 4 Sudarschan  Exemplo ▪R = (A, B, C) F = {A → B, B → C) ▪R 1 = (A, B), R 2 = (B, C) ◦ Decomposição sem perdas: R 1  R 2 = { B } e B → AC ◦ Preservação da dependência ▪R 1 = (A, B), R 2 = (A, C) ◦ Decomposição sem perdas: R 1 R 2= { A } e A → A B ◦ Não preserva a dependência (não é possível verificar B → C sem calcular R 1 R 2 ) ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 5 Sudarschan  BCNF e preservação de dependência ▪Nem sempre é possível atingir a BCNF com preservação da dependência ▪Considere um esquema: dept_advisor(s_ID, i_ID, department_name) ▪Com dependências funcionais: i_ID → dept_name s_ID, dept_name → i_ID ▪dept_advisor não está na BCNF ◦ i_ID não é uma superchave. ▪Qualquer decomposição de dept_advisor não incluirá todos os atributos em s_ID, dept_name → i_ID Assim, não é possível garantir BCNF e preservação da dependência ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 6 Sudarschan  Terceira forma normal Um esquema de relação R está na terceira forma normal (3FN) se para todos:  →  em F+ pelo menos uma das seguintes situações é válida: ◦  →  é trivial (ou seja,    ) ◦  é uma superchave para R ◦ Cada atributo A em  –  está contido numa chave candidata para R. (NOTA : cada atributo pode estar numa chave candidata diferente) ▪Se uma relação está na BCNF, ela está na 3FN (já que na BCNF uma das duas primeiras condições acima deve ser válida). ▪A terceira condição é um relaxamento da BCNF para garantir a preservação da dependência. ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 7 Sudarschan Exemplo 3FN ▪Considere um esquema: dept_advisor ( s_ID , i_ID , dept_name ) ▪Com dependências funcionais: i_ID → dept_name s_ID, dept_name → i_ID ▪Duas chaves candidatas = { s_ID , dept_name }, { s_ID , i_ID } ▪Já vimos anteriormente que dept_advisor não está na BCNF ▪No entanto, está em 3FN, pois ◦ s_ID , dept_name é uma superchave ◦ i_ID → dept_name e i_ID NÃO é uma superchave , mas: ◦ { dept_name} – {i_ID } = {dept_name } e ◦ dept_name está contido numa chave candidata ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 8 Sudarschan Redundância na 3NF Considere o esquema R abaixo, que está na 3FN R = ( J, K, L ) F = { JK → L, L → K } E a instância: Repetição de informação É necessário usar valores nulos (por exemplo, para representar o relacionamento l 2 , k 2 onde não há valor correspondente para J ) ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 9 Sudarschan  Comparação de BCNF e 3NF ▪Vantagens do 3FN sobre a BCNF. É sempre possível obter um desenho na 3FN sem sacrificar a ausência de perdas e a preservação de dependência. Desvantagens da 3FN. ◦ Pode ser necessário usar valores nulos para representar algumas das possíveis associações entre dados. ◦ Pode existir o problema da repetição. ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 10 Sudarschan  Objetivos da Normalização ▪Seja R um esquema de relação com um conjunto F de dependências funcionais. ▪Decida se um esquema de relação R está em “boa” forma. ▪No caso de um esquema de relação R não estar em “boa” forma, é necessário decompô-lo num conjunto de esquemas de relação { R1 , R2 ,..., Rn } tais que: ◦ Cada esquema de relação está em “boa” forma ◦ A decomposição é uma decomposição sem perdas ◦ De preferência, a decomposição deve preservar a dependência. ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 11 Sudarschan  Fecho de um conjunto de dependências funcionais ▪Dado um conjunto F de dependências funcionais, há outras dependências funcionais que são logicamente implícitas por F. ◦ Se A → B e B → C , então podemos inferir que A → C ◦ etc. ▪O conjunto de todas as dependências funcionais logicamente implícitas por F é o fecho de F. Denotamos o fecho de F por F+. ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 12 Sudarschan  Fecho de um conjunto de dependências funcionais Podemos calcular F+ , o fecho de F, aplicando repetidamente os Axiomas de Armstrong : ◦ Regra reflexiva: se   , então  →  ◦ Regra de aumento : se  → , então   →   ◦ Regra de transitividade : se  → , e  →  , então  →  Essas regras são ◦ Corretas -- geram apenas dependências funcionais válidas ◦ Completas — geram todas as dependências funcionais válidas ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 13 Sudarschan  Exemplo de F + ▪R = (A, B, C, G, H, I) F={A→B A→C CG → H CG → I B → H} ▪Alguns membros do F + ◦ A→H ◦ por transitividade de A → B e B → H ◦ AG → I ◦ aumentando A → C com G, para obter AG → CG e então transitividade com CG → I ◦ CG → HI ◦ aumentando CG → I para inferir CG → CGI, e aumento de CG → H para inferir CGI → HI, e então transitividade ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 14 Sudarschan Fecho de Dependências Funcionais (Cont.) Regras adicionais: ◦ União : Se  →  e  → , então  →   ◦ Decomposição : Se  →  , então  →  e  →  ◦ Pseudotransitividade : Se  →  e   → , então   → . As regras acima podem ser inferidas dos axiomas de Armstrong. ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 15 Sudarschan Procedimento para calcular F+ Para calcular o fecho de um conjunto de dependências funcionais F: F+ = F repeat for each dependência funcional f em F + aplicar regras de reflexividade e aumento em f adicione as dependências funcionais resultantes a F+ for each par de dependências funcionais f 1 e f 2 em F + if f 1 e f 2 podem ser combinados usando transitividade then adicione a dependência funcional resultante a F + until F + não mude mais ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 16 Sudarschan  Fecho de conjuntos de atributos ▪Dado um conjunto de atributos  define-se o fecho de  sob F (denotado como + ) como o conjunto de atributos que são funcionalmente determinados por  em F ▪Algoritmo para calcular + , o fecho de  sob F resultado :=  ; while (mudanças no resultado ) do for each  →  in F do begin if   resultado then resultado := resultado   end ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 17 Sudarschan  Exemplo de fecho de conjunto de atributos ▪R = (A, B, C, G, H, I) ▪F = {A → B A→C CG → H CG → I B → H} ▪(AG) + 1. resultado = AG 2. resultado = ABG (A → B) 3. resultado = ABCG (A → C) 4. resultado = ABCGH (CG → H) 5. resultado = ABCGHI (CG → I) ▪AG é uma chave candidata? 1. AG é uma superchave? 1. AG → R? == (AG)+  R 2. Algum subconjunto de AG é uma superchave ? 1. A → R ? == (A)+  R 2. G → R ? == (G)+  R 3. Em geral: verifique cada subconjunto de tamanho n-1 ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 18 Sudarschan  Usos do Fecho de Atributos ▪Existem vários usos do algoritmo de fecho de atributos: ▪Testar superchave : Para testar se  é uma superchave , calculamos + e verificamos se + contém todos os atributos de R. ▪Testar dependências funcionais Para verificar se uma dependência funcional  →  é válida (i.e., está em F + ), basta verificar se   +. Ou seja, calculamos + usando o fecho de atributo e então verificamos se contém . ▪Calcular o fecho de F Para cada   R, encontramos o fecho + , e para cada S  + , produzimos uma dependência funcional  → S. ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 19 Sudarschan  Cobertura canónica ▪Considere um conjunto de dependências funcionais F. Sempre que houver uma atualização na relação, o SGBD deve garantir que a atualização não viola nenhuma dependência funcional; ou seja, todas as dependências funcionais em F são satisfeitas no novo estado da BD. ▪Se uma atualização violar qualquer dependência funcional no conjunto F, o sistema deverá reverter a atualização. ▪Podemos reduzir o esforço gasto na verificação, usando um conjunto simplificado de dependências funcionais que tenham o mesmo fecho que o conjunto fornecido. ▪Este conjunto simplificado é denominado cobertura canónica ▪Para definir a cobertura canónica, devemos primeiro definir os atributos estranhos. ◦ Um atributo de uma dependência funcional em F é estranho se pudermos removê-lo sem alterar F + ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 20 Sudarschan  Atributos estranhos ▪Remover um atributo do lado esquerdo de uma dependência funcional transforma-a numa restrição mais forte. ◦ Por exemplo, se tivermos AB → C e removermos B, obtemos o resultado possivelmente mais forte A → C. É mais forte porque A → C implica logicamente AB → C, mas AB → C não implica logicamente A → C por si só. ▪Dependendo do conjunto F de dependências funcionais, decidimos se é possível remover B de AB → C com segurança. ◦ Por exemplo, suponha que ◦ F = {AB → C, A → D, D → C} ◦ Então podemos mostrar que F implica logicamente A → C, tornando o atributo B estranho em AB → C. ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 21 Sudarschan  Atributos estranhos (continuação) ▪Remover um atributo do lado direito de uma dependência funcional transforma-a numa restrição mais fraca. ◦ Por exemplo, se tivermos AB → CD e removermos C, obteremos a dependência mais fraca AB → D. É mais fraca porque, usando apenas AB → D, não podemos inferir AB → C. ▪Mas, dependendo do conjunto F de dependências funcionais, decidimos se podemos remover C de AB → CD com segurança. ◦ Por exemplo, suponha que F = { AB → CD, A → C} ◦ Então podemos mostrar que mesmo depois de substituir AB → CD por AB → D, ainda podemos inferir AB → C e, portanto, AB → CD. ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 22 Sudarschan  Atributos estranhos ▪Um atributo de uma dependência funcional em F é estranho se pudermos removê-lo sem alterar F + ▪Considere um conjunto F de dependências funcionais e a dependência funcional  →  em F. ◦ Remover do lado esquerdo : O atributo A é estranho em  se ◦ Ae ◦ F implica logicamente ( F – {  →  })  {( – A ) →  }. ◦ Remover do lado direito : O atributo A é estranho em  se ◦ Ae ◦ O conjunto de dependências funcionais ( F – {  →  })  { → (  – A )} implica logicamente F. Nota: a implicação na direção oposta é trivial em cada um dos casos acima, uma vez que uma dependência funcional “mais forte” implica sempre uma mais fraca ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 23 Sudarschan  Testar se um atributo é estranho ▪Seja R um esquema de relação e seja F um conjunto de dependências funcionais que se verificam em R. Considere um atributo na dependência funcional  → . ▪Para testar se o atributo A   é estranho em  ◦ Considere o conjunto: F' = ( F – {  →  })  { → (  – A )}, ◦ verifique se + contém A; se contiver, A é estranho em  ▪Para testar se o atributo A   é estranho em  ◦ Seja  =  – {A}. Verifique se  →  pode ser inferido de F. ◦ Calcule  + usando as dependências em F ◦ Se + inclui todos os atributos em  então , A é estranho em  ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 24 Sudarschan  Exemplos de atributos estranhos ▪Seja F = { AB → CD , A → E, E → C } ▪Para verificar se C é estranho em AB → CD: ◦ Calcule o fecho de AB sob F' = { AB → D, A → E, E → C} ◦ O fecho de AB é ABCDE, que inclui CD ◦ Isto implica que C é estranho ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 25 Sudarschan Cobertura canónica A cobertura canónica para F é um conjunto de dependências Fc tal que ▪F implica logicamente todas as dependências em Fc , e ▪Fc implica logicamente todas as dependências em F, e ▪Nenhuma dependência funcional em Fc contém um atributo estranho e ▪Cada lado esquerdo de uma dependência funcional em Fc é único. Ou seja, não há duas dependências em Fc ◦  1 →  1 e  2 →  2 tal que ◦ 1=2 ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 26 Sudarschan  Cobertura canónica ▪Para calcular uma cobertura canónica para F : repeat Use a regra de união para substituir quaisquer dependências em F do tipo  1 →  1 e  1 →  2 com  1 →  1  2 Encontre uma dependência funcional  →  em Fc com um atributo estranho em  ou em  Se encontrar um atributo estranho, exclua-o de  →  até (F c não mudar) Nota: A regra da União pode se tornar aplicável após alguns atributos estranhos terem sido excluídos, portanto, ela deve ser reaplicada ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 27 Sudarschan  Exemplo: cálculo da cobertura canónica ▪R = ( A, B, C) F = {A → BC , B → C , A → B, AB → C } ▪Combine A → BC e A → B para A → BC ◦ O conjunto agora é {A → BC, B → C, AB → C} ▪A é estranho em AB → C? ◦ Verifique se o resultado da exclusão de A de AB → C é implícito nas outras dependências ◦ Sim: na verdade, B → C já está presente! ◦ O conjunto agora é {A → BC, B → C } ▪C é estranho em A → BC ◦ Verifique se A → C é logicamente implicado por A → B e as outras dependências ◦ Sim : usando transitividade em A → B e B → C. ◦ Pode usar-se o fecho do atributo A em casos mais complexos ▪A cobertura canónica é: A → B , B → C ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 28 Sudarschan Formas Normais VERSÃO SIMPLIFICADA ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 29 Sudarschan  Primeira forma normal (1FN) ▪Um domínio é atómico se os seus elementos são considerados unidades indivisíveis ◦ Exemplos de domínios não atómicos: ◦ Atributos multiplo valor (números de telefone) ◦ Atributos com informação de vários conceitos (e.g., C1.25 – Edifício C, piso 1, sala 25) ▪Um esquema relacional R está na primeira forma normal (1FN) se os domínios de todos os atributos de R são atómicos ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 30 Sudarschan Primeira forma normal (continuação ) Atomicidade é na verdade uma propriedade de como os elementos do domínio são usados. ◦ Exemplo: Strings normalmente seriam consideradas indivisíveis ◦ Suponha os nomes dos clientes são usados para colocar um título, e.g., “Engª Maria”, “Prof. António” ◦ Se a primeira palavra for usada para extrair o título, o domínio não é atómico. ◦ Esta abordagem é muito má ideia: leva à necessidade de codificação no lado da aplicação. ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 31 Sudarschan  Segunda forma normal (2FN) ▪Um esquema relacional R está na segunda forma normal (2FN) se está na 1FN e cada atributo não chave depende completamente dos atributos da chave. ▪ Se estiver na 1FN e chave simples, está na 2FN ▪ Não avalia dependências entre atributos de diferentes chaves ▪ Não avalia dependências entre atributos não chave ▪ NOTA: ser completamente dependente, significa que não depende de parte da chave. Por exemplo, na dependência AB - > C, diz-se que C depende completamente de AB, se não se verifica que A -> C nem B -> C ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 32 Sudarschan  Terceira forma normal (3FN) Um esquema de relação R está na terceira forma normal (3FN) se para todas:  →  em F+ onde   R e   R , pelo menos uma das seguintes situações é válida: ◦  →  é trivial (ou seja,    ) ◦  é uma superchave para R ◦ Cada atributo A em  –  está contido numa chave candidata para R. (NOTA : cada atributo pode estar numa chave candidata diferente) ▪Um esquema relacional R está na terceira forma normal (3FN) se está na 2FN e não existem dependências entre os atributos não chave. ▪ Não avalia dependências entre atributos de diferentes chaves ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 33 Sudarschan  Boyce Codd Normal Form (BCNF) ▪Uma relação R está na forma BCNF em relação a um conjunto F de dependências funcionais se para todas as dependências funcionais em F + da forma → onde   R e   R , pelo menos uma das seguintes situações é válida: ◦  →  é trivial (ou seja,    ) ◦  é uma superchave para R ▪Um esquema relacional R está na BCNF se em todas as dependências funcionais o determinante é uma superchave (ou dependências triviais). ▪Um esquema relacional R está na BCNF se está na 3FN e não existem dependências entre subconjuntos dos atributos das chaves. ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 34 Sudarschan  Boyce Codd Normal Form (BCNF) ▪Exemplo revisitado; Considere um esquema: dept_advisor ( s_ID , i_ID , dept_name ) Com dependências funcionais: i_ID → dept_name s_ID, dept_name → i_ID Duas chaves candidatas = { s_ID , dept_name }, { s_ID , i_ID } ▪Assumimos que está na 1FN (todos os domínios atómicos) ▪Está na 2FN, os atributos não-chave dependem completamente das chaves (não há atributos não-chave) ▪Está na 3FN, pois não existem dependências entre atributos não-chave (não há atributos não-chave) ▪Não está na BCFN pois existem dependências entre subconjuntos dos atributos das chaves: i_ID → dept_name ©José Barateiro 2024 Adaptado de Silberschatz, Korth e BASES DE DADOS, ENGª INFORMÁTICA 2024/25 35 Sudarschan