On Serial Files with Relocatable Records

A serial file is considered in which, after a query is processed, the order in the file is changed by moving the record to which the query referred into the first place in the file. The theory of regular Markov chains is used to demonstrate the existence of E(X) and to show that the law of large numbers holds, where E(X) is the limiting average position of a queried record. A closed-form expression for E(X) is determined. A second method of relocation is proposed, in which the queried record exchanges positions with the record immediately before it in the file. It is conjectured that this method of relocation is at least as good as the first method. It is pointed out that, whichever method of relocation is used, if one only relocated after every Mth query, the limiting average position of a queried record is the same as it is if we relocate after every query.