On the selection of Secondary Indices in Relational Databases

R.S. Choenni, Henk Blanken, Thiel Chang

Research output: Contribution to journalArticleAcademicpeer-review

23 Citations (Scopus)
200 Downloads (Pure)


An important problem in the physical design of databases is the selection of secondary indices. In general, this problem cannot be solved in an optimal way due to the complexity of the selection process. Often use is made of heuristics such as the well-known ADD and DROP algorithms. In this paper it will be shown that frequently used cost functions can be classified as super- or submodular functions. For these functions several mathematical properties have been derived which reduce the complexity of the index selection problem. These properties will be used to develop a tool for physical database design and also give a mathematical foundation for the success of the before-mentioned ADD and DROP algorithms.
Original languageUndefined
Pages (from-to)207-233
Number of pages27
JournalData & knowledge engineering
Issue number11
Publication statusPublished - Dec 1993


  • EWI-6263
  • IR-18207
  • ADD and DROP algorithms
  • METIS-118727
  • submodular functions
  • supermodular functions
  • secondary index selection
  • Physical database design

Cite this