GATE CSE
First time here? Checkout the FAQ!
x
0 votes
344 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 has 1001 distinct values. The maximum possible size of the join result is
asked in Databases by (325 points) 2 6 16 | 344 views
Does the join here means natural join? or any other?
is answer 10,000??
I think the answer depends on type of join being performed
Type of join not mentioned. But how many tuples would result from a natural join? Can it be calculated from the above data?
Is     answer  5000
I think , some foreign key constraints may be given ????

4 Answers

+2 votes
Best answer

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 

answered by Active (1.6k points) 3 6 14
selected by
can   u pls elaborate with table
no, it will 25 only....
@Ashish I want to say  if there are two relation given for eg. R(A,B) and S(A,C).

here comman attribute is A, but it is not PK of any table. if R has total 10 tuples but only 2 distinct values. and S also has 2 distinct values with 5 total number of tuples.( same case as in your given eg)

Then R natural join with S, will give max 37 tuples. this is what I want to say..ignore my first comment.
@ Reena...what you want to say by "Then R natural join with S, will give max 37 tuples"....it is a relational instance, at particular instant of time it is fixed and therefore, it will give value 25 only...
If two relation R ans S, with tuples m and n respectively
1) if no attribute is comman then maximum no of tuples in natural join will be "mn".
2) but if any attribute is comman but not the key of any Table then in this case also max tuples will be "mn".
this is what I found,check it
@Nitish, I am not taking this perticular instance.
My statement is with respect to this question.
yes, this is what you are saying is true....but why are you saying that it will make 37 tupples...it is relational instance...there is nothing like minimum or maximum tupples for a relational instance...it will give fixed amount of tupples..

I am not taking above instance. 

 if there are two relation given for eg. R(A,B) and S(A,C)

I only considered the features of that table, not the values of tuples. 

@Reena ...can   u pls elaborate your answer with table (using data from above tables)... (its just because even i solved and found 25 tuples only)
see, what I am saying

yes its true for the above table answer is 25. what I actually want to say, read my all comments again!
i dint get ur query wrt to above table pls clear that... and ur first comment which said something about 37 tuples
I rremoved that comment. My mistake!!

If two relation R ans S, with tuples m and n respectively
1) if no attribute is comman then maximum no of tuples in natural join will be "mn".
2) but if any attribute is comman but not the key of any Table then in this case also max tuples will be "mn".
this is what I found,check it

2nd statement is wrong, if we consider @venkat_sirvisetti 's answer.
Please correct it! 

@Shyam take an instance and check it by yourself.

If anything wrong in that statement,then let me know!!
In this question, R and S has attribute "A" common but max no of tuples possible is not 10000*5000, hence I asked to correct it, if I misunderstood your 2nd statement then please clarify further.
That is because further conditions are also applied in the relations.
Now I understood properly :)
+4 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.
answered by Junior (685 points) 1 7
yes,true 36000100 is the answer.
0 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. 

answered by Active (1.7k points) 4 32 67
0 votes
ans is 1001. am is crt
answered by (37 points)

Related questions

+2 votes
0 answers
1
asked in Databases by GateAspirant999 Active (2.1k points) 6 42 73 | 298 views
+1 vote
1 answer
2
asked in Databases by rahul sharma 5 Veteran (14.9k points) 12 103 310 | 126 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23242 Points

  2. Bikram

    17048 Points

  3. Habibkhan

    7096 Points

  4. srestha

    6012 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4928 Points

  7. Sachin Mittal 1

    4762 Points

  8. joshi_nitish

    4278 Points

  9. sushmita

    3954 Points

  10. Rishi yadav

    3744 Points


Recent Badges

Popular Question Ml_Nlp
Notable Question set2018
Notable Question rahul sharma 5
Notable Question Sanjay Sharma
Notable Question Lakshman Patel RJIT
Popular Question makhdoom ghaya
Popular Question Çșȇ ʛấẗẻ
Reader kenzou
Popular Question mystylecse
Notable Question Sanjay Sharma
27,262 questions
35,076 answers
83,760 comments
33,185 users