The optimal selection of secondary indices is NP-complete
Author:
Open Access
- 1 January 1983
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 13 (2) , 72-75
Abstract
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.Keywords
This publication has 2 references indexed in Scilit:
- The choice of partial inversions and combined indicesInternational Journal of Parallel Programming, 1974
- An optimization problem on the selection of secondary keys1971