Normal Form Practice Questions

The relation is R(\text{Roll_number}, \text{Name}, \text{Date_of_Birth}, \text{Age}). The functional dependencies (FDs) applicable to $R$ are \{\text{Date_of_Birth} \to \text{Age}, \text{Name} \to \text{Roll_number}, \text{Roll_number} \to \text{Name}\}. The candidate keys are \{\text{Roll_number}, \text{Date_of_Birth}\} and \{\text{Name}, \text{Date_of_Birth}\}. The attribute $\text{Age}$ is a non-prime attribute. The FD \text{Date_of_Birth} \to \text{Age} represents a partial functional dependency because \text{Date_of_Birth} is a proper subset of the candidate key \{\text{Roll_number}, \text{Date_of_Birth}\}. Since a non-prime attribute depends on a part of a candidate key, the relation violates the second normal form (2NF). Therefore, it cannot be in 3NF or BCNF.

A relation $R$ is in BCNF if for every non-trivial functional dependency $X \to Y$ in $F^+$, $X$ is a superkey of $R$. This condition ensures that every determinant in each relation is a candidate key, which fundamentally prevents redundancy caused by functional dependencies. Unlike 3NF, which allows transitive dependencies involving prime attributes, BCNF restricts dependencies such that non-key attributes are never determined by anything other than a superkey. By decomposing $R$ into relations where all dependencies are on superkeys, all redundancy arising from functional dependencies is eliminated. Thus, the redundancy in the resulting set of relations is zero.

A relation is in BCNF if, for every non-trivial functional dependency $X \to Y$, $X$ is a superkey. A relation is in 3NF if, for every non-trivial functional dependency $X \to Y$, $X$ is a superkey or $Y$ is a prime attribute. Since BCNF is a strictly stronger condition than 3NF, checking the BCNF definition is the most direct diagnostic test. If a decomposition satisfies the BCNF condition, it is confirmed as the BCNF decomposition. If it violates the BCNF condition (i.e., there exists a dependency where $X$ is not a superkey) but satisfies the 3NF condition, it is confirmed as the 3NF decomposition.

For a decomposition to be in BCNF, every non-trivial dependency $X \to Y$ must have a superkey as its determinant $X$. In option C, $F = \{AB \to C, C \to AD\}$, the candidate keys are $AB$ and $CB$. The dependency $C \to AD$ violates BCNF because $C$ is not a superkey. Decomposing the relation into $R_1(C, A, D)$ and $R_2(C, B)$ creates a lossless join but causes the dependency $AB \to C$ to be lost. It is a fundamental database theory result that for certain relations, it is impossible to achieve a BCNF decomposition that is both lossless and dependency-preserving; this relation is a classic example. does not satisfy these properties.

To verify $YZ \rightarrow X$, we check if each $(Y, Z)$ pair maps to a unique $X$: $(4, 2) \rightarrow 1$, $(5, 3) \rightarrow 1$, $(6, 3) \rightarrow 1$, and $(2, 2) \rightarrow 3$. Since all are unique, $YZ \rightarrow X$ holds.
To verify $Y \rightarrow Z$, we check if each $Y$ maps to a unique $Z$: $4 \rightarrow 2$, $5 \rightarrow 3$, $6 \rightarrow 3$, and $2 \rightarrow 2$. Since all $Y$ values map to unique $Z$ values, $Y \rightarrow Z$ also holds.
Other options fail: $Z \rightarrow Y$ fails because $Z=2$ maps to $Y=4$ and $Y=2$; $X \rightarrow Z$ fails because $X=1$ maps to $Z=2$ and $Z=3$; and $XZ \rightarrow Y$ fails because $X=1, Z=3$ maps to $Y=5$ and $Y=6$.
is the only set of dependencies satisfied by the instance.

The candidate keys for $R(S, T, U, V)$ are $\{S\}, \{T\}, \{U\}$, and $\{V\}$ because each attribute's closure contains all attributes (e.g., $S^+ = \{S, T, U, V\}$).
Since every attribute in $R$ is part of at least one candidate key, all attributes are prime attributes.
A relation is in 2NF if no non-prime attribute is partially dependent on a candidate key; this condition is vacuously satisfied as there are no non-prime attributes.
A relation is in 3NF if for every functional dependency $X \rightarrow A$, $X$ is a superkey or $A$ is a prime attribute; this is satisfied because all attributes $A$ are prime.
Since all attributes are prime, any decomposition of $R$ results in relations where all attributes remain prime, ensuring the decomposition is in both 2NF and 3NF.

Relational database normalization aims to reduce data redundancy and minimize update, insertion, and deletion anomalies. While higher normal forms like BCNF, 4NF, and 5NF address rare, complex constraints, they often introduce performance overhead and complexity. The Third Normal Form ($3NF$) is considered adequate for most business applications because it successfully eliminates transitive dependencies-where a non-prime attribute depends on another non-prime attribute. By ensuring that every non-key attribute is dependent only on the primary key, $3NF$ strikes an optimal balance between data integrity and query efficiency for practical design.

The candidate key of relation $R(a, b, c, d)$ is $\{a, b\}$ because $\{a, b\}^+ = \{a, b, c, d\}$. The non-prime attributes are $\{c, d\}$. A relation is in 2NF if no non-prime attribute is partially dependent on any candidate key (i.e., dependent on a proper subset of the candidate key). Here, $a \rightarrow c$ and $b \rightarrow d$ are partial dependencies because $c$ depends on $\{a\}$ and $d$ depends on $\{b\}$, both of which are proper subsets of the candidate key $\{a, b\}$. Since partial dependencies exist, the relation is not in 2NF, though it remains in 1NF due to atomic domains.

A relation in 3NF satisfies the condition that for every non-trivial functional dependency $X \to A$, $X$ is a superkey or $A$ is a prime attribute. Redundancy persists in 3NF if there exists a dependency $X \to A$ where $X$ is not a superkey but $A$ is a prime attribute (a BCNF violation). Such dependencies involve prime attributes on the right-hand side (Option B), a scenario that occurs when candidate keys overlap, meaning $X$ and $A$ are both prime attributes (Option D). Since 3NF allows these dependencies while BCNF prohibits them, they serve as a source of data redundancy despite 3NF compliance.

[CORRECT_OPTION: B, D]

To determine dependency preservation, we project the FDs onto each decomposed relation.

1. Project FDs onto R1=(M, N): F1 = {M → N} (since M and N are in R1, and M → N is in F).
2. Project FDs onto R2=(O, P): F2 = {O → P} (since O and P are in R2, and O → P is in F).
3. Project FDs onto R3=(M, N, O): F3 = {M → N, MN → O} (since M, N, O are in R3. Both M → N and MN → O are in F and their attributes are entirely within R3).

Let F' = F1 U F2 U F3 = {M → N, O → P, MN → O}.

Now, we compare (F')+' with F+:

• The original FDs are F = {M → N, O → P, MN → O}.
• All FDs in F are directly present in F'.

Since all original FDs are directly preserved within one of the sub-relations' projected FDs, the decomposition is dependency preserving.

To check for dependency preservation, we need to verify if the closure of the projected functional dependencies (F') for the decomposed relations is equivalent to the closure of the original set of functional dependencies (F+).

1. Project FDs onto R1=(A, B): F1 = {A → B} (since A and B are in R1, and A → B is in F).
2. Project FDs onto R2=(C, D): F2 = {C → D} (since C and D are in R2, and C → D is in F).
3. Project FDs onto R3=(A, C): F3 = {} (No FD in F has both its LHS and RHS entirely within the attributes {A, C}. A → B requires B, C → D requires D, and A → D requires D).

Let F' = F1 U F2 U F3 = {A → B, C → D}.

Now, we compare (F')+' with F+:

• The original FDs are F = {A → B, C → D, A → D}.
• From F', we can infer A → B and C → D.
• However, the FD A → D is not derivable from F'. The attributes A and D are in different relations (A in R1, R3; D in R2), and there is no common attribute or chain of FDs in F' that links A to D. Specifically, (A)+ using F' = {A, B} (from A → B), which does not include D. Therefore, A → D is lost.

Since the FD A → D is not preserved, the decomposition is NOT dependency preserving.

To find the canonical cover F_c, we follow these steps:

1. Split right-hand sides (RHS):
   F' = { P -> Q, P -> R, P -> S, Q -> R, S -> R }
   (P -> QRS is split into P -> Q, P -> R, P -> S).

2. Remove extraneous attributes from left-hand sides (LHS):
   All LHS in F' are single attributes, so there are no extraneous attributes to remove.

3. Remove redundant functional dependencies:
   We check each FD in F' for redundancy:

   • P -> Q: (P)+ from F' - {P -> Q} = {P, R, S} (using P -> R, P -> S, S -> R). 'Q' is not in (P)+. Not redundant.
   • P -> R: (P)+ from F' - {P -> R} = {P, Q, S, R} (since P -> Q and Q -> R imply P -> R; also P -> S and S -> R imply P -> R). 'R' is in (P)+. Therefore, P -> R is redundant. Remove it.
     Current set: F'' = {P -> Q, P -> S, Q -> R, S -> R}.
   • P -> S: (P)+ from F'' - {P -> S} = {P, Q, R} (since P -> Q, Q -> R). 'S' is not in (P)+. Not redundant.
   • Q -> R: (Q)+ from F'' - {Q -> R} = {Q}. 'R' is not in (Q)+. Not redundant.
   • S -> R: (S)+ from F'' - {S -> R} = {S}. 'R' is not in (S)+. Not redundant.

   The canonical cover is F_c = {P -> Q, P -> S, Q -> R, S -> R}.

To find the canonical cover F_c, we follow these steps:

1. Split right-hand sides (RHS):
   F' = { PQ -> R, R -> S, P -> R, P -> S, S -> T }
   (P -> RS is split into P -> R and P -> S).

2. Remove extraneous attributes from left-hand sides (LHS):
   Only PQ -> R has multiple attributes on its LHS.

   • Check for Q in PQ -> R: Is R derivable from (P)+ using F'?
     (P)+ from F' = {P}. Using P -> R, we get {P, R}. Since R is in (P)+, Q is extraneous. Replace PQ -> R with P -> R.
     Current set: F'' = { P -> R, R -> S, P -> R, P -> S, S -> T }. We remove the duplicate P -> R.
     So, F'' = { P -> R, R -> S, P -> S, S -> T }.
     No other FDs have multiple attribute LHS.

3. Remove redundant functional dependencies:
   We check each FD in F'' for redundancy:

   • P -> R: (P)+ from F'' - {P -> R} = {P, S, T} (using P -> S, S -> T). 'R' is not in (P)+. Not redundant.
   • R -> S: (R)+ from F'' - {R -> S} = {R}. 'S' is not in (R)+. Not redundant.
   • P -> S: (P)+ from F'' - {P -> S} = {P, R, S, T} (using P -> R, then R -> S implies P -> S; then S -> T). 'S' is in (P)+. Therefore, P -> S is redundant. Remove it.
     Current set: F''' = { P -> R, R -> S, S -> T }.
   • S -> T: (S)+ from F''' - {S -> T} = {S}. 'T' is not in (S)+. Not redundant.

   The canonical cover is F_c = {P -> R, R -> S, S -> T}.

To check for dependency preservation, we analyze the functional dependencies projected onto each sub-relation.

1. Project FDs onto R1=(X, Y, Z): The FD X → YZ from F has all its attributes (X, Y, Z) within R1. Therefore, F1 contains FDs derived from X → YZ, which are {X → Y, X → Z}.
2. Project FDs onto R2=(Y, W): The FD Y → W from F has all its attributes (Y, W) within R2. Therefore, F2 contains {Y → W}.

Let F' = F1 U F2 = {X → Y, X → Z, Y → W}.

Now, we compare (F')+' with F+:

• The original FDs are F = {X → YZ, Y → W}. Note that X → YZ is equivalent to {X → Y, X → Z}.
• From F', we can directly infer X → Y and X → Z (which together form X → YZ) and Y → W.

Since all original FDs (and their equivalent forms) are present in F', the decomposition is dependency preserving.

To find the canonical cover F_c, we follow these steps:

1. Split right-hand sides (RHS):
   F' = { A -> B, A -> C, B -> D, A -> D, D -> E }
   (A -> BC is split into A -> B and A -> C).

2. Remove extraneous attributes from left-hand sides (LHS):
   All LHS in F' are single attributes, so there are no extraneous attributes to remove.

3. Remove redundant functional dependencies:
   We check each FD in F' for redundancy:

   • A -> B: (A)+ from F' - {A -> B} = {A, C, D, E}. 'B' is not in (A)+. Not redundant.
   • A -> C: (A)+ from F' - {A -> C} = {A, B, D, E} (since A -> B, B -> D, D -> E). 'C' is not in (A)+. Not redundant.
   • B -> D: (B)+ from F' - {B -> D} = {B}. 'D' is not in (B)+. Not redundant.
   • A -> D: (A)+ from F' - {A -> D} = {A, B, C, D, E} (since A -> B and B -> D imply A -> D). 'D' is in (A)+. Therefore, A -> D is redundant. Remove it.
   • D -> E: (D)+ from current F' - {D -> E} = {D}. 'E' is not in (D)+. Not redundant.

   The canonical cover is F_c = {A -> B, A -> C, B -> D, D -> E}.

To check for dependency preservation, we analyze the functional dependencies projected onto each sub-relation.

1. Project FDs onto R1=(U, V): F1 = {U → V} (since U and V are in R1, and U → V is in F).
2. Project FDs onto R2=(V, W): F2 = {V → W} (since V and W are in R2, and V → W is in F).
3. Project FDs onto R3=(U, X): F3 = {} (No FD in F has both its LHS and RHS entirely within the attributes {U, X}. U → V requires V, V → W requires V and W, and UW → X requires W).

Let F' = F1 U F2 U F3 = {U → V, V → W}.

Now, we compare (F')+' with F+:

• The original FDs are F = {U → V, V → W, UW → X}.
• U → V and V → W are directly present in F'.
• However, the FD UW → X is not derivable from F'. To check this, consider the closure of {U, W} using F':
  • (UW)+ using F' = {U, W} (starting attributes)
  • From U → V (in F'), we add V: {U, W, V}
  • From V → W (in F'), W is already present.
  • No further attributes can be added. The closure is {U, V, W}.
    Since X is not in (UW)+, the FD UW → X is not preserved.

Therefore, the decomposition is NOT dependency preserving because the FD UW → X is not preserved.

To determine if a decomposition of R into R1 and R2 is lossless, we check if the intersection of the decomposed relations (R1 ∩ R2) is a superkey for either R1 or R2 under the given set of functional dependencies (FDs).

1. Identify the relations:
   R1 = {A, B, C}
   R2 = {C, D, E}

2. Find the intersection of R1 and R2:
   R1 ∩ R2 = {C}

3. Compute the closure of the intersection, (R1 ∩ R2)+, which is C+ under the FDs F = { A → B, C → D, B → E }:

   • Start with C+ = {C}
   • Apply C → D: C+ becomes {C, D}
   • No other FDs can be applied. (A → B cannot be used as 'A' is not in C+; B → E cannot be used as 'B' is not in C+).
   • Therefore, C+ = {C, D}

4. Check if (R1 ∩ R2) is a superkey for R1 or R2:

   • Is C a superkey for R1 = {A, B, C}? This means C+ must contain all attributes of R1. Since C+ = {C, D} does not contain A and B, C is not a superkey for R1.
   • Is C a superkey for R2 = {C, D, E}? This means C+ must contain all attributes of R2. Since C+ = {C, D} does not contain E, C is not a superkey for R2.

Since {C} is neither a superkey for R1 nor R2, the decomposition is not a lossless-join decomposition.

To find the canonical cover F_c, we follow these steps:

1. Split right-hand sides (RHS):
   All FDs in F already have a single attribute on their RHS. So, F' = F.

2. Remove extraneous attributes from left-hand sides (LHS):

   • Check VW -> X:
     • Is V extraneous? Is X derivable from (W)+ using F'? (W)+ = {W}. X is not in (W)+. V is not extraneous.
     • Is W extraneous? Is X derivable from (V)+ using F'? (V)+ = {V, W, Y} (using V -> W, V -> Y). X is not in (V)+. W is not extraneous.
   • Check WX -> Y:
     • Is W extraneous? Is Y derivable from (X)+ using F'? (X)+ = {X}. Y is not in (X)+. W is not extraneous.
     • Is X extraneous? Is Y derivable from (W)+ using F'? (W)+ = {W}. Y is not in (W)+. X is not extraneous.
       No extraneous attributes are found in any LHS.

3. Remove redundant functional dependencies:
   We check each FD in F' for redundancy:

   • VW -> X: (VW)+ from F' - {VW -> X} = {V, W, Y} (using V -> W, V -> Y). 'X' is not in (VW)+. Not redundant.
   • V -> W: (V)+ from F' - {V -> W} = {V, Y} (using V -> Y). 'W' is not in (V)+. Not redundant.
   • WX -> Y: (WX)+ from F' - {WX -> Y} = {W, X}. 'Y' is not in (WX)+. Not redundant.
   • V -> Y: (V)+ from F' - {V -> Y} = {V, W, X, Y} (using V -> W, then VW -> X derived from V, W, then WX -> Y derived from W, X). 'Y' is in (V)+. Therefore, V -> Y is redundant. Remove it.

   The canonical cover is F_c = {VW -> X, V -> W, WX -> Y}.