IAE Academy

GATE 2024 CS2 Q.56: solution and answer

GATE 2024 · CS2Q.56 · 2 marks · NAT

A functional dependency is termed as a useful functional dependency if and only if it satisfies all the following three conditions:
- is not the empty set.
- is not the empty set.
- Intersection of and is the empty set.

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

See the question in the paper

Answer and solution

ANSWER

The number of useful functional dependencies on a relation with 4 attributes is 50.

Official answer: 50Source: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

  1. A useful dependency is determined by an ordered pair of disjoint, non-empty subsets of the 4 attributes. The condition on means no attribute can be in both.

  2. Place each attribute in exactly one of three places: in , in , or in neither. This gives assignments, and each one gives a disjoint pair , with or possibly empty.

  3. Assignments with : each attribute is in or in neither, so .

  4. Assignments with : each attribute is in or in neither, so .

  5. The single assignment with (every attribute in neither) is counted in both of the previous steps, so by inclusion-exclusion it must be added back once.

  6. Check by the size of : choose in ways, then is any non-empty subset of the remaining attributes, in ways. The term for is because no attribute is left for .

KEY IDEA

Count ordered pairs of disjoint non-empty subsets by giving each attribute one of three places (in X, in Y, in neither), then remove the cases where X or Y is empty by inclusion-exclusion: .

WATCH OUT FOR

Forgetting to add back the case where both X and Y are empty after subtracting the two empty cases, which gives 49. Another slip is counting only pairs, which ignores the disjointness condition.

From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 19 Normal forms questions, with notes

More Normal forms questions