Analytical processing of XML documents: opportunities and challenges

ABSTRACT

Online Analytical Processing (OLAP) has been a valuable tool for analyzing trends in business information. While the multi-dimensional cube model used by OLAP is ideal for analyzing structured business data, it is not suitable for representing and analyzing complex semi-structured data, such as, XML documents. Need for analyzing XML documents is gaining urgency as XML has become the language of choice for data representation across a wide range of application domains. This paper describes a proposal for analyzing XML documents using the abstract XML tree model. We argue that OLAP's multi-dimensional aggregation operators can not express structurally complex analytical operations on XML documents. Hence, we outline new extensions to XQuery for supporting such complex analytical operations. Finally, we discuss various challenges in implementing XML analysis in a real system.

REFERENCES

• 1: Brian Babcock , Surajit Chaudhuri , Gautam Das, Dynamic sample selection for approximate query processing, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872822]
• 2: Daniel Barbará , Mark Sullivan, Quasi-cubes: exploiting approximations in multidimensional databases, ACM SIGMOD Record, v.26 n.3, p.12-17, Sept. 1997 [doi>10.1145/262762.262764]
• 3: David Carmel , Yoelle S. Maarek , Matan Mandelbrod , Yosi Mass , Aya Soffer, Searching XML documents via XML fragments, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860464]
• 4: Surajit Chaudhuri , Gautam Das , Vivek Narasayya, A robust, optimization-based approach for approximate answering of aggregate queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.295-306, May 21-24, 2001, Santa Barbara, California, United States
• 5: Surajit Chaudhuri , Umeshwar Dayal, An overview of data warehousing and OLAP technology, ACM SIGMOD Record, v.26 n.1, p.65-74, March 1997 [doi>10.1145/248603.248616]
• 6: Z. Chen, H. V. Jagadish, L. V. S. Lakshmanan, and S. Paparizos. From Tree Patterns to Generalized Tree Patterns: On Efficient Evaluation of XQuery. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB), pages 237--248, September 2003.
• 7: World Wide Web Consortium. W3C Architecture Domain: XML. www.w3c.org/xml. Online Documents.
• 8: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843 ]
• 9: Moving Pictures Experts Group. MPEG Standards. www.chiariglione.org/mpeg.
• 10: Lin Guo , Feng Shao , Chavdar Botev , Jayavel Shanmugasundaram, XRANK: ranked keyword search over XML documents, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872762]
• 11: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 12: Carlos A. Hurtado , Alberto O. Mendelzon, Reasoning about Summarizability in Heterogeneous Multidimensional Schemas, Proceedings of the 8th International Conference on Database Theory, p.375-389, January 04-06, 2001
• 13: Nam Huyn, Data analysis and mining in the life sciences, ACM SIGMOD Record, v.30 n.3, September 2001 [doi>10.1145/603867.603880]
• 14: H. V. Jagadish , Laks V. S. Lakshmanan , Divesh Srivastava, What can Hierarchies do for Data Warehouses?, Proceedings of the 25th International Conference on Very Large Data Bases, p.530-541, September 07-10, 1999
• 15: Mikael R. Jensen , Thomas H. Møller , Torben Bach Pedersen, Specifying OLAP Cubes On XML Data, Proceedings of the 13th International Conference on Scientific and Statistical Database Management, p.101-112, July 18-20, 2001
• 16: A. Lerner and D. Shasha. Aquery: Query language for ordered data, optimization techniques, and experiments. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB), pages 345--356, September 2003.
• 17: A. Marian and J. Simeon. Projecting XML Documents. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB), pages 213--224, September 2003.
• 18: Gonzalo Navarro , Ricardo Baeza-Yates, Proximal nodes: a model to query document databases by content and structure, ACM Transactions on Information Systems (TOIS), v.15 n.4, p.400-435, Oct. 1997 [doi>10.1145/263479.263482]
• 19: 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
• 20: Dennis Pedersen , Karsten Riis , Torben Bach Pedersen, Query optimization for OLAP-XML federations, Proceedings of the 5th ACM international workshop on Data Warehousing and OLAP, p.57-64, November 08-08, 2002, McLean, Virginia, USA [doi>10.1145/583890.583899]
• 21: N. Pendse. The OLAP Report. Online Document www.olapreport.com.
• 22: Elaheh Pourabbas , Maurizio Rafanelli, Hierarchies and relative operators in the OLAP environment, ACM SIGMOD Record, v.29 n.1, p.32-37, March 2000 [doi>10.1145/344788.344799]
• 23: P. Resnik. Using information content to evaluate semantic similarity in a taxonomy. In In Proceedings of IJCAI, pages 448--453, 1995.
• 24: J. Trujillo, S. Lujan-Mora, and I. Song. Applying UML and XML for designing and interchanging information for data warehouses and OLAP. Journal of Database Management, 15(1):41--72, 2004.
• 25: Panos Vassiliadis , Timos Sellis, A survey of logical models for OLAP databases, ACM SIGMOD Record, v.28 n.4, p.64-69, Dec.1999 [doi>10.1145/344816.344869]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing

Additional Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Design, Experimentation, Measurement, Performance