Research On The Labeling Scheme Of Supporting Dynamic XML Twig Queries

With the development of Internet technology, as information representation and data exchange criterion, XML is increasingly concerned. How to store and query XML data more effectively becomes a hot topic. Twig pattern query is the core operation of XML query, and it plays an important role for improving the query efficiency. However, the key point in XML document query is to find the structure relation of nodes. XML labeling scheme is to assign a sole number to each node in document, so that one can define structure relation of nodes quickly and efficiently by comparing the node number in Twig pattern matching. Hence, many labeling schemes supporting XML Twig pattern query were presented recently. Nevertheless, there are mainly two problems to the current research. Firstly, when inserting data into the document between father-son nodes, the current labeling schemes have to re-encode the XML document. In addition, the absolute storage of nodes also wastes a lot of memory. Secondly, the current XML Twig pattern query algorithms can work well on static documents, but bad on dynamic documents.In order to solve the above-mentioned problems, this paper analyzes the current popular XML labeling scheme DDE and the Twig pattern query algorithm TwigStack deeply. Aiming at the requirements of dynamic XML document, we do researches in two fields:labeling scheme design and Twig pattern query algorithm. Firstly, we propose a novel XML data labeling solution IDDE. On the one hand, it avoids re-coding the XML document when inserting data between father and son nodes in the document. On the other hand, it greatly reduces the cost of document updating. Secondly, we propose a new compressed code storage pattern RDDE. Not only can it reduce the redundant information, but also improve the spatial performance. Thirdly, combining the coding solution provided in this paper with the current Twig pattern query algorithm (TwigStack), a new Twig pattern query algorithm (TwigStackDyn) is brought forward and analyzed, which is applied for dynamic XML labeling scheme. Finally, we compare the new algorithm with other relevant algorithms, which indicates the new one does well in time and spatial performance and satisfies the requirements of dynamic XML Twig pattern query.