GATE CS 2007 Q60 — Tuple Calculus and SQL

To understand what the Tuple Relational Calculus (TRC) query produces, let us analyze the logical expression inside the universal quantifier ($orall x$):

$$\neg employee(x) \vee x.supervisorName \neq e.name \vee x.sex = \text{"male"}$$

Using the logical equivalence $\neg A \vee \neg B \vee C \equiv (A \wedge B) \implies C$, we can rewrite the expression as:

$$(employee(x) \wedge x.supervisorName = e.name) \implies x.sex = \text{"male"}$$

Now, substituting this back into the original query, we get:

$$\{e.name \mid employee(e) \wedge (\forall x) [ (employee(x) \wedge x.supervisorName = e.name) \implies x.sex = \text{"male"} ]\}$$

Let's break down the meaning of this rewritten query:

• $employee(e)$: We are selecting an employee $e$.
• $employee(x) \wedge x.supervisorName = e.name$: This represents any employee $x$ who is an immediate subordinate of $e$ (since $e$ is their supervisor).
• $(\forall x) [\dots \implies x.sex = \text{"male"}]$: For all such employees $x$, if $x$ is an immediate subordinate of $e$, then $x$ must be male.

If all immediate subordinates of $e$ must be male, it logically means that employee $e$ has no immediate female subordinates (vacuously true if $e$ has no subordinates at all).

Therefore, the query retrieves the names of employees with no immediate female subordinates.