GATE CSE 2010 | Question: 43

Question

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$?

• A. $100$
• B. $200$
• C. $300$
• D. $2000$

Comments

Minimum: 0

Also, if S.B is a foreign key referencing to R.B then Minimum & Maximum both = 100.

NOTE that the Classical Relational Algebra doesn't have the concept of "Null Values".

---

here in question they have given 2 table R(A,B,C) and S(B,D,E) now and they have also given some funtional

dependency now, if you will loook at this functional depedndency then B is acting as primary key for table of R and by

using this functional dependency we cannot infer about primary key or candaidate key of S . now

-------------------------------------------------------------------------------------------------------------------------------------------------
lets do some question before doing this 

1)Now, if they are asking for maximum number of tuple in natural join and if their are no attribute matching then we can simply do cross product.

2)now if they have given two table R and S and their attribute is matching and no value inside attribute of both table are matching then there result become 0.

becuse natural join what does it takes a tuple from R and match with every tuple of S and where ever common attribute

value match natural join put its into output table.now in this way it does for all.

3) now second case idea if you will apply  ,now think what type of relation you can create which gives maximum number of tuple .lets see
assume there are any two arbitrarly relation R(a,b) and s(a,d) and assume they havenot told any thing about primary

key or candiadte key .so what will happen actully.assume that all value of a are same in both relation and this is very

much possible also . so every pair of R will match wuth every pair of S so when you will do natural join then in resulatnt

table number of  tuple become |R|*|s|.

=================================================================================
now lets come to this question

becouse here in this question for table R, B is primary key so it will be unique . and you want maxiumum no of tuple in

resultent table so you will try to match as much as possible .

so if in S relation attribut value of B you will take same then one tuple of R will match every tuple of  of S and this gives

100. becuse B is primary key in R so no two value can be same so every one will be disitint so after that no one will

match.
and result will become 100

 

.

---

very nicely explain

Answer 1

(A) $100.$

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

Comments

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.

---

okay!

---

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?

---

Yes.If there was repetition possible then the answer will not be 100.From the given FDs B is the candidate key so there should not be any repetition in B.So maximum number of  tuples possible will be 100.

---

$\text{This is the way to solve such questions}$

---

Very helpful..Thank you for your efforts.

---

Yes, Shashank bruh. In both the cases, either we take 1-100 values (i.e. distinct value) in B (Relation S),

Or, we take repeated value (i.e. 1 * 100 tuples), in both the cases the maximum tuples we can obtain is limited to 100.

 

In the case of minimum, I believe the answer will be zero, as in relation S, B can have value that is not present in relation R. And, when join will be performed, no tuples will be obtained. Am I right? @shashank!

---

no it cannot be 0

you are not right

anshik

---

candidate key can not contain duplicate values

---

@ijnuhb can you please elaborate how?

---

@ijnuhb

I think there is some flaw in your logic.

One important point regarding referential key Integrity

For referential integrity to hold in a relational database, any column in a base table that is declared a foreign key can only contain either null values or values from a parent table's primary key or a candidate key.
Source: wiki

Since it is not mentioned in the question of Ref. IC is followed or not. Therefore let’s take cases.

Case 1: When Ref. IC exists

since we want minimum so there will be no matching between tuples of R and S. We can have all NULLS in S.B

R ⋈ S will have no tuples and also it won’t give us cross-product as there is a common attribute.

Min Tuples : 0

Case 2: When Ref. IC doesn’t exists

This is straightforward as we can give any values to S.B other than that present in R.B. 

Min Tuples : 0

 

---

@pragy agarwal doubt is good one. But in relational algebra duplicate tuples are not present. Consider a case were two tuples have same value for B in R. As B→ AC in R then the value of {A,C} must also be same to satisfy the FD which results in duplicate tuples. Which is a contradiction. So B attribute values must be unique in R.

Answer 2

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.

Comments

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

Answer 3

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

Answer 4

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.