IAE Academy

GATE 2024 CS2 Q.45: solution and answer

GATE 2024 · CS2Q.45 · 2 marks · MCQ

The relation schema, Person(pid, city), describes the city of residence for every person uniquely identified by pid (pid is underlined, the key). 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

  1. (A)

    1

  2. (B)

    2

  3. (C)

    3

  4. (D)

    4

See the question in the paper

Answer and solution

ANSWER

The minimum number of cross product operations is 2, option (B).

Official answer: BSource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

  1. Without grouping or counting operators, "at least 3 persons live in one city" can only be tested by exhibiting three different tuples of Person with the same city. That needs three copies of Person.

  2. Rename three copies: , , .

  3. Combine them: . Joining three relations takes cross products.

  4. Select the tuples where the three persons are distinct and share a city:

  5. Project the city: . This returns exactly the cities with at least 3 residents.

  6. One cross product combines only two tuples at a time. It can show that 2 persons share a city, but never 3, because every tuple of the result holds only two persons. Selection, projection and rename never combine tuples. So 2 cross products are needed, and 2 are enough. The answer is (B).

KEY IDEA

With only selection, projection, cross product and rename, a count of 3 can be tested only by pairing three renamed copies of the relation. Three copies take two cross products.

WATCH OUT FOR

Answering 3 because there are three persons, or 1 because a single self-join feels enough. A pair of tuples (one cross product) proves only 2 residents. Three renamed copies are joined by 2 cross products, not 3.

From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 13 Relational algebra questions, with notes

More Relational algebra questions