GATE CS 2024 Set 2 Q.56: Functional Dependencies and Normalization

A functional dependency $F: X \rightarrow Y$ is termed as a useful functional dependency if and only if it satisfies all the following three conditions:

$X$ is not the empty set.
$Y$ is not the empty set.
Intersection of $X$ and $Y$ is the empty set.

For a relation $R$ with 4 attributes, the total number of possible useful functional dependencies is ________

Your answer

Official answer and solution

Official answer: 50
From: Official GATE 2024 answer key

Solution

Assign each of the 4 attributes to $X$ , $Y$ , or neither ( $3^4$ ), and use inclusion-exclusion to remove cases where $X = \emptyset$ or $Y = \emptyset$ .

Since $X \cap Y = \emptyset$ , each of the $4$ attributes of relation $R$ can be placed into one of $3$ disjoint buckets: $X$ , $Y$ , or $R \setminus (X \cup Y)$ .

Total ways to assign $4$ attributes to the $3$ buckets $= 3^4 = 81$ .
Number of assignments where $X = \emptyset$ (attributes only in $Y$ or neither) $= 2^4 = 16$ .
Number of assignments where $Y = \emptyset$ (attributes only in $X$ or neither) $= 2^4 = 16$ .
Number of assignments where both $X = \emptyset$ and $Y = \emptyset$ $= 1$ .

By inclusion-exclusion, the number of useful functional dependencies is:

3^4 - 2 \cdot 2^4 + 1 = 81 - 32 + 1 = 50

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2024 Computer Science and Information Technology - Set 2 (CS2)
Question: 56 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source