GATE CS 2017 Set 1 Q41 — Tuple Calculus and SQL

A query in Tuple Relational Calculus (TRC) is said to be safe if it yields a finite number of result tuples for any database instance.

Let us analyze the three queries:

• Query I: {$t$ | $\exists$u $\in$ EMP(t[EmpName] = u[EmpName] $\wedge$ $\forall$v $\in$ DEPT(t[DeptId] $\neq$ v[DeptId]))}
• Query II: {$t$ | $\exists$u $\in$ EMP(t[EmpName] = u[EmpName] $\wedge$ $\exists$v $\in$ DEPT(t[DeptId] $\neq$ v[DeptId]))}
• Query III: {$t$ | $\exists$u $\in$ EMP(t[EmpName] = u[EmpName] $\wedge$ $\exists$v $\in$ DEPT(t[DeptId] $=$ v[DeptId]))}

In all three queries, the attribute $t[\text{EmpName}]$ is constrained by $t[\text{EmpName}] = u[\text{EmpName}]$ where $u \in \text{EMP}$. Since the relation $\text{EMP}$ is finite, the set of possible values for $t[\text{EmpName}]$ is always finite.

For $t[\text{DeptId}]$, under the standard relational database assumption, the domain of any attribute is restricted to the active domain (the finite set of all constant values appearing in the database instance). Since the active domain is finite, the possible values for $t[\text{DeptId}]$ are also restricted to a finite set.

Therefore, all three queries produce a finite number of result tuples, making them all safe.