GATE CS 2021 Set 1 Q23 — Tuple Calculus and SQL

To find the estimated number of tuples in the output of the selection query $\sigma_{(A > 10) \vee (B = 18)}(r)$, we assume a uniform and independent distribution of values for attributes $A$ and $B$.

1. Probability of $A > 10$:

• The attribute $A$ has integer values ranging from $6$ to $20$.
• Total number of distinct values of $A = 20 - 6 + 1 = 15$.
• The values satisfying $A > 10$ are $\{11, 12, \dots, 20\}$, which gives $20 - 11 + 1 = 10$ values.
• $P(A > 10) = \frac{10}{15} = \frac{2}{3}$.

2. Probability of $B = 18$:

• The attribute $B$ has integer values ranging from $1$ to $20$.
• Total number of distinct values of $B = 20 - 1 + 1 = 20$.
• The only value satisfying $B = 18$ is $\{18\}$, which is $1$ value.
• $P(B = 18) = \frac{1}{20}$.

3. Combined Probability for the $\vee$ (OR) condition:

Since $A$ and $B$ are independently distributed:

4. Estimated Number of Tuples:

• For $1200$ tuples: $\text{Estimated Tuples} = 1200 \times \frac{41}{60} = 820$
• For $300$ tuples (alternative paper version): $\text{Estimated Tuples} = 300 \times \frac{41}{60} = 205$