GATE CSE 2008 | Question: 15

Question

Which of the following tuple relational calculus expression(s) is/are equivalent to $\forall t \in r \left(P\left(t\right)\right)$?

1. $\neg \exists t \in r \left(P\left(t\right)\right)$
2. $\exists t \notin r \left(P\left(t\right)\right)$
3. $\neg \exists t \in r \left(\neg P\left(t\right)\right)$
4. $\exists t \notin r \left(\neg P\left(t\right)\right)$
   • A. I only
   • B. II only
   • C. III only
   • D. III and IV only

Comments

Change the category of this question from Mathematical Logic to Databases.

---

Thanks :)

---

I think it belongs to both Mathematical Logic & Databases. Keep Database tag, add Mathematical logic too !

---

relational calculus implies that..

---

I understand the meaning of the individual symbols used in this question, but I am not able to clearly interprete their meaning in the way they are used.

1. For example in tuple relational calculus we have ∀t (predicates) or we may have single predicate ∀t P(t). But I am first time seeing "belongs to ∈" symbol following quantifier. Somehow I feel it should be ∀t (r(P(t)))

2. Next we use r(t) in dbms to say tuple t belongs to relation r. But I never saw predicate used inside r(). Should it be "r(t) ^ P(t)" to make it more sensible or better to say to follow more standard usage?

So the whole expression should be ∀t (r(t) ^ P(t))

Am I correct on these? Or I am just plain wrong in understanding the usage of these symbols?

---

what is the exact meaning of third statement??

---

Let predicate $P(t)$ means "student is intelligent"

't' is some person and as for our predicate domain is 'student' so we'll talk when this person belongs to domain 'student'.

$\forall t\in r (P(t))$ will then mean "Every person who is a student is intelligent or simply every student is intelligent"

in other words we can also say it like "there exists no student ($\sim \exists t$) who is dull ($\sim P(t)$)"

---

Mathematical way

$\forall t\in r (P(t))$

$\equiv \sim \sim$( $\forall t\in r (P(t))$ )  //Use one negation to apply Demorgan law

$\equiv \sim \exists t\in r (\sim P(t))$

---

It means for all t which is belongs to r p (t) is true...so it means there exist no t which is belongs to r for which p (t) is false....so option 3 is correct...

Option 2 saying that there exist t which is not belongs to r for which p (t) is true...so this might valid may be not ,so here we cant say anything explicitly about the truthness of the statememt..so its not the correct option....similarly  option 4 and 1 is not correct  option ..

---

question says for all tuple t in r, t satisfies the condition.
It is equivalent to saying that there not exist any tuple t in r which do not satisfies the condition.

Answer 1

Only III is correct.
The given statement means for all tuples from r, P is true. III means there does not exist a tuple in r where P is not true. Both are equivalent.

IV is not correct as it as saying that there exist a tuple, not in r for which P is not true, which is not what the given expression means.

Comments

@ Cristine

please don't call me sir

I'm also an aspirant like your

you are right.

There is lot more difference.

see my comment clearly you will understand better.

In given question $(2)$ and $(4)$ query are unsafe.

see this also https://gateoverflow.in/272670/gatebook-2019-dbms1-16

---

II and IV are incorrect because they are talking about the tuples not in R.But we are bothered about the tuples in R.

I says there exists no tuple in R that satisfied P(t).-Just opposite of what is given to us.Rejected.

III says there is no single tuple in r that does not satisfy P(t).Mean all tuples in r satisfy p(t).so This is correct.

---

r(P(t)) means ? I mean what will be the english translation ?

---

@Lakshman Patel RJIT Why we haven't changed belongs to to not belongs to while applying the negation? 

And How does this expression ∃t∉r(¬P(t)) is unsafe? I mean, it says that 't is variable which doesn't belong to not of P(t)', and not of P(t) means Universe - P(t), which means we cannot have infinite tuples. Correct me, if i am wrong coz I may have interpreted the meaning of statement not accurately.

---

@ayushsomani

 

Why we haven't changed belongs to to not belongs to while applying the negation? 

And How does this expression ∃t∉r(¬P(t)) is unsafe? I mean, it says that 't is variable which doesn't belong to not of P(t)', and not of P(t) means Universe - P(t), which means we cannot have infinite tuples. 

If we write $t\notin r$ mean $t$ is not belong to $r.$ So we can have infinite $t$ here. Which might lead to the infinite tuple.

Here we are talking about tuple which belongs to relation $r.$

In predicate logic the Universe of discourse(UOD) is important.

---

@Lakshman Patel RJIT I mean we have ∀t∈r(P(t)). Now, we take negation of this ¬(∀t∈r(P(t))), we get ¬∀t∈r(¬(P(t))). This is equivalent to ∃t∈r(¬P(t)). My doubt is that, when we have applied negation, why we haven’t change ∈ to ∉? 

And, what does this mean “∀t∈r(P(t))”? 

 

---

@Lakshman Patel RJIT Sorry, I got your explanation. Ignore the Last Comment.

 Just wanted to confirm that, in the above question ¬employee(x) will also lead to unsafe expression. Correct me, if I am wrong.

---

Just wanted to confirm that, in the above question ¬employee(x) will also lead to unsafe expression. Correct me, if I am wrong.

No.

It is safe query.

---

@Lakshman Patel RJIT

Why? Doesn't ¬employee(x) mean x belongs to everything except employee (i.e. Universe - Employee)? 

---

@ayushsomani

sorry I miss that one

• A safe expression yields a finite number of tuples as its result. Otherwise, it is called unsafe.

 From this one https://gateoverflow.in/1258/gate2007-60

$\forall x(\neg employee(x))$ is unsafe expression.

https://www2.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter3/node14.html

---

@Lakshman Patel RJIT @Arjun @srestha

Is this Query unsafe coz of ¬employee(x)? I am really confused coz this links says that (https://www2.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter3/node14.html), 

---

@Arjun Sir, @srestha Ma'am

$\{x\mid \neg employee(x)\}$

(or)

$\{x\mid \neg (x\in employee)\}$

(or)

$\{x\mid x\notin employee)\}$

Here, $x$ is a tuple variable.

The entire expression means $'x'$ is a tuple which does not belong to $employee$ table.So it is not a safe expression(unsafe expression).

see this

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

An expression is safe, if all values in its result are from the domain of the expression.

$dom(t\in borrow\wedge t[amount]<1200)$ is the safe expression.

I have a problem to understand this one

$dom(t\mid\neg (t\in borrow))$ Why this is safe expression ?

---

@Lakshman Patel RJIT @ayushsomani

Is this expression for the above ques, otherwise put this question on differently

@Lakshman Patel RJIT

yes, right.

Then , where u got this expression safe?? 

---

@srestha Ma'am 

see here

---

that is separately mentioned a domain ,dom(P)

It is not general case.

---

Ma'am can you explain how $dom(t \mid\neg (t\in borrow))$ is safe?

---

Create separate question for it.

---

Okay sure

---

no, it is safe.

apply TRUE, FALSE TO THIS QUERY.

THIS EXPRESSION (~EMPLOYEE) IS FALSE IN EVERY CASE.

HENCE THE REMAINING EXPRESSION HAS TO BE TRUE, NOW IF THE EMPLOYEE IS MAN. THEN THE WHOLE EXPRESSION BECOMES TRUE AS THEY ARE JOINED BY BINARY OR OPERATION

BUT IF THE EMPLOYEE IS FEMALE THEN SHE CAN NOT BE THE SUPERVISOR

OTHER HAND, IF THE EMPLOYEE IS MALE THEN NO NEED TO CHECK OTHER CONDITIONS.

---

dont understand the belongs to r thing, never seen it in discrete logic

Answer 2

∀t∈r(P(t)):  All boys in the class are in a relationship.
 

I) ¬∃t∈r(P(t)) : There is not a single boy in the class who is in a relationship.  (X)
II) ∃t∉r(P(t)) : There is at least one boy in the class who does not belong those boys who are in a relationship. (X)
III) ¬∃t∈r(¬P(t)) : There is not a single boy in the class who is not in a relationship. (Matches the qsn)
IV) ∃t∉r(¬P(t)) : There is at least one boy in the class who does not belong to those boys who are not in a relationship. (X)

Only IV is little bit tricky. Please read again carefully.  We need "all boys" instead of "at least one" to match our original qsn.
So only option III is true.
Hence  C is the answer. 

Comments

Such a nice reference! :)

---

simple and clear

Answer 3

(IV) is incorrect as Arjun sir have explained.Above is simplification of given expression to (III).

Note that, ∀_x∈t (P(x))=∀_x (x∊t-->P(x))

                ∃_x∈t (P(x))= ∃_x (x∊t^P(x))

Comments

@jatin saini @Arjun Sir,

Are these 2 rules? 

∀x∈t (P(x))=∀x (x∊t-->P(x))

∃x∈t (P(x))= ∃x (x∊t^P(x))

Answer 4

Concept:- A statement is equivalent to its double negation.

i.e. x=~(~x)

Similarly compare below expression with above expression.

$\forall t \in r \left(P\left(t\right)\right)$ = $\neg$ ( $\exists t \in r \left(\neg P\left(t\right)\right)$ )

Hence C is Ans.

Comments

Why no negation on belongs to symbol?

Answer 5

∃t∈r(⌝ P(t))--means that there are some tuples in relation r which do not satisfy the constraint P(t)

and if we put not before this statement we get there are no tuples in relation r which do not satisfy the constraint P(t) which is equivalent to saying all tuples in relation r satify predicate condition P(t)

Comments

I think even (1) is same as yours.