Exemplo de Decomposição BCNF
(sem calcular F+)
 Problema: decompor para a
BCNF a relação
R(A,B,C,D,E,F,G,H) com
F = {A BCH, CH CD,
E FG, G CH, A CD}
 Decomposição:
R1(A,E,F,G)
R2(A,B,C,D,H)
R3(A,E)
R4(E,F,G)
R5(A,B,C,H)
R6(C,D,H)
Database System Concepts
result := {R};
done := false;
calcular F+;
while (not done) do
if (há um esquema Ri em result que não está na BCNF)
then begin
Seja
uma dependência (não trivial)
sobre Ri tal que
Ri F+, e
= ;
result := (result – Ri) (Ri – ) ( , );
end
else done := true;
Para todo o subconjunto de atributos de Ri, verificar se +
(fecho relativo a F) não inclui nenhum atributo de Ri - , ou
inclui todos os atributos de Ri.
•Se a condição do teste for violada para um subconjunto
R2(A,B,C,D,H) está
na BCNF?
de atributos de Ri, então a dependência funcional
( +R1(A,E,F,G)
está
na
R4(E,F,G)
na)⊂R2
BCNF?
Testar
paraestá
cada
se a F+.
RiBCNF?
pertence
•Usa-se
essa
dependência
decompor
Ri
+ não
Testar
para
cada
β∈F1
não trivial
se

1.
contém
qualquer
elemento
depara
R2-
ou+=R1
Testar
para
cada
⊂R4
se
2.
todos
osde
elementos
de R2
Obriga
ao
cálculo
F1.elemento
Em alternativa…
1.+ contém
não
contém
qualquer
de
ou
Após
testar
de
forma
semelhante
asR4-
relações
+
+
2. contém
todos
os
elementos
deviola
R4 2 ⇒ ok.
={A}
⇒
 ={A,B,C,D,H}.
Testar
para
cada
⊂R1
seNão
R5(A,B,C,H)
e
R6(C,D,H),
conclui-se
que
+={C,D,E,F,G,H}.
+ não contém
={E}
Não
viola
2⇒
1.
qualquer
elemento
de
R1-
ouok.
={B}
⇒

={B}.
Não
viola
1
⇒
ok.
R3(A,E)
está
nana
BCNF?
R(A,B,C,D,E,F,G,H)
está
na
BCNF?
também
estão
BCNF.
+
+todos
2.
contém
os
elementos
deok.
R1
={F}
⇒ cada
={F}.
Não
viola
1⇒
...
Testar
para
⊂R3
se não
Testar
para
cada
β∈F
trivial
se +=R
+
+
+
+ não ⇒
={A}
 ={A,B,C,D,H}.
Não
viola
={G}
={C,D,G,H}.
Não
1 1⇒⇒ok.
={H}
⇒
={H}.
Não viola
1 +viola
⇒
ok.R3-
1.
contém
qualquer
elemento
de
ouok. ≠ R
Considerando
ABCH
⇒
{A}
={A,B,C,D,H}
+={C,D,E,F,G,H}.
+ contém
++={C,D,E,F,G,H}.
={E}
⇒⇒
+todos
2.
os elementos deNão
R3 viola 2 ⇒ ok.
={EF}
={CH}
⇒
={CDH}.
Como {A}+ ≠R,
R
não
está
na
BCNF.
+={C,D,E,F,G,H}.
Como
duas
R1
não
na
={A}
⇒falha
 ={A,B,C,D,H}.
Não
viola
1viola
⇒ ok.
={EG}
as
Não
2está
⇒ i.e.
ok.
Como
falha
as
duas
condições,
R2
não
está
na BCNF.
BCNF.
+condições,
+ para
Usa-se
a⇒
DF


(
-)∈F
decompor
+
+
+
Usa-se
aa⇒DF

R1
para
={E}
⇒
={C,D,E,F,G,H}.
Não
={FG}
 ={C,D,F,G,H}.
Não
viola1decompor
1⇒⇒ok.
ok. i.e.
Usa-se
DF

 (
(+ -- )
) 

R2viola
para
decompor
i.e.
ABCDH.
EFG.
Logo,
Logo,está
estánanaBCNF!
CHD.
1BCNF!
©Silberschatz, Korth and Sudarshan (modificado)
Exemplo de Preservação de DFs
(sem calcular F+)
 Problema: a decomposição
de R(A,B,C,D,E,F,G,H) com
F = {A BCH, CH CD,
E FG, G CH, A CD}
Em R3(A,E), R4(E,F,G),
R5(A,B,C,H), R6(C,D,H)
preserva as dependências
funcionais?
Para verificar se
é preservada na decomposição R
em R1, R2, …, Rn aplica-se o seguinte teste:
result :=
while (alterações a result) do
for each Ri na decomposição
result := result ((result Ri)+ Ri)
Se result contém todos os atributos em , então
é
preservada.
Database System Concepts
A BCH é preservada?
Result = {A}
iteração:
A1ªCD
é preservada? +
Result
{A} (({A} R3) R3) (({A} R4)+ R4)
Result =={A}
+
+
G CH é preservada?
1ª iteração: (({A} R5) R5) (({A} R6) R6) =
Result = {G} = {A} {A} + {} {A,B,C,H} +{} =
Result
(({A}
R3) (({A}
R4)
CH
CD=e{A}
E FG
sãoR3)
preservadas
pois R4)
existem
1ª{A,B,C,H}
iteração:
+
+
(({A} os
R5)seus
(({A} R6
R6)e +R4
R6) =
+ R5)
relações
atributos,
Result
= com
{G} todos
(({G} R3)
R3)
(({G} R4)
R4)
2ª iteração:
=
{A}
{A}
{}
{A,B,C,H}
{}
=
+ R5) (({G} R6)
+ R6) =
respectivamente.
(({G} R5)
Result = {A,B,C,H}
(({A,B,C,H}
R3)+ R3)
{A,B,C,H}
= {G} {} {G} {} + {} = {G}
2ª iteração: (({A,B,C,H} R4) + R4)
Como Result não
contém {C,H},
dependência
(({A,B,C,H}
R5) aR3)
R5)
+ R3)
Result = {A,B,C,H}
(({A,B,C,H}
+
funcional G CH
não
é
preservada.
(({A,B,C,H} R4)
R6)
R6) =
+ R4)
(({A,B,C,H}
=(({A,B,C,H}
{A,B,C,H} {A}
R5)+ {}R5){A,B,C,H}
{C,H,D} = (({A,B,C,H} R6)+ R6) =
=={A,B,C,D,H}
{A,B,C,H} {A} {} {A,B,C,H}
3ª
iteração:
{C,H,D} =
Result = {A,B,C,D,H}
R3)+ R3)
={A,B,C,D,H}(({A,B,C,D,H}
+ R4)
Cmo Result já (({A,B,C,D,H}
contém {C,D}, aR4)
dependência
+
funcional A CD(({A,B,C,D,H}
é preservada. R5)+ R5)
R6) de
R6)
= haver
Notar que ela é(({A,B,C,D,H}
preservada apesar
não
= {A,B,C,D,H}
{A} todos
{} os atributos da
nenhuma relação
que contenha
{A,B,C,H} {C,H,D}
=
dependencia
funcional.
= {A,B,C,D,H}
Como Result contém {B,C,H}, a dependência
funcional A BCH é preservada.
Esta conclusão poderia ser tirada após a 1ª
2 iteração ou por©Silberschatz,
and Sudarshan
(modificado)
observaçãoKorth
directa
que R5 contém