Recently, distributed database (DDB) technologies have advanced rapidly and have been investigated extensively. The development and use of DDB systems has been promoted primarily by the growing dispersion of business operations and the rapid technological changes that make the local area network (LAN) possible and practical. The LAN-based DDB system is very flexible. It may serve the information needs of both small businesses and global businesses.
In designing a DDB, one of the major design issues is the file allocation problem (FAP). FAP determines the location of data files for the design of a DDB. In addition, the assignment of workload to computing servers is critical. This issue is known as WAP (Workload Allocation Problem). The majority of studies in the past for FAP or WAP considered the two problems separately. However, FAP and WAP are interdependent as the location of data files affects the assignment of workload and vice versa. Therefore, it is more effective and realistic to solve the two problems simultaneously. Also, previous FAP or WAP models on LANs considered nodal processing overhead separately because incorporating communication overhead is not a trivial task. However, communication overhead should not be ignored because of its significant bearing on communication protocol delay.
The emphasis of this dissertation is on the integrated file and workload allocation problems which simultaneously incorporate communication overhead and local processing overhead in the design of distributed databases via LANs. Four file and workload allocation problems are investigated with special consideration given to LAN types (one-level LAN/two-level LAN) and allocation policies (non-replication/replication) as follows.
The first problem considers a file and workload allocation problem in a one-level local LAN with broadcasting and multi-access capability. The allocation problem is presented in the form of a nonlinear zero-one integer programming problem. The model adopts the non-replicated file allocation policy. The problem is proved to be NP-complete. Heuristic is developed to solve the particular problems by the employment of their special structures. To illustrate their suitability, the heuristics are compared with exhaustive enumeration for small problems and with a genetic algorithm for large problems. Computational results demonstrate that the proposed model and its relevant heuristic provide effective database designs.
The second problem elaborates on the first problem by considering a file and workload allocation problem in a two-level LAN. The characteristics of the proposed problem and its solution procedure are similar to those of the first problem.
The third problem extends the first problem by considering a replicated file allocation policy in place of a non-replicated file allocation policy on one-level LAN. The problem is presented in the form of a nonlinear zero-one programming problem. The problem is proved to be NP-complete and thus an efficient heuristic is developed to solve specific problems by the employment of its special structure. Workload (query transactions) are assigned or distributed to various sites according to the remaining file service request rate of each server. The fourth problem elaborates on the second problem by taking account of a file replication and workload allocation problem on a two-level LAN.
최근 분산 데이터베이스 기술이 급속도로 발전되면서, 이 분야에 많은 연구들이 수행되어 왔다. 분산 데이터베이스 시스템의 개발 및 사용은 주로 조직의 업무 분산 및 근거리 컴퓨터 통신망(local area network; LAN)의 기술적인 발전 및 실용화에 의해서 촉진되어 왔다. LAB을 기반으로 한 분산 데이터베이스 시스템은 매우 확장성이 좋으며, 따라서 소규모 업무에 있어서 정보의 필요성 뿐만 아니라 대규모 업무에 대한 정보의 필요성도 충분히 지원할 수 있는 시스템이다.
이러한 분산 데이터베이스를 설계할 때, 주요 문제들 중의 하나가 파일 할당 문제(file allocation problem; FAP)이다. FAP은 분산 데이터베이스를 설계할 때 데이터 파일의 위치를 결정하는 문제이다. 덧붙혀서, 분산 데이터베이스시스템에서 처리해야 할 총 부하량(workload)을 각 컴퓨터 서버들에 적절하게 할당하는 것도 중요한 문제이다. 이 문제를 부하량 할당 문제(workload allocation problem; WAP)라고 한다. FAP과 WAP에 관한 과거 대부분의 연구들이 개별적으로 이루어졌다. 그러나, FAP과 WAP은 데이터 파일의 위치가 부하량의 할당에 영향을 미치기 때문에, 상호 의존적이다. 따라서, 이 두 문제를 동시에 해결하는 것이 각 문제를 개별적으로 취급하는 것보다 더 효과적이고, 현실적이다. 또한 과거 FAP 또는 WAP 모델의 대부분은 단지 지역 처리 비용(local processing overhead)만 고려하였는데, 그 이유는 통신비용(communication overhead)을 통합하는 것이 복잡한 작업이었기 때문이다. 그러나, 통신 비용은 데이터 통신을 위하여 TCP/IP와 같은 통신 프로토콜의 실행을 위한 지연 비용(delay overhead)을 무시할 수 없기 때문에, 반드시 고려되어야 한다.
본 논문은 LAB 환경에서 분산 데이터베이스를 설계하기 위하여 통신비용과 지역 처리 비용을 동시에 고려한 통합 데이터파일 및 부하량 할당 문제에 관한 것이다. 본 논문에서는 LAN의 형태(one-level LAB/two-level LAN)와 파일 할당 정책(비중복 정책/중복 정책)을 고려하여, 4개 유형의 파일 및 부하량 할당 문제가 연구된다.
첫번째 문제는 one-level LAN 상에서 파일 및 부하량 할당에 관한 연구이다. 할당 문제는 비선형 0-1 정수계획 문제로 표현된다. 이 모델에서는 비중복 할당 정책을 채택한다. 문제는 NP-complete 임이 증명되었다. 따라서, 이 문제의 특별한 구조를 사용하여 휴리스틱(heuristic) 알고리즘이 개발되었다. 이 휴리스틱의 적합성으로 설명하기 위하여 작은 규모의 문제들에 대해서는 열거법(enumeration method)의 최적해와 비교하고, 대규모 문제들에 대해서는 유전자 알고리즘(genetic algorithm)의 해와 비교되어 진다. 실험 결과는 제시된 모델과 휴리스틱 알고리즘이 분산 데이터베이스 설계를 위한 효과적인 해를 제공하여 준다는 것을 입증하였다.
두번째 문제는 one-level LAN 대신에 two-level LAN 상의 파일 및 부하량 할당 문제를 고려함으로써 첫번째 문제를 확장한 것이다. 문제의 특성 및 해법은 첫번째 문제와 동일한 절차를 거쳤다.
세번째 문제는 파일의 비중복 할당 정책 대신에 중복 할당 정책을 고려함으로써 첫번째 문제인 one-level LAN 상의 파일 및 부하량 할당 문제를 확장한 것이다. 부하량은 각 서버(computing site)들의 잔존 처리능력(remaining processing capacity)을 고려하여 각 사이트에 할당된다. 이 문제 비선형 0-1 정수계획 문제로 제시되었다. 이 문제는 NP- complete 문제이며 따라서, 이 문제를 풀기 위하여 이 문제의 특별한 구조를 이용한 효과적인 휴리스틱 알고리즘이 개발되었다. 네번째 문제는 two-level LAN 상의 파일의 중복 할당 정책을 고려함으로써 두번째 문제를 확장한 것이다.
