关于BCNF转换算法中递归分解非BCNF子模式的正确性咨询

Hey there! Let's break down your BCNF decomposition step by step to confirm that your approach is totally correct.

First, let's recap the core rule of BCNF: A relation schema is in BCNF if, for every non-trivial functional dependency (X \rightarrow Y), (X) is a superkey of the schema.

Step 1: Initial Schema & Dependency Set #

Your starting point:

• Relation (R = (ABCD))
• Functional dependencies (F = {A \rightarrow C, BC \rightarrow A, C \rightarrow D})

First, let's confirm the candidate keys of (R):

• (BC^+ = {B,C,A,D}) (since (BC \rightarrow A), (A \rightarrow C), (C \rightarrow D)), so (BC) is a candidate key.
• (AB^+ = {A,B,C,D}) (since (A \rightarrow C), (C \rightarrow D)), so (AB) is also a candidate key.

Looking at the dependencies:

• (A \rightarrow C): (A) is not a superkey ((A^+ = {A,C,D})), so this violates BCNF.
• (C \rightarrow D): (C) is not a superkey ((C^+ = {C,D})), so this also violates BCNF.
• (BC \rightarrow A): (BC) is a candidate key, so this satisfies BCNF.

Step 2: First Decomposition (Using (A \rightarrow C)) #

You chose to decompose (R) using (A \rightarrow C), and correctly derived:

• (R_1 = (ACD)) with dependencies (F_1 = {A \rightarrow CD, C \rightarrow D, AC \rightarrow D}) (note: (AC \rightarrow D) is redundant, but including it doesn't hurt)
• (R_2 = (AB)) with no non-trivial dependencies ((F_2 = \emptyset))

(R_2) is already in BCNF: its only candidate key is (AB), and there are no violating dependencies.

Step 3: Recursive Decomposition of (R_1) #

You noticed (R_1) still isn't in BCNF (because (C \rightarrow D) violates BCNF—(C) isn't a superkey of (R_1)), so you decomposed (R_1) further:

• (R_3 = (CD)) with dependency (F_3 = {C \rightarrow D})
• (R_4 = (AC)) with dependency (F_4 = {A \rightarrow C})

Let's verify these final schemas:

• (R_3): (C) is a candidate key ((C^+ = {C,D})), so (C \rightarrow D) satisfies BCNF.
• (R_4): (A) is a candidate key ((A^+ = {A,C})), so (A \rightarrow C) satisfies BCNF.

Final Verdict #

Your entire decomposition process is correct. The key point you got right is the recursive nature of BCNF decomposition: whenever a sub-schema fails to meet BCNF, you repeat the decomposition process on that sub-schema until all resulting schemas are in BCNF.

内容的提问来源于stack exchange，提问作者Spyromancer