GATE CS Mastery
Cheat sheets

GATE CS 2014 Set 2 · Databases

Question 40

MCQPrinted as CS Q.302 marksWrong answer: −2/3Easy (estimate)

Question

Consider a join (relational algebra) between relations r(R)r(R) and s(S)s(S) using the nested loop method. There are 3 buffers each of size equal to disk block size, out of which one buffer is reserved for intermediate results. Assuming size(r(R))<size(s(S))\text{size}(r(R)) < \text{size}(s(S)), the join will have fewer number of disk block accesses if

Choose one option
Official answer and solution
Official answer
A
From
Official GATE 2014 answer key

Solution

Compare disk block I/O costs for block nested loop join with smaller versus larger relations in the outer loop.

  1. Buffer Allocation:

    • Total buffers = 3 blocks.
    • 1 buffer is reserved for intermediate output results.
    • Remaining available buffers for input relations = 3−1=23 - 1 = 2 blocks (1 buffer for outer relation block, 1 buffer for inner relation block).

  2. Block I/O Cost Analysis:
    Let B(r)B(r) and B(s)B(s) denote the number of disk blocks occupied by relation r(R)r(R) and s(S)s(S) respectively, with B(r)<B(s)B(r) < B(s).

    • Case 1 (r(R)r(R) in outer loop):
      Cost=B(r)+B(r)×B(s).\text{Cost} = B(r) + B(r) \times B(s).
    • Case 2 (s(S)s(S) in outer loop):
      Cost=B(s)+B(s)×B(r).\text{Cost} = B(s) + B(s) \times B(r).

  3. Comparison:

    Cost(Case1)−Cost(Case2)=B(r)−B(s).\text{Cost}(Case 1) - \text{Cost}(Case 2) = B(r) - B(s).

    Since size(r(R))<size(s(S))\text{size}(r(R)) < \text{size}(s(S)), we have B(r)<B(s)B(r) < B(s), which implies:

    B(r)−B(s)<0  ⟹  Cost(Case1)<Cost(Case2).B(r) - B(s) < 0 \implies \text{Cost}(Case 1) < \text{Cost}(Case 2).

    Therefore, placing the smaller relation r(R)r(R) in the outer loop results in fewer disk block accesses.

Final answer

A

Common trap

Thinking that join selection factor determines block I/O of nested loop joins before any index or filtering is applied.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2014 Computer Science and Information Technology (CS) Session 2
Question
40 of 65, printed as CS Q.30
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.