GATE CS 2021 Set 1 Q.33 (CS Q.23): Relational Algebra and Tuple Relational Calculus

A relation $r(A, B)$ in a relational database has 1200 tuples. The attribute $A$ has integer values ranging from 6 to 20, and the attribute $B$ has integer values ranging from 1 to 20. Assume that the attributes $A$ and $B$ are independently distributed.

The estimated number of tuples in the output of $\sigma_{(A > 10) \lor (B = 18)}(r)$ is __________

Your answer

Official answer and solution

Accepted answers: 819 to 820, or 205
From: Official GATE 2021 answer key

About the official key

GATE accepted either range [819, 820] (based on standard independent disjunction selectivity) or 205 (which corresponds to an alternate interpretation where the condition was read as conjunction or restricted domain).

Note on this question

Official answer key accepts either range 819.0 to 820.0 or 205.0 to 205.0.

Solution

Calculate individual selectivities of the conditions on A and B, then use independent probability for logical OR.

Total tuples in relation $r(A, B)$ is $N = 1200$ .

Attribute $A$ has integer values ranging uniformly from 6 to 20, comprising $20 - 6 + 1 = 15$ distinct values.
The condition $(A > 10)$ covers values $\{11, 12, \dots, 20\}$ , which is $20 - 11 + 1 = 10$ values.
The selectivity of $(A > 10)$ is $s(A) = \frac{10}{15} = \frac{2}{3}$ .

Attribute $B$ has integer values ranging uniformly from 1 to 20, comprising 20 distinct values.
The condition $(B = 18)$ matches 1 value out of 20, with selectivity $s(B) = \frac{1}{20}$ .

Because attributes $A$ and $B$ are independently distributed, the selectivity of the disjunction $(A > 10) \lor (B = 18)$ is:

s(A \lor B) = s(A) + s(B) - s(A) \cdot s(B) = \frac{2}{3} + \frac{1}{20} - \left(\frac{2}{3} \times \frac{1}{20}\right) = \frac{40 + 3 - 2}{60} = \frac{41}{60}

The estimated number of tuples in the output is:

\text{Tuples} = 1200 \times \frac{41}{60} = 20 \times 41 = 820

(Or 819 if computed with slight precision variations).

Final answer

820

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 33 of 65, printed as CS Q.23
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source