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

Safety is asking:

Can the result be guaranteed to be finite?

you shouldn't get distracted by the ∀ versus ∃ when determining safety.

When checking a TRC query for safety:

1. Find the free variables.
2. Ask whether their possible values/tuples are restricted
   to finite database relations.
3. Check whether negation/complement can make them range
   over the unrestricted universe.

For all three:

Query	Free	Bound
I	t	u, v
II	t	u, v
III	t	u, v

(D) — all three are safe.

The important question is:

Can the query produce infinitely many possible output tuples from the unrestricted universe?

Here, t is constrained through:

∃u ∈ EMP
(
    t[EmpName] = u[EmpName]
    ∧ ...
)

Since u must come from the finite relation EMP, the EmpName of the output t must correspond to an existing EMP tuple.

That bounds the possible results.

The v variables are also explicitly restricted:

v ∈ DEPT

so they range only over the finite DEPT relation rather than over the entire universe.

Hence all three are safe. 

Answer 2

Answer: D. I, II and III

A TRC query is safe if, for every finite database, its result is also finite.

Query I:
∃u ∈ EMP restricts t[EmpName] to values from the finite EMP relation. Hence, the result is finite. So I is SAFE.

Query II:
Both u and v are taken from the finite relations EMP and DEPT. Therefore, the result is finite. So II is SAFE.

Query III:
t[EmpName] comes from finite EMP and t[DeptId] must match a value from finite DEPT. Hence, the result is finite. So III is SAFE.

Therefore, all three queries are safe.

Correct Answer: D. I, II and III