Title :
Optimal configuration of nested attribute indexes in object-oriented databases
Author :
Seo, Sang Koo ; Lee, Yoon Joon
Author_Institution :
Dept. of Comput. Sci., Korea Adv. Inst. of Sci. & Technol., Seoul, South Korea
Abstract :
We explore the problem of the optimal configuration of nested attribute indexes in object-oriented database systems. Our approach is to reduce the problem to that of selecting indexes in such a way that the sum of cost savings is maximized subject to a given storage capacity. The correctness of our approach is shown by using analytic cost formulas. We characterize the problem as NP-hard, and propose an approximation algorithm. Experimental results show the algorithm performs well for various input situations
Keywords :
computational complexity; configuration management; indexing; object-oriented databases; query processing; software cost estimation; NP-hard; analytic cost formulas; approximation algorithm; correctness; cost savings; input situations; nested attribute indexes; object-oriented databases; optimal configuration; storage capacity; Ambient intelligence; Application software; CADCAM; Computer aided manufacturing; Computer science; Costs; Database systems; Indexes; Object oriented databases; Query processing;
Conference_Titel :
EUROMICRO 94. System Architecture and Integration. Proceedings of the 20th EUROMICRO Conference.
Conference_Location :
Liverpool
Print_ISBN :
0-8186-6430-4
DOI :
10.1109/EURMIC.1994.390420
