Research On Labeling And Twig Pattern Query Of XML Data

Nowadays, with the constant spread of XML related standards and applications, there are a large number of XML data in lots of fields, particularly in the web.A large number of obvious facts show XML has become the actual standard of the data representation and exchange.The emergence of a large number of XML documents promotes the research on XML database, including XML data storage, index technique, query processing and query optimization technique.Among these, label scheme in index technique and twig pattern matching algorithm in query processing are the current research focus.Kinds of label schemes and twig pattern matching algorithms have been proposed to reduce database accesses, connection operations and improve query efficiency. By analyzing the XML language, XPath language, XQuery language, XML twig pattern query and XML data sets, focusing on a variety of existing XML tree label schemes and twig pattern matching algorithms,this paper summarizes some problems about existing XML tree label schemes and twig pattern matching algorithms.First, there are two main problems about the existing labeling schemes:the low space-time efficiency and insufficient supporting for dynamic update of XML document. Combining with the prime and IBSL label schemes, this paper presents a novel XML tree labeling, called PBSL which has a high efficiency in query, can completely avoid re-labeling any existing nodes when the XML update is performed in any case and greatly reduce the storage space.Then, existing query twig pattern matching algorithms are based on merging with high computational cost or very complex. Considering it and most queries with only one output node, this paper proposes a new twig pattern matching algorithm named TwigNMI.This algorithm is different from most existing algorithms which match from root to leaf node.It matches bottom-up without merging, sets up only one stack and scans lesser data nodes getting the final query result.This paper proposes a new XML tree label scheme-PBSL and a new XML partern matching algorithm-TwigNMI. These are effective attempt research and provide new ideas and methods for the further research on XML database.