Estimating disk head movement in batched searching

The study considers the problem of evaluating the expected disk head movement when the SCAN disk scheduling policy is used to answer a batch of queries. The two cases examined are: (a) the batched queries are based on primary key values, and (b) each query in the batch is based on secondary key values.Earlier works assumed that hit cylinders are non-distinct and derived an exact (approximate) formula for the first (second) case. In this paper, both replacement and non-replacement models are examined and new exact (exact and approximate) formulae are derived for the first (second) case. It is shown that earlier and new approximate results may be used instead of the computationally expensive exact formulae.