GATE IT 2007 | Question: 65

Question

Consider a selection of the form $\sigma_{A\leq 100} (r)$, where $r$ is a relation with $1000$ tuples. Assume that the attribute values for $A$ among the tuples are uniformly distributed in the interval $[0, 500].$ Which one of the following options is the best estimate of the number of tuples returned by the given selection query ?

• A. $50$
• B. $100$
• C. $150$
• D. $200$

Comments

Another way to solve this question

Probability density function $F(x) \  =  \frac{1}{500\  – \ 0} = \frac{1}{500}$

$\therefore P(x \le 100) = \int_{0}^{100} F(x) dx$

$P = \int_{0}^{100} \frac{1}{500} dx$

$P = \frac{1}{500}  \ [x]_{0}^{100}$

$P = \frac{100}{500} = \frac{1}{5}$

So, the total number of tuples $= NP$

$= 1000 \  \times  \ \frac{1}{5}$

$= 200$

---

What a wonderful linking of two condepts.
Appreciated.
Thanks

---

Of course. Here is a concise and conceptually clear way to solve it.

The solution is based on a single key principle: uniform distribution.

1. Find the Fraction of the Range: The query is looking for values in the range of [0, 100]. The total possible range of values is [0, 500]. So, the fraction of the range the query is interested in is:

   500−0100−0​=500100​=51​

2. Apply the Fraction to the Data: Because the data is uniformly distributed (spread evenly), we expect this same fraction (51​) to apply to the total number of tuples.

3. Calculate the Result: Take the total number of tuples (1000) and multiply it by the fraction we found:

   1000×51​=200

The intuition: Since the data is spread evenly across the value range, selecting 20% of the range will select 20% of the data.

Answer 1

$\sigma_{A \leq 100}(r)$
 $r$ has $1000$ tuples

Values for A among the tuples are uniformly distributed in the interval $[0, 500].$ This can be split to $5$ mutually exclusive (non-overlapping) and exhaustive (no other intervals) intervals of same width of $100$ $([0-100], [101-200], [201-300], [301-400], [401-500],$ $0$ makes the first interval larger - this must be a typo in question) and we can assume all of them have same number of values due to Uniform distribution. So, number of tuples with A value in first interval should be

$\frac{\text{Total no. of tuples}}{5} = 1000/5 = 200$

Correct Answer: $D$

Comments

Then what is meaning of <=100??

---

totaltotal we have 1000

 Now we splitting [0-500]---> 0-250, 251-500

Combinely we have 0-250,251-500,0-1000 in the 200 tuple is <=100

---

Since we have 1000 tuples and values between 0 and 500.So we can distribute 0-499 initially.So by that time 500 tuples would have been completed.

Now the next value is 500 which is 501 st  tuple.Now if we try to wrap around and repeat same interval again,since we have 499 tuples remained with values possible from 0 to 499.

So for values A < 100 we can have initial 101 + final 101 =202 tuples in total.

So the best estimate matches 200 tuples?

Can we consider such a distribution?

Answer 2

option D

total numbers are 1000 and they have said that it is uniformly distrubuted between [0,500] it means every number is 2 times thats the only way we can distribute it uniformaly and as per our condition A<=100 at max 100 tuples can be there and and every one can be repeated 2 times so it sums up to 200 hence it is answer

Comments

@adhiti

Here it is not mentioned which attributes we are projecting, so even if the value of A may be same the other attribute's value may be different making the tuples different, hence 200 is the correct answer

---

does select operator removes redundant tuples?

---

@Jhaiyam A relation is a set and so it has no duplicates. Here, select with respect to relational algebra, it does eliminate duplicates.

Answer 3

may be this is best and simple method to understand this question

Answer 4

There must be typo in question. As clearly 1000 tuples written in question. And values of A are uniformly distributed.

By taking (0 500] , A values can be 0.5, 1,1.5.... 100, 100.5....499, 499.5, 500

Total 1000 values.

By which values <=100 are 200.

Answer 5

Hope it helps.

Answer 6

My thought process:-

Since nothing is given about the schema, assume the schema is R(a,b,c,d),

now possible values of ‘a’:- 0,0,1,1,2,2,3,3,4,4,5,5………..499,499 ( not sure why 500 is included in the question if the distribution is uniform, but if we try to bring the distribution to almost be uniform, then i guess we can assume possible values of ‘a’ is 0,1,2,3,4,5….498,499,500,0,1,2,3,4,5,6,……..498.  Either approach should give me the correct answer since we’re dealing with values of ‘a’ less than 200 )

now the query only applies a condition on ‘a’, it does not project the ‘a’ field, therefore thinking about unique ‘a’ values would be wrong as the result will give us 202 tuples, this is where our assumption of the schema being not R(a) only comes into picture.

Hopefully, this should summarise the entire scenario, we have played it safe by assuming the schema to be general.