DOI QR코드

DOI QR Code

XQuery Query Rewriting for Query Optimization in Distributed Environments

분산 환경에 질의 최적화를 위한 XQuery 질의 재작성

  • 박종현 (거제대학 조선정보계열) ;
  • 강지훈 (충남대학교 전기정보통신공학부)
  • Published : 2009.03.31

Abstract

XQuery query proposed by W3C is one of the standard query languages for XML data and is widely accepted by many applications. Therefore the studies for efficient Processing of XQuery query have become a topic of critical importance recently and the optimization of XQuery query is one of new issues in these studies. However, previous researches just focus on the optimization techniques for a specific XML data management system and these optimization techniques can not be used under the any XML data management systems. Also, some previous researches use predefined XML data structure information such as XML schema or DTD for the optimization. In the real situation, however applications do not all refer to the structure information for XML data. Therefore, this paper analyzes only a XQuery query and optimize by using itself of the XQuery query. In this paper, we propose 3 kinds of optimization method that considers the characteristic of XQuery query. First method removes the redundant expressions described in XQuery query second method replaces the processing order of operation and clause in XQuery query and third method rewrites the XQuery query based on FOR clause. In case of third method, we consider FOR clause because generally FOR clause generates a loop in XQuery query and the loop often rises to execution frequency of redundant operation. Through a performance evaluation, we show that the processing time for rewritten queries is less than for original queries. also each method in our XQuery query optimizer can be used separately because the each method is independent.

XQuery가 XML 데이터를 위한 표준 질의어로 제안되면서, XQuery를 효율적으로 처리하기 위한 연구는 새로운 연구의 주제가 되었고, 몇몇 연구자들은 XQuery 질의를 최적화하기 위한 방법을 제안하고 있다. 그러나 앞선 대부분의 연구들은 XML 데이터 관리 시스템에 특화된 최적화 규칙만을 정의하고 있을 뿐 어떠한 시스템에서도 일반적으로 사용할 수 있는 최적화 방법과는 거리가 멀다. 또한 앞선 몇몇 연구에서는 XML 스키마 또는 DTD와 같은 미리 정의된 XML데이터의 구조정보를 이용하여 최적화하는 방법을 제안하고 있다. 그러나 현재 모든 응용이 XML 데이터를 위한 구조정보를 포함하고 있지는 않은 것이 현실이다. 그러므로 본 논문에서는 XQuery 질의의 특성을 파악하고 XQuery 질의 자체만을 이용한 최적화 방법들을 제안한다. 본 논문에서는 XQuery질의의 특성들을 고려한 세 가지 XQuery질의를 최적화 방법을 제안한다. 첫 번째 방법은 XQuery질의에 존재하는 불필요한 표현을 제거하는 것이고, 두 번째 방법은 질의 재배치를 이용한 최적화 방법이다. 마지막으로 세 번째 방법은 XQuery가 For절에 의해서 중첩된다는 점을 고려하여 For절에 의해서 발생하는 불필요한 반복을 최소화하는 방법이다. 성능 평가를 통해 논문에서 제안한 방법들에 의해 재작성 된 질의의 처리시간은 원본 질의의 처리 시간보다 뛰어나다는 것을 알 수 있다. 또한 각 방법들은 독립적으로 수행될 수 있으므로 XQuery 엔진의 필요에 따라 개별적으로 사용이 가능하다.

Keywords

References

  1. 박종현, 강지훈, "디지털 방송을 위한 Set-Top Boxrl반 TV-Anytime 메타데이터 관리 시스템", 한국컴퓨터정보학회논문지, 제 13권, 제 4호, 71-78쪽, 2008년 7월.
  2. F. Frasincar, G. J. Houben & C. Pau "XAL: An Algebra For XML Query Optimization Proc. Australasian Database Conference 2002, Melbourne, Australia, Feb. 2002.
  3. X. Zhang, B. Pielech & E. A. Rundensteiner "XML Algebra Optimization Technical Report, WPI-CS-TR-02-25, Worcester Polytechnic Institute, Oct. 2002.
  4. X. Zhang, B. Pielech & E. A. Rundensteiner, "Honey, I shrunk the XQuery!: an XML algebra optimization approach," Proc. WIDM 2002, McLean, Virginia, USA, Nov. 2002.
  5. Alfred V. Aho, Monica S. Lam, Ravi Sethi & Jeffrey D. Ullman, "Compilers: Principles, Techniques, and Tools (2nd Edition)", Addison Wesley, 2006.
  6. X. Zhang & E. A. Rundensteiner "XAT- XML Algebra for the Rainbow System," Technical Report WPI-CS-TR-02-24, Worcester Polytechnic Institute, July 2002.
  7. M. Grinev & D. Lizorkin "XQuery Function Mining for Optimizing XQuery Queries," Proc. ADBIS 2004, Budapest, Hungary, Sept., 2004.
  8. M. Grinev, & P. Pleshachkov, "Rewriting-Based Optimization for XQuery Transformational Queries," IDEAS 2005, Montreal, Canada, July 2005.
  9. H. Su, E. A. Rundensteiner & Murali "Semantic Query Optimization in an Automata Algebra Combined XQuery Engine over XML Streams," Proc. VLDB 2004, Toronto, Canada, Sept. 2004.
  10. G. Wang, M. Liu, J. X. Yu, B. Sun, G. Yu, J. Lv & H. Lu "Effective Schema-Based XML Query Optimization Techniques," Proc. IDEAS 2003, Hong Kong, China, July 2003.
  11. S. Groppe, & S. Bottcher, "Schema-based Query Optimization for XQuery Queries", Proc. ADBIS 2005, Tallinn, Estonia, Sept. 2005.
  12. C. Koch, S. Scherzinger, N. Schweikardt & B. Stegmaier "FluXQuery: An Optimizing XQuery Processor for Streaming XML Data," Proc. VLDB 2004, Toronto, Canada, Sept. 2004.