This thesis presents a new approach to distributed query processing in the environment where relations are horizontally fragmented over a broadcast local area network. Partitioning relations into horizontal fragments is useful is reducing query processing costs for most queries. However, only a few query processing algorithms have been proposed specifically for fragmented databases.
In fragmented databases, optimizing a join is difficult even if the problem is restricted to a single join between two fragmented relations, which is called two-way join. Two-way joins are the most popular distributed queries, and the optimization of two-way joins serves as a basis for the optimization of multiple joins. In this thesis, we focus on optimizing two-way joins on broadcast local area networks. In order to optimize the total processing costs of two-way joins, a new four-phase approach is proposed: (1) query transformation, (2) semijoin optimization, (3) join optimization, and (4) final processing. In our approach, replicated copies of a fragment are used to improve parallelism and transmission cost, and both of local processing cost and transmission cost are considered to optimize the query processing cost. In addition, the broadcasting capability of local area networks is put to use to reduce data transmissions.
In order to perform query transformation efficiently, the qualification of each fragment is restricted to be represented as a conjunction of comparisons. Then, the query transformation problem is transformed into a rectangle intersection problem, and an efficient algorithm is developed for the transformed problem. In the semijoin optimization phase, a greedy algorithm is developed to obtain beneficial semijoins. For a given set of semijoins, the problem that optimizes the transmission order of the joining attributes is transformed into a minimum weight feedback vertex set problem. The transformed problem is proved to be NP-hard, thus a heuristic algorithm that optimizes the transmission order is developed. In the join optimization phase, two heuristic algorithms are developed for determining the set of data to be transmitted. Some experiments are performed to evaluate the performance of our algorithms. The results show that our algorithms obtain optimal solutions for most test queries and outperforms Chen and Li's join optimization algorithm with respect to total transmission cost. In the final processing phase, the fragment joins are executed at several sites by considering the dynamic load of the distributed database system.
본 논문에서는 방송형 근거리망에 릴레이션들이 수평 분할(horizontal fragmentation) 되어 있는 환경에 대해 새로운 질의 처리 방법을 제안한다. 릴레이션을 수평 분할함으로써 대부분의 질의에 대해 질의 실행 비용을 줄일 수 있다. 그러나, 수평 분할되어 있는 데이타베이스를 위한 질의 처리에 대한 연구가 미흡한 실정이다.
분할된 데이타베이스에서는 두 릴레이션 사이의 죠인(이진 죠인)을 최적화 하는 문제도 매우 어려운 문제이다. 이진 죠인은 가장 흔히 제기되는 분산 질의이며, 이진 죠인의 최적화는 다중 죠인을 최적화 하는 기초가 된다. 본 논문에서는 방송형 근거리망에서 이진 죠인의 실행 비용을 최적화 하기 위해 다음의 네 단계로 이루어진 방법을 제안한다: (1) 질의 변환, (2) 세미죠인 최적화, (3) 죠인 최적화, (4) 분산 실행. 본 논문의 방법에서는 질의 실행의 병렬성을 증가시키고 통신비용을 줄이기 위해 중복된 분할들을 이용한다. 질의 비용에는 통신 비용과 디스크 액세스 비용을 함께 고려한다.
질의 변환을 효율적으로 하기 위해 각 분할의 조건식을 비교연산과 "$\Lambda$" 연산의 조합으로 표현될 수 있는 식으로 제한하였다. 그러면 질의 변환 문제는 직사각형 도형들을 갖고 있는 두 판을 겹쳤을 때 중복된 직사각형들의 쌍을 찾는 문제로 변환된다. 세미죠인 최적화 단계에서는 이득 있는 세미죠인을 구하는 알고리즘을 제안하였다. 또 주어진 세미죠인 스케쥴에 대해 통신 순서를 최적화 하는 문제를 형성한 후, 이 문제가 NP-hard 문제임을 보이고 휴리스틱 알고리즘을 제안하였다. 죠인 최적화 단계에서는 통신망의 방송성을 고려하여 두 휴리스틱 알고리즘을 개발하였다. 성능 분석 결과, 이 알고리즘들은 대부분의 실험 질의에 대해 최적의 실행 스케쥴을 구했으며, 첸(Chen)의 알고리즘보다 우수한 성능을 제공하였다. 분산 실행 단계에서는 시스템의 동적 부하를 고려하여 분할 죠인들을 병렬로 실행한다.
