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.