Title: Towards a comprehensive assessment for selectivity estimation approaches of XML queries

Authors: Sherif Sakr

Addresses: School of Computer Science and Engineering, University of New South Wales, Sydney, NSW 2052, Australia

Abstract: Estimating the sizes of query results and intermediate results is a crucial part of any effective query optimisation process. Due to several reasons, the selectivity estimation problem in the XML domain is more complicated than that in the relational domain. Several research efforts have proposed different selectivity estimation approaches in the XML domain. This paper is a first step towards a comprehensive assessment of the available selectivity estimation approaches of XML queries along with their strengths and weaknesses. We provide a survey of the state-of-the-art of selectivity estimation approaches of XML queries and propose a selectivity estimation benchmark for XML queries, XSelMark. The proposed benchmark consists of a set of 25 queries organised into seven groups and covers the main aspects of selectivity estimation of XML queries. In addition, we suggest some criteria of assessing the capability and quality of the selectivity estimation approaches for XML queries. Finally, we use the proposed benchmark to assess the capabilities of the state-of-the-art of the selectivity estimation approaches.

Keywords: XML queries; synopsis; selectivity estimation; benchmarking; microbenchmarks; query optimisation.

DOI: 10.1504/IJWET.2010.034760

International Journal of Web Engineering and Technology, 2010 Vol.6 No.1, pp.58 - 82

Published online: 21 Aug 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article