查看文章

An index selection algorithm for relational databases is presented. The problem concerns finding an optimal set of indexes that minimizes the average cost of processing transactions. This cost is measured in terms of the number of I/O accesses. The algorithm presented employs an approach called DROP heuristic. In an extensive test to determine the optimality of the algorithm, it found optimal solutions in all cases. The time complexity of the algorithm shows a substantial improvement when compared with the approach of exhaustively searching through all possible alternatives. This algorithm is further extended to incorporate the clustering property (the relation is stored in a sorted order) and also is extended for application to multiple-file databases.