서지주요정보
Optimization of join operations in fragmented distributed database systems on local area networks = 분할된 근거리망 분산 데이타베이스 시스템에서 결합 연산 최적화
서명 / 저자 Optimization of join operations in fragmented distributed database systems on local area networks = 분할된 근거리망 분산 데이타베이스 시스템에서 결합 연산 최적화 / Myoung-Soo Ahn.
저자명 Ahn, Myoung-Soo ; 안명수
발행사항 [대전 : 한국과학기술원, 1991].
Online Access 제한공개(로그인 후 원문보기 가능)원문

소장정보

등록번호

8002103

소장위치/청구기호

학술문화관(문화관) 보존서고

MEE 9135

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

초록정보

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문제이므로 그래프 분할을 위해 많이 사용되는 휴리스틱 접근 방법이 결합 할당을 위해 수정되어 적용되었다. 제안된 알고리듬의 성능을 실제적인 상황하에서 분석하기 위하여 모의실험이 수행되었다. 실험결과 제안된 알고리듬의 성능이 대부분의 실험 환경하에서 기존의 알고리즘들 보다 우수함을 보여줬다. 또한 각 컴퓨터의 부하도 평형 되었다.

서지기타정보

서지기타정보
청구기호 {MEE 9135
형태사항 iv, 58 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 안명수
지도교수의 영문표기 : Myung-Hwan Kim
지도교수의 한글표기 : 김명환
학위논문 학위논문(석사) - 한국과학기술원 : 전기및전자공학과,
서지주기 Reference : p. 56-58
주제 Distributed databases.
Semantic networks (Information theory)
LAN. --과학기술용어시소러스
데이터 베이스. --과학기술용어시소러스
분산 시스템. --과학기술용어시소러스
연산 방식. --과학기술용어시소러스
Local area networks.
QR CODE qr code