in Databases
2,494 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 ?
in Databases
by
2.5k views

4 Answers

2 votes
2 votes
Best answer
Max no of tuple returned by Full outer join is same as no of tuples in Cartesian  Product i.e. m*n.

4 Comments

simply take two relations R(A,B,C) and S(D,E)and apply full outer join with D=E and suppose nothing is equal then obviously it will be converted to cartesian product,so maximum number of tuples will be m*n.

second case when in all the cases D=E then we will get in one of the relations all the tuples matched and remaining tuples from other relation then minimum number of tuples will be MAX(m,n).
–1
–1
When nothing is equal then condition evaluates to be false. then shouldn't it be $0$?
1
1
@arjun sir in all type of join operation the maximum number of tuple is M x N
0
0
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.
by

1 comment

i think this logic is completely wrong
0
0
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

2 Comments

it is  M x N you can google it

0
0

The maximum number of tuple you will get is M x N. You have not considered the join condition in this case. Join operation involves cartesian product of both the tables first which will give you M x N tuples. Now if all the tuples satisfies this join condition then, the maximum number of tuples you will get is M x N. 

0
0
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