GATE CS 2024 Set 2 Q46 — Normal Forms

To find the total number of possible useful functional dependencies $X \rightarrow Y$ for a relation $R$ with $4$ attributes, we need to find the number of pairs of subsets $(X, Y)$ of the attribute set $U$ (where $|U| = 4$) such that:

1. $X \neq \emptyset$
2. $Y \neq \emptyset$
3. $X \cap Y = \emptyset$

We can solve this using two different approaches:

Method 1: Using Attribute Assignments (Combinatorics)

For each of the $4$ attributes in $U$, there are exactly $3$ choices:

• The attribute belongs to $X$.
• The attribute belongs to $Y$.
• The attribute belongs to neither $X$ nor $Y$.

The total number of such assignments is $3^4 = 81$.

However, we must exclude cases where $X$ or $Y$ is empty:

• Case 1: $X = \emptyset$
  Each attribute can either belong to $Y$ or to neither ($2$ choices per attribute).
  Number of ways = $2^4 = 16$.
• Case 2: $Y = \emptyset$
  Each attribute can either belong to $X$ or to neither ($2$ choices per attribute).
  Number of ways = $2^4 = 16$.
• Case 3: Both $X = \emptyset$ and $Y = \emptyset$
  All attributes belong to neither ($1$ choice per attribute).
  Number of ways = $1^4 = 1$.

Using the Principle of Inclusion-Exclusion (PIE):

Method 2: Partitioning by the Size of $X$

Let $|X| = k$. Since $Y$ must be non-empty and disjoint from $X$, $k$ can range from $1$ to $3$.

• If $k = 1$:
  Choose $X$ in $\binom{4}{1} = 4$ ways. The remaining $3$ attributes can form $Y$. Since $Y \neq \emptyset$, there are $2^3 - 1 = 7$ choices for $Y$.
  $\text{Total} = 4 \times 7 = 28$ ways.
• If $k = 2$:
  Choose $X$ in $\binom{4}{2} = 6$ ways. The remaining $2$ attributes can form $Y$. Since $Y \neq \emptyset$, there are $2^2 - 1 = 3$ choices for $Y$.
  $\text{Total} = 6 \times 3 = 18$ ways.
• If $k = 3$:
  Choose $X$ in $\binom{4}{3} = 4$ ways. The remaining $1$ attribute can form $Y$. Since $Y \neq \emptyset$, there is $2^1 - 1 = 1$ choice for $Y$.
  $\text{Total} = 4 \times 1 = 4$ ways.

Summing these up: