# Decomposição sem perda de informação

Projeção de dependências, BCNF, junção sem perda, chase e síntese em 3FN.

Página: https://resumos.rgo.pt/cadeiras/bd/decomposicao/

Separar Venda em Produto e Item retira o nome repetido de cada compra. Precisamos agora de provar duas coisas.

Primeiro, que a junção recupera exatamente os tuplos originais. Segundo, que conseguimos verificar as regras nas novas tabelas. Ausência de perda, preservação de dependências e forma normal são propriedades distintas.

## Projeções e reconstrução

Decompor $R(A,B,C)$ em $R_1(A,B)$ e $R_2(B,C)$ divide os **atributos**. Cada nova instância é uma projeção de $R$, com eliminação de duplicados na teoria relacional. Os esquemas, em conjunto, têm de conter todos os atributos originais.

Para reconstruir, fazemos a junção natural dos resultados. A decomposição é **sem perda** se, para toda a instância de $R$ que satisfaz as DFs, essa junção devolve exatamente $R$. Não pode acrescentar tuplos espúrios nem retirar os originais.

Considera dois tuplos originais:

| A | B | C |
| --- | --- | --- |
| 1 | 2 | 3 |
| 4 | 2 | 5 |

As projeções são $(1,2),(4,2)$ em $AB$ e $(2,3),(2,5)$ em $BC$. Como os quatro pares partilham $B=2$, a junção devolve quatro tuplos: os dois originais e $(1,2,5),(4,2,3)$. A reconstrução fica assim:

| A | B | C | Origem |
| --- | --- | --- | --- |
| 1 | 2 | 3 | original |
| 1 | 2 | 5 | espúrio |
| 4 | 2 | 3 | espúrio |
| 4 | 2 | 5 | original |

As linhas espúrias misturam o A de um tuplo com o C do outro. Nenhum atributo desapareceu, mas perdeu-se a correspondência entre A e C.

## Critério para duas relações

Para uma decomposição binária $R\to R_1,R_2$, sob DFs, a junção é sem perda se e só se o conjunto comum determina um dos lados:

$$
(R_1\cap R_2)\to R_1 \quad\text{ou}\quad (R_1\cap R_2)\to R_2.
$$

As dependências são avaliadas no fecho do conjunto original. Se decompomos $ABC$ em $AB$ e $BC$, o comum é $B$. A condição é $B\to A$ ou $B\to C$, omitindo os atributos triviais.

Se $B\to C$, todas as linhas com o mesmo B têm o mesmo C. Uma linha de AB só pode juntar-se ao C que já tinha. Por isso a junção não inventa outra combinação.

No contraexemplo anterior, $B=2$ tem dois valores de C e dois de A. Nenhuma das condições se verifica.

Quando a condição se verifica, a reconstrução é exata. Com $B\to C$ e os tuplos $(1,2,3)$ e $(4,2,3)$, as projeções são $(1,2),(4,2)$ em AB e $(2,3)$ em BC. A junção devolve os dois originais e nenhum espúrio.

Não concluas que qualquer sequência de projeções é sem perda só porque “as tabelas têm uma coluna comum”. Uma coluna comum permite juntar; a dependência funcional é que justifica a reconstrução correta.

## Projetar dependências

Ao estudar uma relação resultante, usamos todas as DFs implicadas que envolvem apenas os seus atributos. Não basta retirar da lista original as setas com atributos ausentes.

Com $A\to B$ e $B\to C$, a projeção sobre $AC$ inclui $A\to C$, embora essa seta não estivesse escrita originalmente. Para a descobrir, calculamos $A^+$ no conjunto original e conservamos os atributos de AC que aparecem no fecho.

Uma forma sistemática é calcular fechos dos subconjuntos do novo esquema e obter as dependências internas. Em esquemas pequenos, é praticável à mão. Omite as triviais e as redundantes quando apresentares uma base da projeção.

## Decompor até BCNF

Escolhe uma DF não trivial $X\to Y$ cujo determinante não seja superchave. Uma decomposição usual é:

$$
R_1=X\cup Y,\qquad R_2=R-(Y-X).
$$

A interseção contém X, que determina $R_1$, por isso este passo é sem perda. A variante que usa $X^+$ escolhe $R_1=X^+$ e $R_2=X\cup(R-X^+)$. Também é válida. Em ambos os casos, projeta as DFs e repete até todas as relações estarem em BCNF.

Vamos decompor $R(A,B,C,D,E)$ com $AB\to C$, $C\to D$ e $D\to E$. Já sabemos que a candidata é AB.

1.  $D\to E$ viola BCNF, porque $D^+=DE$. Separamos $DE$ e $ABCD$. O comum D determina DE, logo não há perda.
2.  Em ABCD, $C\to D$ viola BCNF. Separamos CD e ABC. O comum C determina CD.
3.  DE está em BCNF, com candidata D. CD também, com candidata C. Em ABC, AB determina C e é candidata; a relação está em BCNF.

O resultado é $ABC,CD,DE$. Cada passo é sem perda, logo a composição dos passos também o é.

A preservação verifica-se em separado. Cada DF original aparece projetada numa das relações: $AB\to C$ em ABC, $C\to D$ em CD e $D\to E$ em DE. A preservação segue dessa localização das DFs, não da ausência de perda. São propriedades independentes, como mostra a secção seguinte.

Uma ordem diferente de escolhas pode produzir esquemas diferentes. Verifica propriedades dos esquemas obtidos, em vez de decorar uma única resposta textual.

## Preservação de dependências

Uma decomposição **preserva as dependências** quando as DFs projetadas sobre as novas relações, tomadas em conjunto, implicam todas as DFs originais. Assim, podemos verificar as regras separadamente sem juntar tabelas.

Considere-se $R(A,B,C)$ com $AB\to C$ e $C\to B$. A DF $C\to B$ viola BCNF. Decompomos em $CB$ e $AC$.

A junção é sem perda: o atributo comum C determina CB. As duas relações estão em BCNF. Porém, não preservam $AB\to C$. Em CB só temos $C\to B$; em AC não há DF não trivial. O fecho de AB sob as DFs locais continua AB, sem C.

O problema pode ser visto nos dados. CB contém $(c_1,b)$ e $(c_2,b)$; AC contém $(a,c_1)$ e $(a,c_2)$. Cada tabela respeita as suas DFs, mas a junção tem dois C distintos para o mesmo par $(a,b)$, violando $AB\to C$.

Ideia-chave

**Sem perda e preservação são propriedades diferentes.** A primeira diz que podemos reconstruir projeções de uma instância válida. A segunda diz que validar tabelas isoladas chega para garantir as regras na instância reconstruída.

## Síntese em 3FN

A síntese em 3FN consegue uma decomposição sem perda que preserva DFs, aceitando a exceção dos atributos primos.

1.  Obtém uma cobertura mínima com um atributo à direita.
2.  Para cada DF $X\to A$, cria uma relação com $X\cup\{A\}$. Podes reunir DFs com o mesmo determinante numa relação.
3.  Retira relações cujo esquema esteja contido no de outra.
4.  Se nenhuma relação contiver uma chave candidata do esquema original, acrescenta uma relação com essa chave.

A última condição assegura a ligação necessária à reconstrução. Não basta criar uma relação para cada seta e esquecer atributos sem dependências.

Para $R(A,B,C,D)$ com cobertura mínima $A\to B$, $B\to C$, $A\to D$, obtemos ABD e BC. A candidata A já está em ABD. As relações estão em 3FN, a junção é sem perda pelo comum B que determina BC, e cada DF tem lugar numa das relações.

Para o exemplo $AB\to C$, $C\to B$, a síntese cria ABC e CB. Como CB está contida em ABC, retiramo-la. Ficamos com ABC, que está em 3FN porque todos os atributos são primos. Conservamos a dependência que a decomposição BCNF tinha perdido.

### Atributos ausentes das dependências

Em $R(A,B,C,D,E)$ com $AB\to C$, $C\to B$ e $A\to D$, a síntese começa por ABC, CB e AD. CB está contida em ABC e pode ser retirada. Mas E ainda não aparece em nenhum esquema: ABC e AD nem sequer cobrem todos os atributos de R.

As candidatas são ABE e ACE. A e E têm de estar em qualquer chave porque nenhuma DF os produz. Acrescentar B permite obter C e D; acrescentar C permite obter B e D. Nenhum atributo desses pares substitui A ou E.

Acrescentar ABE ou ACE resolve a cobertura e a exigência de incluir uma candidata. Acrescentar apenas AE recupera o atributo E, mas não garante ausência de perda: AE só liga E a A e não conserva a combinação desse E com B e C. Cobrir atributos e conter uma candidata são verificações distintas do último passo da síntese.

## Chase para várias relações

O critério binário não testa diretamente uma decomposição arbitrária em três ou mais relações. O **chase** constrói um tableau e aplica as DFs para descobrir se a junção consegue recuperar um tuplo sem ambiguidades.

Cria uma coluna por atributo e uma linha por relação. Numa coluna A, escreve o símbolo distinguido $a_A$ se a relação dessa linha contém A. Nas outras células, escreve símbolos próprios, como $b_{1C}$, que começam distintos de todos os restantes.

Para cada DF $X\to Y$, procura linhas que concordem nas colunas X. Unifica os símbolos nas colunas Y, substituindo todas as ocorrências do símbolo. Se um dos símbolos for distinguido, conserva-o; se nenhum for, escolhe um e conserva a escolha. Repete até estabilizar. Se alguma linha ficar com símbolos distinguidos em todas as colunas, a decomposição é sem perda.

Exemplo: $R(A,B,C)$, $A\to B$, $B\to C$, decomposta em AB, BC e AC.

| Relação | A | B | C |
| --- | --- | --- | --- |
| AB | $a_A$ | $a_B$ | $b_{1C}$ |
| BC | $b_{2A}$ | $a_B$ | $a_C$ |
| AC | $a_A$ | $b_{3B}$ | $a_C$ |

As linhas AB e AC concordam em $a_A$. Por $A\to B$, substituímos $b_{3B}$ por $a_B$:

| Relação | A | B | C |
| --- | --- | --- | --- |
| AB | $a_A$ | $a_B$ | $b_{1C}$ |
| BC | $b_{2A}$ | $a_B$ | $a_C$ |
| AC | $a_A$ | $a_B$ | $a_C$ |

Agora as três linhas concordam em B. Por $B\to C$, substituímos $b_{1C}$ por $a_C$:

| Relação | A | B | C |
| --- | --- | --- | --- |
| AB | $a_A$ | $a_B$ | $a_C$ |
| BC | $b_{2A}$ | $a_B$ | $a_C$ |
| AC | $a_A$ | $a_B$ | $a_C$ |

A linha AB ficou $(a_A,a_B,a_C)$, provando junção sem perda.

O chase aplica **igualdades de símbolos**, não faz uma junção numérica de uma amostra. Se estabilizar sem linha totalmente distinguida, a decomposição tem perda para alguma instância que satisfaz as DFs dadas. Isto não afirma que todas as amostras geram tuplos espúrios; afirma que não há garantia para todas as instâncias válidas.

## Exercícios

Coluna comum não chega

R(A,B,C) tem apenas A → B. A decomposição em AB e BC é sem perda? Dá uma justificação por dependências e um contraexemplo se falhar.

Pista

O atributo comum é B, não A.

Mais uma pista

Experimenta (1,2,3) e (4,2,5), que satisfazem A → B.

Solução

Não há garantia de junção sem perda. B+ é só B, não determina AB nem BC. Nos tuplos (1,2,3) e (4,2,5), a DF A → B é satisfeita, mas as projeções AB e BC juntam também (1,2,5) e (4,2,3). Estes são tuplos espúrios. A presença de B nos dois lados não conserva a correspondência original entre A e C.

Confere a tua resposta:

*   Usei o fecho do atributo comum.
*   Dei uma instância válida e dois tuplos espúrios.

Erros frequentes

Não testes a DF a partir de uma amostra que por acaso tem Bs distintos. A propriedade tem de valer para todas as instâncias válidas.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/bd/decomposicao/#crit%C3%A9rio-para-duas-rela%C3%A7%C3%B5es)

Sem perda mas sem preservação

R(A,B,C), com AB → C e C → B, é decomposta em CB e AC. Verifica BCNF, junção sem perda e preservação das DFs.

Pista

C determina CB. Em AC, há alguma DF não trivial projetada?

Mais uma pista

Calcula AB+ usando apenas C → B, a DF local não trivial.

Solução

CB está em BCNF, com candidata C; AC está em BCNF, com candidata AC e sem DFs não triviais. A junção é sem perda porque a interseção C determina CB. Não preserva AB → C: sob as DFs locais, AB+ = AB. CB com (c1,b),(c2,b) e AC com (a,c1),(a,c2) respeitam as regras locais, mas a junção dá dois Cs para o mesmo AB. O original já estava em 3FN, por isso mantê-lo é uma alternativa se a preservação for necessária.

Confere a tua resposta:

*   Verifiquei BCNF nas duas relações.
*   Provei junção sem perda.
*   Demonstrei a dependência não preservada.

Erros frequentes

As três propriedades não são sinónimos. Sem perda refere-se à reconstrução de projeções válidas; preservação refere-se à suficiência das verificações locais.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/bd/decomposicao/#preserva%C3%A7%C3%A3o-de-depend%C3%AAncias)

A síntese precisa de ligar os factos

R(A,B,C,D) tem apenas A → B e C → D. A síntese cria AB e CD. Está completa? Obtém uma decomposição em 3FN sem perda e que preserve as dependências.

Pista

Quais os atributos que não aparecem à direita?

Solução

A e C têm de pertencer a todas as chaves. AC determina B e D, e retirar A ou C deixa de determinar o esquema completo, por isso AC é candidata. AB e CD preservam as duas dependências, mas não contêm uma candidata original. Acrescenta AC, ficando AB, CD e AC. O passo da candidata completa a síntese sem perda. Podemos também ver a reconstrução em duas etapas: AC junta AB pelo A, que determina AB; o resultado ABC junta CD pelo C, que determina CD. Todas as relações estão em BCNF e, portanto, em 3FN.

Confere a tua resposta:

*   Encontrei AC como candidata.
*   Acrescentei AC à síntese AB e CD.
*   Justifiquei preservação e junção sem perda.

Erros frequentes

AB e CD não têm atributos comuns e a sua junção é um produto cartesiano, que pode inventar combinações de A e C. Preservar as setas não chega para conservar a correspondência original.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/bd/decomposicao/#s%C3%ADntese-em-3fn)

O chase termina sem provar a reconstrução

R(A,B,C) tem apenas AB → C e é decomposta em AB, AC e BC. Aplica o chase. A decomposição é sem perda? Confere também a instância (1,1,2), (1,2,1), (2,1,1).

Pista

A DF só atua quando duas linhas concordam em A e B ao mesmo tempo.

Solução

As linhas iniciais são (aA,aB,b1C), (aA,b2B,aC) e (b3A,aB,aC). Nenhum par concorda simultaneamente em A e B. Não há unificações e nenhuma linha fica totalmente distinguida, logo a decomposição tem perda. Na instância dada, cada AB é diferente, por isso AB → C é satisfeita. Porém, as projeções contêm AB=(1,1), AC=(1,1) e BC=(1,1). A junção acrescenta (1,1,1). Ter conservado todos os pares não conservou o triplo.

Confere a tua resposta:

*   Construí três linhas com símbolos diferentes nas posições ausentes.
*   Observei que nenhuma DF pode unificar símbolos.
*   Dei um tuplo espúrio numa instância que satisfaz AB → C.

Erros frequentes

Não unifiques apenas porque duas linhas concordam em A, nem uses a DF ao contrário. Os símbolos das posições ausentes começam distintos.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/bd/decomposicao/#chase-para-v%C3%A1rias-rela%C3%A7%C3%B5es)

Decompor até BCNF por etapas

R(A,B,C,D,E) tem AB → C, C → D e D → E. Decompõe até BCNF, prova que cada passo é sem perda e verifica preservação das dependências.

Pista

Escolhe uma DF cujo fecho não contenha o esquema inteiro.

Solução

D+ = DE, por isso D → E viola BCNF. Separa DE e ABCD; o comum D determina DE. Em ABCD, onde E já saiu, C+ = CD, por isso C → D viola BCNF. Separa CD e ABC; o comum C determina CD. DE, CD e ABC estão em BCNF, com candidatas D, C e AB. Cada DF original vive numa relação, por isso a decomposição também preserva as dependências.

Confere a tua resposta:

*   Justifiquei cada DF escolhida com um fecho incompleto.
*   Provei cada passo sem perda pelo atributo comum.
*   Verifiquei BCNF e preservação no resultado.

Erros frequentes

Não concluas preservação a partir da ausência de perda. Localiza cada DF original nas relações finais.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/bd/decomposicao/#decompor-at%C3%A9-bcnf)

Recuperar um atributo não é conservar as suas combinações

R(A,B,C,D,E) está em 1FN e tem apenas AB → C, C → B e A → D. Uma síntese propõe ABC, CB e AD. Encontra todas as candidatas e retira esquemas contidos noutros. Compara acrescentar AE com acrescentar ABE ou ACE.

Para conferir AE, usa os tuplos `(a,b1,c1,d,e1)` e `(a,b2,c2,d,e2)`, com b1≠b2, c1≠c2 e e1≠e2. Quais as propriedades garantidas por cada opção? Indica tuplos espúrios quando existirem.

Pista

E não aparece nas DFs, mas continua a ser atributo de R. O que liga cada E ao par B/C original?

Solução

A e E têm de estar em todas as candidatas. AE não obtém B nem C. ABE obtém C por AB → C e D por A → D; ACE obtém B por C → B e D por A → D. São mínimas e são as únicas candidatas. CB está contida em ABC, por isso ficamos com ABC e AD, ainda sem E.

Acrescentar AE cobre todos os atributos e conserva relações em 3FN. As DFs originais são verificáveis em ABC e AD. Porém, não garante junção sem perda: as projeções ABC e AD mantêm os dois pares B/C e AE contém `(a,e1)` e `(a,e2)`. A junção acrescenta `(a,b1,c1,d,e2)` e `(a,b2,c2,d,e1)`. A instância original satisfaz as três DFs, mas a ligação de E ao par perdeu-se.

Acrescentar ABE ou ACE inclui uma candidata e completa a síntese em 3FN, sem perda e com preservação. Em ABC, AB e AC são candidatas e B é primo, por isso C → B satisfaz 3FN. AD tem candidata A. ABE e ACE não têm DFs não triviais internas e estão em BCNF. A garantia final resulta do algoritmo completo, incluindo a relação da candidata.

Confere a tua resposta:

*   Encontrei ABE e ACE como únicas candidatas.
*   Distingui cobertura de atributos, forma normal e ausência de perda.
*   Mostrei tuplos espúrios com AE e completei a síntese com uma candidata.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/bd/decomposicao/#atributos-ausentes-das-depend%C3%AAncias)