Key Technology Research Of XML Query Pattern Matching Based On Structural Joins

This dissertation discusses the key technology of XML query pattern matching based on structural joins. It proposes the definition of containment segment partitions, and presents a new method for structural joins on containment segment partitions. It also studies the join order selection in holistic twig joins procedure based on containment segment partitions, and improves the holistic twig joins algorithm using join order selection. It develops a solution framework for the XML data streams queries using the holistic twig joins algorithm on containment segment partitions. Finally, it studies the XML pattern tree minimization that can improve the performance of the query system further.This paper at first makes a survey of the present research works on two areas: one is twig matching, the other is pattern matching based on indexed nodes. It gives a profile for this research direction, and provides a base for the research in this dissertation. The main contributions of this dissertation are just as follows: It studies the three-tuple index structure on which the structural joins based, and proposes the containment segment partitions concept of index structure space. Using this concept, it improves the algorithm of structural joins. The three-tuple index structure also is the base of the holistic twig joins algorithm on structural joins. This dissertation still introduces concept into holistic twig joins procedure. It first studies the holistic twig joins on containment segment partitions, and then, using the concept of containment segment partitions, it studies the join order selection in holistic twig joins procedure. From the above two aspects, it improves the holistic twig joins algorithm. There is a wonderful characteristic of holistic twig joins algorithm, that is, it only needs to scan the XML document streams once when produces three-tuple index for document nodes. This kind of feature fits for the query processing of the XML document streams very much. And what'smore, the containment segment partitions technology provides a propability to concurrently carry on the XML document streams scans and holistic twig joins algorithm. Therefore, This dissertation, based on the above two aspects, poses a new solution framework for the XML data streams queries using the holistic twig joins algorithm on containment segment partitions. Finally, because the efficiency of XML query pattern matching depends much on the scale of the query pattern tree (the number of tree nodes), this dissertation also discusses the minimization problem of the query pattern tree. The main work in this part is to extend the DTD constraints SC(sibling constraints) to be ESC(extended sibling constraints), and propose a PTIME algorithm for XML pattern tree minimization under ESC constraints.