what is maximum number of tuples in natural join

Question

Given relations R and S, each has n and m tuples, respectively. After natural join of R and S, what could be the maximum numbers of tuples? I saw one given answer is n*m but I couldn't figure out what is such a case. Please help me understand this scenario.

Answer 1

I hope, you understood what Natural Join exactly is. You can review here.

If the tables R and S contains common attributes and value of that attribute in each tuple in both tables are same, then the natural join will result n*m tuples as it will return all combinations of tuples.

Consider following two tables

Table R (With attributes A and C)

 A  |  C
----+----
 1  |  2
 3  |  2

Table S (With attributes B and C)

 B  |  C
----+----
 4  |  2
 5  |  2
 6  |  2

Result of natural join R * S (If domain of attribute C in the two tables are same )

 A | B |  C
---+---+----
 1 | 4 |  2
 1 | 5 |  2
 1 | 6 |  2
 3 | 4 |  2
 3 | 5 |  2
 3 | 6 |  2    

You can see both R and S contain the attribute C whose value is 2 in each and every tuple. Table R contains 2 tuples, Table S contains 3 tuples, where Result table contains 2*3=6 tuples.

Hope this will help.

Answer 2

Writing this post as I could not add to Surajeet's answer

Number of Tuples after a join (R>< S) for relation R(A,B,C) and S(C,D,E) is given by T(R>< S) =

where V(R,C) is distict values of C in relation R and V(S,C) is distict values of C in relation S

in extreme case if there is only 1 distinct value and that value is same (assuming conservation of value sets). Then we get T(R>< S) = T(R) * T(S). Hence n*m.