서지주요정보
대규모 이질적인 XML 문서에 대한 부분 매치 질의 처리 = Partial match query processing for large-scale heterogeneous XML documents
서명 / 저자 대규모 이질적인 XML 문서에 대한 부분 매치 질의 처리 = Partial match query processing for large-scale heterogeneous XML documents / 박영호.
저자명 박영호 ; Park, Young-Ho
발행사항 [대전 : 한국과학기술원, 2005].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8016874

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 05025

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

Partial match queries are particularly useful for searching XML documents when their schemas are heterogeneous while only partial schema information is known to the user such as a search in Internet. The partial match query is defined as the one having the descendent-or-self axis "//" in its path expression. Since they play key roles in XML databases and require a significant cost of processing, efficient algorithms for partial match queries are crucial for improving performance of XML databases. Partial match queries can be classified into linear path expressions (LPEs) and branching path expressions (BPEs). An LPE is defined as a path expression consisting of a sequence of labels having a parent-child relationship or an ancestor-descendent relationship between labels; a BPE is defined as a path expression having branching conditions for one or more labels in the LPE. In this dissertation, we propose two methods: XIR-Linear and XIR-Branching. The former is a method using the information retrieval (IR) technique for handling the LPE. The latter is an extension of XIR-Linear using a novel join technique to handle BPEs. In the first part of the dissertation, we propose XIR-Linear, a method for efficiently evaluating LPEs on large-scale heterogeneous XML documents using in-formation retrieval (IR) techniques. LPEs are the primary form of XPath queries, and their evaluation techniques have been researched actively. XPath queries in their general form are partial match queries, and these queries are particularly useful for searching documents of heterogeneous schemas. Thus, XIR-Linear is geared for partial match queries expressed as LPEs. XIR-Linear has its basis on existing methods using relational tables (e.g., XRe1, XParent), and drastically improves their efficiency using the inverted index technique. Specifically, it indexes the labels in label paths (i.e., sequences of node labels) like keywords in texts, and finds the label paths matching the LPE far more efficiently than string match used in the existing methods. We demonstrate the efficiency of XIR-Linear by comparing it with XRel and XParent using XML documents crawled from the Internet. The results show that XIR-Linear outperforms XRe1 and XParent by an order of magnitude for linear path expressions. In the second part of the dissertation, we propose XIR-Branching, a new method for processing partial match queries on heterogeneous XML documents using information retrieval (IR) techniques and novel instance join techniques. As a general form, a partial match query has branch predicates forming branching paths. This general query type is the BPE. The objective of XIR-Branching is to efficiently support this type of queries for large-scale documents of heterogeneous schemas. XIR-Branching significantly improves their efficiency and scalability using two techniques: an inverted index technique and a novel prefix match join. The former is the method used in XIR-Linear for processing LPEs. The latter supports BPEs and allows for finding the result nodes more efficiently than containment joins used in the conventional methods. XIR-Branching reduces the candidate set for a query by using the information retrieval (IR) technique as a schema-level method, and then, efficiently finds a result set by using the prefix match join as an instance-level method. We compare the efficiency and scalability of XIR-Branching with those of XReI and XParent using XML documents crawled from the Internet. The results show that XIR-Branching is more efficient than both XReI and XParent by several factors for BPEs. In summary, the dissertation proposes new methods for processing linear path expressions (LPEs) and branching path expressions (BPEs). For the proposed methods, we have presented the storage structures including the tables storing all label paths and node paths of the XML documents and the inverted index. Based on these structures, we have presented the query processing algorithms for LPEs and BPEs. Then, we have compared the performances of them with those of XReI and XParent through experiments. The results show that our methods are significantly more efficient and scalable than XReI or XParent for both LPEs and BPEs with the performance gap widening as the database size grows. The importance of this dissertation is in enhancing the XML document query processing to be applicable in the Internet scale. The proposed techniques can be easily incorporated into conventional XML document search engines.

부분 매치 질의 (Partial match queries)는 그들의 스키마가 이질적일 때 인터넷 검색과 같이 사용자에게 부분적 스키마 정보만이 알려진 경우에 특히 유용하다. 부분 매치 질의는 그것의 경로 표현식 (path expression)에 descendent-or-self 축 "//"을 가지고 있는 질의로서 정의된다. 그들은 XML 데이타베이스에서 주요한 역할을 담당하고 처리의 비용이 크기 때문에 부분 매치 질의들을 위한 효과적인 알고리즘들은 XML 데이타베이스들의 성능을 향상시키는데 매우 중요하다. 부분 매치 질의는 선형 경로 표현식 (linear path expressions, LPEs) 과 분기 경로 표현식(branching path expressions, BPEs)으로 구분될 수 있다. LPE는 레이블들 간에 부모-자깃 관계성이나 조상-후손 관계성을 가지는 레이블들의 시퀀스를 구성하는 경로 표현식으로 정의된다. BPE는 그 LPE내에 하나 이상의 레이블들이 분기하는 조건을 가지는 경로 표현식으로 정의된다. 본 학위 논문에서는 XIR-Linear와 XIR-Branching의 두가지 방법을 제안한다. 전자는 LPE를 처리하기 위하여 정보 검색 기술 (information retrieval, IR) 기술을 사용하는 방법이다. 후자는 BPE를 처리하기 위하여 새로운 조인 기술을 사용하여 XIR-Linear를 확장한 방법이다. 본 학위 논문의 전반부에서는 XIR-Linear를 소개한다. 이 방법은 IR 기술을 이용해서 대규모 이질 XML 문서들에 대한 LPE를 효과적으로 처리하기 위한 방법이다. LPE는 XPath 질의의 기본적인 형태이고, 그들의 처리 기술은 활발히 연구되어왔다. LPE 질의의 일반적인 형태로서의 XPath 질의는 부분 매치 질의(partial match query)이고, 이들 질의들은 이질적인 스키마를 가진 문서들을 찾는데 특히 유용하다. 그러므로, XIR-Linear는 LPE로서 표현된 부분 매치 질의에 초점을 맞추고 있다. XIR-Linear는 관계형 테이블을 사용하는 기존 방법들(XRel, XParent)에 그 기초를 두고, 역 인덱스 기술을 사용하여 그들의 효율성을 놀랍게 향상시킨다. 구체적으로, XIR-Linear는 레이블 경로에 존재하는 레이블들을 텍스트 내에 존재하는 키워드들과 같이 인덱스하고, 기존 방법들에서 사용해 온 스트링 매치 보다 훨씬 효과적으로 주어진 LPE에 매칭하는 레이블 경로들을 찾는다. XIR-Linear의 LPE 처리 효율성과 확장성을 보이기 위하여 XRel과 XParent와 비교하였다. 비교 결과 XIR-Linear는 XRel이나 XParent 보다 수십(백)배 우수한 LPE처리 능력을 가졌다는 것을 보이고 있다. 본 학위 논문의 후반부에서는 XIR-Branching을 소개한다. 이 방법은 정보 검색(information retrieval, IR) 기술과 새로운 인스턴스 조인 기술을 사용하여 이질적인 XML 문서들에 대한 부분 매치 질의를 처리하기 위한 새로운 방법이다. 부분 매치 질의의 일반적인 형태는 분기하는 경로들을 형성하는 분기 조건들을 가지는 형태이다. 이러한 일반적인 질의 타입은 BPE가 된다. XIR-Branching의 목적은 이질적인 스키마를 가지는 대규모 문서들에 대하여 BPE 타입의 질의를 효과적으로 지원하는 것이다. XIR-Branching은 두가지 기술을 이용하여 BPE 처리 효율성과 확장성을 의미있게 향상시킨다. 그 두 가지 기술은 역 인덱스 기술과 새로운 프리픽스 매치 조인이다. 전자는 XIR-Linear에서 사용된 방법으로 LPE를 지원한다. 후자는 BPE를 지원하고, 전통적인 방법에서 사용된 포함 관계 조인들 보다 효과적으로 결과 노드들을 발견할 수 있게 해 준다. XIR-Branching은 스키마-레벨 방법으로서 정보 검색 기술을 사용하여 그 질의에 대한 후보 집합을 줄인 다음 효과적 인스턴스-레벨 방법으로서 새로운 프리픽스 매치 조인 방법을 사용하여 결과 집합을 효과적으로 찾는다. 본 논문에서는 XIR-Branching의 BPE 처리 능력을 효율성과 확장성의 측면에서 XRel 및 XParent와 비교하였다. 이를 위해 인터넷으로 부터 크로울한 XML 문서들을 사용하여 실험하였다. 실험 결과 XIR-Branching은 XRel이나 XParent 보다 수배 우수한 BPE처리 능력을 가졌다는 것을 보이고 있다. 요약하면, 본 학위 논문에서는 LPE와 BPE를 처리하기 위한 새로운 방법을 제안하였다. 이를 위해 XML 문서들의 모든 레이블 경로와 그에 대한 역 인덱스 그리고, 노드 경로들을 저장하는 테이블들을 포함하는 모든 저장 구조를 제안하였다. 이들 구조에 기반하여 본 논문에서는 LPE와 BPE를 처리하기 위한 질의 처리 알고리즘을 제안하였다. 이후 실험을 통하여 XRel과 XParent와 제안하는 두 가지 방법의 성능을 비교하였다. 비교 결과는 LPE와 BPE의 처리 성능이 XRel이나 XParent에 비해 매우 효과적이고 확장 가능하며, 데이타베이스의 크기가 커짐에 따라 점차적으로 그 성능 차이가 커진다는 것을 보인다. 본 학위 논문의 중요성은 인터넷과 같은 방대한 규모의 질의 환경에서 XML 문서에 대한 질의 처리 성능을 크게 향상 시킬 수 있다는 점에 있다. 제안된 기술들은 전통적인 XML 문서 검색 엔진들로 쉽게 적용될 수 있다.

서지기타정보

서지기타정보
청구기호 {DCS 05025
형태사항 xii, 78 p. : 삽도 ; 26 cm
언어 한국어
일반주기 저자명의 영문표기 : Young-Ho Park
지도교수의 한글표기 : 황규영
지도교수의 영문표기 : Kyu-Young Whang
학위논문 학위논문(박사) - 한국과학기술원 : 전산학전공,
서지주기 참고문헌 : p. 70-75
주제 XML
역인덱스
프리픽스 매치 조인
부분 매치 질의
선형 경로 표현식
분기 경로 표현식
XML
inverted index
prefix match join
partial match queries
linear path expressions
branching path expressions
QR CODE qr code