13.7

Give an example of a relational-algebra expression and a query-processing strategy in each of the following situations:

  1. MRU is preferable to LRU.

  2. LRU is preferable to MRU.

  1. MRU is preferable to LRU.

MRU is preferable to LRU where \(R_1 \bowtie R_2\) is computed by using a nested-loop processing strategy where each tuple in \(R_2\) must be compared to each block in \(R_1\). After the first tuple of \(R_2\) is processed, the next needed block is the first one in \(R_1\). However, since it is the least recently used, the LRU buffer management strategy would replace that block if a new block was needed by the system.

  1. LRU is preferable to MRU.

LRU is preferable to MRU where \(R_1 \bowtie R_2\) is computed by sorting the relations by join values and then comparing the values by processing through the relations. Due to duplicate join values, it may be necessary to “back up” in one of the relations. This “backing up” could cross a block boundary into the most recently used block, which would have been replaced by a system using MRU buffer management, if a new block was needed.

Under MRU, some unused blocks may remain in memory forever. In practice, MRU can be used only in special situations like that of the nested-loop strategy discussed in Exercise 13.8a.