Decomposição sem perda de informação

Sem perda: o teste

Decompor reparte atributos em esquemas cuja união cobre o original; cada instância nova é uma projeção. A decomposição é sem perda se a junção natural recuperar exatamente os tuplos originais em toda instância válida sob as DFs.

• Duas relações: sem perda se e só se $(R_1\cap R_2)\to R_1$ ou $(R_1\cap R_2)\to R_2$, com DFs avaliadas no fecho das originais. Em $ABC\to AB,BC$, $B$ tem de determinar $A$ ou $C$.
• Sem a condição, $(1,2,3)$ e $(4,2,3)$ com $B=2$ geram também $(1,2,5)$ e $(4,2,3)$: perde-se a correspondência entre $A$ e $C$.
• Uma coluna comum permite juntar; só a DF justifica reconstruir sem espúrios.

Preservar: o outro teste

Usa na relação resultante todas as DFs implicadas internas ao seu esquema: de $A\to B$ e $B\to C$, a projeção em $AC$ inclui $A\to C$.

Há preservação se a união das DFs projetadas implicar as originais; permite validar cada tabela isoladamente. Forma normal, ausência de perda e preservação são três propriedades independentes.

Com $AB\to C$ e $C\to B$, decompor $ABC$ em $CB,AC$ dá BCNF e junção sem perda ($C$ determina $CB$), mas perde $AB\to C$: sob as DFs locais, $(AB)^+=AB$.

Procedimentos

Até BCNF:

1. Escolhe DF não trivial $X\to Y$ com $X$ não superchave.
2. Separa $R_1=X\cup Y$ e $R_2=R-(Y-X)$; o passo é sem perda porque o comum contém $X$.
3. Projeta as DFs e repete; confere a preservação à parte.

Com $AB\to C$, $C\to D$, $D\to E$: separa $DE$ de $ABCD$ e $CD$ de $ABC$; resultado $ABC,CD,DE$, aqui também com preservação.

Síntese em 3FN (sem perda e com preservação garantidas):

1. Cobertura mínima com direitas unitárias.
2. Uma relação $X\cup\{A\}$ por $X\to A$, reunindo direitas do mesmo determinante.
3. Retira esquemas contidos noutros.
4. Se nenhum esquema contiver uma candidata original, acrescenta-a.

Com só $A\to B$ e $C\to D$ em $ABCD$, $AB,CD$ não chegam: acrescenta a candidata $AC$. Em $ABCDE$ com $AB\to C$, $C\to B$, $A\to D$, as candidatas são ABE e ACE; acrescentar só AE cobre $E$ mas não contém candidata nem garante junção sem perda.

Chase (três ou mais relações): uma coluna por atributo e uma linha por relação, com $a_A$ onde o esquema contém $A$ e símbolos próprios distintos nas ausências. Aplica cada DF às linhas que concordam na esquerda, unificando a direita em todas as ocorrências e conservando distinguidos. Uma linha $(a_A,a_B,a_C)$ prova ausência de perda; estabilizar sem nenhuma prova perda para alguma instância válida.

Tableau e aplicação do chase.