In response to a query, a database system must search the index for suitable records and fetch them from the disk. When the database occupies more than one disk, the response can be faster if the records are on different disks so the fetches can be overlapped.
This paper examines the problem of distributing records among disks to maximize fetch overlap. The problem is idealized by considering a system where each attribute has value one or zero and every possible combination of attribute values occurs among the records. For this case, a distribution scheme is presented and proven to be superior to prior known schemes, and close to optimal in a carefully defined sense. The disk chosen for a record is given by the weighted sum of the values of its attributes. In the old scheme, the weights were uniform; but in the new scheme, the weights are systematically chosen from 1,2,4, . . . 2k−1, where there are 2k disks.
Although a well-done piece of mathematics, this paper by itself is of little practical value. Few databases satisfy the highly abstract conditions of the problem solved and the paper gives no consideration to extending its results for less stringent assumptions.