Enhancement of Query processing on XML data

Abstract

XML documents have recently become ubiquitous because of their varied applicability. And this raises new exciting possibilities in database area. In this thesis, we describe our proposed efficient query processing methods on XML data. In our method to process similarity query, new distance measure is defined based on data transformation. It is of linear computational complexity and proved to be a tight lower bound of the well-known tree edit distance. By embedding this distance measure in the filter-and-refine framework, the new method greatly reduces the number of expensive distance computations in the original space and improves the efficiency of query processing. In our work to process XML pattern query, we proved that the sub-optimality of prior algorithms is due to the matching blocks in the data streams. Based on the theoretical analysis, we propose two efficient query processing algorithms by utilizing element labeling scheme. Unlike the prior methods, our algorithms only take one phase to avoid outputting irrelevant intermediate path solutions. And the experimental results verify the effectiveness and the optimality of them.