GATE CS 2024 Set 2 Q.45: Relational Algebra and Tuple Relational Calculus

The relation schema, Person(pid,city), describes the city of residence for every person uniquely identified by pid. The following relational algebra operators are available: selection, projection, cross product, and rename.

To find the list of cities where at least 3 persons reside, using the above operators, the minimum number of cross product operations that must be used is

Official answer and solution

Official answer: B
From: Official GATE 2024 answer key

Solution

Form 3-tuples of distinct persons residing in the same city by taking the cross product of 3 renamed copies of Person.

Without aggregation (COUNT), finding cities with at least $3$ distinct persons requires checking the existence of three tuples $p_1, p_2, p_3 \in \text{Person}$ with the same city and pairwise distinct pids:

\pi_{\text{city}}\Bigl(\sigma_{p_1.\text{city} = p_2.\text{city} \,\wedge\, p_2.\text{city} = p_3.\text{city} \,\wedge\, p_1.\text{pid} \neq p_2.\text{pid} \,\wedge\, p_2.\text{pid} \neq p_3.\text{pid} \,\wedge\, p_1.\text{pid} \neq p_3.\text{pid}}\bigl(\rho_{p_1}(\text{Person}) \times \rho_{p_2}(\text{Person}) \times \rho_{p_3}(\text{Person})\bigr)\Bigr)

Combining $3$ copies of Person requires $3 - 1 = 2$ cross product operations.

Final answer

Option (B)

Common trap

Choosing 3 (the number of relation instances) instead of 2 (the number of binary cross-product operations connecting 3 instances).

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

Source

Paper: GATE 2024 Computer Science and Information Technology - Set 2 (CS2)
Question: 45 of 65
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