GATE CS 2024 Set 2 — Question 56

To find the total number of useful functional dependencies $F: X \to Y$ for a relation $R$ with $4$ attributes, we follow the given conditions:Let the set of attributes be $U = \{A, B, C, D\}$, so $|U| = 4$. For each attribute $a \in U$, there are three possible assignments in a functional dependency X → Y that satisfies $X \cap Y = \emptyset$:

• $a \in X$
• $a \in Y$
• $a \notin X$ and $a \notin Y$

The total number of such assignments for $4$ attributes is $3^4 = 81$.Now, we must exclude the cases where $X = \emptyset$ or $Y = \emptyset$:

• Case 1: $X = \emptyset$

If $X$ is empty, each attribute can either be in $Y$ or in neither set. There are $2^4 = 16$ such cases.

• Case 2: $Y = \emptyset$

If $Y$ is empty, each attribute can either be in $X$ or in neither set. There are $2^4 = 16$ such cases.

• Case 3: $X = \emptyset$ and $Y = \emptyset$

This case is included in both Case 1 and Case 2. It occurs when all attributes are in neither set. There is $1^4 = 1$ such case.Using the Principle of Inclusion-Exclusion, the number of invalid cases (where $X = \emptyset$ or $Y = \emptyset$) is:$$16 + 16 - 1 = 31$$Therefore, the total number of useful functional dependencies is:$$81 - 31 = 50$$