Fast processing of database queries is a primary goal of database systems. Indexes are a crucial means for the physi- cal design to reduce the execution times of database queries significantly. Since indexes cause additional memory con- sumption and the storage capacity of databases is limited, the choice of indexes is also limited, making this an NP- hard problem. Therefore, it is of great interest to determine an efficient selection of indexes for a database management system (DBMS) and thus find a sufficient solution for the so-called index selection problem. This work aims to show how a specific basic index selection problem and various ex- tensions of it can be solved using linear programming. For each defined index selection problem, we present a formal linear programming model that solves the problem. Fur- thermore, we implemented these solutions with the model- ing language AMPL1 and evaluated these implementations using synthetic data sets. We present these evaluation re- sults and indicate possible points on how this project could be continued in the future. Read more
Contributors (equally contributed, ordered by surname):
- Leonardo Hübscher (deeps96)
- Oliver Nordemann (olivernordemann)
- Marcel Weisgut (mweisgut)