On Index Selection Schemes for Nested Object Hierarchies

Abstract

In this paper we address the problem of devising a set of indexes for a nested object hierarchy in an objected-oriented database to improve the overall system performance. Note that the effects of two indexes could be entangled in that the inclusion of one index might affect the benefit achievable by the other index. Such a phenomenon is termed index interaction in this paper. Clearly, the effect of index interaction needs to be taken into consideration when a set of indexes is being built. The index selection problem is first formulated and four index selection algorithms are evaluated via simulation. The effects of different objective functions, which guide the search in the index selection algorithms, are also investigated. It is shown by simulation results that the greedy algorithm which is devised in light of the phenomenon of index interaction performs fairly well in most cases. It in fact agrees with the very nature of index interaction we identify in this study. Sensitivity analysis for various database parameters is conducted. We not only conduct an extensive performance study for index selection algorithms, but also explore the effect of index interaction to deal with this global optimization problem. Index Terms: Object-oriented databases, indexing, nested object hierarchy, index interaction.