GATE CS 2017 Set 1 Q.41 (CS Q.41): Relational Algebra and Tuple Relational Calculus

Consider a database that has the relation schemas EMP(EmpId, EmpName, DeptId), and DEPT(DeptName, DeptId). Note that the DeptId can be permitted to be NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus.

(I) $\{t \mid \exists u \in \text{EMP}(t[\text{EmpName}] = u[\text{EmpName}] \land \forall v \in \text{DEPT}(t[\text{DeptId}] \ne v[\text{DeptId}]))\}$
(II) $\{t \mid \exists u \in \text{EMP}(t[\text{EmpName}] = u[\text{EmpName}] \land \exists v \in \text{DEPT}(t[\text{DeptId}] \ne v[\text{DeptId}]))\}$
(III) $\{t \mid \exists u \in \text{EMP}(t[\text{EmpName}] = u[\text{EmpName}] \land \exists v \in \text{DEPT}(t[\text{DeptId}] = v[\text{DeptId}]))\}$

Which of the above queries are safe?

(I) and (II) only

(I) and (III) only

(II) and (III) only

(I), (II) and (III)

Official answer and solution

Official answer: D
From: Official GATE 2017 answer key

Note on this question

Read strictly, t[DeptId] in queries (I) and (II) is not tied to any relation, which would make them unsafe; the official answer key (D) treats the result tuple t as drawn from the employee tuples u, so every query returns a subset of EMP and is safe.

Solution

A TRC query is safe if it can only return a finite set of tuples whose values come from the database. Here every result tuple is built from an employee tuple of EMP, so each query returns a subset of a finite relation.

A tuple relational calculus query is safe if it is guaranteed to return a finite number of tuples whose attribute values all come from the database (the relations or constants in the query). An unsafe query could return infinitely many tuples.

In all three queries the result tuple $t$ is tied to an employee: $\exists u \in \text{EMP}\,(t[\text{EmpName}] = u[\text{EmpName}] \land \dots)$ . As intended by the question (and by the official key), $t$ describes the employee $u$ , so $t[\text{DeptId}]$ is that employee's DeptId (possibly NULL). Every answer is therefore a subset of the tuples of EMP, which is finite.

Query (I): $\forall v \in \text{DEPT}\,(t[\text{DeptId}] \ne v[\text{DeptId}])$ selects employees whose DeptId matches no department, for example employees with a NULL DeptId. The result is a subset of EMP: safe.
Query (II): $\exists v \in \text{DEPT}\,(t[\text{DeptId}] \ne v[\text{DeptId}])$ selects employees whose DeptId differs from at least one department's DeptId. Still a subset of EMP: safe.
Query (III): $\exists v \in \text{DEPT}\,(t[\text{DeptId}] = v[\text{DeptId}])$ selects employees who belong to an existing department. A subset of EMP: safe.

All three queries are safe, so the answer is (D).

Final answer

Common trap

Treating $t[\text{DeptId}]$ as a free value from an infinite domain. With that strict reading the inequality conditions in (I) and (II) would look unsafe, but the result tuples are employee tuples, so every result is finite.

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

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 1
Question: 41 of 65, printed as CS Q.41
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