Research On Twig Pattern Query In XML Database

With the rapid development of the Internet and Database, XML has been the de-facto standard for information representation and data exchange. As a result of the continued growth of XML data, particularly the emergence of large-scale XML data, it becomes more and more crucial to manage XML efficiently. However, due to the special semi-structure characteristic of XML data, it is inefficient to solve the problem with traditional database technology. Consequently, the ability to efficiently manage XML data becomes increasingly significant.In this thesis, we study the query processing of XML twig query. XML twig query has been widely considered as a core operation in XML query processing because matching twig queries takes a significant share of the computation time in XML query processing. Matching a twig query means finding all the instances of the query tree embedded in the XML data tree. The latest research of XML twig query is the holistic twig pattern matching algorithm, which yields significantly less intermediate results than structural joints. However when it comes to queries with parent-child relationship edges, this approach is still helpless.Our analysis reveals the problem of the existing holistic twig pattern matching algorithms that is the information included in previous labeling scheme is not enough to support such algorithms. We propose a new labeling scheme, which we call the extended region encoding labeling scheme. From the label of an element, we can obtain all distinct tag names of its children. Based on this new labeling scheme, we design a holistic twig pattern matching algorithm named TwigStackBE which is very efficient in processing twig queries with A-D and P-C relationship edges. In order to reduce I/O cost, we use indices on extended region encoding labeling scheme in our algorithm. The experimental results indicate that the proposed algorithm performs much better than the previous.