1,246 views
4 votes
4 votes

Consider a relation $R(A,B,C)$ with the following functional dependencies $AB \to C$ and $AC \to B$. $A$ can take 20 distinct values, $B$ can take 10 distinct values and $C$ can take 100 distinct values. What is the maximum possible size (in tuples) of the self join of $R$ on $C$?

  1. 4,000
  2. 200
  3. 4,00,000
  4. 20,000

2 Answers

Best answer
4 votes
4 votes
$AB\to C$ basically means whenever A,B values repeat C must also repeat. Thus this FD restrict the number of possible tuples in R to number of possible values of A * number of possible values of B, which is 20 * 10 = 200. Now we can either have the sane C value for all these 200 tuples or utilize all our distinct 100 values. Since we join on C, the first case would return 200*200=40000 tuples while the second case can only return a maximum of 2*200=400 tuples when each of the 100 C value is repeated twice.

But we haven't yet considered the FD $AC\to B$ . Due to this FD, we cannot have more than 20 tuples with one C value. So we need minimum 10 distinct C values to get our 200 tuples for R. This would mean join on C returns true for 20 tuples (from 200 we have 10 distinct C values, meaning 20 matching ones for each C value) and we can have a maximum of 200*20 = 4000 tuples in join.
selected by
3 votes
3 votes

A) 4000


due to the restrictions imposed by the functional dependencies we can vary values like:
keep B and C value as constant and loop through all values of A, this gives us 20 possible combinations for the value set to appear in the Relation R.
next on getting exhausted with the above situation we try to change the value of B, keeping C as before but FDs stops us from doing that and the FD set asks us to change the value for C also, therefore for possible combinations of BC we get 10 different sets for which each element of set is associated with 20 values of A. 10 different because we simultaneously change value for C as we change for B as we need maximum possible tuples in the result when performing the Self Join on C.

On Self join we see that for such a story the same values of C are to be combined with the same values of C only Because the join is on C.

for instance
A B C
$a_1$ $b_1$ $c_1$
$a_2$ $b_1$ $c_1$
$a_1$ $b_2$ $c_2$
$a_2$ $b_2$ $c_2$

for first row in the Relation we have with same C 20 different combinations, similarly for the second row on same value of C there that is $c_1$

then same is true for the third row onwards which has 20 different combinations on same value of C i.e. $c_2$ and so on for such 10 possible $b_i$ and $c_i$

Hence, (20*20) * 10 = 4000

edited by

Related questions

3 votes
3 votes
4 answers
2
2 votes
2 votes
1 answer
3
Rakesh K asked Dec 9, 2016
1,295 views