XML data can be represented by a tree or graph structure and XML query processing requires the information of structural relationships among nodes. The basic structural relationships are parent-child and ancestor-descendant, and finding all occurrences of these basic structural relationships in an XML data is clearly a core operation in XML query processing. Several node labeling schemes have been suggested to support the determination of ancestor-descendant or parent-child structural relationships simply by comparing the labels of nodes. However, the previous node labeling schemes have some disadvantages, such as a large number of nodes that need to be relabeled in the case of an insertion of XML data, huge space requirements for node labels, and inefficient processing of structural joins.
Additionally there is a growing interest in the data model and query processing for probabilistic XML data. There are many potential applications of probabilistic data, and the XML data model is suitable to represent hierarchical information and data uncertainty of different levels naturally. However, the previously proposed probabilistic XML data models and query processing techniques separate finding data matches and evaluating the probabilities of results. Therefore, they should repeatedly access the data and need to get full data of paths given in queries to calculate the probabilities of results.
In order to support efficient XML query and update processing, we propose the nested tree structure that eliminates the disadvantages and takes advantage of the previous node labeling schemes. The nested tree structure makes it possible to use the dynamic interval-based labeling scheme, which supports XML data updates with almost no node relabeling as well as efficient structural join processing.
In addition, we suggest an extended interval-based labeling scheme for the probabilistic XML data tree and an efficient query processing procedure using the labeling scheme. Against previous researches, our method accesses only the labels of data specified in queries and finds data matches simultaneously with evaluating the probability of each data match. Also, we present an extended probabilistic XML query model with the predicates for the values of probabilities and a lightweight index for those probabilities in order to eliminate unnecessary accesses to data that will not be included in results.
Experimental results show that the dynamic interval-based labeling scheme is efficient in handling updates and also significantly improves the performance of the structural join processing compared with recent methods. In the case of the extended interval-based labeling scheme, the labeling scheme is efficient in probabilistic XML query processing and our index scheme significantly improves the performance of query processing when the predicates for the values of probabilities are given.
효율적인 XML 질의 처리를 위해 다양한 노드 레이블링 기법들이 활용될 수 있다. 본 학위논문에서는 일반적인 XML 데이터에 대한 질의 및 업데이트를 효율적으로 처리하기 위한 레이블링 기법과 확률적 XML 데이터에 대한 효율적인 질의 처리를 위한 레이블링 기법을 소개한다.
XML 데이터는 트리 또는 그래프 구조로 표현될 수 있으며 이러한 XML 데이터에 대한 질의 처리는 트리 또는 그래프 노드들간의 구조 관계에 대한 정보를 필요로 한다. 가장 기본적인 구조 관계는 부모-자식(parent-child) 관계와 조상-자손(ancestor-descendant) 관계들로서 주어진 XML 데이터에 대해서 이러한 기본 관계 구조에 해당되는 모든 데이터를 찾아내는 것이 XML 질의 처리의 핵심 기능이다. XML 질의 처리를 위해 노드들의 레이블값 비교를 통해서 조상-자손 관계 또는 부모-자식 관계에 대한 판단을 쉽게 처리할 수 있도록 지원하기 위한 여러 가지 노드 레이블링 기법들이 제안되었다. 하지만, 이전의 노드 레이블링 기법들은 XML 데이터가 추가되는 경우 많은 노드들에 대해 다시 레이블링을 하거나, 노드 레이블을 위해 많은 공간이 요구되거나, 또는 비효율적인 구조상의 조인(structural join) 등과 같은 단점을 가지고 있다. 또한, 최근에는 확률적 XML 데이터에 대한 모델과 질의 처리에 대한 관심이 높아지고 있다. 확률적 데이터를 이용하는 많은 응용들이 있으며, XML 데이터 모델은 구조적 정보 및 서로 다른 수준의 데이터에 대한 불확실성을 표현하기에 적합하다. 하지만, 이전에 제안된 확률적 XML 데이터 모델과 질의 처리 기술은 질의에 매치되는 데이터를 찾는 과정과 각 결과에 대한 확률을 계산하는 과정을 분리하여 처리한다. 따라서 이전의 방법들은 반복적으로 데이터에 접근해야 하고 결과에 대한 확률 계산을 위해서 질의에서 주어진 경로에 해당되는 전체 데이터를 다시 읽어야만 한다.
효율적인 XML 질의 및 업데이트 처리를 위해서 본 논문에서는 이전에 제안된 노드 레이블링 기법의 단점을 제거하고 장점을 취한 네스티드 트리 구조(Nested Tree Structure)를 제안한다. 네스티드 트리 구조는 노드에 대한 레이블링을 다시하지 않으면서 XML 데이터 업데이트를 처리할 수 있을 뿐만 아니라 효율적인 구조상의 조인을 가능하게 하는 동적 구간 기반 레이블링 기법(Dynamic Interval-based Labeling Scheme)을 가능하게 한다.
그리고 본 논문에서는 확률적 XML 데이터를 위한 확장된 구간 기반 레이블링 기법(Extended Interval-based Labeling Scheme)과 그 레이블링 기법을 활용한 효율적인 질의 처리 방법을 제안한다. 이전에 제안된 방법들과 비교할 때 본 논문에서 제안하는 레이블링 기법은 질의에서 언급된 데이터에 대한 레이블 값만을 이용하여 질의 처리가 가능하며 동시에 결과에 대한 확률 계산을 가능하게 한다. 또한, 본 논문에서는 확률값에 대한 조건을 줄 수 있는 확장된 확률적 XML 질의 모델과 확률값에 대한 경량 인덱스(Lightweight Index)를 제안하여 결과에 포함되지 않는 데이터에 대한 접근을 제거하는 방법을 제시한다.
마지막으로 실험 결과는 동적 구간 기반 레이블링 기법이 이전의 레이블링 기법과 비교할 때 XML 질의 및 업데이트 처리에 대한 성능을 향상시키고 있음을 보여준다. 또한, 확장된 구간 기반 레이블링 기법의 경우, 제시된 레이블링 기법이 확률적 XML 질의 처리에 효율적이며, 또한 제시된 인덱스 방법이 확률값에 대한 조건이 주어진 질의 처리에 대한 성능을 향상시킴을 보여준다.