The Gateway to Computer Science Excellence

+30 votes

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

- $\neg \exists t \in r \left(P\left(t\right)\right)$
- $\exists t \notin r \left(P\left(t\right)\right)$
- $\neg \exists t \in r \left(\neg P\left(t\right)\right)$
- $\exists t \notin r \left(\neg P\left(t\right)\right)$
- I only
- II only
- III only
- III and IV only

0

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

+2

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?

+5

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

0

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

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

+37 votes

Best answer

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.

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.

0

@ 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

+4

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.

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.

0

@Lakshman Patel RJIT Why we haven't changed * belongs to* to

And How does this expression * ∃t∉r(¬P(t)) *is unsafe? I mean, it says that '

0

Why we haven't changed

tobelongs towhile applying thenot belongs to?negationAnd How does this expression

is unsafe? I mean, it says that '∃t∉r(¬P(t))t is variable which doesn't belong to', andnotof P(t)meansnot of P(t)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.

0

@Lakshman Patel RJIT I mean we have * ∀t∈r(P(t)). *Now, we take

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

0

@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

0

Just wanted to confirm that, in the above question

will also lead to¬employee(x)expression. Correct me, if I am wrong.unsafe

No.

It is safe query.

0

0

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

0

@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),

0

$\{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).

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 ?

0

@Lakshman Patel RJIT @ayushsomani

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

yes, right.

Then , where u got this expression safe??

0

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.

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.

+28 votes

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

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

+14 votes

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

+12 votes

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.

–1 vote

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

52,345 questions

60,510 answers

201,930 comments

95,354 users