GATE CS 2024 Set 2 | Question 56
A functional dependency \(F\colon 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 ________
Explanation
Answer: 50
Since \(X\) and \(Y\) must be disjoint, a dependency is fixed by giving each of the 4 attributes one of three roles: in \(X\), in \(Y\), or in neither. That gives \(3^{4} = 81\) assignments. Remove those with an empty side by inclusion–exclusion:
- \(X\) empty: each attribute is in \(Y\) or in neither, \(2^{4} = 16\) ways;
- \(Y\) empty: likewise 16 ways;
- both empty: 1 way, subtracted twice above, so add it back.
Useful dependencies: \(81 - 16 - 16 + 1 = 50\).
Answer: 50