XML has become the standard of the data representation and exchange through the Internet recently. XML is a markup language that can separate the contents of data and the presentation of data. Because XML data is modeled as a rooted tree, path queries are widely used for the query processing. In the thesis we present XML data placement methods for effective processing of path queries. Specifically, this thesis addresses two issues of XML data placement, data placement on physical medium and wireless air medium.
First, we propose an efficient algorithm that places XML data on the physical storage medium (i.e., magnetic disks) such that the number of disk accesses for path query processing is minimized. The proposed algorithm consists of two steps. In the first step, we assign a number (called the mapping indicator) for each node of a tree in a bottom-up fashion. The mapping indicator of a node denotes the minimum number of disk blocks required for storing the node and all of its descendant nodes. In the second step we map the nodes to disk blocks using the assigned mapping indicator. We analyze the optimality of the proposed method with some relevant proofs. We also show the proposed method provides good performance for various query types with XML data set.
Secondly, we propose a set of XML data placement method for wireless air channels which support energy-efficient processing of queries over the wireless stream in mobile clients. The mobile clients can access the XML stream, organized by the proposed method, in a selective way through various kinds of link addresses to related data and signature information on the stream. After defining the BUX (Broadcast Unit of XML data) structure, which is our proposed structure for XML data placement wireless medium, we propose a set of event-driven stream generation and path query processing algorithms for the proposed stream structure. Through performance experiments, we show that our approaches can effectively improve the performance of XML data access and query processing on the wireless air medium.
최근에 XML은 인터넷 환경에서 정보의 표현과 교환의 표준이 되어가고 있다. XML는 마크업 언어로서 데이터의 컨텐츠와 표현을 나누어 서술할 수 있는 특징을 가지고 있다. XML 데이터는 루트 노드를 가진 트리 형태로 모델링 할 수 있기 때문에, 경로 질의가 XML 데이터에 대한 질의 형식으로 널리 사용되고 있다. 본 논문은 효율적인 경로 질의 처리를 위한 XML 데이터 배치 방법을 제안한다. 본 논문에서는 XML 데이터의 물리 매체에 대한 배치와 무선 매체에 대한 배치의 두 가지 방법을 다룬다.
첫번째로, 경로 질의 처리에 필요한 디스크 블록 접근 횟수를 최소화하도록 XML 데이터를 물리 저장소 매체(디스크)에 배치하는 효율적인 알고리즘을 제안한다. 제안하는 알고리즘은 두 단계로 구성된다. 첫번째 단계에서는 트리의 아래쪽에서 위쪽으로 각 노드마다 값(매핑 인디케이터)을 할당한다. 각 노드의 매핑 인디케이터는 그 노드와 그 노드의 모든 자손 노드들을 저장하였을 경우 접근에 필요한 최소 디스크 블록 횟수를 의미한다. 두번째 단계에서는 매핑 인디케이터 값을 이용하여 노드들을 디스크 블록으로 매핑한다. 그리고, 몇가지 증명을 통하여 제안한 방법의 최적성을 보인다. 또한 제안하는 방법이 XML 데이터의 다양한 질의 타입에서 좋은 성능을 보이는 것을 확인한다.
두번째로, 모바일 클라이언트가 무선 스트림 상에서 에너지 효율적인 질의 처리를 할 수 있도록 XML 데이터를 무선 채널에 배치하는 방법을 제안한다. 모바일 클라이언트는 본 논문에서 제안하는 방법을 통하여 관련된 데이터에 대한 다양한 링크 주소와 시그너쳐를 사용하여 XML 스트림을 선택적으로 접근할 수 있다. 무선 매체에 XML 데이터를 배치하기 위하여 BUX(XML 데이터의 방송 단위)라는 구조를 정의하였으며 이벤트 기반의 스트림 생성 알고리즘을 제안하고 제안한 스트림 구조 상에서 경로 질의를 처리하기 위한 알고리즘을 제안한다. 그리고, 성능 실험을 통하여 제안하는 방법에 의하여 XML 데이터에 효과적으로 접근할 수 있으며 무선 매체에서의 질의 처리 성능을 향상시키는 것을 보인다.
