GATE CSE 2007 | Question: 60

Question

Consider the relation employee(name, sex, supervisorName) with name as the key, supervisorName gives the name of the supervisor of the employee under consideration. What does the following Tuple Relational Calculus query produce?

$\left\{e.name \mid employee(e) \wedge \left(\forall x\right)\left[\neg employee\left(x \right) \vee x.supervisorName \neq e.name \vee x.sex = ``male" \right]\right\}$

• A. Names of employees with a male supervisor.
• B. Names of employees with no immediate male subordinates.
• C. Names of employees with no immediate female subordinates.
• D. Names of employees with a female supervisor.

Comments

$\{e.name|employee(e)\wedge \forall (x)[(employee(x)\wedge x.supervisorName=e.name)\rightarrow x.sex=male]\}$

 

Print the names of those employees who are a supervisor but should not be a supervisor of a female employee 

Ans: C: Names of employees with no immediate female subordinates.

---

Detailed Video Solution: https://youtu.be/RgNpwKnGWPU 

---

we can rewrite P → Q as ¬P V Q

So we can rewrite it as  ∀x(employee(x) → (x.supervisorname≠e.name V x.sex=”male” )

Or ∀x ∈ employee(x) (x.supervisorname≠e.name V x.sex=”male”)

Or ∀x ∈ employee(x)( ¬(x.supervisorname=e.name) V x.sex=”male”)

Or ∀x ∈ employee(x)( x.supervisorname=e.name → x.sex=”male”)

So TRC query will be {e.name | employee(e)∧ ∀x∈employee(x)( x.supervisorname=e.name → x.sex=”male”) which gives those employee names for which if they are supervisor then they are the supervising only male employees. Hence Option C

Answer 1

OR ($\vee$) is commutative and associative, therefore i can rewrite given query as:

$\left\{e.name \mid employee(e) \wedge \left(\forall x\right)\left[\neg employee\left(x \right) \vee x.sex = ``male" \vee x.supervisorName \neq e.name \right]\right\}$

$\left\{e.name \mid employee(e) \wedge \left(\forall x\right)\left[\neg (employee\left(x \right) \wedge x.sex \neq ``male") \vee x.supervisorName \neq e.name \right]\right\}$

$\left\{e.name \mid employee(e) \wedge \left(\forall x\right)\left[ (employee\left(x \right) \wedge x.sex \neq ``male") \Rightarrow x.supervisorName \neq e.name \right]\right\}$

$\left\{e.name \mid employee(e) \wedge \left(\forall x\right)\left[ (employee\left(x \right) \wedge x.sex =``female") \Rightarrow x.supervisorName \neq e.name \right]\right\}$

It is clear now they are saying something about female employees, This query does not say anything about male employees. Therefore Option A and B are out of consideration.

This query retrieves those $e.name$ who satisfies this condition:

$\forall x [(employee(x)\wedge x.sex="female")\Rightarrow x.supervisorName\neq e.name]$
 
Means retrieves those e.name, who is not a supervisor of any female employees.
i.e it retrieves name of employees with no female subordinate.
(here "immediate" is obvious, as we are checking first level supervisor.)

Hence, option C.

Comments

Apply De Morgan law after AND condition. For all P(x) == There does not exist ~P(x). It will be simple after that.

---

Why we are putting () around first two terms only and not the third one in the second step?

---

@Neel123

As mentioned in the answer, $\lor$ is commutative and associative.

So, expression $A \lor B \lor C$ can be considered as either $((A \lor B)\lor C)$ (or) $(A\lor(B \lor C))$

Answer 2

{e.name∣employee(e)∧(∀x)[¬employee(x)∨x.supervisorName≠e.name∨x.sex=‘‘male"]}            ...(1)

By Using De-morgan's law

We can write expression  ∀x(P(X)) as NOT ∃x(NOT P(X)).

Using this concept, we rewrite the conditon (1) as given in question above

{e.name∣employee(e)∧ NOT(∃x)[employee(x) ^ NOT x.supervisorName≠e.name ^  NOT x.sex=‘‘male"]}            ...(2)

Considering only 2 genders are represented in the database as either male or female we can again rewrite expression (2) as

{e.name∣employee(e)∧ NOT(∃x)[employee(x) ^  x.supervisorName = e.name ^   x.sex=‘‘female"]}            ...(3)

Now it is easier to read the expression above.

It Says, for a tuple of employee, there must not be a case that this employee being considered is supervisor of some female employee. That means it selects all those employee who do not supervise any female employee hence do no have any immediate female sub-ordinate.

Hence, Ans (C)

Comments

@SomeEarth-if you have that method, please share fast, we are always in search of better methods. :)

I am not sure about whether venn diagram method will work here.

---

while i was writing the earlier comment I tried my level best to visualize the inner query and try to present u but I wasn't able to do that so I thought to share that idea with u. (but unfortunately we all are running short on time so I guess I'll do the Brainstroming on this after Gate on this q and for other question as well. (Multiple possible answer for any question makes it easier to Understand ) ((as u and other Senior member of GO community are doing))

---

@ayush sir , I didn't get the term "  x.supervisorName = e.name" can you please elaborate ?

Answer 3

Query is selecting e such that e is an employee and for all x, either x is not an employee or x's supervisor's name is not e.name or x is male.

So, this is equivalent to saying, select all employees who don't have an immediate female subordinate. (Assuming there is no transgender). (C) option.

Comments

x's supervisor's name is not e.name, can someone explain me this line.

---

wait for a day i will explain with example.

---

I think it means either e is not a supervisor of any employee and if he/she is then his subordinate is male only.

Answer 4

  Apply de morgen laws and then simplify as follows.