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

@sachin!

If you have got the solution please post it ..i am alo having same doubt 

---

So the fact that DeptId can be null has nothing to do with safety of expressions isn't it? It's just been given to confuse.

---

Previous year question from 2001 seems to have a similar format. Options A and D from the previous question were deemed safe, rephrased are similar to options 2 and 3 in the current question. we can only conclude these options to be “safe“ if it is implicitly implied that t is within the range of EMP otherwise they cannot be safe. They both are similarly framed, I guess they both came from some textbook. 

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

very good point. U mean it can be proved by mathemetical logic,rt?

---

@2018 @srestha Doesn't this mean that we are considering the relations to have infinite no. of tuples? If yes, is it right to assume so?

---

very nice explanation @ 2018 ,,,this solution should be best answer

---

true for finite no of tupes ∧ true for infinte no of tuples, over all true for finite tuple.

@2018

I didn't get this ...

For Query 1

We can have (FINITE number of tuples t that making part 1 true) AND (INFINITE number of tuples t making part 2 true+Part1 true as well)

eg , All tuples in OUTPUT as same name as any one of employee and any dept_id other than that is in DEPT table

---

listen this video

---

But in Our question

t | ∃u ∈ EMP ( t[EmpName] = u[EmpName] ∧ ∀v ∈ DEPT (t[DeptId] ≠ v[DeptId]))}

For first part to be True tuple should be from R1 with same empName

and for second part tuple can come from both outside R1 and R2

MY DOUBT IS :

In first part condition is on only empName for tuple u, So our tuple 't' can differ in other attributes right ??

that is

Output('t'): empName deptid -  {(raju,dept_id)}

EMP table('u') : - {(e1,raju 32),(e2,ramesh 43)}

So here for 't' there is u such that t[name] = u[name] , dept_id can be different right ?==> u->(e1,raju 32)

Now for that same tuple 't' we can put value of dept_id such that it doesnt matches with valid dept no

t = {(raju,200)(raju,300)(raju,400)(raju,500)....}  Let valid dept_no in DEPT table are{10,12,15,16}

Where I am going wrong

---

@Shaik

Thanks a lot for sharing ,

Is the first operation is like SET DIFFERENCE operation,

that it belong to the 1st table and at the same time it does not belong to the 2 nd table

---

@Learner_jai

can you please check the above comment

---

suppose instead of ^ , there would have 'OR' then it will not be a safe query?

---

@jatin

To prove a query to be safe, we have to make sure that to get the result we should iterate on given tables ONLY. The example which you have given is also fine. Where it is iterating on tables other than EMP, DEPT ?

---

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.

Answer 2

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 3

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

if NULL values were not permitted in DeptId in Emp then first query would be unsafe right? as it will return infinite #tuples?

---

belong to some department? or same department?plz clarify.

---

jayanth

it should be some.

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