Comments on an optimal set of indices for a relational database

M. Y. L. Ip et al., (see ibid., vol.SE-9, p.135-43, 1983) solved the index selection problem for a relational database by reducing it to a classical knapsack problem and then applying an approximation algorithm. It is shown that this reduction process does not work in general by providing a counterexample, and its practical significance is discussed. It turns out that the main idea of Ip et al. need not be discarded. In particular, the approximation algorithm used can be adapted fairly easily to take care of the problems which were raised by the counterexample. In spite of its simplicity, this modification can lead to a reduced number of indices, which is rather attractive from a practical point of view.<>