XML 데이터를 위한 효율적인 디스크 블록 할당 방법

Abstract

XML과 같은 준구조적 데이타가 많이 사용됨에 따라 이를 효과적으로 저장하고 관리하는 것이 중요해지고 있다. XML 데이타는 트리 형태로 모델링이 가능하며, 기본적으로 질의 처리는 트리를 탐색하는 방식으로 이루어진다. 본 논문에서는 XML 데이타를 디스크 블록에 저장하는 알고리즘을 제안한다. 제안하는 알고리즘은 트리의 각 노드마다 아래쪽에서 위쪽으로 숫자를 할당하며 그 숫자를 이용하여 디스크 블록에 노드들을 매핑한다. 제안하는 알고리즘은 접근 패턴 정보를 필요로 하지 않으며 어떠한 접근 패턴에 대해서도 좋은 성능을 보인다. 제안하는 방법의 몇가지 특성을 증명하고, 실험을 통해서 성능을 평가한다.

With the recent proliferation of the use of semi-structured data such as XML, it becomes more important to efficiently store and manage the semi-structured data. The XML data can be logically modelled as a rooted tree e.g., the DOM tree. In order to process a query on the XML data, we traverse the tree structure. In this paper we present an algorithm that places the XML data to disk blocks. The proposed algorithm assigns a number to each node of the tree in a bottom-up fashion. Then, the nodes are allocated to disk blocks using the assigned number. The proposed algorithm does not need access pattern information, and provides good performance for any access pattern. The characteristics of the proposed method are presented with analysis. Through experiments, we evaluate the performance of the proposed method.