Search

The index selection problem for a relational database is of considerable practical importance. In [4], a solution to this problem is offered by reducing it to a classical knapsack problem and then applying an approximation algorithm. Here we show that this reduction process does not work in general by providing a counter-example. We also briefly discuss the practical significance of this counter-example. It turns out that the main ideas in [4] 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 counter-example. 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. [ABSTRACT FROM AUTHOR]