Performance optimization is emerging as one of important issues in object-oriented databases. In this thesis, we explore the problem of the optimal index configurations in object-oriented database systems. The problem is to find a set of nested attribute indexes under which the overall cost of processing retrieval queries and maintaining the indexes for update queries in a given workload is minimal. We also take into account a space limit for storing the indexes. The primary idea of the proposed methodology is to reduce the problem to that of selecting indexes in such a way that the sum of cost savings are maximal subject to a given storage capacity. The correctness of our approach is proved using analytic cost formulas. We characterize the computational difficulty of the problem, which is shown to be NP-hard. We propose two methods for finding index configurations: a simple but effective approximation algorithm and an Integer Programming formulation. Experiments are conducted to assess the performances of the proposed methods. The experiment results indicate that the proposed approximation algorithm works well for various mixtures of input parameters and the Integer Programming model is well suited to find optimal solutions for a wide range of problem sizes.
As an initial effort to extend the index configuration problem to the context of class-attribute hierarchy, the later part of this thesis explores the optimization of object-oriented queries with multiple path predicates in class-attribute hierarchies. We formulate the query optimization problem and apply a genetic strategy to it. Experiment results show that our formulation is well suited to the behaviour of genetic algorithms. Genetic algorithm works efficiently both in the solution quality and execution time, indicating its feasibility for use in query optimizations of database systems.
성능 최적화는 객체지향 데이타베이스 시스템의 중요한 연구과제이다. 최근에 제안된 중첩 애트리뷰트 색인은 객체지향 질의의 최적화에 크게 기여할 수 있는 것으로 보고되었다. 그러나, 이들 색인은 기존의 단순 애트리뷰트에 대한 색인에 비해 저장공간 및 갱신유지 비용이 큰 부담이 있다. 또한, 색인의 종류에 따라 검색성능이 다른 특성도 있다. 그러므로, 중첩 애트리뷰트 색인을 통한 질의처리의 잇점이 저장공간 및 갱신유지를 위한 부담으로 인해 상쇄되지 않게 하기 위해서는 색인들이 매우 신중히 구성되어야하며, 효과적인 색인구성 방법에 관한 연구는 필수적이라 하겠다.
본 논문에서는, 객체지향 데이타베이스에서 클래스 애트리뷰트 계층상의 하나의 경로에 대한 중첩 애트리뷰트 색인의 최적 구성 문제를 연구하였다. 최적 색인구성 문제는 하나의 경로에 대한 검색및 갱신질의들이 주어지고 색인화일에 대한 저장공간 한계가 주어졌을 때에, 질의의 총 처리비용을 최소화할 수 있는 색인구성을 결정하는 문제이다. 분석을 통해, 최적 색인구성 문제는 경로 길이가 1씩 증가함에 따라 가능한 색인구성의 수가 세배씩 늘어나는 방대한 문제공간을 갖으며 NP-hard에 속한다는 것을 설명하였다. 비용모델로부터 색인의 비용절약을 유도하여, 비용절약의 총 이 최대화되는 색인구성을 구하는 문제로 변환하는 방법을 제안하고, 이의 옳음을 증명하였다.
효과적인 색인 구성을 구하기 위한 한가지 방법으로서, 근사 알고리즘을 제안하였다. 제안된 근사 알고리즘은 다양한 형태의 문제에 대하여 짧은 시간내에 최적해에 가까운 해를 구할 수 있음을 실험을 통해 보여 주었다. 보다 긴 경로에 대한 최적색인 구성을 구하기 위한 방법으로 Integer Programming (IP) 모델을 또한 제안하였다. IP는 근본적으로 지수함수의 복잡도를 갖는 알고리즘을 바탕으로하지만, 최근의 상당한 기술진전으로 그 문제해결의 범위가 넓어지고 있다. 그러나, 최적 색인구성 문제를 IP 모델로 표현하는 것은 그리 간단하지 않다. 본 논문에서는, 색인에 대해 결정함수를 부여하고, 최적화 목표함수와 저장공간 및 비겹침 제약조건을 표현하는 방법을 상세히 기술하였다. 이렇게 표현된 IP 모델은, backtracking 기법으로 구현한 알고리즘과 비교한 실험을 통하여, 그 문제표현의 옳음뿐만 아니라 큰 문제범위에 대해서도 그 문제해결 가능성을 보였다.
클래스 애트리뷰트 계층 전체를 대상으로하는 최적색인 구성을 구하기 위해서는 보다 복잡한 질의형태들에 대한 질의 최적화 연구가 선행되어야 한다. 이를 위해 본 논문에서는, 여러개의 경로술어를 갖는 질의의 최적화 문제를 연구하였다. 비용함수를 이용하여 문제를 정의하고, 이에 genetic 알고리즘을 적용하였다. 실험을 통하여, 본 논문에서 제안한 질의 최적화를 위한 문제표현이 genetic 알고리즘의 특성에 잘 부합하여, 많은 문제들에 대하여 완전탐색 방법보다 짧은 시간내에 최적해를 구할 수 있음을 보여 주었다.