It is important to derive an efficient query processing strategy in distributed database systems since their performances critically depend on the strategies. Join is a frequently used operation and the costs to process it are high. Thus, Join query optimization has received great attentions during past decades. Though the fragmented distributed database systems on local area networks have many advantages and are widely used, not many join optimization algorithms deal with them.
In this thesis, we propose an efficient join optimization algorithm for the joins between two fragmented relations in a distributed database system on a nonbroadcast fast local network. Our objective is to minimize the response time of a join. Semantic information associated with fragments is used to eliminate unnecessary processings. Duplicate copies of each fragment are considered to increase parallelism and to reduce the costs to process a join. A join is transformed into a union of the fragment joins and then each fragment join is assigned to a site. The similarities between the fragment join assignment problem and the balanced graph partitioning problem are identified. Since both problems are NP-hard, a heuristic method for graph partitioning is modified to solve the fragment join assignment problem.
Simulation studies are conducted to validate the performance of the proposed algorithm. The results show that the proposed algorithm outperforms the existing algorithm and the loads of sites are balanced.
분산 데이타베이스의 성능, 신뢰성, 이용 가능성, 그리고 모듈화에 대한 잇점과 통신 및 워크스테이션 기술의 발달로 인하여 근거리망에 구축된 분산 데이타베이스 시스템이 널리 사용되고 있다. 이러한 분산 데이타베이스 시스템의 성능에 미치는 질의 최적화 알고리듬의 영향은 매우 크다. 특히, 결합 연산은 질의 처리를 위해 자주 사용되고, 많은 비용이 들기때문에 결합 연산을 최적화하기위한 연구가 활발하게 진행되어 오고 있다. 그러나 분할된 근거리망 분산 데이타베이스의 중요성에 비해 이를 정확히 모델링하고 효율적인 알고리듬을 제시하는 연구결과는 많지 않다.
본 논문에서는 근거리망에 기반한 분산 데이타베이스에서 분할된 두 릴레이션 사이의 결합 연산을 최적화하기위한 일반적인 비용 함수를 세우고 효율적인 알고리듬을 제안한다. 최적화의 목표는 응답시간을 최소화하는 것으로 정했다. 제안된 알고리듬은 프래그먼트(fragment ) 결합 할당 방법을 사용하며, 분할에 관한 정보를 사용하여 불필요한 처리를 제거한다. 한 프래그먼트가 여러개의 복사본을 갖고 있을 때 이를 이용하여 병렬 처리 능력을 향상시키고, 전체적인 처리 비용을 줄인다. 프래그먼트 결합 할당 문제와 평형된 그래프 분할 문제 사이의 유사성이 식별되었다. 두 문제가 모두 NP문제이므로 그래프 분할을 위해 많이 사용되는 휴리스틱 접근 방법이 결합 할당을 위해 수정되어 적용되었다.
제안된 알고리듬의 성능을 실제적인 상황하에서 분석하기 위하여 모의실험이 수행되었다. 실험결과 제안된 알고리듬의 성능이 대부분의 실험 환경하에서 기존의 알고리즘들 보다 우수함을 보여줬다. 또한 각 컴퓨터의 부하도 평형 되었다.
