Supporting efficient query processing on compressed XML files

ABSTRACT

XML has been widely accepted as the de facto format for data representation and exchange. However, it is also known for the excessive information redundancy in its representation. While various compression schemes have been proposed and some of them can support query processing over compressed files, it is usually inevitable to perform partial (or full) data decompression which is expensive and in some cases may dominate the query processing time.In this paper, we propose a new XML compression scheme based on the Sequitur compression algorithm. By organizing the compression result as a set of context free grammar rules, the scheme supports efficient processing of XPath queries without decompression. The experimental results show that this scheme achieves comparable compression ratio as gzip while its query processing time is among the best of existing algorithms.

REFERENCES

• 1: J. Cheng, and W. Ng, "XQzip: Querying Compressed XML using Structural Indexing," In EDBT 2004, LNCS 2992, 2004.
• 2: A. Arion and et. al. "XQueC: Pushing Queries to Compressed XML Data," In Proceedings of VLDB (Demo), 2003.
• 3: P. Buneman, M. Grohe, and C. Koch, "Path Queries on Compressed XML," In Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003.
• 4: Mary F. Fernandez , Dan Suciu, Optimizing Regular Path Expressions Using Graph Schemas, Proceedings of the Fourteenth International Conference on Data Engineering, p.14-23, February 23-27, 1998
• 5: Hartmut Liefke , Dan Suciu, XMill: an efficient compressor for XML data, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.153-164, May 15-18, 2000, Dallas, Texas, United States
• 6: Jun-Ki Min , Myung-Jae Park , Chin-Wan Chung, XPRESS: a queriable compression for XML data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872775]
• 7: A. R. Schmidt, F. Waas, M. L. Kersten, M. J. Carey, I. Manolescu, R. Busse, "XMark: A Benchmark for XML Data Management," In Proceedings of the International Conference on Very Large Data Based (VLDB), pages 974--985, Hong Kong, China, August 2002.
• 8: Craig G. Nevill-Manning , Ian H. Witten, Linear-Time, Incremental Hierarchy Inference for Compression, Proceedings of the Conference on Data Compression, p.3, March 25-27, 1997
• 9: Mathias Neumüller , John N. Wilson, Improving XML Processing Using Adapted Data Structures, Revised Papers from the NODe 2002 Web and Database-Related Workshops on Web, Web-Services, and Database Systems, p.206-220, October 07-10, 2002
• 10: Shakespeare, http://www.navdeeps.com/shakespeare/, Data Set, 2001.
• 11: XGRIND: A Query-Friendly XML Compressor, Proceedings of the 18th International Conference on Data Engineering, p.225, February 26-March 01, 2002
• 12: World Wide Web Consortium. XML Path Language (XPath) Version 1.0. http://www.w3.org/TR/xpath/, W3C Recommendation 16 November 1999.
• 13: J. Ziv and A. Lempel, "A Universal Algorithm for Sequential Data Compression," In IEEE Transactions on Information Theory, May 1977.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Keywords:
XML, data compression, query processing