Normal Form Practice Questions

To find the candidate keys, we first determine the attribute closure for each attribute.
Attributes that do not appear on the right-hand side of any FD are 'D' and 'H'. Thus, any candidate key must include D and H.
Let's test closures:
$(AD)^{+} = AD$ (A $\rightarrow$ BC) $= ABCDH$ (B $\rightarrow$ CFH) $= ABCDFGH$. Since all attributes are covered, AD is a candidate key.
$(BD)^{+} = BD$ (B $\rightarrow$ CFH) $= BCDFH$ (C and F are not determinant in closure calculation. We need to check all attributes) (C in CH->G) $= BCDFGH$ (A in E->A) (E is not in closure, so it doesn't give A) (CD in A->BC) $= BCDFGH$. D and H are present in BD. BCFH has C, F, H. CH -> G gives G. E->A doesn't apply. So $(BD)^+ = BDFHCG$.
$(ED)^{+} = ED$ (E $\rightarrow$ A) $= ADE$ (A $\rightarrow$ BC) $= ABCDE$ (B $\rightarrow$ CFH) $= ABCDEFH$ (F $\rightarrow$ EG) $= ABCDEFGH$. Since all attributes are covered, ED is a candidate key.
$(FD)^{+} = FD$ (F $\rightarrow$ EG) $= FDEG$ (E $\rightarrow$ A) $= FDEGA$ (A $\rightarrow$ BC) $= FDEGABC$ (B $\rightarrow$ CFH) $= FDEGBCH$. Since all attributes are covered, FD is a candidate key.

All these candidate keys (AD, ED, FD) are found by combining irreducible left-hand sides of FDs with the attributes not appearing on the right-hand side. We are missing one more candidate key. Let's re-evaluate.
We are looking for minimal superkeys. Start with attributes not on the RHS: D, H.
Candidate Key Set will be combinations of $\{A, B, C, E, F\}$ with D and H.

1. $(ADH)^+ = ADH$. $A \rightarrow BC$. So $(ADH)^+ = ADHBC$. $B \rightarrow CFH$. So $(ADH)^+ = ADHBCFG$. All attributes covered. So ADH is a key. (We can remove H, if D is sufficient as above).
2. $(BDH)^+ = BDH$. $B \rightarrow CFH$. So $(BDH)^+ = BDFHC$. $C \rightarrow G$. So $(BDH)^+ = BDFHCG$. All attributes covered. So BDH is a key.
3. $(EDH)^+ = EDH$. $E \rightarrow A$. So $(EDH)^+ = EDHA$. $A \rightarrow BC$. So $(EDH)^+ = EDHABC$. $B \rightarrow CFH$. So $(EDH)^+ = EDHABCF$. $F \rightarrow EG$. So $(EDH)^+ = EDHABCFG$. All attributes covered. So EDH is a key.
4. $(FDH)^+ = FDH$. $F \rightarrow EG$. So $(FDH)^+ = FDHEG$. $E \rightarrow A$. So $(FDH)^+ = FDHEGA$. $A \rightarrow BC$. So $(FDH)^+ = FDHEGABC$. $B \rightarrow CFH$. So $(FDH)^+ = FDHEGABCF$. All attributes covered. So FDH is a key.

The candidate keys are AD, BD, ED, FD.

Let's analyze each option:
A. Every relation in 3NF is not necessarily in BCNF. BCNF is a stricter form of normalization than 3NF. A relation can be in 3NF but not BCNF if for some functional dependency $X \to A$, $X$ is not a superkey and $A$ is a prime attribute.
B. This option describes the definition of 2NF, not 3NF. A relation is in 3NF if it is in 2NF and every non-prime attribute is non-transitively dependent on every key.
C. BCNF is a stricter normal form than 3NF. This means that if a relation satisfies the conditions for BCNF, it automatically satisfies the conditions for 3NF. Therefore, every relation in BCNF is also in 3NF.
D. This statement is false because, as explained in option C, every relation in BCNF is also in 3NF, implying they can certainly be in both.

Armstrong's inference rules form a sound and complete set of axioms used to derive all functional dependencies from a given set $F$. The three fundamental axioms are:

1. Reflexivity: If $Y \subseteq X$, then $X \rightarrow Y$.
2. Augmentation: If $X \rightarrow Y$, then $XZ \rightarrow YZ$ for any attribute set $Z$.
3. Transitivity: If $X \rightarrow Y$ and $Y \rightarrow Z$, then $X \rightarrow Z$.
   These specific rules are the core axioms from which all other properties, such as decomposition or union, can be derived. Therefore, the set containing Transitive, Augmentation, and Reflexive rules represents the complete set of Armstrong's axioms.

Second Normal Form ($2NF$) is defined by the requirement that a relation must be in $1NF$ and contain no partial functional dependencies. A partial dependency occurs when a non-prime attribute is functionally dependent on only a proper subset of a candidate key. To satisfy $2NF$, every non-prime attribute must be "fully functionally dependent" on the entire candidate key, meaning it cannot be determined by any strict subset of the key. While $1NF$ addresses atomicity and $3NF$ eliminates transitive dependencies, the enforcement of full functional dependency is the fundamental criterion for $2NF$.

A relation is in BCNF if, for every non-trivial functional dependency $X \to Y$, $X$ is a superkey. In $Suppliers$, the candidate keys are $\{sid\}$ and $\{sname, city\}$. All functional dependencies, such as $sid \to \{sname, city, street\}$ and $\{sname, city\} \to \{sid, street\}$, have a superkey as the left-hand side. In $Parts$, the key is $\{pid\}$ with FDs $pid \to \{pname, color\}$, where $pid$ is a superkey. In $Catalog$, the key is $\{sid, pid\}$ with the FD $\{sid, pid\} \to cost$, where $\{sid, pid\}$ is a superkey. Since the LHS of every functional dependency in all relations is a superkey, the entire schema is in BCNF.

For $R_{Book} = \{Title, Author, Catalog\_no, Publisher, Year, Price\}$, the keys are $K_1 = \{Title, Author\}$ and $K_2 = \{Catalog\_no\}$. The functional dependency $Publisher, Title, Year \rightarrow Price$ violates 3NF because the determinant is not a superkey and $Price$ is not a prime attribute. Since all non-prime attributes $\{Price, Publisher, Year\}$ are fully functionally dependent on the keys, $R_{Book}$ is in 2NF but not 3NF.

For $R_{Coll} = \{Title, Author, Catalog\_no\}$, the only FD is $Title, Author \rightarrow Catalog\_no$. Since $\{Title, Author\}$ is a superkey, this schema satisfies BCNF, and consequently, it is in 3NF. Thus, $Book$ is in 2NF and $Collection$ is in 3NF.

To determine the normal form of $R(A, B, C, D, E, P, G)$, we first identify the candidate key. Calculating the closure of $\{A, B\}$, we get $\{A, B\}^+ = \{A, B, C, D, E, P, G\}$, making $\{A, B\}$ a candidate key. The prime attributes are $\{A, B\}$ and the non-prime attributes are $\{C, D, E, P, G\}$.

A relation is in 2NF if every non-prime attribute is fully functionally dependent on the entire candidate key (i.e., no partial dependencies exist). We observe the functional dependency $B \to G$. Since $B$ is a proper subset of the candidate key $\{A, B\}$ and $G$ is a non-prime attribute, this represents a partial functional dependency. Consequently, the relation violates 2NF.

To determine if the decomposition of $R(A, B, C, D)$ into $R_1(A, B)$, $R_2(B, C)$, and $R_3(B, D)$ is lossless and dependency preserving:

1. Lossless Join: A decomposition is lossless if the join of the relations can reconstruct $R$. Joining $R_2(B, C)$ and $R_3(B, D)$ on $B$ is lossless because $B \to C$ (or $B \to D$) holds in $F^+$. The result, $R_{23}(B, C, D)$, joined with $R_1(A, B)$ on $B$, is also lossless because $B \to \{C, D\}$ holds in $F^+$. Thus, it is a lossless join.

2. Dependency Preserving: We check if all FDs in $F = \{A \to B, B \to C, C \to D, D \to B\}$ can be derived from the union of projections $F_1 \cup F_2 \cup F_3$:

   • $R_1$ preserves $A \to B$.
   • $R_2$ preserves $B \to C$ and $C \to B$ (since $B \to C, C \to D, D \to B \implies B \equiv C$).
   • $R_3$ preserves $B \to D$ and $D \to B$.
   • The original dependency $C \to D$ can be derived as $C \to B$ (from $R_2$) and $B \to D$ (from $R_3$). Since all original FDs are preserved, it is dependency preserving.

1. Implication (i) is false because multivalued dependencies ($A \rightarrow \rightarrow B$ and $A \rightarrow \rightarrow C$) do not imply a functional dependency ($A \rightarrow BC$).
2. Implication (ii) is true because $A \rightarrow B$ and $A \rightarrow C$ imply $A \rightarrow BC$ by the union rule, and $A \rightarrow BC$ implies $A \rightarrow \rightarrow BC$ by the replication rule.
3. Implication (iii) is false because $A \rightarrow \rightarrow BC$ and $A \rightarrow B$ do not necessarily force $A \rightarrow C$; they only guarantee $A \rightarrow \rightarrow C$.
4. Implication (iv) is true because $A \rightarrow BC$ implies $A \rightarrow C$ (decomposition rule), which in turn implies $A \rightarrow \rightarrow C$ (replication rule).
5. Therefore, only implications (ii) and (iv) are valid, making the total count 2.

Let's analyze each statement:

1. A. Any relation with two attributes is in BCNF.
   Let the relation be $R(A, B)$. The possible non-trivial functional dependencies (FDs) are $A \to B$ or $B \to A$.

   • If $A \to B$ is the only FD, then $\{A\}$ is a key (and superkey). Since $A \to B$ has $A$ as a superkey, it's in BCNF.
   • If $B \to A$ is the only FD, then $\{B\}$ is a key (and superkey). Since $B \to A$ has $B$ as a superkey, it's in BCNF.
   • If both $A \to B$ and $B \to A$ hold, then $\{A\}$ and $\{B\}$ are both keys. For any FD, its left-hand side is a superkey. It's in BCNF.
   • If no non-trivial FDs exist, then $\{A, B\}$ is the key. BCNF holds vacuously.
     This statement is TRUE.

2. B. A relation in which every key has only one attribute is in 2NF.
   A relation is in 2NF if it is in 1NF and no non-prime attribute is partially dependent on any candidate key. A partial dependency occurs when a non-prime attribute is dependent on a proper subset of a candidate key. If every key has only one attribute (i.e., keys are not composite), then there cannot be any proper subsets of a key for a non-prime attribute to be partially dependent on. Therefore, no partial dependencies can exist.
   This statement is TRUE.

3. C. A prime attribute can be transitively dependent on a key in a 3NF relation.
   A transitive dependency exists if $K \to X$ and $X \to Y$ hold, where $K$ is a key, $X$ is not a superkey, and $X \not\to K$. A relation is in 3NF if for every non-trivial FD $A \to B$, either $A$ is a superkey or $B$ is a prime attribute.
   Consider $R(K, X, P)$ with FDs $K \to X$ and $X \to P$. Let $K$ be a key, $X$ be a non-prime and non-superkey attribute, and $P$ be a prime attribute.
   For $X \to P$ to exist in a 3NF relation, since $X$ is not a superkey, $P$ must be a prime attribute. This is consistent with the statement.
   Example: $R(A, B, C, D)$ with FDs $A \to B$, $B \to C$, $CD \to A$. Candidate keys are $A$ and $CD$. Prime attributes are $A, C, D$. $B$ is non-prime. The FDs $A \to B$ and $B \to C$ represent a transitive dependency where key $A$ transitively determines prime attribute $C$ via non-superkey $B$. This relation is in 3NF because $A \to B$ ($A$ is a superkey), $B \to C$ ($B$ is not a superkey, but $C$ is prime), $CD \to A$ ($CD$ is a superkey).
   This statement is TRUE.

4. D. A prime attribute can be transitively dependent on a key in a BCNF relation.
   For a relation to be in BCNF, for every non-trivial FD $X \to Y$, $X$ must be a superkey.
   If a prime attribute $P$ is transitively dependent on a key $K$, it implies FDs $K \to X$ and $X \to P$ exist, where $X$ is not a superkey and $X \not\to K$.
   For the FD $X \to P$ to exist in a BCNF relation, by the definition of BCNF, $X$ must be a superkey. This directly contradicts the condition for transitive dependency that $X$ is not a superkey.
   Therefore, transitive dependencies (via a non-superkey attribute) cannot exist in a BCNF relation.
   This statement is FALSE.

The final answer is $\boxed{D}$

A relation is in BCNF if for every non-trivial functional dependency $X \to Y$, the determinant $X$ acts as a superkey.
However, decomposing a relation into BCNF may fail to preserve all functional dependencies.
This issue frequently arises when a relation contains overlapping composite candidate keys.
For instance, in $R(A, B, C)$ with dependencies $AB \to C$ and $C \to B$, the keys are $AB$ and $AC$, both being composite.
Decomposing to BCNF would force a loss of the dependency $AB \to C$, making 3NF often preferred to ensure dependency preservation.
Thus, BCNF is effectively not used in scenarios featuring two overlapping composite candidate keys.

Armstrong's axioms provide a set of fundamental rules for inferring functional dependencies ($FDs$) in relational databases. The three primary axioms are:

1. Reflexivity: If $Y \subseteq X$, then $X \rightarrow Y$.
2. Augmentation: If $X \rightarrow Y$, then $XZ \rightarrow YZ$.
3. Transitivity: If $X \rightarrow Y$ and $Y \rightarrow Z$, then $X \rightarrow Z$.
   Because Reflexivity, Augmentation, and Transitivity are the core axioms, "Mutual dependency" is not an inference rule defined within this system.

Let $F$ be a Conjunctive Normal Form (CNF) formula with $m$ clauses, $C_1, \ldots, C_m$.
Consider a random truth assignment where each variable is assigned 'true' with probability $1/2$ independently.
For any non-empty clause $C_j$, it is false only if all its literals are false. The probability of this is $P(C_j \text{ is false}) = (1/2)^{k_j}$ (where $k_j$ is the number of literals in $C_j$), so $P(C_j \text{ is true}) = 1 - (1/2)^{k_j}$. Since $k_j \ge 1$, $P(C_j \text{ is true}) \ge 1 - 1/2 = 1/2$.
Let $S$ be the total number of true clauses. The expected number of true clauses is $E[S] = \sum_{j=1}^m P(C_j \text{ is true}) \ge \sum_{j=1}^m (1/2) = m/2$.
By the probabilistic method, since the expected number of true clauses is at least $m/2$, there must exist at least one specific truth assignment for which at least half the clauses evaluate to true.

The attributes $X$ and $Y$ do not appear on the right-hand side of any functional dependency, so they must be part of any candidate key.
We test the attribute closure of the option $VXY$:

1. Begin with the set $\{V, X, Y\}$.
2. Using the dependency $VY \to W$, we add $W$ to get $\{V, W, X, Y\}$.
3. Using the dependency $WX \to Z$, we add $Z$ to get $\{V, W, X, Y, Z\}$.
   Since the closure includes all attributes in $R$ and no subset is a superkey, $VXY$ is a candidate key.

In database normalization, the $3NF$ synthesis algorithm guarantees that any relation can be decomposed into a $3NF$ schema that is both lossless-join and dependency-preserving. However, $BCNF$ is a stricter normal form that prioritizes the elimination of redundancy over dependency preservation. It is a well-established fact that not every relation can be decomposed into $BCNF$ while maintaining all original functional dependencies, making dependency preservation a property not guaranteed for $BCNF$ decomposition. Therefore, the statement asserting that such decomposition is "always possible" is false.

Given the functional dependencies: $A \rightarrow B$, $A \rightarrow C$, $CD \rightarrow E$, $B \rightarrow D$, $E \rightarrow A$.

• For Option A: $\{CD\}^+ = \{C, D, E, A, B\}$, which contains both $A$ and $C$, so $CD \rightarrow AC$ is implied.
• For Option B: $\{BD\}^+ = \{B, D\}$, which does not contain $C$, so $BD \rightarrow CD$ is NOT implied.
• For Option C: $\{BC\}^+ = \{B, C, D\}$, which contains $C$ and $D$, so $BC \rightarrow CD$ is implied.
• For Option D: $\{AC\}^+ = \{A, C, B, D, E\}$, which contains $B$ and $C$, so $AC \rightarrow BC$ is implied.

To determine the normal form, we first identify the candidate key. The closure of the set $\{F_1, F_2\}$ is $\{F_1, F_2, F_3, F_4, F_5\}$, making $(F_1, F_2)$ the candidate key. A relation is in $2\text{NF}$ if it is in $1\text{NF}$ and has no partial dependencies, meaning no non-prime attribute should depend on a proper subset of a candidate key. Here, $F_1 \to F_3$ and $F_2 \to F_4$ are partial dependencies because $F_3$ and $F_4$ depend only on $F_1$ and $F_2$ respectively, which are proper subsets of the candidate key $(F_1, F_2)$. Since partial dependencies exist, the relation fails $2\text{NF}$ and remains in $1\text{NF}$.

1. The primary key of the relation $Empdtl$ is $empcode$.
2. A relation is in 2NF if it is in 1NF and has no partial dependencies (where a non-prime attribute depends on a proper subset of a candidate key). Since the key $\{empcode\}$ consists of a single attribute, no proper subset exists, meaning there are no partial dependencies; therefore, the relation is in 2NF.
3. A relation is in 3NF if for every functional dependency $X \rightarrow Y$, $X$ is a superkey or $Y$ is a prime attribute.
4. Consider the dependency $pincode \rightarrow \{city, state\}$: $pincode$ is not a superkey, and $\{city, state\}$ are not prime attributes.
5. This indicates a transitive dependency ($empcode \rightarrow pincode \rightarrow \{city, state\}$) that violates 3NF, confirming the relation is in 2NF but not 3NF.