3,678 views
4 votes
4 votes
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 has 1001 distinct values. The maximum possible size of the join result is

4 Answers

Best answer
4 votes
4 votes

Refering page no. 121 - 123 of    http://cs.iit.edu/~cs525/slides/allhandouts.pdf 

CASE 2 : W = R1 Join R2 when X ∩ Y = A

T(W) = T(R2) * T(R1) / max{ V(R1,A), V(R2,A) }

where V(R1,A) = Max distinct column A tuples in Relation R1

   and  V(R2,A) = Max distinct Column A tuples in Relation R2

it should be (10000*5000)/1001 = 49950

A B
1 a1
1 a2
1 a3
1 a4
1 a5
2 b1
2 b2
2 b3
2 b4
2 b5
A C
1 u
1 v
2 w
2 y
2 z

R1(A,B) Join R2 (A,C) = 10*5/2 = 25 Tuples 

selected by
7 votes
7 votes
Considering natural join property where tuples are joined when the values of the common attributes are equal, the maximum joins wil be in this scenario:

In relation r, there are 1001 distinct values of A. Since total of 10000 tuples in r, we get 8,999 tuples with repeated values of A

Similary in realtion s, there are 1001 distinct values of A. Since total of 5000 tuples in s, we get 3,999 tuples with repeated values of A.

The maximum joins happen when all tuple are repeated with same value.

Hence total maximum joins possbile is (9000*4000) + 1000 = 36001000.
1 votes
1 votes

Consider this Scenario : 

R (A,B) : 10000 rows ( showing Seperate Values Of A and B for a tuple/row)

A Tuples ( a1,a2,.......,a1001, (a1001,........ a1001) 8999 times ) B Tuples ( b1,b2,b3,.........,b10000 )

S (A,C) : 5000 rows ( showing Seperate Values Of A and C for a tuple/row)

A Tuples ( a1,a2,.......,a1001, (a1001,........ a1001) 3999 times ) C Tuples ( c1,c2,c3,.........,c5000 )

Now Making Join Of Both (Natural Join) ( For each tuple of R matching with Each tuple of S on basis of Common Column A)

For a1 : Match Found : 1 ; a2 : Match Found 1 ; ................ ; a1000 : Match Found 1 ; (Inidividual Match (A) :1000 )

For a1001 :

Match Found  : For R -> A ( row no 1001) : With S ->  A (row no 1001)

                         For R -> A ( row no 1001) : With S ->  A (row no 1002)

                         ... So 4000 matches for R -> A ( row no 1001 )  .... Similarly 4000 matches for R -> ( row no 1002)  ....

                         For Others : 8999 a1001's of relation R  -> Matches by Duplicate (B) :  9000 * 4000 = 36 * 10^6 

Total Matches  : (A) + (B) : 36000000 + 1000 = 36001000. (Answer)

P.S. : Here we are taking as many as duplicates in Relation R and S ; because we need to find maximum number of tuples. 

Related questions

0 votes
0 votes
1 answer
2
srestha asked Dec 16, 2017
1,521 views
Consider the relation schema:Student(roll no, name course no)Enroll(roll no, course no,course name)The number of tuples in the student and enroll table is 30 and 40 respe...
3 votes
3 votes
2 answers
3
iarnav asked Dec 6, 2017
1,255 views
Say we have two relations R (a,b,c) and S (b,d,e).Now, R has 200 tuples and S has 300 tuples. What will be Minimum number of tuples when we do R ⋈ S ( ⋈ = Natural Joi...
2 votes
2 votes
1 answer
4