XML 데이터베이스에서 효율적인 경로처리를 위한 구조적 세미조인 기법 = Structural Semi-Join Operators for Efficient Path Processing in XML Databases

국문 초록 (Abstract)

구조적 조인은 효율적인 XML 질의 처리를 위한 핵심 연산자 중의 하나이다. 구조적 조인은 대용량의 XML 노드들을 대상으로 계층관계(조상-자손 및 부모-자식관계)를 형성하는 쌍을 효율적으로 계산한다는 측면에서, 경로패턴으로 표현된 질의를 처리하는 데 주로 사용될 수 있다. 하지만 구조적 조인 알고리즘은 XML의 경로 처리과정에서 많은 오버헤드를 야기 시킨다. 이에 대한 개선된 연산자인 구조적 세미조인은 효율적인 처리를 위하여 XML 노드 간의 조인 결과를 조상노드 혹은 자손노드로 한정시키는 새로운 연산자이다. 본 논문에서는 구조적 세미조인 알고리즘을 소개하고, 구조적 세미조인을 이용한 경로처리 알고리즘을 제시한다. 실험을 통하여 개선된 방식의 구조적 세미조인 알고리즘이 XML 경로처리에 있어서 매우 효율적임을 보여준다.

다국어 초록 (Multilingual Abstract)

The structural join is one of core operators for efficient processing of XML queries. It can be mainly used for path-represented XML queries as it efficiently retrieves the node pairs that form a hierarchical relationship (i.e., ancestor-descendant, parent-child relationship) among large-scale XML nodes. However, the structural join algorithms still suffer potential overhead in the middle of processing of XML path queries. In addressing this problem, the structural semi-join is proposed as a novel operator that retrieves only the ancestor or descendant nodes as join results for efficient processing. In this paper, we describe the algorithms for the structural semi-join and present the methods of XML path processing based on the structural semi-join algorithms. The experimental results show that the structural semi-join algorithms are very efficient in processing XML path processing.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 구조적 세미조인
• 3. 구조적 세미조인을 이용한 다중경로패턴 처리
• 4. 실험결과
• 5. 결론
• 참고문헌

참고문헌 (Reference)

1 D. Srivastava, "Structural joins:A primitive for efficient XML query pattern matching" 141-152, 2002

2 Y. Wu, "Structural join order selection for XML query optimization" 443-454, 2003

3 S. Son, "Structural Semi-Join : A light-weight structural operator for efficient XML query pattern matching" 223-240, 2007

4 C. Zhang, "On supporting containment queries in relational database management systems"

5 C. Mathis, "Locking-aware structural join operators for XML query processing" 467-478, 2006

6 P. Mandawat, "Indexing schemes for efficient aggregate computation over structural joins" 55-60, 2005

7 Q. Li, "Indexing and querying XML data for regular path expressions" 361-370, 2001

8 N. Bruno, "Holistic twig joins: optimal XML pattern matching" 310-321, 2002

9 C. Mathis, "Hash-based structural join algorithms" 136-149, 2006

10 C. Luo, "Estimating XML structural join size quickly and economically" 62-62, 2006

11 K.-L. Wu, "Efficient structural joins with on-the-fly-indexing" 1028-1029, 2005

12 S.-Y. Chien, "Efficient structural joins on indexed XML documents" 263-274, 2002

13 K. Liu, "Efficient computation of aggregate structural joins" 21-30, 2003

14 H. Li, "An evaluation of XML indexes for structural join" 33 (33): 28-33, 2004