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

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

A Query Processing Technique for XML Fragment Stream using XML Labeling

XML 레이블링을 이용한 XML 조각 스트림에 대한 질의 처리 기법

  • 이상욱 (중앙대학교 컴퓨터공학부) ;
  • 김진 (중앙대학교 컴퓨터공학부) ;
  • 강현철 (중앙대학교 컴퓨터공학부)
  • Published : 2008.02.15
Download PDF
⟨ Previous Next ⟩

Abstract

In order to realize ubiquitous computing, it is essential to efficiently use the resources and the computing power of mobile devices. Among others, memory efficiency, energy efficiency, and processing efficiency are required in executing the softwares embedded in mobile devices. In this paper, query processing over XML data in a mobile device where resources are limited is addressed. In a device with limited amount of memory, the techniques of XML. stream query processing need to be employed to process queries over a large volume of XML data Recently, a technique Galled XFrag was proposed whereby XML data is fragmented with the hole-filler model and streamed in fragments for processing. With XFrag, query processing is possible in the mobile device with limited memory without reconstructing the XML data out of its fragment stream. With the hole-filler model, however, memory efficiency is not high because the additional information on holes and fillers needs to be stored. In this paper, we propose a new technique called XFLab whereby XML data is fragmented with the XML labeling scheme which is for representing the structural relationship in XML data, and streamed in fragments for processing. Through implementation and experiments, XML showed that our XFLab outperformed XFrag both in memory usage and processing time.

유비쿼터스 컴퓨팅의 실현을 위해서는 이동 단말기의 자원 및 컴퓨팅 파워의 효율적 사용이 필수적이다. 특히, 이동 단말기에 내장된 소프트웨어의 수행에 있어 메모리 효율성 에너지 효율성, 그리고 처리 효율성이 요구된다. 본 논문은 자원이 제약되어 있는 이동 단말기에서의 XML 데이타에 대한 질의 처리에 관한 것이다. 메모리 용량이 크지 않은 단말기의 경우 대량의 XML 데이타에 대한 질의 처리를 수행하기 위해서는 XML 스트림 질의 처리 기술이 활용되어야 한다. 최근에 제시된 XFrag는 홀-필러 모델을 이용하여 XML 데이타를 XML 조각으로 분할하여 스트림으로 전송하고 처리할 수 있는 기법이다. 이는 메모리가 부족한 이동 단말기에서 조각 스트림으로부터 XML 데이타를 재구성하지 않고 질의 처리를 가능하게 한다. 그러나 홀-필러 모델을 사용할 경우 홀과 필러에 대한 부가적인 정보를 저장해야 하므로 메모리 효율성이 높지 못하다. 본 논문에서는 XML 데이타의 구조 정보를 표현하는 XML 레이블링 기법을 이용하여 XML 데이타를 조각으로 분할하여 처리하는 새로운 기법 XFLab을 제시한다. 구현 및 성능 실험 결과 XFLab이 XFrag보다 메모리 사용량과 처리 시간 양면 모두에서 우수한 것으로 나타났다.

Keywords

References

  1. "XML Fragment Interchange," W3C Candidate Recommendation 2001
  2. S. Bose, L. Fegaras, D. Levine, and V. Chaluvadi, "A Query Algebra for Fragmented XML Stream Data," DBLP 2003
  3. L. Fegaras, D. Levine, S. Bose, and V. Chaluvadi, "Query Processing of Streamed XML Data," CIKM 2002, pp. 126-133
  4. S. Bose and L. Fegaras, "XFrag: A Query Processing Framework for Fragmented XML Data," Web and Databases 2005
  5. H. Huo, G. Wang, X. Hui, R. Zhou, B. Ning, and C. Xiao, "Effiecient Query Processing for Streamed XML Fragments," Proc. Int'l Conf. on DASFAA, 2006
  6. M. Altinel and M. Franklin, "Efficient Filtering of XML Documents for Selective Dissemination of Information," Proc. Int'l Conf. on VLDB, 2000, pp. 53-64
  7. C. Chan et al., "Efficient Filtering of XML Documents with XPath Expressions," Proc. Int'l Conf. on Data Eng., 2002
  8. Y. Diao, M. Altinel, M. Franklin, H. Zhang, and P. Fischer, "Path Sharing and Predicate Evaluation for High-Performance XML Filtering," ACM Trans. on Database Systems, Vol.28, No.4, Dec. 2003, pp. 467-516 https://doi.org/10.1145/958942.958947
  9. A. Gupta and D. Suciu, "Stream Processing of XPath Queries with Predicates," Proc. ACM SIGMOD Int'l Conf. on Management of Data, 2003, pp. 419-430
  10. T. Green, A. Gupta, G. Miklau, M. Onizuka, and D. Suciu, "Processing XML Streams with Deterministic Automata and Stream Indexes," ACM Trans. on Database Systems, Vol.29, No.4, Dec. 2004, pp. 752-788 https://doi.org/10.1145/1042046.1042051
  11. J. Kwon, P. Rao, B. Moon, and S. Lee, "FiST: Scalable XML Document Filtering by Sequencing Twig Patterns," Proc. of Int'l Conf. on VLDB, 2005, pp. 217-228
  12. K. Candan, W. Hsiung, S. Chen, J. Tatemura, and D. Agrawal, "Afilter: Adaptable XML Filtering with Prefix-Caching and Suffix-Clustering," Proc. of Int'l Conf. on VLDB, 2006, pp. 559-570
  13. Z. Ives, A. Levy, and D. Weld, "Efficient Evaluation of Regular Path Expressions on Streaming XML Data," Tech. Rep. UW-CSE-2000-05-02, U. of Washington, 2000
  14. B. Ludascher, P. Mukhopadhyay, and Y. Papakonstantinou, "A Transducer-Based XML Query Processor," Proc. Int'l Conf. on VLDB, 2002
  15. F. Peng and S. S. Chawathe, "XPath Queries on Streaming Data," Proc. ACM SIGMOD Int'l Conf. on Management of Data, 2003, pp.431-442
  16. D. Florescu, C. Hillery, D. Kossmannn, P. Lucas, F. Riccardi, T. Westmann, M. Carey, A. Sundararajan, and G. Agrawal, "The BEA/XQRL Streaming XQuery Processor," Proc. Int'l Conf. on VLDB, 2003
  17. L. Fegaras, "The Joy of SAX," Proc. Int'l Workshop on XQuery Implementation, Experience, and Perspectives, 2004
  18. C. Koch, S. Scherzinger, N. Schweikardt, and B. Stegmaier, "FluXQuery: An Optimizing XQuery Processor for Streaming XML Data," Proc. Int'l Conf. on VLDB, 2004
  19. E. Wong, A. Chan, and H. Leong, "Efficient Management of XML Contents over Wireless Environment by Xstream," Proc. ACM Symp. on Applied Computing, 2004, pp 1122-1127
  20. S. Abiteboul, O. Benjelloun, B. Cautis, I. Manolescu, T. Milo, and N. Preda, "Lazy Evaluation for Active XML," Proc. ACM SIGMOD Int'l Conf. on Management of Data, 2004
  21. L. Mignet, D. Barbosa, and P. Veltri, "The XML Web: a First Study," WWW 2003
  22. P. O'Neil, E. O'Neil, S. Pal, I. Cseri, G. Schaller, and N. Westbury, "ORDPATHs: Insert-Friendly XML Node Labels," SIGMOD 2004
  23. C. Li and T. Ling, "QED: A Novel Quaternary Encoding to Completely Avoid Re-labeling in XML Updates," CIKM 2005
  24. I. Tatarinov, S. Viglas, K. Beyer, J. Shanmugasundaram, E. Shekita, and C. Zhang, "Storing and Querying Ordered XML Using a Relational Databse System," SIGMOD 2002
  25. A. Schmidt, F. Waas, M. Kersten, M. Carey, I. Manolescu, and R. Busse, "XMark: A Benchmark for XML Data Management," Proc. Int'l Conf. on VLDB, 2002, pp. 974-985