GATE CSE 2001 | Question: 2.24

Question

Which of the following relational calculus expression is not safe?

• A. $\left\{t \mid \exists u \in R_1\left(t[A] = u[A]\right) \land \neg \exists s \in R_2 \left(t[A] = s[A]\right)\right\}$
• B. $\left\{ t \mid \forall u \in R_1\left(u[A]="x" \Rightarrow \exists s \in R_2\left(t[A] = s[A] \land s[A] = u[A]\right)\right) \right\} $
• C. $\left\{t \mid \neg (t \in R_1)\right\} $
• D. $\left\{t \mid \exists u \in R_1\left(t[A]=u[A]\right) \land \exists s \in R_2 \left(t[A] = s[A]\right)\right\}$

Comments

Does not help at all !!!

---

Any expression whose result uses “constants / values”that do not appear in the instances of any of the database relations.     

or in Simple words

the expression which results in finite no of output is considered as Safe expression and which expression can give infinite output is unsafe.

---

                                                            R1

\[
\begin{array}{|c|c|}
\hline
\textbf{StudentID} & \textbf{Name} \\
\hline
101 & Alice \\
102 & Bob \\
103 & Charlie \\
\hline
\end{array}
\]

 

• t is a tuple (a row). For example, one possible t from R1 is the row (101, 'Alice').

 

• t ∈ R1 means "t is a row that exists in the table R1".

 

• t[A] means "the value of attribute A (the StudentID column) for the tuple t".
  • If t is the row (101, 'Alice'), then t[A] is 101.
  • If t is the row (103, 'Charlie'), then t[A] is 103.

Answer 1

Answer: C.

It returns tuples not belonging to R1 (which is infinitely many). So, it is not safe.

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

Comments

`JEET

"A" also has ¬s. It shouldn't be safe as well.

I mean that too contains too many tuples.

I think as it contains “There exists”  so even just one out of domain tuple will work. 

and hence option C is more stronger.

---

Option A is just a way to Write (R1-R2)

---

Shouldn't option B also be right? 
Consider an instance where no tuple of R1​ has u[A]="x". The implication is then vacuously true for every u∈R1​, making the whole formula true for every t. Therefore the result is the entire infinite domain. By that standard, B should also be included in the key.

Answer 2

Answer should be $B,C.$

TRC Queries in both Option B, C are Unsafe Queries. 

Definition of “Unsafe TRC Expression”: Any expression whose result uses “constants / values” that do not appear in the instances of any of the database relations.  

Option B:

NOTE that “$x$” is some constant value, in the domain of variable $A.$

Case 1:

If the instance of $R_1$ has at least one tuple where $R_1.A = $ ”$x$” & the instance of $R_2$ also has at least one tuple where $R_2.A = $ ”$x$” then the result of the TRC query will be a table with single column named $A$ and only one row with value “$x$”.

Case 2:

If the instance of $R_1$ has at least one tuple where $R_1.A = $ ”$x$” BUT the instance of $R_2$ also has NO tuple where $R_2.A = $ ”$x$” then the result of the TRC query will be an Empty table with single column named $A$ i.e. Output is Empty.

Case 3:

If the instance of $R_1$ has NO tuple where $R_1.A = $ ”$x$” then every value in the domain of attribute $A$ will satisfy the condition given in the TRC query & hence, will appear in the output. Hence, in this case, we get an infinite number of tuples in the output.

Hence, Query in Option B is Unsafe. 

Comments

See this model is thoeritical so we can predict that their would be infinte tuples although in practice this aint true.

---

@Deepak Poonia sir @GO Classes Support, in case 3 you assumed that domain of A is infinite, can we do that every time for queries like these

also can't we say that as no. of output tuples is variable ( irrespective of R1 and R2) ,this is a unsafe query 

@Ajay Sreenivas i would be grateful if you can give some clarification

---

An expression is safe if every value in the result comes from DOM(P), the constants written in the formula plus the values in the relations it names. Equivalently: the result depends on the data alone, not on what the domain happens to be.

Option B - Let dom(A) = {1, 2, 9}, R1 = {1}, R2 = {1}, and the constant x = 9. No tuple of R1 has A = 9, so the antecedent is false for every u, the implication holds vacuously, and every t satisfies the formula. The result is {1, 2, 9}.
But DOM(P) =  {1} ∪ {1} ∪ {9} = {1, 9}.
But 2 is in the output without appearing in the formula or in either relation. Enlarge the domain to {1, 2, 9, 10} and the result grows to {1, 2, 9, 10} with the database untouched.

Or just look at C with the same finite domain. Take dom(A) = {1, 2} and R1 = {1}; then {t | ¬(t ∈ R1)} returns {2}, which is finite. If finiteness were the test, C would be safe.  Domain independence is the actual criterion, and B fails it.

Answer 3

{t∣¬(t∈R1)}

If we run this query the tuples we get does not belong to the instances of relation R1, so according to definition this expression is unsafe.

ANSWER: C

 

Answer 4

Well it’s obvious that the answer is (C).

But can anyone verify my analysis of other Options?

Option (A) : Prints values which are in column A of R1,but not in Column A of R2.

Option (B) : It will print ‘x’ every time it is in column A of R1 and in atleast one time in column A of R2. Oh wait ,bcoz it is a Set ,’x’ will be printed only once!

Option (D) : Prints values if which are in column A
of both relations R1 & R2

Comments

Option B is an implication. If the implicant is false then the over implication is always true so infinite tuples could be there.

Answer 5

The relations that result in infinite number of tuples are considered to be unsafe operations. And so safe operations give us finite number of tuples. But here option (C) gives us infinite number of tuples as it results in tuples which are not belonging to R and since they are infinite.

Answer 6

Imagine we have two tables: R1(A,B,C) and R2(A,M,N) where "u" and "s" denote tuples from each relation respectively. 

The output tuple "t" should satisfy the following condition:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(a) SAFE

t[A]=u[A] AND NOT(t[A]=s[A])

This means: the attribute will be present in the output tuple "t" if it is the attribute A from R1​, and that same value of A should not appear in R2​.

From this analysis, there is no possibility of the relation generating an infinite output.
Thus, option (a) is safe and the correct answer

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(b) SAFE

In predicate logic, "for all" (∀) is usually followed by implication (⇒), keeping things simple.

If all u[A] in R1​ are "x", then " t " will have that value from R2
If not, the result is empty.

This clearly means the output won’t be infinite, so the query is safe.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(c) UNSAFE

Assume R is a finite set. Then NOT R means we're considering everything not in R, which has no defined boundary. It could include an infinite number of unknown values.

So, as simple as that , the result can be infinite, making it unsafe.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(d) SAFE

Here, the output will include only those values of A that are common to both R1(A)and R2(A).
Basically, it’s like saying, “Give me what’s in both friend circles.”