The hardness result for selecting an optimal index configuration was shown by Shapiro [60]. Therefore, the challenge was similar to that in the area of query optimization – identifying the right set of heuristics to guide the selection of physical design. One set of papers advocated an approach based on rule-based expert systems. The rules took into account query structures as well as statistical profiles and were “stand-alone” applications that recommended indexes. A tool such as DEC RdbExpert falls in this category. Rozen and Shasha [56] also used an external cost model but their cost model was similar to that.
