계층 그리드 화일의 벌크로드를 위한 기법 = A Technique for Bulk-Loading of Multilevel Grid File

국문 초록 (Abstract)

계층 그리드 화일은 다중 애트리뷰트 액세스를 효율적으로 지원하는 다차원 화일이다. 데이타베이스를 구축하는 경우에는 매우 방대한 양의 객체들을 대상으로 하므로 다차원 화일의 효율적인 벌크 로드는 매우 중요하다. 본 논문에서는 계층 그리드 화일을 위한 새로운 벌크 로드 기법인 MLGF_BulkLoad를 제안한다. MLGF_BulkLoad는 계층 그리드 화일의 구성 요소인 각 페이지를 디스크로부터 한번 액세스할 때, 이곳에 저장될 모든 객체 및 디렉토리 엔트리들을 한꺼번에 처리하는 방식을 사용한다. 따라서 기존의 삽입 알고리즘을 반복적으로 적용함으로써 계층 그리드 화일을 구성하는 경우 같은 페이지를 디스크로부터 여러번 액세스하게 되는 오버헤드를 제거할 수 있다. MLGF_BulkLoad는 두 단계로 구성된다. 첫 번째 단계에서는 다차원의 데이타 공간상에서 인접한 객체들을 일차원의 물리적 공간내에 인접하도록 재배열시키는 작업을 수행한다. 이를 위하여 다차원 공간을 일차원 공간으로 사상시킬 때 원 공간에서의 인접성을 효과적으로 유지시키는 Z 변환을 사용한다. 두 번째 단계에서는 재배열된 객체들을 페이지 단위로 저장시키는 작업과 각 객체 페이지와 대응되는 리프 단계 디렉토리 엔트리를 생성시키는 작업을 수행한다. 또한, 이와 병행하여 같은 작업을 상위 단계 디렉토리에도 재귀적으로 적용시킨다. 성능 평가를 위하여 수행시 발생되는 디스크 액세스 수를 분석함으로써 MLGF_BulkLoad의 우수성을 규명하였다. 또한, 시뮬레이션을 통하여 각 인자들의 값의 변화에 따르는 MLGF_BulkLoad의 성능상의 경향을 제시하였다.

다국어 초록 (Multilingual Abstract)

The multilevel grid file(MLGF) is a multidimensional file supporting multi-attribute accesses efficiently. The efficient bulk-loading of a multidimensional file is very important in constructing a database since this should handle an enormous volume of objects. In this paper, we propose the MLGF_BulkLoad, a new technique for bulk-loading the MLGF. The main feature of the MLGF_BulkLoad is to simultaneously process all the objects or directory entries to be placed on each page belonging to the MLGF when accessing the page. This avoids the overhead for accessing the same page multiple times, which results from applying the MLGF insertion algorithm repeatedly. The MLGF_BulkLoad consists of two phases. The first phase relocates all the objects in order that the logically-adjacent objects in multidimensional data space are clustered in one-dimensional physical space. For this, we employ the Z transformation, which has been known to map effectively multidimensional space into one dimensional space preserving proximity. The second phase paginates the relocated objects and creates the leaf-level directory entries, each of which corresponds to the page containing a set of objects. Simultaneously, it performs the same actions on the directory entries recursively in a bottom-up fashion. For performance evaluation, we analyze the MLGF_BulkLoad in terms of the number of page accesses. The result shows the superiority of the MLGF_BulkLoad. We also present performance tendency of the MLGF _BulkLoad according to the changes of various parameter values through simulation.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 계층 그리드 화일
• 3. MLGF_BulkLoad
• 4. 성능 분석
• 5. 결론
• Acknowledgment
• 참고문헌
• 저자소개