Stanford InfoLab Publication Server

On Index Selection Schemes for Nested Object Hierarchies

Chawathe, S. and Chen, M. and Yu, P. (1993) On Index Selection Schemes for Nested Object Hierarchies. Technical Report. Stanford InfoLab. (Publication Note: 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile (VLDB 1994))




In this paper we address the problem of devising a set of indexes for a nested object hierarchy in an object-oriented database to improve the overall system performance. It is noted 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. 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. Sensitivity analysis for various database parameters is conducted. Index Terms: Object-oriented databases, indexing, nested object hierarchy, index interaction.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:Object-oriented databases, nested objects, path expressions, index selection
Subjects:Computer Science > Data Integration and Mediation
Related URLs:Project Homepage
ID Code:33
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:05 Feb 2009 16:01

Download statistics

Repository Staff Only: item control page