XML, selectivity estimation, self tuning, Markov histogram, simple queries

Abstract

To give an accurate selectivity estimation, the statistics needs to capture the distribution information and depict it correctly and efficiently. The semi-structured nature of XML complicate this problem by introducing more strong correlations to be captured (both path-to-path and path-to-value).In this thesis, we first provide a survey of recent selectivity estimation techniques in both relational databases and in XML databases. We identify the drawbacks of previous work and possible future research directions. As a preliminary work, we propose amodified data structure to capture the correlations in an XML data more accurately and efficiently. Detailed discussion about itsconstruction, usage and update techniques are given in the thesis along with the results obtained from experiments.