단축-경로와 확장성 해싱 기법을 이용한 경로-지향 질의의 평가속도 개선 방법 = A Way to Speed up Evaluation of Path-oriented Queries using An Abbreviation-paths and An Extendible Hashing Technique

국문 초록 (Abstract)

최근 인터넷의 폭발적인 성장과 인기로 인하여 인터넷을 통한 정보 교환이 극적으로 증가하고 있다. 또한 XML은 인터넷상에서 데이터를 교환하기 위한 표준인 동시에 중요한 수단이 되고 있다. 따라서 XML 문서를 검색하는데 있어서, 경로-지향 질의에 대한 평가 속도를 개선하는 문제는 중요한 이슈이다. 본 논문에서는 문서 데이터베이스에서 경로-지향 질의의 검색 성능을 개선하기 위한 새로운 인덱싱 방법을 제안하다. 새로운 인덱싱 방법에서는 경로-지향 질의를 효과적으로 수행하기 위해 단축-경로 파일을 생성하고 그것의 해시 코드 값을 인덱스 키로 사용한다. 또한 검색 평가 속도를 촉진시키기 위하여 단축-경로 파일을 확장성 해싱 기법과 결합하는 것으로 검색질의의 평가속도를 가속화하였다.

다국어 초록 (Multilingual Abstract)

Recently, due to the popularity and explosive growth of the Internet, information exchange is increasing dramatically over the Internet. Also the XML is becoming a standard as well as a major tool of data exchange on the Internet. so that in retrieving the XML document. the problem for speeding up evaluation of path-oriented queries is a main issue. In this paper, we propose a new indexing technique to advance the searching performance of path-oriented queries in document databases. In the new indexing technique, an abbreviation-path file to perform path-oriented queries efficiently is generated which is able to use its hash-code value to index keys. Also this technique can be further enhanced by combining the Extendible Hashing technique with the abbreviation path file to expedite a speed up evaluation of retrieval.

참고문헌 (Reference)

1 H. M. Deitel, "XML How TO PROGRAM" Prentice Hall 2000.

2 Rambihia, "XML Distributed Systems Design" SAMS 2002.

3 "W3C＂XML Query (XQuery) Requirements＂ http://www. w3.org/TR/2003/WD-xquery-requirements-20031112, 2003." 2003.

4 "W3C＂XML Path Language (XPath) 2.0＂ http://www.w3. rg/2003/08/DIFF-xpath20" 2-0, 2003.

5 "W3C＂Extensible Markup Language (XML) http://www. w3.org/XML" 1998.

6 "W3CDocument Object Model^DOM^//www.w3. org/DOM/" 2002.

7 Y. Chen, "Path signature：A Way to Speed up Evaluation of Path-oriented Queries in Document Databases" 240-244, 2000.

8 D. H. C. Du, "Multilevel Extensible Hashing：A File Structure for Very Large Database" 3 : -3, 1991.

9 W. B. Frakes, "Information Retrieval：Data Structures and Algorithms" 1992.

10 W. Frakes, "Information Retrieval：Data Structures and Algorithms" 1992.

11 M. J. Folk, "File Structures An Object-Oriented Approach with C++" 1998.

12 "C. Faloutsos an ACM Computing Surveys Access Methods for Text" 17 (17): 48-74, 1985.

13 C. Zaniolo et al, "Advanced Database Systems" Morgan Kaufmann Publishers 1997.

14 H. Mochizuki, "A substring search algorithm in extendible hashing" 108 : 13-30, 1998.

15 S. Helmer, "A Robust Schema for Multilevel Extendible" 220-227, 2003.