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\}$

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

Am not able to understand this question..can someone please explain me in detail about how the queries are solved? I cannot understand the following logic.can someone help me please

 

πa,b(πa,b(r)×s−πR(r))

= (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 (s/r), which will be true only if c in r is a foreign key referring to c in 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

---

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

= $\pi_{a,b}(r) - \pi_{a,b} \left (\pi_{a,b} (r) \times s - \pi_{R}(r) \right)$
= $(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.

r

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

s

c
$12$
$14$

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

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

Comments

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