The Gateway to Computer Science Excellence
+26 votes

The following functional dependencies hold for relations $R(A, B, C)$ and $S(B, D, E).$ 

  • $ B \to A$
  • $A \to C$

The relation $R$ contains $200$ tuples and the relation $S$ contains $100$ tuples. What is the maximum number of tuples possible in the natural join  $R \bowtie S$?

  1. $100$
  2. $200$
  3. $300$
  4. $2000$
in Databases by Veteran (105k points)
edited by | 3.4k views

7 Answers

+36 votes
Best answer

(A) 100.

Natural join will combine tuples with same value of the common rows(if there are two common rows then both vaues must be equal to get into the resultant set). So by this defn: we can get at the max only $100$ common value.

by Active (3.4k points)
edited by
That happens only if the join attribute is unique in at least one of the relation rt?
B is the candidate key in relation R according to the functional dependency that they gave(b-> a, a->c), i.e. there can be no no repetition of B So we have 200 B's and combined with 100 may be unique B's, so it should gibe at the max 100 unique b only
Yes. That's correct.
B is the candidate key, but it is not the chosen key. How can we say that B is actually chosen as the key, and so has unique entries. It might be possible that all the rows are the same. The functional dependency will hold in that case too.

B -> C means each B value is associated with precisely one C value, so to satisfy the functional dependency all the rows with same value can't occur  

@Pragy FD C->A is not given so all rows cannot be equal + even if C->A was given then too Bs must be unique as we have to find the maximum tuples.
But how do we know that B  is the foreign key in S referring to the candidate key B of relation R?
Because im realation S(B, D, E ) no funtional dependancy present so candidate key is BCD now B in S reffrer to R in which B is candidate key.
What will be minimum tuple in above case
so in that case answer will be 20000.

Dheeresh kushawaha

What will be minimum tuple in above case

It will be $0$ because of $S(B,D,E)$ $B$ is $FK$,So,it may contain $NULL$

Since "BDE" is a Candidate Key for S and B is a part of candidate key it can't contain NULL value. So min and max in this case is (100, 100).
if R contain 100 tuples and S contain 200 tuples ,in this case answer will be 200?
+26 votes

From the given set of functional dependencies, it can be observed that B is a candidate key of R. So all 200 values of B must be unique in R.

There is no functional dependency given for S.

To get the maximum number of tuples in output, there can be two possibilities for S.
1) All 100 values of B in S are same and there is an entry in R that matches with this value. In this case, we get 100 tuples in output.
2) All 100 values of B in S are different and these values are present in R also. In this case also, we get 100 tuples.

by Boss (33k points)
yeah !! thats actually satisfying and apt answer
still its not chosen as key so how we can say this??
How can we say that the unmatched  tuples present in R also plz explain this point
+6 votes

as B is key in R and in table S, B is Foreign key that referencing to B in R

we have to find maximum number of tuples possible so there may be case that in table S every tuple of Attribute B is same

and we know natural join will combine tuples with same value

by Boss (12.3k points)
+4 votes

Every tuple in S can find atmost 1 matching tuple (with the same B value) in R...

Since asked maximum number of tuples, we can assume that every tuple in S finds 1 tuple in R. In that case natural joined table will have 100 tuples.

If we want minimum number of tuples, we can assume that every tuple in S finds 0 tuples in R. In that case natural joined table will have 0 tuples.

by Loyal (8k points)
+2 votes
Give FD is lossless join as B is the key in one table and it is common attribute for the table so the maximum no. of tupples will be 100 in natural join of R & S.
by Active (1.3k points)
Didn't get u bro
Given FD is said to be lossless join is the common key(here B) is the Key attribute of one of the table so here B is the Candidate key of R(A,B,C) so the max no. of tupples in the natural join will be min of(R,S)=100.
+2 votes

here B is common in both relations R and S .B is key in relation R bcoz B closure determines(A,B,C) all attributes of R but non-key in relation S.

B is unique in rel R but repetetion allowed in rel S.

so maximum number of tuples possible in the natural join  R⋈S depend on non-key

so 100 is ans

by Active (4.5k points)
0 votes

As simple as possible:)

by Junior (825 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,368 users