레벨 정보를 이용한 효과적인 구조 조인 기법 (Effective Structural Joins using Level Information)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회 컴퓨팅의 실제 논문지 / 14권 / 6호 / 582 ~ 587페이지
· 저자명 : 김종익

초록

구조 조인은 XML 경로 질의를 처리하기 위한 대표적인 방법 중의 하나이다. 최근의 연구에서는 B+트리 등에 색인된 가로 방향의 엘리먼트 분포 정보를 이용하여 조인 결과에 포함되지 않는 엘리먼트들을 조인 연산에서 배제하는 방법에 초점을 맞추고 있다. 하지만, 이러한 방법은 조인 연산 자체가 매우 복잡해지며 분포 정보를 위한 색인의 부담으로 항상 좋은 성능을 보장하지는 못한다. 본 논문에서는 레벨 정보를 이용하여 조인 결과에 참여하지 못하는 엘리먼트들을 효과적으로 걸러내는 구조 조인 기법을 제안한다. 제안하는 기법의 레벨 정보는 엘리먼트의 세로방향의 분포정보라는 점에서 기존의 기법과 차별화되며 조인 연산을 위한 별도의 색인을 필요로 하지 않는다는 장점을 가진다. 본 논문에서는 실험을 통하여 제안된 기법의 효율성을 보인다.

영어초록

Structural join is one of the most typical techniques for evaluating XML path queries. Recent researches for structural joins focus on techniques of skipping unnecessary elements using the horizontal distribution information of elements that is indexed on a structure like B+ tree. However, those techniques make the structural join complicated and cannot guarantee efficient join processing due to the overhead of an index structure. In this paper, we propose a new structural join technique that exploits the level information of XML elements. Our technique can skip unnecessary elements using level information, which is vertical distribution information of elements. Through the experimental results, we show that our technique can evaluate structural joins efficiently.

참고자료

· 없음