A Relative Cost Model of XQuery for Optimization Based on Rewriting

Soichiro HIDAKA  Hiroyuki KATO  Masatoshi YOSHIKAWA  

Publication
D - Abstracts of IEICE TRANSACTIONS on Information and Systems (Japanese Edition)   Vol.J91-D   No.4   pp.873-888
Publication Date: 2008/04/01
Online ISSN: 1881-0225
Print ISSN: 1880-4535
Type of Manuscript: Special Section PAPER (Spesial Section on Formal Approaches)
Category: 
Keyword: 
query languages,  program transformation,  cost model,  

Full Text(in Japanese): PDF(678.2KB)
>>Buy this Article


Summary: 
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.