Journal of KIISE:Databases (한국정보과학회논문지:데이타베이스)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

A Parallel Match Method for Path-oriented Query Processing in iW- Databases

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

  • 박희숙 (부경대학교 전자컴퓨터정보통신공학부) ;
  • 조우현 (부경대학교 전자컴퓨터정보통신공학부)
  • Published : 2005.10.01
Download PDF
⟨ Previous Next ⟩

Abstract

The XML is the new standard fir data representation and exchange on the Internet. In this paper, we describe a new approach for evaluating a path-oriented query against XML document. In our approach, we propose the Parallel Match Indexing Fabric to speed up evaluation of path-oriented query using path signature and design the parallel match algorithm to perform a match process between a path signature of input query and path signatures of elements stored in the database. To construct a structure of the parallel match indexing, we first make the binary tie for all path signatures on an XML document and then which trie is transformed to the Parallel Match Indexing Fabric. Also we use the Parallel Match Indexing Fabric and a parallel match algorithm for executing a search operation of a path-oriented query. In our proposed approach, Time complexity of the algorithm is proportional to the logarithm of the number of path signatures in the XML document.

XML은 인터넷상에서 데이타를 표현하고 교환하기 위한 새로운 표준이다. 본 논문에서는, XML문서에 대한 경로-지향 질의어의 평가를 위한 새로운 접근법에 대하여 기술한다. 본 논문의 접근법에서는, 경로-지향 질의어의 평가속도를 개선하기 위해 경로서명을 이용하는 병렬 매치 인덱싱 구조의 제안과 함께 데이타베이스 안에 저장된 엘리먼트들의 경로서명들과 입력된 질의어의 경로서명 사이에 매치작업을 수행하기 위한 병렬 매치 알고리즘을 설계한다. 먼저, 병렬 매치 구조를 형성하기 위해서는 XML 문서상의 모든 경로서명들에 대한 이진 트라이를 구성한 다음 이들을 병렬 매치 인덱싱 구조로 변환한다. 경로-지향 질의어의 검색 연산을 수행하기 위해 병렬 매치 인덱싱 구조와 병렬 매치 알고리즘을 사용한다. 본 논문에서 제안한 방법에서 알고리즘의 시간 복잡도는 XML 문서내의 경로서명의 수에 대하여 로그값에 비례한다.

Keywords

References

  1. T. Bray and E.maler and J. Paoli and C.M.SPErberg McQueen, 'Extensible Markup Language (XML) 1.0,' http://www.w3.org/TR/2000/REC-xml-20001006. Oct. 2000
  2. A. Deutch and M. Fernandez and D. Forescu and A. Levy and D. Suciu, 'XML-QL : A Query Language for XML,' http://www.w3.org/TR/NOTE-xml-ql, Aug. 1998
  3. S. Boag and D. Chanberlin and M. Fernandez and D. Florescu and D. Florescu and J. Robie and J. Simeon, 'XQuery 1.0 : An XML Query Language,' http://www.w3.org/TR/2002/WD-xquery-20020S16, Aug. 2002
  4. D. Eastlake and J. Reagle and D. Solo and W3C Recommendation, 'XML-Signature Syntax and Processing,' http://www.w3.org/TR/2002/REC-xmIdsig-ore-20020212, Feb. 2002
  5. C. Faloutsos and ACM Computing Surveys, 'Access Methods for Text,' Vol.17, No.1, pp.48-74, March 1985 https://doi.org/10.1145/4078.4080
  6. Carlo Zaniolo et al., 'Advanced Database Systems,' Morgan Kaufman Publishers, 1997
  7. J. D. Ullman, 'Computational Aspects of VLSI,' Computer Science Press, Maryland, 1984
  8. Yangjun Chen and Gerald Huck, 'Path Signature : A Way to Speed up Evaluation of Path-oriented Queries in Document Database,' Proceedings of WISE 2000 Conference, pp. 240-244, Jun. 2000
  9. Brian F. Cooper et aI., 'A Fast Index and Querying XML Data for Regular Path Expression,' Proceeding of the 27th VLDB Conference, 2001
  10. Q. Li and B. Moon, 'Indexing and Querying XML Data for Regular Path Expression,' Proceeding of the 27th VLDB Conference, 2001
  11. World Wide Web Consortium, 'Document Object Model (DOM),' http://www.w3.org/DOM/, 2002
  12. Harvey M. Deitel et al., 'XML How TO PROGRAM,' Prentice Hall, pp. 134-155, pp. 192-216, pp. 298-310, 2000
  13. William B. Frakes and Ricardo Baeza-Yates, 'Information Retrieval : Data Structures and Algorithms,' Prentice Hall PTR; Facsimile edition, pp. 44-80, 1992
  14. S. Stanfill and B. Kahle, 'Parallel free-text search on the connection machine system,' Communication of ACM, Vol.29, No.12, pp. 1229-1239, 1986 https://doi.org/10.1145/7902.7907
  15. 박희숙, 조우현, '단축-경로와 확장성 해싱 기법을 이용한 경로-지향 질의의 평가속도 개선 방법,' 정보처리학회논문지, 제11-D권, 제7호, pp. 1409-1416, 2004 https://doi.org/10.3745/KIPSTD.2004.11D.7.1409