GATE CS 2017 Set 1 — Question 41

A tuple relational calculus query is safe if it is guaranteed to return a finite result, i.e. every value in every result tuple can be drawn from the database itself.(III) $\{t \mid \exists u \in \text{EMP}(t[\text{EmpName}] = u[\text{EmpName}] \wedge \exists v \in \text{DEPT}(t[\text{DeptId}] = v[\text{DeptId}]))\}$$t[\text{EmpName}]$ must equal an EmpName in EMP and $t[\text{DeptId}]$ must equal a DeptId in DEPT. Both values come from finite relations, so (III) is safe.(I) and (II) use $t[\text{DeptId}] \neq v[\text{DeptId}]$ (for all $v$ in (I), for some $v$ in (II)). Read strictly, an inequality does not bind $t[\text{DeptId}]$ to any database value: in (I) $t[\text{DeptId}]$ may be any value outside DEPT's DeptIds, and in (II) any value different from at least one of them. Over an unrestricted domain both of these sets are infinite, so on a literal reading (I) and (II) are unsafe and only (III) is safe, which matches none of the options.The official answer. The official GATE 2017 (Set 1) key gives (D), i.e. all three queries are safe. This corresponds to the reading the question intends: $t$ is a tuple built from an employee $u \in \text{EMP}$, so its DeptId is the employee's own DeptId (as if the condition were written with $u[\text{DeptId}]$), and the DEPT clause only filters which employees appear (those whose department matches no / some / a DEPT entry, the "NULL DeptId" note being why (I) can be non-empty). Under that reading every output value comes from EMP, the result is a subset of a finite relation, and all three queries are safe.This key is widely disputed, because the printed queries constrain $t[\text{DeptId}]$ only by inequality in (I) and (II). The official key stands, so the expected answer is (D).

• (A) and (B) each leave out one query; under the intended reading all three are safe.
• (C) excludes (I): under the intended reading (I) is safe, and on the literal reading (II) is unsafe as well, so (C) is not right either way.
• (D) matches the official key.

Answer: (D) (I), (II) and (III)