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:
- $36 - 40$
- $44 - 48$
- $60 - 64$
- $100 - 104$
