BCNF 분해 알고리즘이 작동하지 않습니다.

Question

다음과 같은 문제가 있습니다 : R (ABCDEFG) 및 F = {AB-> CD, C-> EF, G-> A, G-> F, CE-> F}. 분명히 B & G는 종속 세트의 일부가 아니므로 키의 일부 여야합니다. 또한, BG + = ABCDEFG, 따라서 후보 키. 분명히, AB-> CD는 BCNF를 위반합니다. 그러나 알고리즘을 따를 때 어떤 대답으로도 끝나지 않습니다. 아마 뭔가 잘못하고있는 것 같아. 누구든지 분해에 이르기 위해 알고리즘을 올바르게 적용하는 방법을 보여줄 수 있습니까?

미리 감사드립니다.

Answer 1

먼저 종속성에 대한 정식 커버를 계산해야합니다. 이 경우에는은 : (독특한) 후보 키 B G, 기능적 종속성 만족 BNCF이다

{ A B → C 
    A B → D 
    C → E 
    C → F 
    G → A 
    G → F } > 

입니다. 그런 다음 BCNF를 위반하는 기능적 종속성 X → Y부터 시작하여 X, X+의 종료를 계산하고 원본 관계 R<T,F>을 두 개의 관계 R1<X+> 및 R2<T - X+ + X>으로 바꿉니다. 그렇지 않으면 우리가 적용, 그리고

R2 < (A B G) , 
    { G → A } > 

우리는 BCNF를 만족 있는지 확인하기 위해 각 분해 관계를 확인 :

R1 < (A B C D E F) , 
    { A B → C 
     A B → D 
     C → E 
     C → F} > 

과 : 그래서,이 경우 종속성 A B → C을 chosing, 우리는 원래 관계를 교체 재귀 적으로 알고리즘. 이 경우

는, 예를 들어, R1에 키 때문에 C -> E는 BCNF를 위반 A B, 우리는 함께 R1 교체 :

R3 < (C E F) , 
    { C → E 
     C → F } > 

과 : 만족

R4 < (A B C D) , 
    { A B → C 
     A B → D } > 

이 관계를 BCNF.

R5 < (A G) , 
    { G → A } > 

과 : (키가 B G입니다 beacuse) R2 너무 BCNF를 만족하지 않기 때문에

마지막으로, 우리는 R2에서 분해 BCNF에

R6 < (B G) , 
     { } > 

합니다.

따라서 최종 분해는 R3, R4, R5 및 R6의 관계로 구성됩니다. 또한 원본 관계 에 대한 종속성 G → F은 분해시이 유실됨을 알 수 있습니다.