본 논문에서는 최근 방대해지는 XML문서의 효율적인 관리를 위해서 노드 범위와 Pre-Order List를 이용한 XML문서들의 인덱싱 기법을 제안한다. 기존의 제안된 인덱싱 기법들은 크게 패스(Poth)와 넘버링(Numbering)을 기반으로 하고 있다. 그러나, 패스기반의 인덱싱 기법은 중간 노드와 최하위 노드의 검색과 조상-후손관계의 조인연산에 의해 효율이 떨어지는 단점을 가진다. 또한, 넘버링기반의 방법은 XML문서의 모든 노드에 번호를 부여하기 때문에 검색-오버헤드가 증가하는 문제를 가지며, 인덱스를 위해 많은 공간이 낭비된다. 따라서 본 논문에서는 이러한 문제점들을 해결하기 위해서 모든 XML문서에 노드범위 (Node Range)와 Pre-Order List를 이용한 인덱싱 기법을 제안한다. 이 방법은 유사한 구조의 XML문서가 많을수록 인덱스의 크기를 효과적으로 줄일 수 있으며, 검색 성능을 효율적으로 높일 수 있다. 또한 XML문서의 삽입, 삭제가 용이하다.
본 논문에서는 최근 방대해지는 XML문서의 효율적인 관리를 위해서 노드 범위와 Pre-Order List를 이용한 XML문서들의 인덱싱 기법을 제안한다. 기존의 제안된 인덱싱 기법들은 크게 패스(Poth)와 넘버링(Numbering)을 기반으로 하고 있다. 그러나, 패스기반의 인덱싱 기법은 중간 노드와 최하위 노드의 검색과 조상-후손관계의 조인연산에 의해 효율이 떨어지는 단점을 가진다. 또한, 넘버링기반의 방법은 XML문서의 모든 노드에 번호를 부여하기 때문에 검색-오버헤드가 증가하는 문제를 가지며, 인덱스를 위해 많은 공간이 낭비된다. 따라서 본 논문에서는 이러한 문제점들을 해결하기 위해서 모든 XML문서에 노드범위 (Node Range)와 Pre-Order List를 이용한 인덱싱 기법을 제안한다. 이 방법은 유사한 구조의 XML문서가 많을수록 인덱스의 크기를 효과적으로 줄일 수 있으며, 검색 성능을 효율적으로 높일 수 있다. 또한 XML문서의 삽입, 삭제가 용이하다.
In this paper, we propose indexing method to manage large amount of XML documents efficiently, using the range of node and Pre-Oder List. The most of XML indexing methods are based on path or numbering method. However, the method of path-based indexing method shows disadvantages of performance degra...
In this paper, we propose indexing method to manage large amount of XML documents efficiently, using the range of node and Pre-Oder List. The most of XML indexing methods are based on path or numbering method. However, the method of path-based indexing method shows disadvantages of performance degradation for join operations of ancestor-descendent relationships, and searching for middle and lower nodes. The method of numbers-scheme based indexing has to number all nodes of XML documents, since search overhead increased and the disk space for indexes was wasted. Therefore, in this paper, we propose a novel indexing method using node ranges and Preorder-Lists to overcome these problems. The proposed method more efficiently stores similar structured XML documents. In addition, our method supports flexible insertion and deletion of XML documents.
In this paper, we propose indexing method to manage large amount of XML documents efficiently, using the range of node and Pre-Oder List. The most of XML indexing methods are based on path or numbering method. However, the method of path-based indexing method shows disadvantages of performance degradation for join operations of ancestor-descendent relationships, and searching for middle and lower nodes. The method of numbers-scheme based indexing has to number all nodes of XML documents, since search overhead increased and the disk space for indexes was wasted. Therefore, in this paper, we propose a novel indexing method using node ranges and Preorder-Lists to overcome these problems. The proposed method more efficiently stores similar structured XML documents. In addition, our method supports flexible insertion and deletion of XML documents.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 위에서 언급한 문제점을 해결하기 위하여 넘버링기법에 기반하면서 동시에 모든 문서의 패스를 통합하여 관리하고 노드범위와PteOtder list란 별도의 인덱스를 관리하는 새로운 방법을 제안한다. 제안된 방법은 다음과 같은 장점을 가진다.
그러나 각 문서별로 문서내의 모든 노드에 번호를 부여하고, 각각의 데이터와 속성에도 번호를 부여함으로써 검색-오버헤드가 커질 뿐만 아니라 인덱스의 공간 또한 비효율적으로 관리된다. 본 논문에서는 이러한 문제점을 해결하기 위한 방법을 제안하였다.
본 절에서는 제안한 인덱싱 기법의 실험환경, 실험 데이터 등에 대하여 간략히 설명하고 기존의 인덱싱 기법과 비교 실험하여 제안방법이 인덱스 공간을 줄이고, 검색성능향상에 기여하였 음을 보이고자 한다. 비교실험 인덱스는 패스를 기반으로 방법의 경우 2장에서 설명한 바와 같이 중간노드, 조상-후손관계의 조인연산 등에서 효율이 매우 떨어지므로, 기존의 넘버링기법 기 반의 대표적 인덱싱 기법 중 하나인 XISS와 비교.
가설 설정
d2 < m.d2의 관계를 만족하며, m이 n의 자녀라면 n.d3 + 1 = md3의 관계를 만족한다. 즉 <dl, d2, d3>는 <preorder, postorder, level>의 속성을 갖는다.
첫째, XPath 질의를 빠르게 분석한다. 둘째, 패스의 인덱스 저장공간을 효율적으로 관리한다. 셋째, PreOrder List를 이용하여 실제 검색할 데이터의 범위를 줄인다.
제안 방법
각 항목엔 Name Index의 preoider와 데이터테이블 이름이 보관되어 있으며, 크기가 매우 작다. XPath의 질의처리 시 Name Index(A)를 통하여 최하위의 preorder와 노드범위를 얻고, 이를 이용하여 PieOrder List(B)의 위치로 직접 이동한 후 데이터테이블의 이름을 얻어 바로 개방하는 방법을 수행하게 된다. 예를 들어 XPath질의 "Book//Title[='VisualC++']”를 처리한다고 할 때 기존의 XISS와 비교해보면 다음 (그림4)와 같다.
평가하였다. 또한 제안한 PreOrder List를 동적배열이 아닌 디스크 기반으로도 구현하여 같이 비교 실험하였다. 결과적으로 기존의 방법보다 우수한 검색성능을 보였다.
또한, 3가지 실험결과는 기존의 XISS 방법과 본 논문에서 제안한 방법을 (표2)와 (표3)를 각각 이용한 Pre-Order (1), PreOrder(2), 그리고 PreOrder List를 동적배열이 아닌 디스크 기반으로 구현한 총 4가지의 인덱스 방법의 성능을 비교한 결과이다. 이 때, 실험 검색 질의는 크게 심플패스 질의, 조상 -후손관계의 조인연산, 조상-후손관계의 조건연 산의 세가지 패턴으로 나누어 구성하였다.
이 문제를 해결하기 위하여Data Guide[ll]란 색인기법이 제안되었다. 이 방법은 XML문서에 대응되는 모든 질의 형태를 심플패스로 요약하고 데이터의 저장 위치를 보 관하여 중복된 경로를 통합하는 방법을 사용하였다. 이를 기반으로 하여 l lndex / 2-Index / T- Index[16]등이 제안되었다.
즉 <dl, d2, d3>는 <preorder, postorder, level>의 속성을 갖는다. 이러한 속성을 이용하여 각 XML문서에 부여된 번호를 비교하여 사용자의 질의처리를 수행한다. 그러나 중간 노드나 하위노드의 삽입 시에 모든 노드의 번호를 재조정해 주어야 하는 문제점을 해결하기 위흐!]서, XISS [9, 10] 는 모든 노드를 <preorder, postorder> 대신에<order, size>로 확장하였고, size에는 하위노드에 포함될 데이터의 개수 + 확장가능 범위가 들어가도록 하였다.
제안된 시스템은 (그림2)에 의해서 설명될 수 있다. 제안 시스템은 통합패스를 구성하여 XPath 질의를 분석하기 위한 Nante Index(A), 통합패스의 모든 노드를 preorder 순으로 구성하여 데이터테이 블의 이름을 저장하는 PreOder List(B), 데이터테이블 안에 포함된 XML문서의 ID를 보관하는 Doc_id_TB(C), 그리고 실제 데이터를 저장하는 Data Table(D)로 구성된다. XML문서의 삽입 시에 DOM Parser를 이용하여 모든 데이터를 심플패스와 데이터로 구성하여 임시 Raw Data에 보관한다.
제안된 방법은 다음과 같은 장점을 가진다. 첫째, XPath 질의를 빠르게 분석한다. 둘째, 패스의 인덱스 저장공간을 효율적으로 관리한다.
본 논문에서 제안한 방법은 다음과 같은 장점을 가진다. 첫째, 패스를 통합하여 인덱스의 공간을 줄였다. 둘째, 노드별로 preorder, postorder, node range를 부여하고 별도의 preprder List를 추가하여 관리함으로써, 비교연산의 수를 줄이고 검색성능을 높였다.
대상 데이터
0과「SQL을 사용하였다. 또한 실험 XML문서들의 내부 데이터와 구조를 추출하기 위한 Parser로는 Micro Soft 사의 MSXML (DOM) 라이브러리를 사용하였다.
본 연구는 정보통신부 및 정보통신연구진흥원의 대학 rr연구센터 육성.지원사업의 연구결과로 수행되었음.
실험데이타(A) 는 실제 법률 사이트에서 운영되고 있는 법률 XML문서들 로 구성되며, 각각의 문서 안에 포함된 노드 및 데이터의 수는 적으나, 문서의 수는 매우 많은 특징을 가진다. 실험 데이터(B)는 XISS의 실험에서 사용된 세익스피어 희곡 XMIR]이터로 문서의 수는 적으나 각 문서들 내부에 포함된 노드와 데이터의 수가 매우 많으므로 문서별 크기가 매우 큰 특징을 가진다. 실험 데이터(C)는 임의의 Synthetic Dataset으로 많은 중복 노드와 데이터를 포함하고 레벨이 매우 깊은 특징을 가진 대용량의 XML문서들로 구성되어 있다.
실험 데이터(B)는 XISS의 실험에서 사용된 세익스피어 희곡 XMIR]이터로 문서의 수는 적으나 각 문서들 내부에 포함된 노드와 데이터의 수가 매우 많으므로 문서별 크기가 매우 큰 특징을 가진다. 실험 데이터(C)는 임의의 Synthetic Dataset으로 많은 중복 노드와 데이터를 포함하고 레벨이 매우 깊은 특징을 가진 대용량의 XML문서들로 구성되어 있다. 상세 내역은 다음의 (표1)과 같다.
실험데이터는 서로 다른 구조의 세 종류의 데이터로 구성하였다. 실험데이타(A) 는 실제 법률 사이트에서 운영되고 있는 법률 XML문서들 로 구성되며, 각각의 문서 안에 포함된 노드 및 데이터의 수는 적으나, 문서의 수는 매우 많은 특징을 가진다.
데이터처리
본 절에서는 제안한 인덱싱 기법의 실험환경, 실험 데이터 등에 대하여 간략히 설명하고 기존의 인덱싱 기법과 비교 실험하여 제안방법이 인덱스 공간을 줄이고, 검색성능향상에 기여하였 음을 보이고자 한다. 비교실험 인덱스는 패스를 기반으로 방법의 경우 2장에서 설명한 바와 같이 중간노드, 조상-후손관계의 조인연산 등에서 효율이 매우 떨어지므로, 기존의 넘버링기법 기 반의 대표적 인덱싱 기법 중 하나인 XISS와 비교.평가하였다.
이론/모형
이를 기반으로 하여 l lndex / 2-Index / T- Index[16]등이 제안되었다. Index Fabric[2]은 복잡한 XML문서의 패스연산을 줄이기 위하여 Patricia Trie[4]를 적용하였다. Patricia Trie는 문자열 삽입시에 중복된 문자를 제거하고 서로 다른 문자의 위치와 해당문자를 저장하는 압축 방식으로 구현된다.
성능/효과
(그림5)의 세가지 실험 결과에서 모든 질의에서 본 논문이 제안한 방법이 기존의 방법보다 검색 결과가 우수함을 볼 수 있다. 첫번째 실험 의 경우, 통합패스 자체의 크기도 각 문서내의 노드별로 인덱스를 구성한 XISS보다 적으며, 데이터 역시 Q1 부터 Q7까지는 넘버를 비교하지 않고, PreOrder List안의 데이터 테이블을 개방함으로써 결과를 리턴하기 때문에 검색속도가 우수하다.
또한 제안한 PreOrder List를 동적배열이 아닌 디스크 기반으로도 구현하여 같이 비교 실험하였다. 결과적으로 기존의 방법보다 우수한 검색성능을 보였다.
두번째 실험의 경우, 첫번째 실험결과와 검색성능의 차이가 크지는 않았다. 그러나, 많은 데이터가 포함되어 있는 조건 질의 Q8의 경우는 제안된 방법이 우수한 검색 성능을 보였다. 세번째 실험의 경우, XISS는 질의에 포함된 노드의 수가 많을수록 많은 자체-조인연산이 일어나므로 제안된 방법보다 검색성능이 떨어짐을 보여준다.
또한, 본 논문에서 제안한 방법은 새로운 XML 문서의 삽입에도 효과적이다. 그리고 넘버링기법 의 대표적인 인덱싱 기법 중 하나인 XISS와의 비교 실험을 통해 검색성능의 우수함을 증명하였다.
첫째, 패스를 통합하여 인덱스의 공간을 줄였다. 둘째, 노드별로 preorder, postorder, node range를 부여하고 별도의 preprder List를 추가하여 관리함으로써, 비교연산의 수를 줄이고 검색성능을 높였다.
또한 Q8과 Q9의 질의의 경우엔 데이터 인덱스의 넘버를 비교하며, 조건을 검색하므로 더욱 성능이 떨어짐을 볼 수 있다. 또한 본 논문에서 제안한 방법은 패스를 통합하여 관리 하고, 각 데이터 테이블에 번호를 부여하지 않으므로 기존 방법보다 인덱스 공간을 효율적으로 사용할 수 있었다.
(그림5)는 (표1)의 3가지 실험 데이터들을 이용한 실험결과를 보여준다. 또한, 3가지 실험결과는 기존의 XISS 방법과 본 논문에서 제안한 방법을 (표2)와 (표3)를 각각 이용한 Pre-Order (1), PreOrder(2), 그리고 PreOrder List를 동적배열이 아닌 디스크 기반으로 구현한 총 4가지의 인덱스 방법의 성능을 비교한 결과이다. 이 때, 실험 검색 질의는 크게 심플패스 질의, 조상 -후손관계의 조인연산, 조상-후손관계의 조건연 산의 세가지 패턴으로 나누어 구성하였다.
또한, 본 논문에서 제안한 방법은 새로운 XML 문서의 삽입에도 효과적이다. 그리고 넘버링기법 의 대표적인 인덱싱 기법 중 하나인 XISS와의 비교 실험을 통해 검색성능의 우수함을 증명하였다.
본 논문에서 제안하는 방법은 문서의 패스를 통합 관리하므로 인덱스의 크기가 작으며 패스 연산의 검색-오버헤드도 매우 적다. 또한 데이터와 속성 인덱스는 번호를 부여하지 않으므로 번호에 대한 비교연산을 하지 않는다.
그러나, 많은 데이터가 포함되어 있는 조건 질의 Q8의 경우는 제안된 방법이 우수한 검색 성능을 보였다. 세번째 실험의 경우, XISS는 질의에 포함된 노드의 수가 많을수록 많은 자체-조인연산이 일어나므로 제안된 방법보다 검색성능이 떨어짐을 보여준다. 또한 Q8과 Q9의 질의의 경우엔 데이터 인덱스의 넘버를 비교하며, 조건을 검색하므로 더욱 성능이 떨어짐을 볼 수 있다.
둘째, 패스의 인덱스 저장공간을 효율적으로 관리한다. 셋째, PreOrder List를 이용하여 실제 검색할 데이터의 범위를 줄인다. 넷째, 데이터를 최하위노드별로 유지하여 삽입, 삭제를 용이하게 한다.
(그림5)의 세가지 실험 결과에서 모든 질의에서 본 논문이 제안한 방법이 기존의 방법보다 검색 결과가 우수함을 볼 수 있다. 첫번째 실험 의 경우, 통합패스 자체의 크기도 각 문서내의 노드별로 인덱스를 구성한 XISS보다 적으며, 데이터 역시 Q1 부터 Q7까지는 넘버를 비교하지 않고, PreOrder List안의 데이터 테이블을 개방함으로써 결과를 리턴하기 때문에 검색속도가 우수하다. 두번째 실험의 경우, 첫번째 실험결과와 검색성능의 차이가 크지는 않았다.
후자는 각 노드에 부여된 vprearder, postorder> 혹은 등의 번호를 비교하여 검색하며 평균적으로 우수한 검색성능을 보인다.
후속연구
또한 서로 다른 구조의 XML 문서들이 많이 존재한다면, 그 만큼 최하위노드가 늘어나게 되므로 데이터테이블의 수도 늘어나게 된다. 향후에는 이와 같은 문제점들을 보완 할 수 있는 방법을 지속적으로 연구할 것이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.