Using QLSM

1. Selection of local replacement policies.
2. Estimate sizes for the localoty sets of each file instance.
   1. Straight Sequential
      1. The locality set size is 1.
      2. On page fault, read from disk and overwrite data on the buffer page.
   2. Clustered Sequential
      1. The locality set size is (# of records in largest cluster)/(blocking factor).
      2. The page replacement discipline can be both LRU or FIFO for optimality.
   3. Looping Sequential
      1. The locality set size is the total number of pages in the file.
      2. The page replacement discipline is MRU for optimality.
   4. Independent Random
      1. The locality set size has an upper bound(approx) provided by Yao's formula. It estimates the total # of pages referenced, b, in a series of k random record accesses.
      2. When references are sparse, 1 page is sufficient.
      3. The actual size can be one of the two depending on the likelihood that each page is re-referenced.
      4. The page replacement discipline choice is immaterial.
   5. Clustered Random
      1. The locality set size is approximated by the number of records in the largest cluster.
      2. The page replacement discipline can be both LRU or FIFO for optimality.
   6. Straight Heirarchical (SH), H/SS, H/CS
      1. The locality set size is 1.
      2. CS references is applicable here xpt each member in a cluster is now a key-pointer pair than a data record.
   7. Looping Hierarchical
      1. An ideal reference algo should keep the active pages of the upper levels of a tree resident and multiplex the rest of the pages in a scratch buffer.
      2. ``Residual Buffer'' concept can be used to determine the number of upper levels to be kept in memory.
      3. In many cases, root is the only page worth keeping in memory, since fan-out is large. Then LIFO and 3-4 buffers with root pinned gives a reasonable level of performance.