edited by
22,206 views
74 votes
74 votes

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:

  1. $36 - 40$
  2. $44 - 48$
  3. $60 - 64$
  4. $100 - 104$
edited by

10 Answers

Best answer
89 votes
89 votes
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'
                         )
select R.did from Cars C, Reserves R where R.cid = C.cid and C.colour = 'red'

So, first, get $2$ red cars by scanning $4$ tuples of the cars relation. Now, for each of the two 'red' cars, we scan all the $10$ tuples of the 'Reserves' relation and thus we get $2\times 10 + 4 = 24$ comparisons. But this is not optimal. We can check in the reverse order for each tuple of the 'Reserves' relation because 'cid' is a primary key (hence unique) of 'Cars' relation.

Supposing our earlier selection is $\langle 102, 104 \rangle$ then this requires $3 + 7\times 2 = 17$ comparisons. due to if $( \text{R.cid} ==102 || \text{R.cid} == 104 )$

If the order was $\langle104, 102 \rangle$, then $2 + 8\times 2 = 18 $ comparisons. due to if $(\text{R.cid} ==104 || \text{R.cid} == 102 )$

Thus, totally $21$ to $22$ comparisons and gives $\langle 22, 31, 64\rangle$ as did.

Similarly for the 'green' car we get $4+10 = 14$ comparisons. due to if $( \text{R.cid} ==103 )$ and gives $\langle 22, 31, 74\rangle$ as did.

Intersect requires $1+2+3 = 6$ comparisons in the best case and $3 + 2 + 3 = 8$ in the worst case and this gives $\langle 22, 31 \rangle$.

Finally, we have to locate the did $22$ and did $31$ from the driver table and did is the primary key. As told in the question, we use linear search and for $22$, we hit on the first try, and for $31$ we hit on the third try. So, $1 + 3 = 4$ comparisons.

Thus total no. of comparisons $= ( 21\; \text{to} \;22 ) + 14 + ( 6\; \text{to} \;8 ) + 4 = 45\; \text{to} \;48.$

Correct Answer: B.

edited by
42 votes
42 votes

4 for finding red cars with 20 for Did & 4 for finding green cars with 10 for Did

red Did :22 31 64

green Did : 22 31 74

6 for intersection

1 for searching 22 in driver relation

& 3 for 31

total 38+6+4=48

therefore B is the answer


 

19 votes
19 votes

from the first inner query:

select R.did from Cars C, Reserves R
where R.cid = C.cid and C.colour = ‘red’

C.color = “Red”, comparisons=4 (Cars has four rows)

R.cid=C.cid so there are five rows extracted to this where condition.
comparisons=(2 red cars * 10 Reserves rows)=20

from the second inner query:
select R.did from Cars C, Reserves R
where R.cid = C.cid and C.colour = ‘green’

C.color = “Green”, comparisons=4 (Cars has four rows)

R.cid=C.cid so there are three rows extracted to this where condition.
comparisons=(1 green car*10 Reserves rows)=10

R.did = {22, 22, 31,31, 64} for first inner query
R.did = {22, 31, 74} for second inner query

Here unique sets are, R.did={22,31,64} and R.did={22,31,74} respectively for first and second inner queries.
so for intersection, 6 comparisons (for 22, we hit on the first try and for 31,we hit on the second try,and for 74,we hit on all three try, so comaprisons=1+2+3)
Finally we have to locate the did – 22 and did 31 from the driver table and did is the primary key. As told in the question, we use linear search and for 22,
we hit on the first try and for 31 we hit on the third try. So, 1 + 3 = 4 comparisons.
so total no of comparisons= 4+20+4+10+6+4=48
therefore B is the answer.

12 votes
12 votes
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'
                         )

In this query we are trying to find name of the drivers who have reserved all the green and red cars.

Step 1. Find the cid of all the red and green cars using cars relation.

Step 2. Find the did of drivers that have reserved both red and green cars using reserves relation.

Step 3. Find  dname of the drivers who have reserved green and red cars using drivers relation


STEP 1

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

For each tuple we will check whether it has color= red or green. i.e. at max $2$ comparison will be done for each tuple

For each tuple
{
  First we check whether it is red or Not // 1 comparison 
    if yes 
      then move to next tuple 
    else check whether it is green or Not // 1 comparison 
      then move to next tuple
}

$$\overset{\text{C: Cars relation}}{\begin{array}{|c|c|c|c|}\hline
\textbf {Cid} & \textbf {Cname} & \textbf{colour} \\\hline
101 & \text{Renault} & blue\ {\color{Magenta}{ (not\ red\ ,\ not\ green)} }    \\ \hline    102 & \text{Renault} & red\ {\color{Magenta}{ (yes\  red)} }   \\ \hline   
103 & \text{Ferrari} & green\ {\color{Magenta}{ (not\ red\ ,\ yes\ green )} }    \\\hline
104 & \text{Jaguar} & red\ {\color{Magenta}{ ( yes\ red)} }   \\\hline
\end{array}}$$

So $6$ comparison needed here.

The cid of all the red and green cars using cars relation are  $102,103,104.$

Using $3$ more comparison we can find out that $102 $ and $104$ are red and $103$ is green.

$\therefore$ Total number of comparisons done in STEP 1.  $=6+3=9$


STEP 2

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

STEP 2a.  Find tuples whose Cid = 102 or 104

For each tuple
{
  First we check whether it is Cid=102 or Not // 1 comparison 
    if yes 
      then move to next tuple 
    else check whether Cid is 104 or Not // 1 comparison 
      then move to next tuple
}

$$\overset{\text{R: Reserves relation}}{\begin{array}{|c|c|c|}\hline
\textbf {did} & \textbf {Cid} & \textbf {day} \\\hline
22 & 101 \color{Magenta}{ ( not\ 102\ ,\ not\ 104)} & 10-10-06   \\ \hline   
22 & 102 \color{Magenta}{ ( yes\ 102)}& 10-10-06\\     \hline
22 & 103 \color{Magenta}{ ( not\ 102\ ,\ not\ 104)} & 08-10-06    \\\hline
22 & 104 \color{Magenta}{ ( not\ 102\ ,\ yes\ 104)} & 07-10-06     \\\hline
31 & 102 \color{Magenta}{ ( yes\ 102)} & 10-11-16  \\\hline    
31&  103 \color{Magenta}{ ( not\ 102\ ,\  not\ 104)} &06-11-16    \\\hline   
31 & 104 \color{Magenta}{ ( not\ 102\ ,\ yes\ 104)} &12-11-16      \\\hline 
64 & 101\color{Magenta}{ ( not\ 102\ ,\  not\ 104)}&05-09-06     \\\hline 
64&  102 \color{Magenta}{ ( yes\ 102)} & 08-09-06       \\\hline 
74 & 103 \color{Magenta}{ ( not\ 102\ ,\ not\ 104)} & 08-09-06  \\\hline 
\end{array}}$$

So  $17$ comparisons needed here.

The did of all the cars whose Cid = 102 or 104 using reserves relation are  $22,31,64.$

STEP 2b.  Find tuples whose Cid = 103

For each tuple
{
  First we check whether it is Cid=102 or Not // 1 comparison 
  then move to next tuple 
    
}

$$\overset{\text{R: Reserves relation}}{\begin{array}{|c|c|c|}\hline
\textbf {did} & \textbf {Cid} & \textbf {day} \\\hline
22 & 101 \color{Magenta}{ ( not\ 103)}& 10-10-06   \\ \hline   
22 & 102 \color{Magenta}{ ( not\ 103)}& 10-10-06\\     \hline
22 &   103 \color{Magenta}{ ( yes\ 103)}& 08-10-06    \\\hline
22 & 104  \color{Magenta}{ ( not\ 103)} & 07-10-06     \\\hline
31 & 102 \color{Magenta}{ ( not\ 103)} & 10-11-16  \\\hline    
31&103 \color{Magenta}{ ( yes\ 103)}&06-11-16    \\\hline   
31 & 104 \color{Magenta}{ ( not\ 103)}&12-11-16      \\\hline 
64 & 101 \color{Magenta}{ ( not\ 103)}&05-09-06     \\\hline 
64& 102 \color{Magenta}{ ( not\ 103)}& 08-09-06       \\\hline 
74 & 103 \color{Magenta}{ ( yes\ 103)} & 08-09-06  \\\hline 
\end{array}}$$

So  $10$ comparisons needed here.

The did of all the cars whose Cid = 103 using reserves relation are  $22,31,74.$

STEP 2c. Find  did whose Cid = 102 or 104 and Cid = 103

We now need to compare the set $\{22,31,64 \}$ with $\{22,31,74\}$ and find common elements between them.

This would require $8$ comparisons.

And the common did  that we get are $\{ 22,31 \}$

$\therefore$ Total number of comparisons done in STEP 2. $=17+10+8=35$


STEP 3.

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

Here did is the primary key(so they are unique) so once we find both $22$ and $31$ in the did then we can stop searching.

STEP 3a. Find tuples whose did = 22 or 31

Here we just need to run linear search 2 times

fist time to find did = 22

second time to find did = 31

For each tuple
{
  check whether its did=22 or not // 1 comparison 
     if Yes then Exit from loop
}
For each tuple
{
  check whether its did=31 or not // 1 comparison 
     if Yes then Exit from loop 
}

.$$\overset{\text{D: Drivers relation}}{\begin{array}{|c|l|r|c|}\hline
\textbf{did}&    \textbf{dname}&  \textbf{rating}& \textbf{age} \\\hline
22\color{Magenta}{ ( yes\ 22 \ STOP)\ ( not\ 31)}&    \text{Karthikeyan}&    7&      25  \\ \hline   
29\color{Magenta}{ ( not\ 31)}&     \text{Salman}& 1&      33 \\     \hline
31\color{Magenta}{ ( yes\ 31 \ STOP)}&     \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}} $$

$\therefore$ Only $4$ comparisons are needed in STEP 3.


$\therefore$ Total number of comparisons done in STEP 3.

= Comparisons made in STEP 1 +Comparisons made in STEP 2 + Comparisons made in STEP 3

= $9+35+4$

=$48$

$\therefore$ Option $B.$ is the correct choice.

edited by
Answer:

Related questions

31 votes
31 votes
3 answers
2
22 votes
22 votes
2 answers
3
Ishrat Jahan asked Nov 1, 2014
6,320 views
Consider a relation R with five attributes $V, W, X, Y,$ and $Z.$ The following functional dependencies hold:$VY→ W, WX → Z,$ and $ZY → V.$Which of the following is...
42 votes
42 votes
4 answers
4