# Dependências funcionais e normalização Fechos, chaves candidatas, 3FN e BCNF, com decomposições sem perda e preservação de dependências. Página: https://resumos.rgo.pt/cadeiras/lbaw/normalizacao/ | Bilhete | Sessão | Evento | Título atual | | --- | --- | --- | --- | | B1 | S12 | E3 | Noite de Fado | | B2 | S12 | E3 | Noite de Fado | Se o título do evento mudar, é preciso corrigir as duas linhas, e escolher `Bilhete` como chave não elimina essa repetição. A **normalização** usa dependências funcionais para separar factos, como fizemos ao guardar o título em `eventos`; as regras vêm do domínio, não apenas das coincidências nos dados atuais. O cálculo de fechos e formas normais usa por isso uma relação de matrículas com dependências explícitas. ## Dependência funcional e fecho Em `R(aluno, uc, docente, sala)`, vamos assumir três regras: um aluno pode frequentar várias UC; cada UC tem um docente; cada docente tem uma sala. Escrevemos `uc → docente` e `docente → sala`. A dependência `X → Y` diz que duas linhas que concordam em todos os atributos de X também concordam em Y. Não afirma que Y identifica X. Por transitividade, `uc → sala`. A dependência `(aluno,uc) → aluno` é **trivial**, porque o lado direito já está no esquerdo. As regras de Armstrong são reflexividade, aumento e transitividade: se `X → Y`, então `XZ → YZ`; se também `Y → Z`, então `X → Z`. O **fecho X⁺** reúne os atributos que X determina. Começa em X e aplica dependências até deixar de acrescentar atributos: | Passo para `{uc}⁺` | Atributos conhecidos | | --- | --- | | Inicial | uc | | uc → docente | uc, docente | | docente → sala | uc, docente, sala | Falta aluno. `{uc}` não é superchave. `{aluno,uc}⁺` contém os quatro atributos, logo é superchave. É **chave candidata** porque retirar qualquer dos dois atributos deixa de determinar tudo. Uma superchave pode ter atributos a mais; uma chave candidata é mínima por inclusão, não apenas a que tem menos caracteres. Um atributo é **primo** se pertence a alguma chave candidata. Ao estudar 3FN precisas de todas as chaves candidatas, não só da chave primária escolhida para o SQL. ![Aluno e UC juntos identificam uma matrícula. UC determina docente, que determina sala.](https://resumos.rgo.pt/cadeiras/lbaw/normalizacao/figura-1.svg) ## As anomalias que queremos retirar Com `(Ana,PFL,Joana,B204)` e `(Bruno,PFL,Joana,B204)` na mesma tabela: * **Atualização:** mudar a sala da Joana exige atualizar as duas linhas. Alterar só uma viola `docente → sala`. * **Inserção:** não conseguimos guardar uma UC nova sem inventar uma matrícula, se aluno fizer parte da chave obrigatória. * **Eliminação:** apagar a última matrícula de PFL também apaga a informação de quem a leciona. Escolher um `id` artificial para cada linha não resolve nenhuma destas repetições. As dependências do domínio continuam a existir. ## 1FN, 2FN, 3FN e BCNF Considera dependências não triviais que resultam das regras declaradas, incluindo as inferidas. | Forma | O que verificar | | --- | --- | | 1FN | Cada posição contém um valor do domínio definido, sem um grupo repetido usado como várias linhas escondidas. | | 2FN | Está em 1FN e nenhum atributo não primo depende de uma parte própria de uma chave candidata. | | 3FN | Para cada X → A, X é superchave ou A é primo. | | BCNF | Para cada X → Y não trivial, X é superchave. | Uma lista de UC separada por vírgulas numa coluna torna difíceis as restrições e as junções por UC. Converte-a numa relação de matrículas. O facto de o PostgreSQL suportar arrays e JSON não elimina a necessidade de escolher o modelo adequado ao problema. Na nossa relação, `uc → docente` viola 2FN, pois UC é uma parte da chave `(aluno,uc)` e docente não é primo; `docente → sala` também impede BCNF, pois docente não é superchave da relação completa. Decompomos por isso em: ``` matricula(aluno, uc) chave: (aluno, uc) uc(uc, docente) chave: uc docente(docente, sala) chave: docente ``` Em cada relação, os determinantes das dependências não triviais são chaves, sob estas regras. As três estão em BCNF. Se uma UC puder ter vários docentes, `uc → docente` deixa de valer e esta solução tem de mudar. Normaliza a partir das regras reais, não de uma relação que gostarias de ter. ## Decomposição sem perda e preservação de dependências Uma decomposição é **sem perda** quando juntar as projeções recupera exatamente a relação original, sem fabricar combinações. Para uma decomposição binária `R1,R2`, sob dependências funcionais, basta que os atributos comuns determinem todos os atributos de R1 ou de R2. Este critério também é necessário neste contexto. Ao separar `docente,sala` do resto, a interseção é docente e `docente → sala` determina a primeira relação. Ao separar `uc,docente`, a interseção é UC e UC determina essa relação. Os dois passos são sem perda. A decomposição **preserva dependências** se as regras projetadas nas relações novas permitem verificar todas as dependências originais, sem fazer uma junção. No exemplo, `uc → docente` e `docente → sala` ficam em tabelas próprias, logo são preservadas. Contraexemplo: em `R(A,B,C)`, sejam `AB → C` e `C → B`. As chaves candidatas são AB e AC. `C → B` satisfaz 3FN porque B é primo, mas viola BCNF porque C não determina A. Decompomos em `CB` e `AC`: é sem perda porque C determina CB. Porém, `AB → C` não fica preservada. | Instância de CB | | | Instância de AC | | | | --- | --- | --- | --- | --- | --- | | C | B | | A | C | | | c1 | b1 | | a1 | c1 | | | c2 | b1 | | a1 | c2 | | A junção produz `(a1,b1,c1)` e `(a1,b1,c2)`, violando `AB → C`. Para impedir isto precisamos de coordenação entre tabelas, ou de uma decomposição que preserve a regra. BCNF reduz certas anomalias adicionais, mas nem sempre conserva todas as dependências; uma síntese em 3FN pode ser preferível quando essa conservação é essencial. Sem perda descreve a reconstrução de dados originalmente válidos, enquanto preservação descreve a possibilidade de impedir novas escritas inválidas por verificações locais. ## Resolver uma pergunta de normalização 1. Escreve os atributos e as dependências que o enunciado autoriza. 2. Calcula fechos para encontrar todas as chaves candidatas. 3. Identifica os atributos primos e testa a forma pedida. 4. Mostra uma dependência concreta que viola a forma, quando existe. 5. Decompõe e justifica separadamente ausência de perda e preservação de dependências. Dizer «tem uma chave primária, portanto está normalizada» não demonstra uma forma normal. No exemplo das matrículas, a verificação depende das regras `uc → docente` e `docente → sala`, não da presença de uma PK artificial. ## Desnormalização é uma decisão de custo Depois de normalizar, pode haver uma leitura frequente cujo custo justifica guardar um valor derivado. Um total de bilhetes pagos por sessão evita contar sempre todas as linhas, mas precisa de ser atualizado em cada compra, cancelamento ou correção. Se um desses caminhos o esquecer, o total deixa de representar os dados. Esta **desnormalização** troca certas leituras por mais armazenamento e coordenação nas escritas. Mede a carga antes e depois. Não é uma garantia automática de maior velocidade, nem uma razão para omitir as dependências e as invariantes do desenho. Um preço histórico da compra tem outro significado que o preço atual; guardá-lo não é duplicar o mesmo facto. ## Exercícios Calcular o fecho de um atributo R(A,B,C,D), A→B e B→C. Qual é o fecho de A? Pista Começa com A e aplica todas as regras possíveis. Mais uma pista D não aparece no lado direito de nenhuma regra útil. Solução A⁺={A,B,C}. AD é chave candidata neste conjunto de dependências: determina tudo e nenhum atributo pode ser retirado. * **A,B,C..** A não determina D pelas dependências dadas. * **A,B,C,D..** Não há regra que obtenha D. * **Só A,B..** B→C permite acrescentar C. Erros frequentes Não acrescentes uma dependência porque parece natural nos dados. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/lbaw/normalizacao/#depend%C3%AAncia-funcional-e-fecho) Justificar a violação R(A,B,C), AB→C e C→B. Está em BCNF? Pista Calcula C⁺. Mais uma pista C⁺={C,B}, sem A. Solução Não. C→B é não trivial e C não é superchave. Está em 3FN: B é primo porque pertence à chave AB. Confere a tua resposta: * Calculo chaves AB e AC. * Mostro que C não é superchave. * Uso C→B como violação não trivial. Erros frequentes Não chames BCNF a toda a relação em 3FN. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/lbaw/normalizacao/#1fn-2fn-3fn-e-bcnf) Verificar a interseção A decomposição R(A,B,C) em AB e BC é garantidamente sem perda apenas com A→B? Pista O atributo comum é B, não A. Mais uma pista Aplica o critério à interseção. Solução Não há garantia. Linhas (a1,b,c1) e (a2,b,c2) satisfazem A→B; projetar e juntar cria também (a1,b,c2) e (a2,b,c1). * **Não. B não determina nenhuma das duas relações..** A interseção é B; a regra dada não garante B→A nem B→C. * **Sim, porque B existe nas duas..** Uma interseção não basta sem a dependência adequada. * **Sim, toda a decomposição binária é sem perda..** Podem surgir tuplos espúrios. Erros frequentes Não confundas recuperar atributos com recuperar exatamente os tuplos originais. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/lbaw/normalizacao/#decomposi%C3%A7%C3%A3o-sem-perda-e-preserva%C3%A7%C3%A3o-de-depend%C3%AAncias) Duas propriedades diferentes Em R(A,B,C), AB→C e C→B, o que perde a decomposição CB,AC? Pista C determina a relação CB. Mais uma pista Nenhuma das tabelas contém A e B juntos. Solução A decomposição é sem perda para relações válidas, mas não preserva AB→C. Por exemplo, CB contém (c1,b1) e (c2,b1), e AC contém (a1,c1) e (a1,c2). A junção cria (a1,b1,c1) e (a1,b1,c2): o mesmo AB determina dois C. As regras locais aceitam as tabelas, mas não impedem esta violação. Confere a tua resposta: * Conservo a ausência de perda por C→B. * Identifico AB→C como não preservada. * Mostro que validação local não chega. Erros frequentes Não confundas uma garantia sobre projetar dados válidos com uma garantia sobre todas as novas escritas. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/lbaw/normalizacao/#decomposi%C3%A7%C3%A3o-sem-perda-e-preserva%C3%A7%C3%A3o-de-depend%C3%AAncias) Decompor uma relação de matrículas Considera `R(aluno, uc, docente, sala)` em 1FN. As dependências dadas são `uc → docente` e `docente → sala`, sem outras regras além das inferidas. Encontra as chaves candidatas, decompõe até BCNF e justifica ausência de perda e preservação de dependências. Pista Atributos que nunca podem ser acrescentados pelo fecho têm de estar na chave inicial. Solução `aluno` e `uc` não surgem em lados direitos, por isso têm de pertencer a qualquer chave. O fecho de `(aluno,uc)` inclui docente por `uc → docente` e sala por `docente → sala`. É a única chave candidata. `uc` não determina aluno e `docente` não determina aluno nem uc, portanto ambos violam BCNF em R. ``` matricula(aluno, uc) chave: aluno, uc uc(uc, docente) chave: uc docente(docente, sala) chave: docente ``` Primeiro separa docente e sala: a interseção docente determina essa relação. Depois separa uc e docente: a interseção uc determina essa relação. Ambos os passos são sem perda. As duas dependências originais ficam verificáveis nas suas próprias tabelas, logo são preservadas. Cada relação resultante tem apenas determinantes que são superchaves, sob as regras dadas. Confere a tua resposta: * Justifico a chave aluno, uc. * Identifico os determinantes que não são superchaves. * Verifico BCNF, ausência de perda e preservação. [Voltar à explicação](https://resumos.rgo.pt/cadeiras/lbaw/normalizacao/#1fn-2fn-3fn-e-bcnf)