Register

GATE IT 2006 | Question: 85

• edited by
38,056 views
115 115 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$

11 Answers

4 4 votes

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.

1 1 vote

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

1 1 vote

we have 10 DID in Reserves relation and 4 CID in cars relation so we have to match for every DID with every CID
 

for DID in reserves: # DID count = 10
      for CID in cars: # CID count = 4
          if DID == CID: # no of comparions = 10 * 4 = 40
              if cars.color == blue: 
                  blue_set.add(DID)
              if cars.color == green: 
                  green_set.add(DID)

for with 40 comparions we now have the DID's for blue and green car. I can't think of any better approach for this task,
now 

blue_set = {22, 31, 64} 
green_set = {22, 31, 74} 

22 is matched with the first comparison    ----------------    1

31 is matched with the second comparions --------------    2

64 is not matched and it takes three comp to find -------   3
 

so for intersection it took us 1 + 2 + 3 = 6 comparions so current total => 40 + 6 => 46 comparions
intersection_did = {22, 31}
 

To get the dname, we simply need to iterate the first 3 to locate both 22 and 31, and we can stop now, so the total comparions is: 46 + 2 => 48.

0 0 votes
–2 –2 votes
In car C there are 3 tuples has selected. These 3 tuples are comparing with 10 rows of R. So total comparison 3*10=30.

Then for C.color=green we get 3 tuples from R and C.color= red we get 5 tuples

Then comparing for the boat having red and green color both 3*5=15 comparison

Total comparison 30+15=45
Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE IT 2006 | Quest...Next → · GATE IT 2004 | Quest...
← Previous in category · GATE IT 2006 | Quest...Next in category → · GATE IT 2004 | Quest...
Position:
Show:

Related questions

31 31 votes
5 answers 5 answers
7.1k
7.1k views
Ishrat Jahan asked Nov 1, 2014
7,112 views
GATE IT 2006 | Question: 84
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 ...
44 44 votes
2 answers 2 answers
12.3k
12.3k views
Ishrat Jahan asked Nov 1, 2014
12,311 views
GATE IT 2006 | Question: 61
In a database file structure, the search key field is $9$ $bytes$ long, the block size is $512$ $bytes$, a record pointer is $7$ $bytes$ and a block pointer is $6$ $bytes...
38 38 votes
3 answers 3 answers
10.2k
10.2k views
Ishrat Jahan asked Nov 1, 2014
10,224 views
GATE IT 2006 | Question: 60
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 a can...
59 59 votes
5 answers 5 answers
28.9k
28.9k views
Ishrat Jahan asked Oct 31, 2014
28,896 views
GATE IT 2006 | Question: 14
Consider the relations $r_{1}\text{(P, Q, R)}$ and $r_{2}\text{(R, S, T)}$ with primary keys $\text{P}$ and $\text{R}$ respectively. The relation $r_{1}$ contains $2000$ ...