The optimal selection of secondary indices is NP-complete
Gregory Piatetsky-Shapiro · ACM SIGMOD Record · 1983
The problem of selecting secondary indices for a file so as to minimize the expected transaction cost was frequently analyzed before. We prove that it is NP-complete by reducing the MINIMUM SET COVER problem to it.