Normal Form Practice Questions

This is a combinatorial problem from the 2024 paper involving the definition of non-trivial and minimal dependencies within a 4-attribute set. (Calculation based on $2^n - (n+1)$ logic for specific FD types).

$B \to C$: $B^+$ without it = $\{B,A\}$ via $B \to A$, then $A \to B$ (cycle), $A \to C$ gives $C \in A^+$ but $B \to A \to C$. So $B^+$ without $B \to C$ includes $A$ (via $B \to A$) then $C$ (via $A \to C$). $C \in B^+$. Redundant - remove. Remaining: $\{A \to B,\ B \to A,\ A \to C,\ C \to D\}$. Check $A \to C$: $A^+$ without $A \to C$ = $\{A,B\}$ (cycle). $C \notin$. Not redundant. All 4 remaining are needed. Canonical cover: 4 FDs.

The candidate keys of $R$ include $AB$, $CA$, $CB$ (since $AB \to C$, $CA \to B$, $CB \to A$ and $B \to D$, $D \to E$). Since $B \to D$ violates BCNF ($B$ is not a superkey), decompose on $B \to D$ to get $(B, D)$ and residual. Then $D \to E$ gives $(D, E)$, leaving $(A, B, C)$. Lossless check: $(B, D) \cap (D, E) = \{D\}$ and $D \to E$, so $D$ is a key for $(D, E)$ - lossless. Result $(B, D, E)$ joined with $(A, B, C)$: intersection $\{B\}$, and $B \to D \to E$ makes $B$ a key for the merged side - lossless overall.

$\{A \to B,\ B \to C,\ C \to A\}$: each LHS is unique, no redundant FDs, no extraneous attributes. Closure check: $A^+ = \{A,B,C\}$, $B^+ = \{B,C,A\}$, $C^+ = \{C,A,B\}$ - same as original $F^+$. This is a valid minimal canonical cover.

A canonical cover (as defined in Silberschatz) is a minimal cover with the additional constraint that no two FDs share the same LHS (LHS uniqueness). In some textbooks, 'minimal cover' allows multiple FDs with same LHS, while 'canonical cover' merges them. Both have no redundant FDs and no extraneous attributes.

In option A: $R_1$ preserves $A \to BC$. $R_2$ preserves $C \to D, D \to E$. $E \to A$ is preserved because $E \to D$ and $D \to C$ (implied) and $C^+ = \{C, D, E, A, B, C\}$ in the original, but checking closure $(E)^+$ with projected FDs $(E \to D, D \to C, C \to A)$ gives $E^+ = \{E, D, C, A\}$.

Option A: $R_1(A,B) \cap R_2(A,C,D,E) = \{A\}$. $A \to B$, so $A$ is a superkey for $R_1(A,B)$. Condition $R_1 \cap R_2 \to R_1$ holds. Lossless ✓. Option C: $R_1(A,B,C,D) \cap R_2(D,E) = \{D\}$. $D \to E$, so $D$ is a superkey for $R_2(D,E)$. Condition $R_1 \cap R_2 \to R_2$ holds. Lossless ✓. Option B: $(BCD) \cap (ABE) = \{B\}$. $B^+$ with given FDs: $B$ alone does not determine any other attribute directly. Not lossless. Option D: $(ABC) \cap (CDE) = \{C\}$. $C^+$: $E \to C$ means $C$ is a target not a determinant; no FD has $C$ on the left. Not a superkey for either. Not lossless.

(i) TRUE: correct definition for LHS extraneous attribute. (ii) TRUE: correct definition for RHS extraneous attribute. (iii) TRUE: removing an attribute from LHS makes it a more general (stronger) FD - it applies to fewer attribute combinations. (iv) FALSE: removing from RHS makes the FD determine fewer attributes - it is weaker/less informative, not less restrictive. So (i), (ii), (iii).

$\{A \to B,\ B \to C,\ C \to D\}$: each FD has a single-attribute RHS, each LHS is unique, no FD is redundant ($A \to B$ cannot be derived without it), and no LHS attribute is extraneous (all LHS have single attributes). This is already a canonical cover.

$A \to D$: compute $A^+$ without $A \to D$ = $\{A\} \to B,C$ then $\to D$ via $B \to D$. $A^+ = \{A,B,C,D\}$. $D \in A^+$. So $A \to D$ is redundant. Only 1 FD removed. $F_c = \{A \to BC,\ B \to D,\ C \to D\}$ (3 FDs with merged LHS).

(i) TRUE: The canonical cover must have the same closure as $F$. (ii) TRUE: No extraneous attributes allowed. (iii) FALSE: There is no requirement for one FD per attribute. (iv) TRUE: Each LHS in $F_c$ is unique (this is what distinguishes canonical cover from minimal cover in some formulations). So (i), (ii), and (iv).

3NF synthesis using canonical cover guarantees: (1) Every resulting schema is in 3NF, (2) dependency preservation (every FD in $F_c$ is represented in some schema), and (3) lossless join (achieved by adding a schema containing a candidate key if none already exists).

Canonical cover removes redundancy in functional dependencies.

First, find the canonical cover and keys: $A^+ = \{A, B, C, D, E\}$ (via $A \to BC$, $B \to D$, $CD \to E$, $E \to A$), making $A$ a key. Using the 3NF synthesis algorithm: create a relation for each FD in the canonical cover - $(A, B, C)$ for $A \to BC$, $(B, D)$ for $B \to D$, $(C, D, E)$ for $CD \to E$, $(A, E)$ for $E \to A$. Since one of these relations $(A, E)$ contains the key $A$, no extra key relation is needed. This decomposition in option B matches the synthesis output exactly - guaranteed lossless join and dependency preserving by the 3NF synthesis theorem.

$A \to B$ is in $R_1$. For $R_2$, we check $B \to C$. Since $A \to B$ and $A \to C$ (via transitivity), the dependency $B \to C$ can be verified through the common attribute $A$. Actually, $A \to C$ and $C \to D$ are both contained in $R_2$, and $A \to B$ is in $R_1$. The union of FDs covers the original set.

To ensure the lossless-join property in 3NF synthesis, if no resulting schema contains a candidate key of $R$, we add an additional schema $R_i$ containing any one candidate key of $R$. This step ensures the natural join of all schemas recovers $R$ without spurious tuples.

A canonical cover is NOT necessarily unique. Different orderings of steps (choosing which extraneous attributes to remove first) may yield different canonical covers, all equivalent (same closure $F^+$) but syntactically different.

To check for dependency preservation, we need to verify if all FDs in F can be derived from the projected FDs of the decomposed relations (F1 U F2)+.

Projected FDs:
F1 on R1(K, L, M):

• K → L (from K → L)
• L → M (from L → MN)
  So, F1 = { K → L, L → M }

F2 on R2(L, N, O):

• L → N (from L → MN)
• MN → O cannot be directly projected since M is not in R2.
  So, F2 = { L → N }

Let's check each FD in F against (F1 U F2)+:

1. K → L: This FD is directly present in F1, so it is preserved.
2. L → MN: This multi-valued dependency implies L → M and L → N.
   • L → M: This is present in F1, so it is preserved.
   • L → N: This is present in F2, so it is preserved.
     Therefore, L → MN is preserved.
3. MN → O: The attributes {M, N, O} are not all in R1 nor all in R2. We check if O can be derived from MN using (F1 U F2).
   (MN)+(F1 U F2): Initially {M, N}.
   Using F1: {K → L, L → M}. No rules apply.
   Using F2: {L → N}. No rules apply.
   The closure (MN)+(F1 U F2) = {M, N}. It does not contain O. Thus, MN → O is not preserved.

Since MN → O is not preserved, the decomposition is not dependency preserving.