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

Amazing insight about the foreign key.

---

@Deepak Poonia

Amazing insight sir!

We cannot say Relation S has NULL values in FK, hence the natural join will result in 0 tuples

---

very nice explanation thanks bro

Answer 1

Relation \( R(A, B, C) \):

• Functional Dependencies: \( B \to A \), \( A \to C \)
• From these dependencies, \( B \) is a candidate key for \( R \) because it determines all attributes in \( R \). Therefore, each value of \( B \) in \( R \) is unique. 

Relation \( S(B, D, E) \):

• No specific functional dependencies are given for \( S \), so we have no constraints on the values of \( B \) in \( S \). 
• Relation \( R \) contains 200 tuples. - Relation \( S \) contains 100 tuples. 

The natural join \( R \bowtie S \) will combine tuples from \( R \) and \( S \) that have the same value for the attribute \( B \), which is common to both relations. Since \( B \) is a candidate key in \( R \), each value of \( B \) in \( R \) is unique. Thus, \( R \) can have at most 200 unique values of \( B \). For the maximum number of tuples in the join, we want every tuple in \( S \) to find a matching tuple in \( R \). This is possible if all 100 values of \( B \) in \( S \) are also present in \( R \). 

The maximum number of tuples in the natural join \( R \bowtie S \) is determined by the number of tuples in \( S \) that can successfully match tuples in \( R \) based on the common attribute \( B \). Since \( S \) has 100 tuples, and we assume that all values of \( B \) in \( S \) are present in \( R \), the maximum number of tuples in the join is 100.  Therefore, the correct answer is: (A) 100.

Comments

Incomplete logic.

We will get 100 only if there are unique values in Attribute B. In the question B is a candidate key so there will be unique values so the answer will be 100.

---

Doubt : Does B necessarily needs to be candidate key, does the functional dependency necessarily make it a candidate key? - essence of many comments to this question like by @Pragy Agarwal sir, @Shukla_

 

Solution :

 

ChatGPT says,

 

1. Functional Dependency (FD):This does not by itself say anything about whether b uniquely identifies a tuple — it just forces consistency of values.

2. Candidate Key

A candidate key requires uniqueness: no two distinct tuples can share the same value of the key.

 

So, by definition, b is a candidate key.

 

3. Your Worry: What if I don’t assume uniqueness?

If you drop the uniqueness requirement, then you’re no longer talking about a candidate key, you’re just talking about FDs holding.

 

For example, a possible relation:

 

b | a | c

--+---+--

1 | 2 | 3

1 | 2 | 3

This satisfies b → a and a → c, but here b is not unique in practice.

But relational model says: duplicates are not allowed (relations are sets of tuples). So such a relation isn’t considered valid in theory.

 

Thus:

 

In relational algebra theory: yes, b is necessarily a candidate key (since duplicates are disallowed).

 

In SQL (practical world): duplicates are allowed unless you declare a key constraint → so FDs may hold without b being unique, and b won’t automatically become a key unless you declare it as such.

 

So FInal Conclusion, in case if specified that this is done within a SQL System, then the answer will be 200*100 i.e. in case when all the b values in both the relation is same(i.e. constant throughout.)

---

@amanbadone0 dont post content which was generated by AI. 

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

How can we say that the unmatched  tuples present in R also plz explain this point

---

This is much more comprehensive

---

In relation R ,
according to f.d. : {b=>a, a=>c}
so we can say if two tupple has same value of b , then they would have same value of a and same value of c. (core of FD)

this implies b is a unique key here.
In relation S,
b is not a key, so for same b , there can be different value of d and e .

but for maximum cardinality we assume b is unique in relation S too and all values of b is present in relation R

 

 

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

Comments

Amazing🔥

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.

Answer 5

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.

Comments

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.

Answer 6

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