3,327 views
5 votes
5 votes
Why is the maximum number of tuples in full outer join equal to m*n, where m is the number of attributes in one relation and n is the attribute count in other ?

Can someone give an example to illustrate this ?

4 Answers

Best answer
2 votes
2 votes
Max no of tuple returned by Full outer join is same as no of tuples in Cartesian  Product i.e. m*n.
3 votes
3 votes
Let it be any type of join.
Join means, apply Cross product then filter out some tuples based on condition.

Join is something like  Cross Product + Sigma

So when no attribute from any side matches, we do not get 0, we get m*n  tuples because of cross product.
We get 0 tuples when attributes match but no tuple satisfy the condition.

Hence it is clear that when no attribute from two relation match we get  m*n tuples from join.
0 votes
0 votes

First off, there is no relation between number of tuples in the result of outer join and the number of ATTRIBUTES.

Assuming you meant to say that m and n denotes the number of tuples in R and S where R and S are the relations that are being full outer joined, then the minimum possible number of tuples are max(m,n) and the maximum possible number of tuples are (m+n).

Eg-

TABLE R

A B
1 x
2 y
3 z

 

Table S

C D
4 g
5 h
6 i
7 j

 

Here if we perform (R outer full join S) then the result will be

R FULL JOIN S
A B C D
1 x NULL NULL
2 y NULL NULL
3 z NULL NULL
NULL NULL 4 g
NULL NULL 5 h
NULL NULL 6 i
NULL NULL 7 j

This the maximum possible number of tuples that can be present in FULL JOIN, that is (m+n)

 

if I am mistaken please feel free to comment

0 votes
0 votes

the actual reason for this is – if you have two relation say and and suppose both share a common attribute based on which they will be join then for join and we will get M x N tuples the worst case would be that if each tuple in m*n will satisfy the join condition. 

an example of this would be suppose R.A has all value 1 in every tuple of and S.A too have all value of as 1 

and join condition will be R.A = S.A then all the tuple will satisfy the condition

Related questions

6 votes
6 votes
2 answers
2
hacker16 asked Jan 9, 2018
3,747 views
Why is the minimum number of tuples in full outer join equal to max (m,n) ?
3 votes
3 votes
1 answer
3
techbrk3 asked Nov 9, 2017
1,976 views
R(A, B) foreign key B refers S.S(A, B) foreign key A refers R. (primary keys are bold)None of the attributes is nullable. R contains 75 tuples and S contains 25 tuples. W...
4 votes
4 votes
4 answers
4
kauray asked May 9, 2017
3,687 views
Suppose you are given relations r(A, B) and s(A, C). Suppose that r has 10000 tuples, and s has 5000 tuples. Suppose attribute r.A has 1001 distinct values, and s.A also ...