GATE2009-45

Question

Let $R$ and $S$ be relational schemes such that $R=\{a,b,c\}$ and $S=\{c\}.$ Now consider the following queries on the database:

1. $\pi_{R-S}(r) - \pi_{R-S} \left (\pi_{R-S} (r) \times s - \pi_{R-S,S}(r)\right )$
2. $\left\{t \mid t \in \pi_{R-S} (r) \wedge \forall u \in s \left(\exists v \in r \left(u = v[S] \wedge t = v\left[R-S\right]\right )\right )\right\}$
3. $\left\{t \mid t \in \pi_{R-S} (r) \wedge \forall v \in r \left(\exists u \in s \left(u = v[S] \wedge t = v\left[R-S\right]\right )\right ) \right\}$

4. Select R.a,R.b
       From R,S
       Where R.c = S.c

Which of the above queries are equivalent?

• A. $1$ and $2$
• B. $1$ and $3$
• C. $2$ and $4$
• D. $3$ and $4$

Comments

The first one is relational algebra expression and 2nd and 3rd are relational calculus ones. Both are not difficult, but you should know their usage:

Relational Algebra: http://db.grussell.org/section011.html

Relational Calculus: http://www.cs.sfu.ca/CourseCentral/354/jpei/slides/RelationalCalculus.pdf

---

If we think πR-S(r)=π(a,b)

then how πR-S,S(r)=πR(r)??

I think πR-S,S(r)=πRUS(r). Is not it true??                     i.e. R-S means R without S ,

                                                                                                      now (R without S, S)= RUS

---

and RUS = {a,,b,c} U {c} ={a,b,c} = R . ryt?

---

@Arjun sir what is the means of πR−S(r) in question

---

@arjun sir how does projection(R-S,S)(r) becomes projection(R) (r)  ???

---

Here i am not getting this just because v is the variable which is running in only R relation but here what does it means by writing like v[R-S] and v[S] i am not getting this just because v is the variable which is running only in R table ....please explain .

---

1st one is R divide S 

refer: http://users.abo.fi/soini/divisionEnglish.pdf page number 3

---

@Arjun Thank you sir for all the links provided it is very useful in understanding the concepts. Have you put up any blog which contains standard resources and links for all concepts/subjects? 

Answer 1

1. $\pi_{R-S}(r) - \pi_{R-S} \left (\pi_{R-S} (r) \times s - \pi_{R-S,S}(r)\right )$
   $\quad= \pi_{a,b}(r) - \pi_{a,b} \left (\pi_{a,b} (r) \times s - \pi_{R}(r) \right)$
   $\quad=(r/s) $
2. Expanding logically the statement means to select $t (a,b)$ from $r$ such that for all tuples $u$ in $s,$ there is a tuple $v$ in $r,$ such that $u = v[S]$ and $t = v[R-S].$ This is just equivalent to $(r / s)$
3. Expanding logically the statement means that select $t (a,b)$ from $r$ such that for all tuples $v$ in $r,$ there is a tuple $u$ in $s,$ such that $u = v[S]$ and $t = v[R-S].$ This is equivalent to saying to select $(a,b)$ values from $r,$ where the $c$ value is in some tuple of $s.$
4. This selects $(a,b)$ from all tuples from $r$ which has an equivalent $c$ value in $s.$ 

So, $1$ and $2$ are equivalent.
$$\overset{r}{\begin{array}{|c|c|c|} \hline \textbf{a} & \textbf {b} & \textbf {c} \\\hline   \text{Arj }& \text{TY} & 12 \\\hline  \text{Arj }& \text{TY} & 14 \\\hline   \text{Cell }& \text{TR} & 13\\\hline  \text{Tom }& \text{TW} & 12\\\hline  \text{Ben }& \text{TE} & 14\\\hline \end{array}} \qquad \overset{s}{\begin{array}{|c|c|c|} \hline  \textbf {c} \\\hline  12 \\\hline 14\\\hline \end{array}}$$

1. will give $\langle Arj, TY \rangle.$
2. will give $\langle Arj, TY \rangle.$
3. will not return any tuple as the $c$ value $13,$ is not in $s.$
4. will give $\langle Arj, TY\rangle, \langle Arj, TY \rangle, \langle Tom, TW \rangle, \langle Ben, TE \rangle.$ 

http://pages.cs.wisc.edu/~dbbook/openAccess/firstEdition/slides/pdfslides/mod3l1.pdf

Correct Answer: $A$

Comments

I and II should be equivalent they both depict the division operator.If it was given that c is the foreign key in S then III  and IV will be equivalent.

Suppose if you have relation R of this form:

a	b	c
Arjun	DBMS	1
Arjun	DBMS	2
Arjun	DBMS	3
Arjun	DBMS	4
Prakash	DAA	1

and Raletion S of this form:

c
1
2
3
4

Here answer of Query II and IV will differ

---

Yes. You are right. Answer is corrected now. The 4th SQL query is not having "Distinct". So, it cannot be equivalent to a project as project operation removes duplicates.  For your example, the output of queries will be as following rt?

1. <Arjun, DBMS>
2. <Arjun, DBMS>
3. <Arjun, DBMS>, <Prakash, DAA>
4. <Arjun, DBMS>, <Arjun, DBMS>, <Arjun, DBMS>, <Arjun, DBMS>, <Prakash, DAA>

---

Yes. That would be the answer.

---

@Arjun sir...in option #2..how your relation instance is giving <Arj,TY>? ...........should it not give <Arj,TY>,<Tom,TW> and<Ben,TE>???? as bcoz when all tuples of s is matched with tuples of r...then we are getting four tuples matched...these are  <Arj,TY>,<Arj,TY>,<Tom,TW> and<Ben,TE>....pls explain..getting a bit confused in this...

---

@debanjan-sarkar In the four tuples you told, <Arj, TY> is being repeated twice. The reason is it matched with BOTH  12 and 14 values in S. And this is exactly what we want for the division operator. (As in mathematical division, we select a row only when it matches with all the rows of the divisor relation). So, only <Arj, Ty> will be out by option II. You were actually just taking the join.

---

@arjun sir v[s] and v[R-S] what does this variable point i cant able to understand plzz help as u have explained above,  Expanding logically the statement means to select t (a,b) from r such that for all tuples u in s, there is a tuple v in r, such that u = v[S] and t = v[R-S]. This is just equivalent to but tuple v in r then how can i match as u=v[s] what is scope of v?

---

Fisr of all s should be S I suppose, but this was like this in actual GATE paper. I changed it now.

Now, v[S], here v is a tuple (row) of a table. And when we apply v[S], it selects the columns corresponding to S from the tuple.

---

sir you mean the third option means that select all the tuples(R-S) of  only if they refer to some c in relation S. Thats the only case right?? or am i missing something? why u wrote it as s/r??

---

Yes, that only. And that is s/r if we consider only C attribute. I removed that part to avoid ambiguity..

---

@Arjun canyou explain what does the xpression (r/s) means?
also i am not able to understand the II and III options. Can you help me with that too?

---

That is division operator which is described in relational algebra chapter of DBMS. r/s means the selected r tuple must be matched with every tuple of s (in normal join matching is for a single tuple of s). A practical example would be to select the name of the party which has contested in all states in India where the relations can be guessed per state election and political party.

---

More About Division Operator

---

Sir How they used small r here . As the tables given are R and S and they are slecting from r.

---

In option C, for a moment forget about 'u', then it becomes

Now it says select t only if it equals to all v[R-S], which does not make much sense.

I mean putting 'distinct' in 4th SQL query does not make 3rd and 4th same. They are entirely different.
Am i right ?

If i replace $\forall v$ with $\exists v$ and i put Distinct in 4th query then 3rd and 4th will output smae result.

3. $\left\{t \mid t \in \pi_{R-S} (r) \wedge \exists v \in r \left(\exists u \in s \left(u = v[S] \wedge t = v\left[R-S\right]\right )\right ) \right\}$

4. 

Select Distinct R.a,R.b
From R,S
Where R.c = S.c

Now 3rd and 4th same ?

Anyone check it plz.

---

In 3rd query i think the result should be <Arj,TY>,<Tom,TW>,<Ben,TE>. 

As 4th and 3rd query differ by that fact that mathematical representation of sets doesn't allow duplicate values. But SQL does.

according to me 3rd query says that for every tuple v in r , there is at least a tuple u in s, such that u=v[s]. since Arj, Tom and ben has matching tuples in S, therefore they must be distinctively present in the result.

I could be wrong also in understanding this. :/ 

r

a	b	c
Arj	TY	12
Arj	TY	14
Cell	TR	13
Tom	TW	12
Ben	TE	14

---

. For the third query,if i say tuple t is in output then it means that for all v tuples of R there is at least a tuple u    in s, such that u=v[s] and V[R-S]=t, does that mean that if tuple t is in output then for all tuples [R-S] is   same as t?

---

thank u sir

---

according to me the difference between 3rd and 4th is that in 3rd query a,b values from r  relation will be printed if they contain their c value in relation s (need not be the case that all the c values in s relation will be paired with this a,b value in r relation so this c values can be even a subset of the c values in s relation .. all such a,b values which contain even a subset of c values that have atleast an entry in s relation are printed ).

in query 4 its simple even if one of the c value matches a,b values are printed but in 3 all the subset of c values should match atleast one tuple in s ... so 3 and 4 are different

---

Third expression will return all the tuples of R( after a,b projection) if c is a foreign key from R to S and

if c is not foreign key then, it will not return any tuple. Arjun Sir please verify.

---

@Arjun Sir, I'm really having a very hard time in choosing values in relations. I mean, how do you take values/tuples under R and S?

---

@Arjun sir. Why (iii) is not returning empty list in output?

Copied @Sachin comment :- Now it says select t only if it equals to all v[R-S], which does not make much sense. 

Now this condition will be always false.If there are two tuples a1,b1,c1 and a2,b2,c2

Now for a1,b1 to be in output, for all other records belonging to relations their a,b values has to be equal to a1,b1. So,a1,b1 is not inoutput.And similarly for others.Can you please check once 

---

1. π_R−S(r)−π_R−S(π_R−S(r)×s−π_R−S,S(r))  simple one division query.

2. {t∣t∈π_R−S(r)∧∀u∈s(∃v∈r(u=v[S]∧t=v[R−S]))}

Lets break it down : ∀u∈s(∃v∈r(u=v[S]∧t=v[R−S]))} says for all c (c1,c2,c3) there exist atleast 1 a.b exist. Same as division query.

3. {t∣t∈π_R−S(r)∧∀v∈r(∃u∈s(u=v[S]∧t=v[R−S]))}

∀v∈r(∃u∈s(u=v[S]∧t=v[R−S]))} says for all a,b there exist 1 c (either c1, or c2, or c3)  . means ab will from R select if some c is there which is same as relation S.

4. Below one is natural join i.e. select ab value for which atleast one c match.

Select R.a,R.b
    From R,S
    Where R.c = S.c

---

I couldn't understand how 1 & 2 are equivalent......according to me 2 & 4 seems to be equivalent.....please clarify how 1&2 are equivalent...

---

Thanks

---

Can any one will explain second option it's confusing me I am getting <arj, Ty> <Tom, TW> <Ben, TR> please explain step by step .

---

$\pi_{R-S}(r) - \pi_{R-S} \left (\pi_{R-S} (r) \times s - \pi_{R-S,S}(r)\right )$
$\quad= \pi_{a,b}(r) - \pi_{a,b} \left (\pi_{a,b} (r) \times s - \pi_{\color{\red}{a,b,c}}(r) \right)$  [See here I have written a,b,c because $R-S$ tuple returning a,b and now adding column of S, here comma operation doing union of columns]

Now, $\pi_{a,b} (r) \times s$ what it returns?

It is doing nothing but concatenation of $a,b$ column of $r$ and $c$ column of $s$

So, it is returning 

a	b	c
Arj	TY	12
Arj	TY	14
Cell	TR	12
Cell	TR	14
Tom	TW	12
Tom	TW	14
BEN	TE	12
BEN	TE	14

 

Now, we can do this part of question, which returning nothing but the rows of $r$, which is not in original table

i.e. $ \pi_{R-S} \left (\pi_{R-S} (r) \times s - \pi_{R-S,S}(r)\right )$

And finally,

$\pi_{R-S}(r) - \pi_{R-S} \left (\pi_{R-S} (r) \times s - \pi_{R-S,S}(r)\right )$

$\quad=(r/s) $

---

I think iii) will produce any output only if value of $(A,B)$ is same in all the tuples of $R$ and the value of $(C)$ is in some tuple of $S$.

---

@srestha @Arjun

there is a subtle difference between

a) $\forall x \exists y$

b)$\exists y \forall x$

b option says there is a unique y that satisfies all element in domain of x (i.e y1 for all (x1,x2,x3.....xn))

a option says for each x there is 1 y (for x1 there is y1,x2 there is y2,......xn there is y2)

for r/s we if there exist a tuple of (R-S) that appeared with all tuples of 'S' we select it in the result.

so condition would be : $\exists v \forall xu

(i)∀u∈s(∃v∈r(condition)) is what given in the 2nd option.  which is case b.

 

 

---

However in this case s/r will leave out no columns right? For s/r to produce some result s should have some column which is not present in r.