Algorithms for efficient structure-based grouping in XML-OLAP

ABSTRACT

This paper discusses algorithms that efficiently compute structural grouping over XML data, which is a core operation in the interactive analysis of XML data, called "XML-OLAP". XML-OLAP allows interactive analysis over XML data to discover important information, and aggregation computation according to XML's tree hierarchy or TOPOLOGICAL ROLLUP, which plays a key role in XML structure-based grouping. We propose several variations of algorithms for efficient TOPOLOGICAL ROLLUP computation. Initially, these are basic algorithms: Top-Down and Bottom-Up, which are based on well-known Structural Join algorithms. We then propose a modified Bottom-Up algorithm to improve applicability, and the Single-Scan algorithms that make use of dedicated data structures. We finally perform comparative experimental analysis over the proposed algorithms, and demonstrate efficiency.

REFERENCES

• 1: Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of the 18th International Conference on Data Engineering, p.141, February 26-March 01, 2002
• 2: Rajesh R. Bordawekar , Christian A. Lang, Analytical processing of XML documents: opportunities and challenges, ACM SIGMOD Record, v.34 n.2, June 2005 [doi>10.1145/1083784.1083790]
• 3: C. Gokhale, N. Gupta, P. Kumar, L. Lakshmanan, R. Ng, and B. Prakash. Complex group-by queries for xml. In Proc. of ICDE 2007, pages 646--655, April 2007.
• 4: M. R. Jensen, T. H. Møller, and T. B. Pedersen. Specifying olap cubes on xml data. In Proceedings of SSDBM 2001, pages 101--112, July 2001.
• 5: Chantola Kit , Toshiyuki Amagasa , Hiroyuki Kitagawa, OLAP Query Processing for XML Data in RDBMS, Proceedings of the 2007 IEEE International Workshop on Databases for Next Generation Researchers, p.7-12, April 15-15, 2007 [doi>10.1109/SWOD.2007.353190]
• 6: Evangelos Kotsakis, Structured information retrieval in XML documents, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain [doi>10.1145/508791.508919]
• 7: Dennis Pedersen , Karsten Riis , Torben Bach Pedersen, XML-Extended OLAP Querying, Proceedings of the 14th International Conference on Scientific and Statistical Database Management, p.195-206, July 24-26, 2002 [doi>10.1109/SSDM.2002.1029721]
• 8: W3C. Xml path language (xpath) version 1.0, http://www.w3.org/tr/1999/rec-xpath-19991116, w3c recommendation 16 november 1999.
• 9: W3C. Xquery: A query language for xml, http://www.w3.org/tr/xquery. w3c working draft 2001.
• 10: N. Wiwatwattana, H. Jagadish, L. V. Lakshmanan, and D. Srivastava. X³: A cube operator for xlm olap. In Proc. of ICDE 2007, pages 916--925, April 2007.
• 11: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration
          Subjects: Data warehouse and repository

General Terms:
Algorithms, Design, Management, Performance

Keywords:
TOPOLOGICAL ROLLUP, XML, XML-OLAP, structural join