프리픽스 매취 조인을 이용한 XML 문서에 대한 분기 경로 질의 처리 = Branching Path Query Processing for XML Documents using the Prefix Match Join

국문 초록 (Abstract)

본 논문에서는 정보 검색(Information Retrieval, IR) 기술과 새로운 인스턴스 조인 기술을 이용하여 방대하고도 이질적인 XML 문서들에 대한 부분 매취 질의(Partial Match Query)를 처리하는 새로운 방법으로, XIR-Branching을 제안한다. 부분 매취 질의는 경로 표현식에 조상-후손 관계성 (descendent-or-self axis) "//"를 가지는 질의로 정의되며, 선형 경로 표현식(Linear Path Expression, LPE)과 분기 경로 표현식(Branching Path Expression, BPE)으로 구분된다. 일반적 형식의 부분 매취 질의는 분기하는 경로들을 만드는 분기 조건들을 가진다. XIR-Branching의 목적은 이질적인 스키마들을 가진 방대한 문서들에 주어지는 부분 매취 질의를 효과적으로 지원하는 것이다. XIR-Branching은 관계형 테이블을 사용하는 전통적인 스키마-레벨 방법들(XRel, XParent, XIR-Linear[21])에 그 기초를 두고, 역 인덱스(inverted index) 기술과 새롭게 소개하는 인스턴스-레벨 조인 기술인 프리픽스 매취 조인(Prefix Match Join)을 사용하여 질의 처리 효율성과 확장성을 향상시킨다. 전자는 LPE를 처리하기 위한 기술로 XIR-Linear[21]에서 사용한 방법이다. 후자는 BPE를 처리하기 위한 기술로 본 논문에서 새롭게 제안하는 기술이며, 전통적인 방법에서 사용하는 포함 관계 조인(containment join) 보다 효과적인 방법으로 결과 노드(result node)를 찾는다. 기존 연구인 XIR-Linear는 역 인덱스를 사용하여 LPE 처리에 우수한 성능을 보이고 있지만, BPE 처리 방법을 다루지 않았다. 그러나, 더욱 구체적이고 일반적인 질의를 위해서는 BPE도 처리할 수 있어야 한다. 본 논문에서는 BPE까지 다룰 수 있는 새로운 방법으로 기존의 XIR-Linear를 확장한 XIR-Branching을 제안한다. 제안하는 방법은 스키마-레벨 방법으로 질의 대상 후보 집합을 크게 줄인 후, 인스턴스-레벨 조인 방법인 프리픽스 매취 조인으로 최종 결과 집합을 효과적으로 구하는 방법이다. XIR-Branching의 우수성을 보이기 위해 기존 BPE 처리 방법인 XRel, XParent와 비교 분석을 수행한다. 마지막으로, 성능 평가를 통하여 XIR-Branching이 기존 방법들에 비해 수십에서 수백배 효과적이고 확장성 또한 뛰어남을 보인다.

다국어 초록 (Multilingual Abstract)

We propose XIR-Branching, a novel method for processing partial match queries on heterogeneous XML documents using information retrieval(IR) techniques and novel instance join techniques. A partial match query is defined as the one having the descendent-or-self axis "//" in its path expression. In its general form, a partial match query has branch predicates forming branching paths. The objective of XIR-Branching is to efficiently support this type of queries for large-scale documents of heterogeneous schemas. XIR-Branching has its basis on the conventional schema-level methods using relational tables(e.g., XRel, XParent, XIR-Linear[21]) and significantly improves their efficiency and scalability using two techniques: an inverted index technique and a novel prefix match join. The former supports linear path expressions as the method used in XIR-Linear[21]. The latter supports branching path expressions, and allows for finding the result nodes more efficiently than containment joins used in the conventional methods. XIR-Linear shows the efficiency for linear path expressions, but does not handle branching path expressions. However, we have to handle branching path expressions for querying more in detail and general. The paper presents a novel method for handling branching path expressions. XIR-Branching reduces a candidate set for a query as a schema-level method and then, efficiently finds a final result set by using a novel prefix match join as an instance-level method. We compare the efficiency and scalability of XIR-Branching with those of XRel and XParent using XML documents crawled from the Internet. The results show that XIR-Branching is more efficient than both XRel and XParent by several orders of magnitude for linear path expressions, and by several factors for branching path expressions.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 연구 배경
• 3. 관련 연구
• 4. XML 저장 구조
• 5. XIR 질의 처리 알고리즘
• 6. 성능 평가
• 7. 결론
• 참고문헌
• 저자소개

참고문헌 (Reference)

1 "정보 검색 기술을 이용한 대규모 이질적인 XML 문서에 대한 효율적인 선형 경로 질의 처리" 31 (31): 2004년10월

2 "eXtensible Markup Language(XML)"

3 "a High-Performance ORDBMS Tightly-Coupled with IR Features National Center of Sciences" National Center of Sciences 2005.4

4 "Xyleme"

5 "XRel: A Path-based Approach to Storage and Retrieval of XML Documents using Relational Databases" 110-141, 2001

6 "XRANK: Ranked Keyword Search over XML Documents" 16-27, 2003.6

7 "XR-Tree: Indexing XML Data for Efficient Structural Joins" 253 5-264 8, 2003

8 "XQuery/ IR: Integrating XML Document and Data Retrieval" 1-6, 2002

9 "XParent: An Efficient RDBMS-Based XML Database System" 335-336, 2002.3

10 "XML Path Language (XPath), W3C Recommendation" (v) : 1999.11

11 "The Niagara Internet Query System" 27-33, 2001.6

12 "Teleport Pro Version 1.29"

13 "Structural Joins: A Primitive for Efficient XML Query Pattern Matching" 141-152, 2002.5

14 "Structural Joins: A Primitive for Efficient XML Query Pattern Matching" 141-152, 2002.3

15 "Storing and Querying Ordered XML Using a Relational Database System" 204-215, 2002.6

16 "Statistical Synopses for Graph-structured XML Databases" 358-369, 2002.6

17 "Sentences for Example-Based Machine Translation" 2002.6

18 "ReGet Deluxe 3.3 Beta(build 173),"

19 "Query Optimization for XML" 315 7-326 10, 1999.9

20 "Path Materialization Revisited: An Efficient Storage Model for XML Data" 85 28-94, 2002.2

21 "On Supporting Containment Queries in Relational Database Management Systems" 425-436, 2001.5

22 "Odysseus: a High-Performance ORDBMS Tightly-Coupled with IR Features" KAIST 2004.12

23 "Mixed Mode XML Query Processing" 225 9-236 12, 2003.9

24 "Introduction to Modern Information Retrieval" McGraw-Hill

25 "Integrating Keyword Search into XML Query Processing" 119-135, 2000.5

26 "Indexing and Querying XML Data for Regular Path Expressions" 361 11-370 14, 2001.9

27 "Holistic Twig Joins: Optimal XML Pattern Matching" 310-321, 2002.6

28 "Holistic Twig Joins on Indexed XML Documents" 273 9-284 12, 2003.9

29 "Estimating the Selectivity of XML Path Expressions for Internet Scale Applications" 591 11-600 14, 2001.9

30 "Efficient Filtering of XML Documents for Selective Dissemination of Information" 53 10-64 14, 2000.9

31 "Efficient Evaluation of Regular Path Expressions on Streaming XML Data" University of Washington 2000

32 "DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases" 436 26-445 29, 1997.8

33 "Covering Indexes for Branching Path Queries" 133-144, 2002.6

34 "A Fast Index for Semistructured Data" 341 11-350 14, 2001.9