number of functional dependencies

Question

Find the number of functional dependencies in a relation having n attributes?

On first thought , I figure out that left hand side can have N+1 possibilities(null can also be there.) and similarly N+1 possibility for right hand side.
Hence total no of FD should be
(n+1)*(n+1) - 1

But ans given is 2^(n+1) .

On analyzing the answer , We can see they are not including trivital ones like ABC -> A etc .

So what should be the correct ans ???

Answer 1

I think 2^n *2 is the answer because it includes all basic minimal FD’s and the rest can be derived from axioms or are trivial. A -> BC will have A -> B, A -> C, etc. ABC -> A, etc. are trivial.

Although it’s not clear from question whether to include all trivial cases. In that case the answer will be 2^n * 2^n. Because we can have 2^n choices for both LHS and RHS .

Answer 2

2^n possible attribute sets on the LHS, and again 2^n possible attribute sets on the RHS. Both counts include the empty set.

Number of possible distinct pairs between those is 2^n * 2^n.

While technically correct, this answer also implies that FDs such as {AB} -> {} are also considered. How many of those are there ? For each cardinality l of the LHS, there are 2^l possible subsets, each of those giving a trivial FD if it appears on the RHS. So the number of trivial FDs is 2^0 + 2^1 + 2^2 + ... + 2^n = 2^(n+1) - 1. Leaving in total 2^(2*n) + 1 - 2^(n+1).

But now we have excluded only {AB} -> {A} and the like, and not {AB} -> {AC}. If we want the RHS to mention only attributes that are not mentioned on the LHS, then for each cardinality l of the LHS, there are 2^(n-l)-1 possible subsets on the RHS (that extra minus one is needed because the empty set must be excluded). Summing up to 2^0 - 1 + 2^1 - 1 + 2^2 - 1 + ... + 2^n - 1 = 2^(n+1) - 1 - (n + 1).

Still different from the answer given. And at any rate, the question was formulated hopelessly poorly. The question DID NOT STATE that trivial FDs were to be excluded. The question DID NOT STATE that "partially trivial" FDs were to be excluded.

BTW let's take the answers to the test. Choose a relation of degree 1, {A}. There are four possible FDs :

{} -> {} trivial, RHS subset of LHS
{} -> {A}
{A} -> {} trivial, RHS subset of LHS
{A} -> {A} trivial, RHS subset of LHS.

The correct answer, if trivial FDs are to be excluded, is "one". Your textbook says it's "four".