Performing grouping and aggregate functions in XML queries

ABSTRACT

Since more and more business data are represented in XML format, there is a compelling need of supporting analytical operations in XML queries. Particularly, the latest version of XQuery proposed by W3C, XQuery 1.1, introduces a new construct to explicitly express grouping operation in FLWOR expression. Existing works in XML query processing mainly focus on physically matching query structure over XML document. Given the explicit grouping operation in a query, how to efficiently compute grouping and aggregate functions over XML document is not well studied yet. In this paper, we extend our previous XML query processing algorithm, VERT, to efficiently perform grouping and aggregate function in queries. The main technique of our approach is introducing relational tables to index values. Query pattern matching and aggregation computing are both conducted with table indices. We also propose two semantic optimizations to further improve the query performance. Finally we present experimental results to validate the efficiency of our approach, over other existing approaches.

REFERENCES

• 1: MonetDB. http://monetdb.cwi.nl/.
• 2: A. Berglund, D. Chamberlin, M. F. Fernandez, M. Kay, J. Robie, and J. Simeon. XML path language XPath 2.0. W3C Working Draft, 2007.
• 3: Kevin Beyer , Don Chambérlin , Latha S. Colby , Fatma Özcan , Hamid Pirahesh , Yu Xu, Extending XQuery for analytics, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066215]
• 4: K. S. Beyer, R. Cochrane, L. S. Colby, F. Ozcan, and H. Pirahesh. XQuery for analytics: Challenges and requirements. In XIME--P, pages 3--8, 2004.
• 5: S. Boag, D. Chamberlin, M. F. Fernandez, D. Florescu, J. Robie, and J. Simeon. XQuery 1.0: An XML query. W3C Working Draft, 2003.
• 6: V. Borkar and M. Carey. Extending XQuery for grouping, duplicate elimination, and outer joins. In XML Conference and Expo., 2004.
• 7: Nicolas Bruno , Nick Koudas , Divesh Srivastava, Holistic twig joins: optimal XML pattern matching, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564727]
• 8: Peter Buneman , Susan Davidson , Wenfei Fan , Carmem Hara , Wang-Chiew Tan, Keys for XML, Proceedings of the 10th international conference on World Wide Web, p.201-210, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371984]
• 9: Stefano Ceri , Sara Comai , Ernesto Damiani , Piero Fraternali , Stefano Paraboschi , Letizia Tanca, XML-GL: a graphical language for querying and restructuring XML documents, Proceedings of the eighth international conference on World Wide Web, p.1171-1187, May 1999, Toronto, Canada
• 10: Alin Deutsch , Yannis Papakonstantinou , Yu Xu, The NEXT framework for logical XQuery optimization, Proceedings of the Thirtieth international conference on Very large data bases, p.168-179, August 31-September 03, 2004, Toronto, Canada
• 11: D. Engovatov. XML query (XQuery) 1.1 requirements. W3C Working Draft, 2007.
• 12: Leonidas Fegaras , David Levine , Sujoe Bose , Vamsi Chaluvadi, Query processing of streamed XML data, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584816]
• 13: Thorsten Fiebig , Guido Moerkotte, Algebraic XML Construction and its Optimization in Natix, World Wide Web, v.4 n.3, p.167-187, 2001 [doi>10.1023/A:1013831700817]
• 14: C. Gokhale, N. G. 0003, P. Kumar, L. V. S. Lakshmanan, R. T. Ng, and B. A. Prakash. Complex group-by queries for XML. In ICDE, pages 646--655, 2007.
• 15: Gang Gou , Rada Chirkova, Efficiently Querying Large XML Data Repositories: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.19 n.10, p.1381-1403, October 2007 [doi>10.1109/TKDE.2007.1060]
• 16: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 17: Torsten Grust , Maurice Van Keulen , Jens Teubner, Accelerating XPath evaluation in any RDBMS, ACM Transactions on Database Systems (TODS), v.29 n.1, p.91-131, March 2004 [doi>10.1145/974750.974754]
• 18: M. H. Kay. Positional grouping in XQuery. In XIME-P, 2006.
• 19: Won Kim, On optimizing an SQL-like nested query, ACM Transactions on Database Systems (TODS), v.7 n.3, p.443-469, Sept. 1982 [doi>10.1145/319732.319745]
• 20: Norman May , Sven Helmer , Guido Moerkotte, Strategies for query unnesting in XML databases, ACM Transactions on Database Systems (TODS), v.31 n.3, p.968-1013, September 2006 [doi>10.1145/1166074.1166081]
• 21: Norman May , Guido Moerkotte, Efficient XQuery Evaluation of Grouping Conditions with Duplicate Removals, Proceedings of the 5th international Symposium on XML Database: Database and XMLTechnologies, September 23-24, 2007, Vienna, Austria [doi>10.1007/978-3-540-75288-2_6]
• 22: Wei Ni , Tok Wang Ling, GLASS: A Graphical Query Language for Semi-Structured Data, Proceedings of the Eighth International Conference on Database Systems for Advanced Applications, p.363, March 26-28, 2003
• 23: Stelios Paparizos , Shurug Al-Khalifa , H. V. Jagadish , Laks V. S. Lakshmanan , Andrew Nierman , Divesh Srivastava , Yuqing Wu, Grouping in XML, Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers, p.128-147, March 24-28, 2002
• 24: Christopher Re , Jerome Simeon , Mary Fernandez, A Complete and Efficient Algebraic Compiler for XQuery, Proceedings of the 22nd International Conference on Data Engineering, p.14, April 03-07, 2006 [doi>10.1109/ICDE.2006.6]
• 25: Jayavel Shanmugasundaram , Kristin Tufte , Chun Zhang , Gang He , David J. DeWitt , Jeffrey F. Naughton, Relational Databases for Querying XML Documents: Limitations and Opportunities, Proceedings of the 25th International Conference on Very Large Data Bases, p.302-314, September 07-10, 1999
• 26: H. Wu, T. W. Ling, and B. Chen. VERT: A semantic approach for content search and content extraction in XML query processing. In ER, pages 534--549, 2007.
• 27: XMark. An XML benchmark project. http://www.xml-benchmark.org, 2001.
• 28: XRel: a path-based approach to storage and retrieval of XML documents using relational databases, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.110-141, Aug. 2001 [doi>10.1145/383034.383038]
• 29: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms

Keywords:
aggregate function, grouping, query processing, xml