[논문]XML 데이타베이스에서 경로-지향 질의처리를 위한 병렬 매치 방법

박희숙; 조우현

문제 정의

XQL과 XML-QL 같은 몇 가지 경로-지향 질의 언어들이 XML문서들의 교차 참조(cross-reference) 및 애트리뷰트들과 엘리먼트들을 트리와 같은 구조로 다루기 위해 제안되었다. 다음은 그림 1의 XML문서에 대한 간단한 경로-지향 질의어 예이다.
따라서 N의 수가 커지면 키의 비교 횟수도 증가하게 된다. 본 논문에서는 많은 적합한 엘리먼트들을 검색하는데 있어서 경로서명 매치 작업을 수행할 때 성능을 개선하기 위한 새로운 접근법으로 병렬 매치 인덱싱 구조와 병렬 매치 알고리즘 의사용을 제안한다.
이진 트라이에서 최대 레벨은 경로서명의 길이(h)와 같다. 본 논문은 XML문서의 모든 엘리먼트들에 대한 경로 서명들을 이진 트라이로 구성하는 알고리즘 설계로부터 시작한다. 예를 들어 하나의 XML문서내의 모든 엘리먼트들에 대한 경로서명 파일의 내용이 다음과 같다고 하자.
평가를 수행 하여야만 한다. 본 논문에서 우리는 관계형 데이타베이스에 저장된 XML문서에 대한 경로- 지향 질의어 처리 평가 속도를 개선하기 위해 병렬 매치 인덱싱 구조와 병렬 매치 알고리즘에 대한 설계 및 구현과 그에 대한 성능 실험을 수행하였다. 이진 트라이는 이진 비트 패턴내에 연속적인 비트 값들을 이용하여 루트에서부터 아래쪽으로 향하는 트라이의 경로를 결정한다.

제안 방법

이것은 본 논문에서 제안하는 방법과 유사한 방법을 사용하고 있다[14L 그러나 본 논문에서는 텍스트가 아닌 경로에 기반을 둔 XML문서를 검색대상으로 하며, 평가를 하고자하는 질의어 형태는 Xpath등과 같은 경로-지향 질의를 평가대상으로 한다. 또한, 각 엘리먼트들에 대한 경로 정보를 고려한 경로서명 파일을 생성하며, 관계형 데이타베이스에 저장된 XML문서에 대한 평가를 위해 경로-지향 질의어가 입력될 때 이들의 검색 속도를 개선하기 위해 이 경로서명 파일을 이용하여 병렬 매치 인덱싱 구조를 구성한다.
실행한다. 첫째, 생성된 경로서명 파일을 이용하여 이진 트라이 구조를 구성한다. 둘째, 구성된 이진 트라이 구조를 프로세스 엘리먼트(Process Element: PE)들로 구성된 병렬 매치 인덱싱 구조 (Parallel Match Indexing Fabric: PMIF)로 변환한다.
가려내는 것이다. 본 논문의 실험에 사용되는 각 엘리먼트의 경로서명 값은 XML문서의 파싱 과정에서 각 엘리먼트들의 경로 정보를 고려하여 생성한다. 즉, 루트 엘리먼트에서 각 엘리먼트에 이르는 경로 상에 존재하는 모든 엘리먼트들의 첫 번째 머리글자만을 추출하고 이들을 결합(concatenation)하여 각 엘리먼트의 경로 서명 값을 생성한다.
본 장에서는 XML문서가 파싱되어 데이타베이스 내부에 저장되는 형태와 경로서명 파일을 이용하여 병렬 매치 인덱싱 구조를 구성하는 방법 그리고 이들에 대한 병렬 매치 알고리즘 수행에 관하여 기술한다.
본 논문에서는 적합한 엘리먼트들을 검색하는데 있어서 검색 성능올 향상시키기 위해 그림 3의 이진 트라이구조를 병렬 매치 구조로 변환한다. 병렬 매치 구조로 변환하는 작업은 그림 3의 이진 트라이 구조에서 각 증간 노드인 분기노드를 PE로 변환하고 정보노드에는 경로 서명 파일내의 경로서명들에 대한 정보를 저장한다.
이 트라이에서 루트 노드에서부터 단말 노드까지 이르는 비트 스트링은 경로서명과 동일하다. 본 논문의 병렬 매치 알고리즘은 경로서명 매치 작업 수행을 위해 2가지 단계로 구성된다. 첫 번째 단계 수행 후 트라이에서레벨 1의 루트 노드는 매치하려는 경로서명의 가장 왼쪽 비트 값을 가지며 레벨 [의 노드들은 그들의 z.
하드웨어는 윈도우즈 2000 운영체제를 탑재한 펜티엄 4 시스템으로 메모리 1GB, CPU 속도 L7GHz, HDD 80GB 그리고 데이타베이스 시스템으로는 Oracle 9i를 사용하여 수행하였다. 또한, 실험을 위한 시스템의 구현은 C++언어와 JAVA를 사용하여 소프트웨 어 적 으로 구현하였다.
시스템의 성능 실험을 위해 입력되는 경로-지향 질의어의 경로는 모두 절대위치경로(absolute location path) 형태로 입력하였으며, 경로-지향 질의 유형은 단순 경로들만 입력하는 형태와 술어를 힘꺼) 포함하는 형태 2가지로 실험하였다. 실험에 사용한 데이타들은 표 1과 같다.
이진 트라이는 이진 비트 패턴내에 연속적인 비트 값들을 이용하여 루트에서부터 아래쪽으로 향하는 트라이의 경로를 결정한다. 본 논문에 제안한 접근법에서는 XML문서에 포함된 각 엘리먼트들의 경로 정보를 저장하기 위해 단축- 경로를 생성하고, 이들을 경로서명 파일에 저장한 후 이진 트라이 구조를 형성하는데 활용하였으며, 경로-지향질의어에 대한 평가속도를 개선하기 위해 이진 트라이구조를 병렬 매치 인덱싱 구조로 변환하였다. 또한, 제안된 구조를 이용하여 병렬 매치 처리를 수행하기 위한 병렬 매치 알고리즘을 설계하였다.
본 논문에 제안한 접근법에서는 XML문서에 포함된 각 엘리먼트들의 경로 정보를 저장하기 위해 단축- 경로를 생성하고, 이들을 경로서명 파일에 저장한 후 이진 트라이 구조를 형성하는데 활용하였으며, 경로-지향질의어에 대한 평가속도를 개선하기 위해 이진 트라이구조를 병렬 매치 인덱싱 구조로 변환하였다. 또한, 제안된 구조를 이용하여 병렬 매치 처리를 수행하기 위한 병렬 매치 알고리즘을 설계하였다. 본 논문에서 제안한 방법을 이용한 성능 실험 분석 결과에 따르면 제안된 알고리즘은 XML문서 파일에 대한 경로서명 엔트리 수에 대해 log2N과 유사한 크기 순서를 가진다.

대상 데이터

병렬 매치 방법에 관한 기존의 연구는 주로 텍스트 문서 검색을 위한 방법들이 주류였으며, 그들 중에서 가장 대표적인 것으로는 SIMD 컴퓨터 구조와 수평적 서명 분할법을 사용하는 방법이 Stanfill 과 Kahle에 의해 이미 연구된 바 있다. 이것은 본 논문에서 제안하는 방법과 유사한 방법을 사용하고 있다[14L 그러나 본 논문에서는 텍스트가 아닌 경로에 기반을 둔 XML문서를 검색대상으로 하며, 평가를 하고자하는 질의어 형태는 Xpath등과 같은 경로-지향 질의를 평가대상으로 한다. 또한, 각 엘리먼트들에 대한 경로 정보를 고려한 경로서명 파일을 생성하며, 관계형 데이타베이스에 저장된 XML문서에 대한 평가를 위해 경로-지향 질의어가 입력될 때 이들의 검색 속도를 개선하기 위해 이 경로서명 파일을 이용하여 병렬 매치 인덱싱 구조를 구성한다.
위한 방법이다. 그렇기 때문에 본 논문에는 우리와 동일하게 XML문서에 대한 한 경로-지향 질의어 평가를 위해 연구된 Ch印의 방법[8]을 성능비교 대상으로 삼는다.

이론/모형

XML문서에 대한 경로-지향 질의어 평가를 위해서는 XML문서 내의 모든 엘리먼트(Element)들의 경로와 검색을 위해 입력되는 경로-지향 질의어의 경로들 사이에 매치(Match)를 수행하기 위해 매치 알고리즘을 사용한다. 이것은 인덱싱 시스템의 성능을 측정하는데 있어서 중요한 핵심요소이다.
본 논문에서는 경로서명을 이용하여 경로-지향 질의어의 평가 처리 속도를 개선하기 위해 병렬 매치 방법을 사용한다. 병렬 매치 방법에 관한 기존의 연구는 주로 텍스트 문서 검색을 위한 방법들이 주류였으며, 그들 중에서 가장 대표적인 것으로는 SIMD 컴퓨터 구조와 수평적 서명 분할법을 사용하는 방법이 Stanfill 과 Kahle에 의해 이미 연구된 바 있다.
본 논문에서는 경로-지향적 질의어의 평가 성능을 개선하기 위해 병렬 매치 인덱싱 구조를 사용한다. 병렬 매치 인덱싱 구조는 기존의 이진 트라이(Binary Trie) 구조와 유사하다.

성능/효과

둘째, 구성된 이진 트라이 구조를 프로세스 엘리먼트(Process Element: PE)들로 구성된 병렬 매치 인덱싱 구조 (Parallel Match Indexing Fabric: PMIF)로 변환한다. 셋째, 평가를 위해 입력된 경로-지향 질의에 포함된 엘리먼트들의 경로 서명 값을 생성하고 연속적인 이진 비트 패턴(binary bit pattern)들로 이루어진 이들의 경로서명 값을 비트 단위로 루트에서부터 아래쪽으로 연결된 각 PE들로 입력된 값을 순차적으로 전달한다. 넷째, 병렬 매치를 수행하기 위해 루트 PE에 매치 처리 수행 시작 신호를 입력한다.
첫째, 사용자가 입력한 경로-지향 질의어에 포함된 경로들의 경로 서명을 생성한 다음 병렬 매치 인덱싱 구조로 전달한다.
셋째, 질의 수행 결과를 적당한 출력양식으로 구성하여 사용자에 전달하는 역할을 수행한다.
병렬 매치 인덱싱 구조를 이용한 병렬 매치 방법은 정확하다. 즉, 매치된 결과로서 이진 트라이에서각 단말 노드는 정확한 매치 신호와 경로서명 파일 내에서 유효한 엘리먼트들의 경로서명 값을 출력한다.
실험에 사용한 데이타들은 표 1과 같다. 실험결과, 병렬 매치 알고리즘을 사용한 본 논문의 방법에 대한 시간 복잡도는 0(h) 이다. 왜냐하면 h-클럭이후 입력 스트링의 첫 번째 비트패턴 값(가장 오른쪽 비트 패턴)이 리프 노드에 도착하고 마지막 매치 신호는 h-클럭 이후 루트 노드에 입력되기 때문이며, 2*h 클럭 이후에 매치 또는 노-매치 신호가 리프 노드에 도착하기 때문이다.
즉, 이 방법은 logsN과 유사한 크기 순서를 가진다. 결과적으로, 병렬 매치 알고리즘은 경로서명 파일의 개수(N)에는 영향을 받지 않으며 단지 경로서명의 길이 h에 의해만 영향을 받는다. 다음의 그림 10은 패트리샤 트리를 이용하는 기존의 Chen[8]의 알고리즘과 본 논문의 병렬 매치 인덱싱 구조를 사용하는 병렬 매치 알고리즘의 수행 결과에 대한 키의 최대 비교 횟수를 비교분석한것이다.
또한, 기존의 방법은 1로 설정된 비트의 수가 많고 적음 또는 경로서명 파일내의 경로 서명의 엔트리 수에 따라서 수행 성능에 많은 차이를 보인다’ 그러나 제안된 방법은 경로서명 파일내의 경로 서명의 수가 많고 적음이나 경로서명 값에서 1로 설정된 비트의 수가 많고 적음에는 영향을 받지 않으며 오직 경로서명의 갈이(h)에만 영향을 받는다. 따라서 중간규모 이하의 데이타베이스에 대한 검색에는 기존의 방법이 더 나은 성능을 나타내고 있으며 정적인 대규모의 XML문서 데이타베이스에서는 제안된 방법이 더 우수한 성능을 나타낸다. 그러나 본 논문에서 제안한 병렬 매치 인덱싱 구조에서 PE들을 구현함에 있어서 실제 하드웨어로 구현한다면 성능개선과 비용문제 측면에서 tradeoff가 일어 날 수 있다.
또한, 제안된 구조를 이용하여 병렬 매치 처리를 수행하기 위한 병렬 매치 알고리즘을 설계하였다. 본 논문에서 제안한 방법을 이용한 성능 실험 분석 결과에 따르면 제안된 알고리즘은 XML문서 파일에 대한 경로서명 엔트리 수에 대해 log2N과 유사한 크기 순서를 가진다. 따라서 경로 서명 파일의 개수에는 영향을 받지 않기 때문에 결과적으로 알고리즘의 시간 복잡도는 0(h)이다.

후속연구

따라서 중간규모 이하의 데이타베이스에 대한 검색에는 기존의 방법이 더 나은 성능을 나타내고 있으며 정적인 대규모의 XML문서 데이타베이스에서는 제안된 방법이 더 우수한 성능을 나타낸다. 그러나 본 논문에서 제안한 병렬 매치 인덱싱 구조에서 PE들을 구현함에 있어서 실제 하드웨어로 구현한다면 성능개선과 비용문제 측면에서 tradeoff가 일어 날 수 있다. 또한 병렬 시스템을 구현함에 있어서 필연적으로 PE들 사이에 통신오버헤드 문제가 발생할 것이나 본 논문에서는 통신오버헤드 문제는 고려하지 않았다.
또한 병렬 시스템을 구현함에 있어서 필연적으로 PE들 사이에 통신오버헤드 문제가 발생할 것이나 본 논문에서는 통신오버헤드 문제는 고려하지 않았다. 또 다른 문제는 각 엘리먼트에 대한 경로서명을 생성할 때 단축-경로 구성상의 단순함 때문에 서로 다른 경로에 대해 동일한 경로서명 값이 생성될 수 있으며 이것으로 인해 발생하는 허위 드롭의 수를 줄이기 위한 효율적인 방안에 대한 연구가 필요하다.
향후 연구과제로 XML문서에 포함된 각 엘리먼트들의 경로 서명 값을 생성할 때 그 방법상의 단순성으로 인하여 허위적중의 비율이 증가하는 요인이 되었다. 따라서 이에 대한 문제를 해결하기 위한 효율적인 방안에 대한 연구가 필요하며, 본 논문에서 제안한 병렬 매치 인덱싱 구조의 PE들을 실제 하드웨어로 구현하고 이에 대한 실험 및 결과 분석에 따른 정확한 성능 평가에 대한 연구가 필요하다.
따라서 이에 대한 문제를 해결하기 위한 효율적인 방안에 대한 연구가 필요하며, 본 논문에서 제안한 병렬 매치 인덱싱 구조의 PE들을 실제 하드웨어로 구현하고 이에 대한 실험 및 결과 분석에 따른 정확한 성능 평가에 대한 연구가 필요하다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

[국내논문] XML 데이타베이스에서 경로-지향 질의처리를 위한 병렬 매치 방법
A Parallel Match Method for Path-oriented Query Processing in iW- Databases 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

Keyword

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

참고문헌 (15)

이 논문을 인용한 문헌

저자의 다른 논문 :

활용도 분석정보

활용도 Top5 논문

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

[국내논문] XML 데이타베이스에서 경로-지향 질의처리를 위한 병렬 매치 방법 A Parallel Match Method for Path-oriented Query Processing in iW- Databases 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

Keyword

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

참고문헌 (15)

이 논문을 인용한 문헌

저자의 다른 논문 :

박희숙 (15) 조우현 (11)

활용도 분석정보

활용도 Top5 논문 더보기

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

[국내논문] XML 데이타베이스에서 경로-지향 질의처리를 위한 병렬 매치 방법
A Parallel Match Method for Path-oriented Query Processing in iW- Databases 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

활용도 Top5 논문