GATE CS 2024 Set 2 Q35 — Relational Model: Relational Algebra

To find the cities where at least $3$ distinct persons reside, we need to compare three different tuples from the Person relation to ensure they have the same city but different person IDs (pid).

Let $P$ be the relation Person(pid, city). To compare three tuples from $P$, we must create three renamed instances of $P$:

• $P_1(pid_1, city_1) = \rho_{P_1}(P)$
• $P_2(pid_2, city_2) = \rho_{P_2}(P)$
• $P_3(pid_3, city_3) = \rho_{P_3}(P)$

To combine these three relations using only the permitted operators, we perform the cross product of these three instances:

This requires exactly $2$ cross product operations: $(P_1 \times P_2) \times P_3$.

We can then apply selection and projection to filter the required cities:

Why fewer operations are not possible:

• With $0$ cross products, we can only query single tuples, which cannot compare different persons.
• With $1$ cross product ($P_1 \times P_2$), we can only compare at most two tuples, which can identify cities with at least $2$ residents, but not $3$.

Thus, the minimum number of cross product operations required is $2$.