GATE IT 2006 | Question: 85

Question

Consider a database with three relation instances shown below. The primary keys for the Drivers and Cars relation are did and cid respectively and the records are stored in ascending order of these primary keys as given in the tables. No indexing is available in the database.$$\overset{\text{D: Drivers relation}}{\begin{array}{|c|l|r|c|}\hline
\textbf{did}&    \textbf{dname}&  \textbf{rating}& \textbf{age} \\\hline
22&     \text{Karthikeyan}&    7&      25  \\ \hline   
29&     \text{Salman}& 1&      33 \\     \hline
31&     \text{Boris}&  8&      55      \\\hline
32&     \text{Amoldt}& 8&      25      \\\hline
58&     \text{Schumacher}&     10&     35  \\\hline    
64&     \text{Sachin}& 7&      35     \\\hline   
71&     \text{Senna}&  10&     16       \\\hline 
74&     \text{Sachin}& 9&      35       \\\hline 
85&     \text{Rahul}&  3&      25       \\\hline 
95&     \text{Ralph}&  3&      53 \\\hline 
\end{array}} \qquad \overset{\text{R: Reserves relation}}{\begin{array}{|c|c|c|}\hline
\textbf {did} & \textbf {Cid} & \textbf {day} \\\hline
22 & 101 & 10-10-06   \\ \hline   
22 & 102 & 10-10-06\\     \hline
22 &   103 & 08-10-06    \\\hline
22 & 104   & 07-10-06     \\\hline
31 & 102 & 10-11-16  \\\hline    
31&103 &06-11-16    \\\hline   
31 & 104&12-11-16      \\\hline 
64 & 101 &05-09-06     \\\hline 
64& 102 & 08-09-06       \\\hline 
74 & 103 & 08-09-06  \\\hline 
\end{array}}$$ $$\overset{\text{C: Cars relation}}{\begin{array}{|c|c|c|c|}\hline
\textbf {Cid} & \textbf {Cname} & \textbf{colour} \\\hline
101 & \text{Renault} & \text{blue}   \\ \hline    102 & \text{Renault} & \text{red}   \\ \hline   
103 & \text{Ferrari} & \text{green}   \\\hline
104 & \text{Jaguar} & \text{red}   \\\hline
\end{array}}$$

select D.dname
from Drivers D
where D.did in  (
                        select R.did
                        from Cars C, Reserves R
                        where R.cid = C.cid and C.colour = 'red'
                        intersect
                        select R.did
                        from Cars C, Reserves R
                        where R.cid  = C.cid and C.colour = 'green'
                         )

Let $n$ be the number of comparisons performed when the above SQL query is optimally executed. If linear search is used to locate a tuple in a relation using primary key, then $n$ lies in the range:

• A. $36 - 40$
• B. $44 - 48$
• C. $60 - 64$
• D. $100 - 104$

Comments

@Bikram sir

can you please confirm execution flow?

As per my knowledge 

1 cartesian product

2 condition check.....  right?

---

https://gateoverflow.in/3641/gate-it-2006-question-85?show=387692#a387692

A diagrammatical approach of Arjun sir’s explanation

 

---

Beautiful Question, and awesome explanation!

Answer 1

I am not satisfied with any one of the answer 

Whenever we have SQL query the first thing that we seen is relation then condition and finally select part

In the above query From cars , Reserver will doo cartesian product 

NOw Rxs= 40 tuples 

Then we will check each these tuple with R.cid= C.cid and C.colour = red (40 comparision ) and it will give 5 tuples 

Now similarly we will do for other 

we will get 40 tuple R.cid= C.cid and C.colour = green (40 comparision ) and it will give 3 tuples

Now for the intersection we need to compare previous 5 tuples with next 3 tuples which will take15 comaprison and we would get 22 an 31 as intersection 

now the 22 nd 31 will be compared with 20 tuples 

I wont say exact 20 

whenevr we are using In clause 

we actually expand,, "......... where did in ( did = 22 OR did = 31) "as soon as first one match we dont need to take next comparision . But if first one doesnt match with did =22 then we need  ti check for 31  , If i take this into consideration it will give 19 comparison 

So total calculation = 40 + 40 + 15 +19 = 114 comparision 

Comments

@srestha Oh yes let arjun sir reply . and yes in your answer too then no of comparison would reduce :)

---

ok :)

---

what u r saying is true cz cartesian product must take place first bcz the execution flow in sql is first  from clause then where clause , but in the qs the line mentioned is  'Let n be the number of comparisons performed when the above SQL query is optimally executed.' 

Answer 2

A diagrammatical approach of Arjun sir’s explanation

 

Answer 3

According to wiki

There are two types of optimization. These consist of logical optimization—which generates a sequence of relational algebra to solve the query—and physical optimization—which is used to determine the means of carrying out each operation.

I think @Arjun sir did here physical optimization.

We can do the same by logical optimization. By writing sequence of relation algebra  operation then convert them to equivalent sql queries.

so here we can rewrite the query in order to optimally excute is like below:-

select D.dname
from Drivers D
where D.did in  (
                        select distinct R.did
                        from Cars C, Reserves R
                        where R.cid = C.cid and ( C.colour = 'red' or C.Colour='green' )
                 )

I think above query has same effect as above query. Means I can call it as optimized version of above query.

So here total tuple comparison is 40 for inner query .

The reason is :-

cross product of Cars and Reserves table in from Clause results into 40 tuples(Cross product is just one operation which don't need any comparison)

now search the constraint ->>R.cid = C.cid and ( C.colour = 'red' or C.Colour='green' ) in 40 tuples so atmost 40 comparison required .

and its o/p is did <22,31,64> now search this in driver relation which requires another 6 comparison.(if u comparing from top in Driver relation . note that did is primary key in Driver relation.)

so total 40+6=46 comparison  Hence Option B is Ans.

@Arjun sir, Plz Verify my approach.

Comments

@rajesh

seems right

but shouldnt it be 

( C.colour = 'red' and C.Colour='green' )
                 

---

@A_i_$_h

No , it is correct.

as we need red or green , not both together.

Answer 4

Here from "car relation" we do  C.colour = 'red' comparison ---------> 4 comparisons (getting 2 tuples from here)

then from Reservation table R.cid = C.cid we do ----------------> 2⨉10=20 comparisons (got 5 tuples)

Same done with C.colour = 'green' comparison ------------>4 comparison (getting 1 tuple)

then from Reservation table R.cid = C.cid we do ----------------> 1⨉10=10 comparisons (got 3 tuples)

Now for intersection each of 5 tuple of red compare with 3 tuple of color green =5⨉3=15 comparison (got 2 tuples)

Now, these 2 tuples compare with 10 tuples of driver 2⨉10=20

So, total 73 comparisons

Comments

@Arjun sir , @Arpit chk it