On the selection of Secondary Indices in Relational Databases

Sunil Choenni; Henk Blanken; Thiel Chang

doi:10.1016/0169-023X(93)90023-I

On the selection of Secondary Indices in Relational Databases

Sunil Choenni^*
, Henk Blanken
, Thiel Chang

^*Corresponding author for this work

Databases (Former)

Research output: Contribution to journal › Article › Academic › peer-review

26 Citations (Scopus)

260 Downloads (Pure)

Abstract

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 language	English
Pages (from-to)	207-233
Number of pages	27
Journal	Data & knowledge engineering
Volume	3
Issue number	11
DOIs	https://doi.org/10.1016/0169-023X(93)90023-I
Publication status	Published - Dec 1993

Keywords

ADD and DROP algorithms
Submodular functions
Supermodular functions
Secondary index selection
Physical database design

Access to Document

10.1016/0169-023X(93)90023-I

ArticleFinal published version, 1.58 MB

26 Citations
1 Report

On the selection of indices in Relational Databases
Choenni, R. S., Blanken, H. M. & Chang, S. C., 1992, Enschede: University of Twente. 15 p. (Memoranda informatica; no. 92-72)
Research output: Book/Report › Report › Professional

Cite this

@article{e4ac1da3be4f4d3985edf8e535ba34e0,

title = "On the selection of Secondary Indices in Relational Databases",

abstract = "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.",

keywords = "ADD and DROP algorithms, Submodular functions, Supermodular functions, Secondary index selection, Physical database design",

author = "Sunil Choenni and Henk Blanken and Thiel Chang",

year = "1993",

month = dec,

doi = "10.1016/0169-023X(93)90023-I",

language = "English",

volume = "3",

pages = "207--233",

journal = "Data \& knowledge engineering",

issn = "0169-023X",

publisher = "Elsevier",

number = "11",

}

TY - JOUR

T1 - On the selection of Secondary Indices in Relational Databases

AU - Choenni, Sunil

AU - Blanken, Henk

AU - Chang, Thiel

PY - 1993/12

Y1 - 1993/12

N2 - 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.

AB - 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.

KW - ADD and DROP algorithms

KW - Submodular functions

KW - Supermodular functions

KW - Secondary index selection

KW - Physical database design

U2 - 10.1016/0169-023X(93)90023-I

DO - 10.1016/0169-023X(93)90023-I

M3 - Article

SN - 0169-023X

VL - 3

SP - 207

EP - 233

JO - Data & knowledge engineering

JF - Data & knowledge engineering

IS - 11

ER -

On the selection of Secondary Indices in Relational Databases

Abstract

Keywords

Access to Document

Fingerprint

Research output

On the selection of indices in Relational Databases

Cite this