GATE CS 1999 Q2.7 — Normal Forms

To determine the normal form of the decomposed relations, let us first analyze the functional dependencies (FDs) of the relation $R(S, T, U, V)$:

Step 1: Find the Candidate Keys of $R$

Let's compute the attribute closures:

• $S^+ = \{S, T, U, V\}$
• $T^+ = \{T, U, V, S\}$
• $U^+ = \{U, V, S, T\}$
• $V^+ = \{V, S, T, U\}$

Since the closure of each individual attribute contains all the attributes of the relation, the candidate keys of $R$ are: $\{S\}$, $\{T\}$, $\{U\}$, and $\{V\}$.

Step 2: Identify Prime and Non-Prime Attributes

• Prime attributes (attributes that are part of any candidate key): $\{S, T, U, V\}$
• Non-prime attributes: None ($\emptyset$)

Step 3: Analyze the Decomposition $R_1$ and $R_2$

For any decomposition $R = (R_1, R_2)$ where $R_1 \cap R_2 \neq \emptyset$:

1. The attributes in any sub-relation $R_i$ ($R_1$ or $R_2$) are a subset of $\{S, T, U, V\}$.
2. Since the original FDs form a complete cycle, every single attribute in $R_i$ can determine all other attributes in $R_i$. Thus, every attribute in $R_i$ is a candidate key for $R_i$.
3. Consequently, there are no non-prime attributes in either $R_1$ or $R_2$.

Step 4: Check Normal Forms

• 2NF (Second Normal Form): A relation is in 2NF if there is no partial dependency of a non-prime attribute on any candidate key. Since there are no non-prime attributes, 2NF is trivially satisfied.
• 3NF (Third Normal Form): A relation is in 3NF if, for every non-trivial dependency $X \rightarrow Y$, either $X$ is a superkey or $Y$ is a prime attribute. Since all attributes in $R_1$ and $R_2$ are prime, 3NF is also satisfied.

Thus, the decomposition is in both 2NF and 3NF.