GATE CS 2019 Q.65 (CS Q.55): Relational Algebra and Tuple Relational Calculus

Consider the following relations $P(X, Y, Z)$ , $Q(X, Y, T)$ and $R(Y, V)$ :

How many tuples will be returned by the following relational algebra query?

\Pi_X(\sigma_{P.Y=R.Y \land R.V=V2}(P \times R)) - \Pi_X(\sigma_{Q.Y=R.Y \land Q.T>2}(Q \times R))

Answer: ________.

Your answer

Official answer and solution

Solution

Evaluate the two projection terms separately and take their set difference.

We are given the relational algebra expression:

\Pi_X(\sigma_{P.Y=R.Y \land R.V=V2}(P \times R)) - \Pi_X(\sigma_{Q.Y=R.Y \land Q.T>2}(Q \times R))

Step 1: Evaluate the first term:

T_1 = \Pi_X(\sigma_{P.Y=R.Y \land R.V=V2}(P \times R))

In relation $R(Y, V)$ , tuples with $V = V2$ are $(Y3, V2)$ and $(Y2, V2)$ . So the qualifying $Y$ values from $R$ are $Y3$ and $Y2$ .
Joining with $P(X, Y, Z)$ $P (X, Y, Z)$ on $P.Y = R.Y$ $P . Y = R . Y$ , we find tuples in $P$ $P$ having $Y \in \{Y3, Y2\}$ $Y \in {Y 3, Y 2}$ :
- $(X1, Y1, Z1)$ has $Y = Y1$ (no match)
- $(X1, Y1, Z2)$ has $Y = Y1$ (no match)
- $(X2, Y2, Z2)$ has $Y = Y2$ (matches $(Y2, V2)$ )
- $(X2, Y4, Z4)$ has $Y = Y4$ (no match)
Projecting attribute $X$ yields:

T_1 = \{X2\}

Step 2: Evaluate the second term:

T_2 = \Pi_X(\sigma_{Q.Y=R.Y \land Q.T>2}(Q \times R))

In relation $Q(X, Y, T)$ $Q (X, Y, T)$ , tuples satisfying $Q.T > 2$ $Q . T > 2$ are:
- $(X1, Y2, 5)$ with $Y = Y2$
- $(X1, Y1, 6)$ with $Y = Y1$
  (Tuple $(X2, Y1, 2)$ has $T = 2 \ngtr 2$ , and $(X3, Y3, 1)$ has $T = 1 \ngtr 2$ )
Now check if these $Y$ $Y$ values ( $Y2, Y1$ $Y 2, Y 1$ ) exist in relation $R$ $R$ :
- $R$ contains $Y1$ (in $(Y1, V1)$ ) and $Y2$ (in $(Y2, V3)$ and $(Y2, V2)$ ). Both exist in $R$ .
Projecting attribute $X$ from the matching tuples:
Both $(X1, Y2, 5)$ and $(X1, Y1, 6)$ have $X = X1$ .
Thus:

T_2 = \{X1\}

Step 3: Set difference:

T_1 - T_2 = \{X2\} - \{X1\} = \{X2\}

The resulting relation contains exactly 1 tuple, namely $(X2)$ .

Therefore, the number of tuples returned is 1.

Final answer

Common trap

Treating $Q.T > 2$ as $\ge 2$ which would include $(X2, Y1, 2)$ with $X = X2$ , making the set difference empty ( $0$ tuples).

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

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.