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

fYear

1994

fDate

5-8 Sep 1994

Firstpage

379

Lastpage

386

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;

fLanguage

English

Publisher

ieee

Conference_Titel

EUROMICRO 94. System Architecture and Integration. Proceedings of the 20th EUROMICRO Conference.

Conference_Location

Liverpool

Print_ISBN

0-8186-6430-4

Type

conf

DOI

10.1109/EURMIC.1994.390420

Filename

390420