Normal Form Practice Questions

$A \to B$ is in $R_1$, $B \to C$ is in $R_2$, and $C \to D$ is in $R_3$. To check $D \to A$, we find $D^+$ using only preserved FDs: $D^+ = \{D\}$. Since $A$ is not in the closure, $D \to A$ is lost.

A canonical cover is a simplified (minimal) version of $F$ - it removes redundant FDs and extraneous attributes. It can NEVER have more FDs than the original set because it is obtained by removing FDs and simplifying, not adding. So option C is FALSE.

Check $A \to C$: $A^+$ without $A \to C$ = $\{A,B,A,C,...\}$: $A \to B \to C$, so $C \in A^+$. $A \to C$ is REDUNDANT. Remove it. Remaining: $\{A \to B,\ B \to A,\ B \to C\}$. Each LHS is unique, no extraneous attributes. Canonical cover has 3 FDs.

Check redundancy: $A \to B$ (needed; $A^+$ without it = $\{A\}$). $B \to C$ (needed). $C \to B$ (needed; $C^+$ without it = $\{C\}$). $B \to A$: $B^+ = \{B,C,A\}$ even without $B \to A$? Without $B \to A$: $B \to C \to B$ (cycle), $B^+ = \{B,C\}$, so $A \notin B^+$. So $B \to A$ is needed. All 4 are needed, but $B \to C$ and $C \to B$ and $B \to A$: merge $B \to C$ and $B \to A$ → $B \to CA$. Canonical cover: $\{A \to B,\ B \to AC,\ C \to B\}$ - 3 FDs with unique LHS.

To determine if a decomposition of a relation R into R1 and R2 is lossless, we apply the Lossless Join Decomposition rule. This rule states that the decomposition R = {R1, R2} is lossless if and only if (R1 ∩ R2) is a superkey for R1 OR (R1 ∩ R2) is a superkey for R2.

Let's analyze the given problem:

1. Identify the intersection (R1 ∩ R2):
   R1 = (A, B, C)
   R2 = (C, D, E)
   R1 ∩ R2 = {C}

2. Calculate the closure of the intersection, (R1 ∩ R2)+ = C+, under the given FDs:
   F = { A → B, BC → D, D → E }

   • Start with C+ = {C}
   • Check FDs whose LHS is a subset of {C}:
     • A → B: LHS is 'A', not in {C}.
     • BC → D: LHS is 'BC', 'B' is not in {C}.
     • D → E: LHS is 'D', not in {C}.
   • No new attributes can be derived from {C} using the given FDs.
     Therefore, C+ = {C}.

3. Check if (R1 ∩ R2) is a superkey for R1:
   An attribute set X is a superkey for a relation schema S if X+ contains all attributes of S.
   Here, X = (R1 ∩ R2) = {C}, and S = R1 = (A, B, C).
   C+ = {C}.
   Does C+ contain all attributes of R1? That is, is {A, B, C} ⊆ {C}? No, because 'A' and 'B' are not in C+.
   Thus, (R1 ∩ R2) is NOT a superkey for R1.

4. Check if (R1 ∩ R2) is a superkey for R2:
   Here, X = (R1 ∩ R2) = {C}, and S = R2 = (C, D, E).
   C+ = {C}.
   Does C+ contain all attributes of R2? That is, is {C, D, E} ⊆ {C}? No, because 'D' and 'E' are not in C+.
   Thus, (R1 ∩ R2) is NOT a superkey for R2.

Conclusion:
Since (R1 ∩ R2) is neither a superkey for R1 NOR a superkey for R2, the decomposition is lossy.

Let's evaluate the options:

• A. Incorrect. (R1 ∩ R2)+ = {C}, which does not contain R1 (A, B, C).
• B. Incorrect. (R1 ∩ R2)+ = {C}, which does not contain R2 (C, D, E).
• C. Correct. The decomposition is lossy because C+ does not contain R1, nor does it contain R2.
• D. Incorrect. C is not a superkey for R1 because C+ = {C} does not contain all attributes of R1 (A, B, C).

A is false (Decomposition rule only applies to the right side). B is true (Decomposition rule). C is true (Pseudotransitivity rule). D is true (Transitivity rule).

For $D_1$: Step 1 - $R_3 \cap R_4 = \{Y\}$. $Y \to ZW$, so $Y$ is a superkey for $R_4(Y, Z, W)$. Merge to $R_{34}(Q, Y, Z, W)$. Step 2 - $R_1 \cap R_{34} = \{Q\}$ (common attributes). $Q \to Y$ and $Y \to ZW$, so $Q$ is a superkey for $R_{34}$. Merge to $R_{134}(P, Q, S, T, Y, Z, W)$. Step 3 - $R_{134} \cap R_2 = \{P, T\}$. $P \to YX$ so $P \to X$ (decomposition), making $P$ a superkey for $R_2(P, T, X)$. Final merge is the full relation - $D_1$ is lossless.

1. Lossless Join: $R_1 \cap R_2 = \{Y\}$. Since $Y \to Z$, $Y$ is a superkey for $R_2(Y, Z)$. The condition $R_1 \cap R_2 \to R_2$ holds. Hence lossless. 2. Dependency Preservation: $WX \to Y$ is preserved in $R_1$ and $Y \to Z$ is preserved in $R_2$. All FDs are preserved.

To test if $A \in \alpha$ is extraneous in $\alpha \to \beta$: compute $(\alpha - A)^+$ using the full set $F$. If $\beta \subseteq (\alpha - A)^+$, then $A$ is extraneous in LHS and can be removed. This tests whether the LHS can be simplified.

Split: $A \to B,\ A \to C,\ CD \to E,\ B \to D,\ E \to A$. Test $C$ extraneous in $CD \to E$: $D^+ = \{D\}$ (only $B \to D$ goes to $D$, not from $D$). $D^+ = \{D\}$, $E \notin D^+$. Test $D$ extraneous: $C^+ = \{C\}$ (no FD with $C$ on LHS alone). $E \notin C^+$. So no LHS simplification is possible for $CD \to E$.

Canonical cover removes redundant FDs and attributes.

In option B: $AB^+ = \{A, B, C, D, E\}$ so $AB$ is a key. $C \to AD$ violates BCNF since $C^+ = \{C, A, D, E\}$ (not all attributes, missing $B$). Decomposing on $C \to AD$: split into $(C, A, D, E)$ and $(A, B, C)$. In $(A, B, C)$, $AB \to C$ is an FD - $AB$ is a key here, so BCNF holds. But now the FD $AB \to C$ is preserved, while $C \to AD$, $D \to E$ are in the other part. However $D \to E$ then requires another BCNF split - and at each step the FD $AB \to C$ cannot be preserved without losing losslessness. It is a known result that this schema cannot achieve BCNF + lossless + dependency preserving simultaneously.

Check if $B$ is extraneous in $AB \to C$: compute $(AB - B)^+ = A^+$ under $F$. $A^+$: $A \to D$, $D \to A$ (no new), $D \to C$. So $A^+ = \{A, D, C\}$. Since $C \in A^+$, $B$ is extraneous. Simplified FD: $A \to C$ (but $D \to C$ already exists; $A \to C$ follows transitively). So $AB \to C$ simplifies to $A \to C$, which is then redundant.

To check for dependency preservation, we need to determine the set of functional dependencies (FDs) that hold within each sub-relation (projected FDs) and then verify if the original set of FDs (F) can be logically derived from the union of these projected FDs.

1. Identify FDs local to R1 = (A, B, C):
   We consider FDs X → Y such that X, Y ⊆ {A, B, C} and X → Y is derivable from F.

   • From f1: A → B. A, B are in R1. So, A → B is preserved in R1.
   • Let's check other closures within R1 from F:
     • (A)⁺_F = {A, B, D, E} (using A→B, A→D, D→E). Projected onto R1, this is {A, B}. This implies A → B.
     • (C)⁺_F = {C}. Projected onto R1, this is {C}. No non-trivial FD.
     • (AC)⁺_F = {A, B, C, D, E}. Projected onto R1, this is {A, B, C}. This implies AC → B. However, AC → B is implied by A → B using augmentation (if A → B, then AC → B). So A → B is sufficient for F1.
       Thus, F1 = {A → B}.

2. Identify FDs local to R2 = (A, D, E):
   We consider FDs X → Y such that X, Y ⊆ {A, D, E} and X → Y is derivable from F.

   • From f3: D → E. D, E are in R2. So, D → E is preserved in R2.
   • From f4: A → D. A, D are in R2. So, A → D is preserved in R2.
   • Let's check other closures within R2 from F:
     • (A)⁺_F = {A, B, D, E}. Projected onto R2, this is {A, D, E}. This implies A → D and A → E. A → E is derivable from A → D and D → E. So A → D, D → E are sufficient for F2.
     • (AD)⁺_F = {A, B, D, E}. Projected onto R2, this is {A, D, E}. This implies AD → E, which is implied by D → E using augmentation.
       Thus, F2 = {A → D, D → E}.

3. Combined Projected FDs (F'):
   F' = F1 ∪ F2 = {A → B, A → D, D → E}.

4. Check if each original FD in F is derivable from F':

   • f1: A → B: Yes, A → B is directly in F'. (Preserved)
   • f2: BC → D: We need to compute (BC)⁺_F'.
     • Starting with {B, C}.
     • None of the FDs in F' ({A → B, A → D, D → E}) have B or C on their left-hand side (LHS).
     • So, (BC)⁺_F' = {B, C}. The attribute D is not in {B, C}.
     • Therefore, BC → D is NOT preserved.
   • f3: D → E: Yes, D → E is directly in F'. (Preserved)
   • f4: A → D: Yes, A → D is directly in F'. (Preserved)

Since at least one functional dependency (BC → D) from the original set F is not derivable from the projected FDs (F'), the decomposition is NOT dependency preserving.

Final Answer is B because it correctly identifies the decomposition as not dependency preserving and provides the specific FD that fails to be preserved.

$A \to BCD$ splits into $A \to B$, $A \to C$, $A \to D$ (3 FDs). $B \to D$ (1), $D \to A$ (1), $AB \to D$ (1). Total = 3 + 1 + 1 + 1 = 6 FDs after splitting.

1. Lossless Join: $R_1 \cap R_2 = \{B, C\}$. Since $BC \to ADE$, by decomposition, $BC \to A$. So $BC$ is a superkey for $R_1(A, B, C)$. The condition $R_1 \cap R_2 \to R_1$ holds. Hence lossless. 2. Dependency Preservation: $BC \to A$ is testable in $R_1$, $BC \to D$ and $BC \to E$ are testable in $R_2$. The original FD $BC \to ADE$ is collectively preserved.

1. Dependency Preservation: $A \to B$ is in $R_1$ and $C \to D$ is in $R_2$. All original FDs are covered. 2. Lossless Join: $R_1 \cap R_2 = \emptyset$. Since the intersection is empty, it cannot be a superkey for either $R_1$ or $R_2$. Thus, it is lossy.

(i) TRUE: 3NF synthesis uses canonical cover. (ii) TRUE: each FD generates a schema. (iii) FALSE: 3NF synthesis guarantees 3NF, NOT BCNF. BCNF is stronger and may violate dependency preservation. (iv) TRUE: a candidate key schema is added if missing to ensure lossless join. So (i), (ii), (iv).