Normal Form Practice Questions

Split: $A \to B,\ A \to C,\ A \to D,\ BC \to D,\ BC \to E,\ B \to D$. Now $A \to D$: $A^+$ without $A \to D$ = from $A \to B,\ A \to C,\ BC \to D,\ B \to D$: $A^+ \ni B,C$ then $BC \to D$, so $D \in A^+$. Redundant - remove. $BC \to D$: $B^+ \supseteq \{B,D\}$; $(BC-C)^+ = B^+ = \{B,D\}$, $D \in B^+$. So $C$ is extraneous in $BC \to D$: becomes $B \to D$ (already exists). Redundant - remove. Remaining: $\{A \to B,\ A \to C,\ BC \to E,\ B \to D\}$ - merge same LHS: $\{A \to BC,\ BC \to E,\ B \to D\}$ = 3... but with $A \to B$ and $A \to C$ as separate, unique LHS gives $A \to BC$ (1 FD). Total = $\{A \to BC,\ BC \to E,\ B \to D\}$ = 3. Recount without merging: 4 single-RHS FDs. Answer: 4 (before merging same LHS).

To check for dependency preservation, we first project the original functional dependencies (F) onto the decomposed relations R1 and R2.

Relation R1 = (SatelliteID, SensorType, TelemetryRate)
The functional dependencies from F that are entirely contained within R1's attributes, or can be derived from them, form F1:

• SatelliteID -> SensorType (f1 is in R1)
• SensorType -> TelemetryRate (f2 is in R1)
  So, F1 = { SatelliteID -> SensorType, SensorType -> TelemetryRate }

Relation R2 = (TelemetryRate, OrbitAltitude, PowerConsumption, LastCalibration)
The functional dependencies from F that are entirely contained within R2's attributes, or can be derived from them, form F2:

• TelemetryRate, OrbitAltitude -> PowerConsumption (f3 is in R2)
• SatelliteID, PowerConsumption -> LastCalibration (f4 is NOT entirely in R2, as SatelliteID is missing from R2's attributes. Thus, f4 cannot be directly projected to F2).
  So, F2 = { TelemetryRate, OrbitAltitude -> PowerConsumption }

Now, let F' = F1 ∪ F2 = { SatelliteID -> SensorType, SensorType -> TelemetryRate, TelemetryRate, OrbitAltitude -> PowerConsumption }. For the decomposition to be dependency-preserving, it must be true that F+ = (F')+. This means all original FDs in F must be derivable from F'. Let's check each original FD:

1. SatelliteID -> SensorType (f1): This FD is present in F'. (Preserved)
2. SensorType -> TelemetryRate (f2): This FD is present in F'. (Preserved)
3. TelemetryRate, OrbitAltitude -> PowerConsumption (f3): This FD is present in F'. (Preserved)
4. SatelliteID, PowerConsumption -> LastCalibration (f4): We need to check if this FD can be derived from F'. Let's compute the closure of {SatelliteID, PowerConsumption} under F':
   • Closure({SatelliteID, PowerConsumption}) = {SatelliteID, PowerConsumption} (initial)
   • Using SatelliteID -> SensorType (from F1): {SatelliteID, PowerConsumption, SensorType}
   • Using SensorType -> TelemetryRate (from F1): {SatelliteID, PowerConsumption, SensorType, TelemetryRate}
   • Using TelemetryRate, OrbitAltitude -> PowerConsumption (from F2): The determinant TelemetryRate, OrbitAltitude requires OrbitAltitude, which is not in our current closure. So, this FD cannot be applied to derive more attributes.
     The final closure is {SatelliteID, PowerConsumption, SensorType, TelemetryRate}. Since LastCalibration is not in this closure, the FD SatelliteID, PowerConsumption -> LastCalibration cannot be derived from F'.

Since f4 cannot be derived from F', the decomposition is NOT dependency-preserving.

Let's evaluate the options:
A. Incorrect. F4 is not directly projected to F2. Also, the decomposition is not dependency-preserving.
B. Incorrect. The decomposition is not dependency-preserving because f4 is not derivable.
C. Incorrect. SensorType -> TelemetryRate is directly available in F1.
D. Correct. The decomposition is not dependency-preserving because SatelliteID, PowerConsumption -> LastCalibration cannot be derived from the FDs in the decomposed relations.

An attribute $A$ is extraneous in FD $\alpha \to \beta$ if removing $A$ does not change $F^+$. If $A \in \alpha$: $A$ is extraneous if $\beta \subseteq (\alpha - A)^+$ under $F$. If $A \in \beta$: $A$ is extraneous if $A \in (\alpha)^+$ under $F - \{\alpha \to \beta\} \cup \{\alpha \to (\beta - A)\}$.

1. Lossless Join: $R_1 \cap R_2 = \{C\}$. $C \to D$, so $C$ is a superkey for $R_2(C, D)$. The condition $R_1 \cap R_2 \to R_2$ holds. Hence lossless. 2. Dependency Preservation: $AB \to C$ is in $R_1$ ✓. $C \to D$ is in $R_2$ ✓. $D \to A$: $D$ appears only in $R_2(C, D)$ and $A$ appears only in $R_1(A, B, C)$. $D \to A$ cannot be tested in either relation alone. Hence not dependency preserving.

Check $Y$ extraneous in $XY \to Z$: $(XY-Y)^+ = X^+ = \{X,Y,Z,...\}$: $X \to Y,\ XY \to Z$, so $X^+ = \{X,Y,Z\}$. $Z \in X^+$, so $Y$ is extraneous. $XY \to Z$ becomes $X \to Z$. Now $F = \{X \to Z,\ X \to Y,\ Y \to X,\ Z \to X\}$. Check $X \to Z$: $X^+$ without $X \to Z$: $X \to Y \to X$ (cycle), $X^+ = \{X,Y\}$. $Z \notin$. Not redundant. All remaining are non-redundant. Merge same LHS: $X \to YZ$, $Y \to X$, $Z \to X$ = 3 FDs.

(i) Valid: $A^+=\{A,B,C\}$, $B^+=\{B,C,A\}$, $C^+=\{C,A,B\}$. Same as original. (ii) Invalid: $B \to AC$ has $A$ which may be extraneous ($B \to C \to A$ - check: $B^+$ without $B \to A$: via $B \to C \to A$. Yes, $A$ is extraneous. So not canonical). (iii) Valid: $A \to BC$ and $C \to A$ - same closure check passes. (iv) Valid: $A^+=\{A,C,B\}$, etc. All three (i), (iii), (iv) are valid canonical covers - demonstrating non-uniqueness.

The only key of $R$ is $A$ (since $A^+ = \{A, B, C, D\}$). For option B: $R_1 \cap R_2 = \{B\}$. Since $B \to C$, $C \to D$, and $D \to B$, we get $B^+ = \{B, C, D\}$. So $B$ is a superkey for $R_2(B, C, D)$. The condition $R_1 \cap R_2 \to R_2$ holds. Hence lossless.

After splitting and simplification, $ACD \to B$: compute $(ACD)^+$ using remaining FDs. $ACD \to$ ($C \to A$ already), $D \to EG$, so $ACDEG$; $BE \to C$ (no $B$ yet)... actually checking $B$ without this FD is complex. This is a classic GATE-style question where $ACD \to B$ is shown to be derivable from remaining FDs in the canonical cover computation.

The canonical cover algorithm has three steps: (i) Use the union rule to decompose RHS to single attributes, (ii) find and remove extraneous attributes from both sides, and (iii) remove redundant FDs. Step (iv) - converting to BCNF - is a separate normalization process and is NOT part of computing canonical cover.

A BCNF decomposition is always lossless, but it is NOT always dependency preserving. A classic example is $R(A, B, C)$ with $AB \to C$ and $C \to B$.

Split $X \to YZ$ into $X \to Y$ and $X \to Z$. Now $F = \{X \to Y,\ X \to Z,\ Y \to X,\ Z \to X\}$. Check redundancy: $X \to Z$: since $X \to Y$ and $Y \to X$ and $Z \to X$... $X^+$ without $X \to Z$ = $\{X,Y\}$ (using $Y \to X$, stays $\{X,Y\}$). Since $Z \notin \{X,Y\}$, $X \to Z$ is NOT redundant. However, since the canonical cover must have unique LHS - but $X \to Y$ and $X \to Z$ can be merged back. Final: $F_c = \{X \to Y,\ Y \to X,\ Z \to X\}$ after removing $X \to Z$ (since $X \to Y$, $Y \to X$, $Z \to X$ gives $Z^+ = \{Z,X,Y\}$ so $X \to Z$ becomes derivable via $Z \to X$ is reverse... $X \to Z$: remove it; $X^+ = \{X,Y\}$ not containing $Z$, so NOT redundant. So $F_c = \{X \to YZ,\ Y \to X,\ Z \to X\}$ with merged LHS. Option C is also valid.

1. Lossless Join: $R_1 \cap R_2 = \emptyset$. An empty intersection cannot be a superkey for either $R_1$ or $R_2$. The lossless join condition requires $R_1 \cap R_2 \to R_1$ or $R_1 \cap R_2 \to R_2$, which fails. Hence the join is lossy. 2. Dependency Preservation: $A \to B$ is fully preserved in $R_1$ and $C \to D$ is fully preserved in $R_2$. All original FDs are covered. Hence it is dependency preserving.

Since $A \to BCD$, $A$ is the key of $R$. In all three options, $A$ appears in both sub-relations, so $R_1 \cap R_2 \supseteq \{A\}$. Since $A \to BCD$, $A$ is a superkey for every sub-relation that contains $A$ plus a subset of $\{B, C, D\}$. The condition $R_1 \cap R_2 \to R_1$ (or $\to R_2$) is satisfied in all cases. Hence all three are lossless.

Dependency preserving ensures all FDs are maintained locally.

1. Lossless Join: $R_1 \cap R_2 = \emptyset$. An empty intersection cannot satisfy $R_1 \cap R_2 \to R_1$ or $R_1 \cap R_2 \to R_2$. Hence the join is lossy. 2. Dependency Preservation: $B \to C$ (bridges $R_1$ and $R_2$) and $D \to A$ (bridges $R_2$ and $R_1$) cannot be tested within either relation alone. Hence not dependency preserving.

To determine dependency preservation, we must check if every functional dependency in F can be logically derived from the union of the functional dependencies projected onto the decomposed relations (F1 U F2)+.

Projected FDs:
F1 on R1(A, B, C):

• A → B (from F)
  So, F1 = { A → B }

F2 on R2(C, D, E):

• E → C (from F)
  So, F2 = { E → C }

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

1. A → B: This FD is directly present in F1, so it is preserved.
2. E → C: This FD is directly present in F2, so it is preserved.
3. BC → E: The attributes {B, C, E} are not all within a single decomposed relation. We test if E can be derived from BC using (F1 U F2).
   (BC)+(F1 U F2): Initially {B, C}.
   Applying F1 ({A → B}) or F2 ({E → C}): No rules apply to extend {B, C} to include E.
   The closure (BC)+(F1 U F2) = {B, C}. It does not contain E. Thus, BC → E is not preserved.
4. D → A: The attributes {D, A} are not all within a single decomposed relation. We test if A can be derived from D using (F1 U F2).
   (D)+(F1 U F2): Initially {D}.
   Applying F1 ({A → B}) or F2 ({E → C}): No rules apply to extend {D} to include A.
   The closure (D)+(F1 U F2) = {D}. It does not contain A. Thus, D → A is not preserved.

Since both BC → E and D → A are not preserved, the decomposition is not dependency preserving.

The standard algorithm: (1) Use the union rule to split all RHS to single attributes, (2) Find and remove extraneous attributes from LHS and RHS, (3) Remove any FD that becomes redundant (i.e., derivable from remaining FDs). Steps must be done in this order for correctness.

Step 1: Replace $A \to BC$ with $A \to B$ and $A \to C$. Now $F = \{A \to B,\ A \to C,\ B \to C,\ A \to B,\ AB \to C\}$. Step 2: $A \to C$ is redundant ($A \to B \to C$). $AB \to C$ is redundant ($B \to C$). Remove them. Step 3: $F_c = \{A \to B,\ B \to C\}$. Each LHS is unique and no extraneous attributes remain.