GATE CSE 2024 Session 2 Q56: Number of useful functional dependencies on 4 attributes

A functional dependency $F: X \to 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 ________

Try it: numerical answer: type the value

Your answer

Numerical answer. No negative marking.

Show answer and explanation

Answer: 50 (official GATE 2024 final answer key)

Concept used: Counting ordered pairs of disjoint non-empty subsets: each attribute goes to $X$ , $Y$ or neither.

First step: There are $3^4$ assignments; subtract those with $X$ empty ( $2^4$ ) or $Y$ empty ( $2^4$ ) and add back the one with both empty.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2024 Session 2 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key