경로 기반의 효율적인 XML 질의 처리 기법

다국어 초록 (Multilingual Abstract)

Since XML emerged as a standard of data exchange and representation on the web, there has been extensive research conducted on XML data processing and management. In the near future, we expect the era of ubiquitous computing where the mobile devices such as smart phones play a key role in full blossom, and we still need to investigate into more effective XML query processing for such an environment because the mobile devices are limited in resources.

In this thesis, we describe research on XML query processing when XML document is stored in the database server, and user queries in XPath need to be processed in a more efficient way. First of all, we examine background knowledge and previous work. Among others we focus on tag name-based query processing which is now regarded as the most representative approach to XML query processing, and analyze the problems inherent in that approach. It has the following two major limitations: First, its query tree consists of tag name-labeled nodes. As such, when the XML node list for each query tree node is retrieved from the XML database, the retrieval is through tag name match. Thus, for a query tree node, all the irrelevant XML nodes with the same tag name but not on the target path are retrieved as well. Secondly, though only a subset of the query tree nodes needs to be dealt with in producing a correct query result, every query tree node is accessed for structural joins that check the parent-child or ancestor-descendant relationship. As such, query performance is degraded.

To overcome these problems, we investigate into path-based query processing using the reduced query tree. First, instead of the conventional tag name-based query tree, we employ its path-based reduced query tree to eliminate unnecessary structural joins. Secondly, when the XML node list is retrieved, we conduct path identifier match instead of tag name match, avoiding the retrieval of the XML nodes irrelevant to the query. This approach results in a significant improvement in query performance in most of the queries. Its overhead is the transformation of the tag name-based query tree into its reduced counterpart, and the storage space for the tag structure of the XML document. Through implementation and extensive set of experiments, we show that the path-based approach outperforms the tag name-based one and that the aforementioned overhead is negligible.

국문 초록 (Abstract)

XML이 웹에서 데이터 교환 및 표현의 표준으로 확립되면서 XML 데이터의 처리 및 관리에 대한 여러 연구가 활발히 진행되고 있다. 향후에는 스마트폰 등의 이동 단말기를 사용하는 유비쿼터스 컴퓨팅 시대가 본격적으로 도래 하면서, 이들 이동 단말기의 제약된 자원 때문에 보다 효율적인 XML 질의 처리에 대한 연구가 필요하다고 할 수 있다.

본 논문은 XML 문서가 서버의 데이터베이스에 저장되어 있고, 사용자들이 XPath 질의를 요청했을 때 그 결과를 반환하기까지의 질의 처리 과정을 보다 빠르고 효율적으로 처리하는 기법에 관한 것이다. 먼저, 이러한 연구를 위해 필요한 배경 지식과 기존 연구들을 살펴보았다. 기존 연구의 주류를 구성하는 태그 이름 기반의 질의 처리 방식에 대해서 자세히 살펴보고, 이 방식의 문제점을 분석하였다. 태그 이름 기반의 질의 처리 방식에서는 태그 이름을 노드로 하는 질의 트리의 각 노드에 해당되는 XML 노드 리스트를 검색할 때, 태그 이름으로 검색하기 때문에 실제로는 질의 트리의 해당 경로 상에 존재하지 않지만 같은 태그 이름을 가진 XML 노드들도 불필요하게 검색된다는 문제점이 있다. 또한, 질의의 결과를 나타내기 위해서 실제로 접근이 필요한 질의 트리의 노드는 모든 노드가 아니라, 일부 노드임에도 불구하고, 모든 노드의 부모-자식 및 조상-후손 관계를 점검하면서, 구조조인을 하기 때문에 질의 처리 성능이 저하된다는 문제점도 있다.

이러한 문제점을 극복하기 위해 본 논문에서는 단축 질의 트리를 이용한 경로 기반의 질의 처리 방식을 연구하였다. 먼저 기존의 태그 이름 기반의 질의 트리 대신에, 경로 기반의 단축 질의 트리를 사용하여, 불필요한 구조조인의 과정을 줄였다. 또한, 단축 질의 트리의 각 노드에 해당되는 XML 노드 리스트를 검색할 때, 태그 이름으로 검색하는 대신, 경로 식별자를 이용한 검색을 통해서, 질의 처리에 필요 없는 노드에 대한 검색을 차단하였다. 이를 통해 대부분의 질의에 대해 큰 성능 향상을 가져올 수 있다. 그러나 이러한 방식의 질의 처리가 갖는 부담은, 기존의 태그 이름 기반의 질의 트리를 단축 질의 트리로 변환하는 것과, 경로 식별자를 이용한 검색을 위해 XML 문서의 태그 구조에 대한 저장 공간을 추가로 필요로 한다는 것이다. 구현 및 다양한 실험을 통한 성능평가에서 본 논문에서 제안하는 경로 기반의 질의 처리 방식이 기존의 태그 이름 기반의 방식에 비해 더 효율적이라는 것과, 성능 향상에 비해서 부담은 아주 미비하다는 것을 확인하였다.

목차 (Table of Contents)

• 제 1 장 서론 1
• 1.1 연구 배경 1
• 1.2 본 논문의 목적 2
• 1.3 본 논문의 구성 3
• 제 2 장 관련 연구 5
• 2.1 배경 지식 5
• 2.1.1 XML의 태그 구조 5
• 2.1.2 XPath 7
• 2.2 기존 연구 12
• 2.2.1 XML 저장 12
• 2.2.2 XML 레이블링 기법 15
• 2.2.3 XML 질의 처리와 구조 조인 21
• 제 3 장 태그 이름 기반의 질의처리 25
• 3.1 XPath식의 질의트리 변환 25
• 3.2 질의트리의 자료구조 27
• 3.3 질의트리에서의 구조조인 30
• 3.4 질의트리에서의 XML 노드 리스트 검색을 위한 SQL문 34
• 3.5 태그 이름 기반 질의 처리의 문제점 35
• 제 4 장 경로 기반의 질의처리 37
• 4.1 XPath 스텝 단축 37
• 4.2 경로 기반의 질의 처리 39
• 4.2.1 질의트리의 단축질의트리 변환 41
• 4.2.2 단축질의트리의 자료구조 43
• 4.2.3 단축질의트리에서의 XML 노드 리스트 검색을 위한 SQL문 44
• 제 5 장 구현 및 성능평가 47
• 5.1 실험 환경 47
• 5.2 실험에 사용된 질의 집합 50
• 5.3 질의의 길이에 따른 성능평가 51
• 5.4 질의의 형태에 따른 성능평가 53
• 5.5 경로 기반 질의 처리의 공간 부담 66
• 제 6 장 결론 및 향후 연구 69
• 참고문헌 72
• 부록 76
• 국문초록 81
• Abstract 83