RDBMS에서의 효율적인 XML 부분 매치 질의 처리

Abstract

부분 매치 질의는 경로 질의 상에 조상-자손 관계성 '//'를 가지는 질의로 정의되며, 선형 경로 질의와 분기 경로 질의로 구분된다. 본 논문에서는 상이한 구조를 가지는 대규모 문서들에 대해서 부분 매치 질의를 효과적으로 처리하기 위하여 2가지 방법을 제안한다. 제안 방식은 기존의 순수 RDBMS를 기반을 두고 새로운 인덱스 기술과 조인 알고리즘을 사용하여 질의 처리 효율성과 확장성을 개선한다. 하나는 인덱스 구축을 위해 사용된 기법으로 경로 레이블 정보를 저장함에 있어서, 기존의 연구에서 사용된 순방향 레이블 경로 대신 역방향 레이블 경로를 사용하여 경로 인덱스를 구축한다. 구축된 인덱스는 대량의 상이한 구조의 문서가 존재하는 상황에서도 전체 매치 질의는 물론 부분 매치 질의 처리시 해당되는 레이블 경로들에 대하여 빠른 접근을 허용하여 질의 처리 성능을 개선시킨다. 또 하나는 선형 경로 질의 결과 간의 결합을 위해 사용되는 조인 알고리즘을 제안한다. 제안된 조인 알고리즘은 먼저 두 레이블 경로 간에 유효하지 않은 경로 연결을 식별하고 나서, 유효한 레이블 경로에 소속된 레이블 경로 인스턴스들만을 이용함으로써 조인 연산에 참여하는 튜플들의 비교 횟수를 줄인다. 제안 알고리즘은 단독 또는 조인 연산의 성능을 개선시키기 위하여 기존 조인 알고리즘과 함께 사용될 수 있다. 마지막으로, 제안방식의 효율성 검증을 위해 기존 연구들과의 비교 분석을 수행하였다.

A partial match query is defined as the one having the descendant-or-self axis '//' in its path query. It can be classified as a linear path query or a branching path query. In this thesis, we suggest two methods for processing partial match queries efficiently on a large amount of the differently-structured documents. One is the new index structure constructed using backward label paths instead of forward label paths used in previous researches for storing the path information. It allows for finding the label paths efficiently than the conventional methods and improves the performance of query processing. The other is the join algorithm used for merging results of linear path queries. The proposed algorithm reduces the number of the comparison of tuples that participate in join operation firstly by identifying invalid connections among the two label paths and then, using only abel path instances belong to valid path-connections. It can be used alone or to improve the performance of the join operation with the conventional join algorithm. Finally, We demonstrated the efficiency of the proposed method by comparing it with the conventional methods.