The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+38 votes

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\}$

- Names of employees with a male supervisor.
- Names of employees with no immediate male subordinates.
- Names of employees with no immediate female subordinates.
- Names of employees with a female supervisor.

+77 votes

Best answer

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.

$\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.

+1

if we use the for all conversion to ' not there exist' and thus in process invert all boolean varables within braces then we get the desired result as option (c)

+28 votes

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.

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

+3

i think (not)(employee(x)) doesnt mean those tuples which are not employee

Read this->http://en.wikipedia.org/wiki/Tuple_relational_calculus

there it says->

- if
*f*is in*F*[*S*,*type*] then the formula " ¬*f*" is also in*F*[*S*,*type*]

means (not)(employee(x)) --> employee(x) will be true for all tuples(i.e x) of employee

so (not)(employee(x)) will give false for every tuple of employee

(SO in all the answer given has the same meaning)

but here is the difference..

x in (not)(employee(x)) will never get a tuple outside of emloyee table hence it simply means "

"DON'T INCLUDE ANY EMPLOYEE" which is equivalent to " x is not an employee" only in english Not in database

because "x is not an employee" will check for every tuple in database

an UNSAFE QUERY (which actually isn't happening)

but anyways the answer would be same

0

:O Actually the wiki line

- if
*f*is in*F*[*S*,*type*] then the formula " ¬*f*" is also in*F*[*S*,*type*]

just means if t is a formula, then ¬t is also a formula.

For these topics I find wikipedia quite confusing to follow. Google is much better.

http://www.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter3/node11.html

+3

http://people.cs.pitt.edu/~chang/156/10calculus.html

under safe queries

so we can say above query is unsafe and it actually is checking every tuple of database???

under safe queries

so we can say above query is unsafe and it actually is checking every tuple of database???

0

@arjun Sir how did you conclude answer from

Query is selecting e such that

eis 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.

+1

Sir I m not reaching the answer from this line "**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.** " plzz elaborate

+2

can we replace above query

into p ->q

{e.name∣employee(e)∧

(∀x)[[employee(x) and x.supervisorName=e.name ] ->x.sex=‘‘male"] }

now it is simple to analyse..

into p ->q

{e.name∣employee(e)∧

(∀x)[[employee(x) and x.supervisorName=e.name ] ->x.sex=‘‘male"] }

now it is simple to analyse..

+5

@kvkumar Loyal

Nice explanation.

In words :

If e is an employee in an organization then below test conditions should be true for this employee (e) to be displayed :

We will consider all the members in the organization one by one (say x) and the below condition should be true for all of them:

If x is an employee in the same organization as e and

e is the supervisor of this x

then

x should be male

If the above loop fails for even one employee then e won't be selected for display.

In short, it means that all the employee (e) are selected for display which have only male employee (and hence no female employees) working under them.

Nice explanation.

In words :

If e is an employee in an organization then below test conditions should be true for this employee (e) to be displayed :

We will consider all the members in the organization one by one (say x) and the below condition should be true for all of them:

If x is an employee in the same organization as e and

e is the supervisor of this x

then

x should be male

If the above loop fails for even one employee then e won't be selected for display.

In short, it means that all the employee (e) are selected for display which have only male employee (and hence no female employees) working under them.

+9 votes

{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)**

0

*@Ayush Upadhyaya Can you please explain these one by one in simple English - *

*employee(x)*

*x.supervisorName = e.name*

*x.sex=‘‘female"*

0

I am not able to get your statement s Iarnav.

Could you tell me where are you facing problem in understanding the solution above?

It's just a simple application of de-morgan's law for quantifiers that I have Used.

Still if you have any trouble, let me know. Happy to help. :)

Could you tell me where are you facing problem in understanding the solution above?

It's just a simple application of de-morgan's law for quantifiers that I have Used.

Still if you have any trouble, let me know. Happy to help. :)

0

@ Ayush Upadhyaya In eq 3, **what does the below line means? Can you tell it in Hindi?**

**I mean, does it mean - Koi bhi Supervisor aur employee ka naam same nai hai and jo supervisor hai woh female nai hai kyunki bracket ke bahar NOT likha hai?**

**x.supervisorName = e.name ^ x.sex=‘‘female"**

+2

@Iarnav-

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

**(∃x)[employee(x) ^ x.supervisorName = e.name ^ x.sex=‘‘female"]**

The highlighted text means tumne ek randomly employee table se tuple select kra

aur check kra ki uska supervisor ka naam is same as the tuple 'e'( ie. e.name) jo consider kra h and yeh jo tuple x hai wo female employee ka hona chahiye.

Means, you select an employee jo kisi female employee ka boss hai.

matlab female employee isko report krti h

Now notice that there is a not symbol also in eq 3.

This implies that wo saare employee de do jo kisi bhi female employee k boss na ho

means koi b female employee inhe report nahi karti.

This is good trick in logic to write expression for "none" kind of statements.

Example : Consider x to be domain of all people in world and B(X) be the predicate that x is best in this world.

Now you write "Someone is best in this world" as ∃x(B(X)).

Now, this ∃x becomes false when there is not even a single value of x which satisfies a predicate.

matlab x ko manlo can take domain values as x1,x2,x3

then ∃x(B(X)) = (B(x1) v B(x2) v B(x3) )

koi b x1,x2,x3 k liye agar B(X) true hua toh ∃x(B(X)) true hoga.

agar kisi k liye nahi hua toh ∃x(B(X)) is false.

So when you place not in it,

∼ ∃x(B(X)) = ∀x(∼B(x1) ^ ∼B(x2) ^ ∼B(x3) )

and this becomes "**No one is best in this world**"

I hope kch smajh aya hoga

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.6k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.3k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 480
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,748 questions

47,471 answers

145,585 comments

62,234 users