6.4k views

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

1. Names of employees with a male supervisor.
2. Names of employees with no immediate male subordinates.
3. Names of employees with no immediate female subordinates.
4. Names of employees with a female supervisor.
+1
0

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.
edited
0
great explanation !
+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)
0
Negation has highest priority. I doubt if we could solve like this, bcoz you introduced parenthesis and you made it like (a+b)' instead of a'+b.
+1
Thanks @Sachin such a great Explanation.
+1
easiest and clearest sol. thanks!!
0
great sachin sir salute u sir
0
All employees, if they are a boss, they should not be a boss of a female employee.
0

we can do the operation with this also

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

this query will also produces the same result no problem with that therefor no need to associate the operation here.

0
Apply De Morgan law after AND condition. For all P(x) == There does not exist ~P(x). It will be simple after that.
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.
+3
thanks Arjun, nice way of explaining :)
+3

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

there it says->

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

1. 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???
0
Yes. That is true.
0
sir,

I am not getting what does immediate subordinate means .

Plz tell
0

@arjun Sir how did you conclude answer from

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.

+1
Well, that is difficult to explain. Guess, I tried to find such an "x" :)
+1
staff lower in rank or position is called subordinate
+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

+3
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..
+2
most politically correct answer i've seen in this website
+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.
0
x's supervisor's name is not e.name, can someone explain me this line.
0
wait for a day i will explain with example.

{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. :)
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"

+4

@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

0

@ Ayush Upadhyaya Yes, thank you, brother.

0

@Ayush Upadhyaya thank you sir it helps me to understand this question

0

can we use Venn diagram Approach in order to understand query so that we need not to transform the query into simpler form (Although that method is far superior ) OR will that will be too complex (considering the time constraint of exm) .

0

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

0
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))

Apply de morgen laws and then simplify as follows.

Have a look on it if u didn't understand

+1 vote
here we need to use quantifiers inter conversiom,

i.e. 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)

1
2