GATE CSE 2017 | Set 1 | Question: 41

Question

Consider a database that has the relation schemas EMP(EmpId, EmpName, DeptId), and DEPT(DeptName, DeptId). Note that the DeptId can be permitted to be NULL in the relation EMP. Consider the following queries on the database expressed in tuple relational calculus.

1. {$t$ | $\exists$u $\in$ EMP(t[EmpName] = u[EmpName] $\wedge$ $\forall$v $\in$ DEPT(t[DeptId] $\neq$ v[DeptId]))}
2. {$t$ | $\exists$u $\in$ EMP(t[EmpName] = u[EmpName] $\wedge$ $\exists$v $\in$ DEPT(t[DeptId] $\neq$ v[DeptId]))}
3. {$t$ | $\exists$u $\in$ EMP(t[EmpName] = u[EmpName] $\wedge$ $\exists$v $\in$ DEPT(t[DeptId] $=$ v[DeptId]))}

Which of the above queries are safe?

• A. I and II only
• B. I and III only
• C. II and III only
• D. I, II and III

Comments

It is given our Deptid can be NULL ,

A) return such persons (EmpName ,deptid) such that there exist some employ(atleast one )  which does not belong to any deptid .

it is safe and it returns finite tuples as deptid can be null for some employ.

if this assumption would not have given in this question , it may have been unsafe.

B)  return such persons (EmpName ,deptid) such that   There exist some employ which does not belong to atleast one deptid.

yes it is safe . as it returns finite tuples .

C)  return Such persons (EmpName ,deptid) such that there exist at least obe employ and it belongs to at least one department.

yes safe ..

---

@Sun Wukong

Can you please elaborate what do you mean by

"it is safe and it returns finite tuples as deptid can be null for some employ. if this assumption would not have given in this question , it may have been unsafe."

I think, even if this condition is not given, the query should be safe, as t can take rows only from EMP, and it is finite

---

In the question all variables are restricted to domains only , Supoose in the question $\{t \mid \neg(t \in \text{EMP})\}$ they gave like this , now the domain changes to infinity , In this case we need to check the things carefully .

Answer 1

Answer is (D)

before $\wedge$ operation all three expressions are the same,

i.e.return true if for each tuple $t$ we have finite no of tuple $u$ in employee table for which they have same employee_name.

(I)  but in $2^{\text{nd}}$ part, for each tuple $v$ in department there may exist infinite no of tuple $t$ for which they may not be equal.

i.e. true for finite no of tuples $\wedge$ true for infinite no of tuples, over all true for finite tuple.

(II) there may exist infinite no of tuple for which at least one tuple $v$ belongs to department table for which they may not be equal.

i.e. true for finite no of tuples $\wedge$ true for infinite no of tuples, over all true for finite tuple.

(III) this one actually true for finite no of tuples, as there may exist only finite tuple which may be equal to at least one tuple $v$ in

department. because department table contain finite no of tuple all tuple $t$ which are same may not be more than all tuple $v$ in

department table in case of equality operation.

      i.e. true for finite $\wedge$ true for finite tuple, over all true for finite tuple.

So all TRC query will return finite tuple which implies all are safe.

References:

• http://www.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter3/node14.html
• http://people.cs.pitt.edu/~chang/156/10calculus.html
• http://www.cs.princeton.edu/courses/archive/fall13/cos597D/notes/relational_calc.pdf

Comments

Note that t is answer tuple and t is going to have two attributes viz EmpnName and DeptId.

"t[EmpName] = u[EmpName]" doesnt mean we are comparing t[empname] and u[empname] but rather we are assigning u[empname] to t[empname]. Therefore i think that the second subexpression " ∀v ∈ DEPT(t[DeptId] ≠ v[DeptId]))" will not yield infinite number of tuples but rather it says that for an employee Jones(say), the answer tuple t will have EmpName=Jones and DeptId=NOT the deptId of the Department in which Jones is working. I only have confusion that will be the the value assigned to asnwer tuple t's DeptId field because question is telling what NOT to assign but it doesnt tell what  to assign.

---

Hey i have a small doubt on how finite^ infinite is becoming finite.

condier that EMP has empnames = e1,e2,e3,e4,e5. and DEPT has DIDs (d1,d2,d3).

the trc variable t can take up values (e1,x1);(e1,x2);(e1,x3)....(e1,xn) right?? since here t[empname] = u[empname= i.e (e1) and t[dif] != v[Dif] (as x1!=d1/d2/d3) and so on. is satosfied which is the predicate in the given TRC expression?

so shouldnt t have infite values for i and ii??????

---

here the deptid in the  employee table is knwon to eb refeered from the department table so according o the x1 x2 x3 x4..so on xn willl contain the values from deptid only  and at some point they will be equal

Answer 2

safe is one that is guaranteed to yield a finite number of tuples as its results. Otherwise, it is called unsafe

as question given

I. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∀ v ∈ DEPT (t[DeptId] ≠ DeptId]))} : Gives empnames who donot belong to any department

II. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] ≠ DeptId]))} :  empnames who donot belong to some department

III. {t | ∃ u ∈ EMP (t[EMPName] = u[EmpName] ∧ ∃ v ∈ DEPT (t[DeptId] = DeptId]))}:  empnames who  belong to same department

Comments

jayanth

it should be some.

---

nope it wont return infinite tuples because then in that case it will be definetley having some depart id from the depertment table so which will make false for all hence it will return false always

---

i think for 3rd output  empnames who  belong to some department

Answer 3

Answer should be D) as all the bounded variables are tied with one specific Emp and Dept table and does not range over the universe.

Comments

what do we mean by "does not range over the universe"?

---

@Regina Phalange That is, the result or output of query on these two given relations will always be from the given relations and don't go out of the scope of these two relations (finite number of tuples in output always) i.e  never be from U set.

U set contains all the relations of the world. Something like Emp and Dept relations of all the companies present in whole world (infinite tuples in output) leads to unsafe expression/query!

Answer 4

3rd is the employees who are in a department which consists of atleast one employee (that can be they themsleves also)

2nd is the employees for which there exists a department other than their own which means unless in the case of all the employees belonging to the same department are present in the database this will return all the tuples because for every tuple there exists atleast one other tuple which belongs to the other department

1st returns employees whos foriegn key(dept id) is NULL in the EMP table as they may not be assigned to any other department yet

in all the above queries the tuples are coming from the domain which is EMP*DEPT so these are safe queries :)

Comments

@Venkat

My understanding resonates with your explanation completely

 

@abhishek tiwari

 

for 3rd trc , can you please explain how you got to the conclusion 'empnames who do not belong to same dept'

from my understanding it will just list the employees which have a non null value in their deptid field in employee table

Answer 5

All the above explanations are simply amazing but I want to add one point . One of the simplest way to check whether query is safe or not , one should check whether “free variable” (variable not bounded by quantifiers) is complemented in query or not , if not then it is definitely safe . Hence ans here seems to be D)

Comments

@mohnish  bro can u  elaborate more how?

---

Is there any edge cases or exception for your statement ?

Answer 6

To solve this question you need 2 things to understand
1.what is safe query?
->query which is not returning infinite number of tupples
eg of unsafe query so that you can understand it better
->{t | t doesn't belong to EMP}
   here return tuples which doesn't belong to EMP which can be infinite
2.how to read calculas query?
->{t | .......} means t such that where t is tuple

now i think anyone can solve this question

but still for easness given 3 queries are like first half telling that tuple of EMP table and 2nd half like DepId and there variation