A relative cost model for XQuery

ABSTRACT

XQuery is a functional query language for XML. We propose a relative XQuery cost model that is able to estimate the performance gain during source level transformation. This research facilitates the evaluation of various rewriting techniques without introducing real engines. The cost model consists of simple recursive functions based on functional language constructs. They are determined using formal semantics and other known efficient algorithms. Analytic comparison of costs between expressions before and after transformation is possible in an engine-independent manner. The relativity of the model allows uninterpreted components within, which do not affect the mathematical proof of the comparison. Moreover, it can be tailored to reflect engine specific evaluation strategies such as the order of evaluation of operands.

REFERENCES

• 1: A. Balmin , T. Eliaz , J. Hornibrook , L. Lim , G. M. Lohman , D. Simmen , M. Wang , C. Zhang, Cost-based optimization in DB2 XML, IBM Systems Journal, v.45 n.2, p.299-319, January 2006
• 2: From XML Schema to Relations: A Cost-Based Approach to XML Storage, Proceedings of the 18th International Conference on Data Engineering, p.64, February 26-March 01, 2002
• 3: A. Deutsch, Y. Papakonstantinou, and Y. Xu. The NEXT Logical Framework for XQuery. In VLDB, pages 168--179, 2004.
• 4: D. Draper, P. Fankhauser, M. Fernández, A. Malhotra, K. Rose, M. Rys, J. Siméon, and P. Wadler. XQuery 1.0 and XPath 2.0 Formal Semantics. W3C Candidate Recommendation, June 2006.
• 5: G. Gottlob, C. Koch, and R. Pichler. Efficient Algorithms for Processing XPath Queries. In VLDB, pages 95--106, 2002.
• 6: S. Hidaka, H. Kato, and M. Yoshikawa. An XQuery Cost Model in Relative Form. Technical Report NII-2005-016E, National Institute of Informatics, Nov. 2005.
• 7: H. V. Jagadish , S. Al-Khalifa , A. Chapman , L. V. S. Lakshmanan , A. Nierman , S. Paparizos , J. M. Patel , D. Srivastava , N. Wiwatwattana , Y. Wu , C. Yu, TIMBER: A native XML database, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.274-291, December 2002 [doi>10.1007/s00778-002-0081-x]
• 8: Prasan Roy , S. Seshadri , S. Sudarshan , Siddhesh Bhobe, Efficient and extensible algorithms for multi query optimization, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.249-260, May 15-18, 2000, Dallas, Texas, United States

INDEX TERMS

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

          Nouns: XML

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Languages