GATE CS Relational Algebra Previous Year Questions

GATE CS 2024 Set 1 | Question 35

NAT · 1 mark

Consider the following two relations, \(\boldsymbol{R(A,B)}\) and \(\boldsymbol{S(A,C)}\):

\(\boldsymbol{R}\)
\(\boldsymbol{A}\)	\(\boldsymbol{B}\)
10	20
20	30
30	40
30	50
50	95

\(\boldsymbol{S}\)
\(\boldsymbol{A}\)	\(\boldsymbol{C}\)
10	90
30	45
40	80

The total number of tuples obtained by evaluating the following expression

\[\boldsymbol{\sigma_{B \lt C}(R \bowtie_{R.A=S.A} S)}\]

is _________

Your answer

Explanation

Answer: 2

The join pairs each tuple of \(R\) with the tuples of \(S\) that have the same \(A\) value:

\(A = 10\): \((10, 20)\) pairs with \((10, 90)\).
\(A = 30\): \((30, 40)\) and \((30, 50)\) both pair with \((30, 45)\).
\(A = 20\) and \(A = 50\) have no match in \(S\), and the \(S\) tuple with \(A = 40\) has no match in \(R\).

So the join has 3 tuples, whose \((B, C)\) values are \((20, 90)\), \((40, 45)\) and \((50, 45)\). The selection \(B \lt C\) keeps the first two and removes \((50, 45)\), leaving 2 tuples.

Answer: 2

GATE CS 2024 Set 2 | Question 45

MCQ · 2 marks · −0.66

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

1 2 3 4

Explanation

Answer: (B)

With no grouping or counting, “at least 3 persons” has to be found as three tuples with the same city and pairwise different pids. Two cross products bring three renamed copies together:

\[\pi_{P_1.\mathit{city}}\big(\sigma_{C}(\rho_{P_1}(\mathit{Person}) \times \rho_{P_2}(\mathit{Person}) \times \rho_{P_3}(\mathit{Person}))\big)\]

where \(C\) requires equal cities and \(P_1.\mathit{pid} \ne P_2.\mathit{pid}\), \(P_1.\mathit{pid} \ne P_3.\mathit{pid}\), \(P_2.\mathit{pid} \ne P_3.\mathit{pid}\).

One cross product is not enough. An expression with at most one cross product builds each answer from at most two Person tuples. If it reported a city with three residents, it would also report that city for a relation holding only the two tuples it used, where that city has at most two residents.

Answer: B