Research Of Pipelining XML Holistic Twig Query Algorithm

Currently, XML has been playing an increasingly important role in the Internet environment, and has gradually become a widely accepted standard for data storage, exchange and presentation. In order to satisfy the demand of querying and manipulating XML data, W3C officially released the recommendation of XQuery language which is used as the specification for XML query and processing. Being a powerful XML query and manipulation language, XQuery language plays a similar role as SQL language in the relational database. It can be used to extract desired data from different types of XML data sources, and then reconstruct them into a specified structure.As the most basic and common execution unit, query that focus on the branch structure of XML data is one of the most expensive operation in XQuery program. Its performance has an important impact on the implementation of the XQuery Language. These branch structures can be extracted and converted into a Twig Pattern. Then, Twig Query can be employed to find all matched elements from the XML data.With the gradual expansion and deepening of XML applications' development, the corresponding XQuery programs become more complex, and the scale of XML data grows bigger. Hence, the execution performance of the XQuery program becomes very important. Therefore, how to increase the query and manipulation performance through optimizing the process has significant research meaning. Twig Query has drawn much attention of some prominent scholars in recent years. Various approaches have been proposed to improve the performance of Twig Query. However, those existing algorithms either are designed for single-core architecture, or require the prior knowledge of the overall topology, which is always impractical.In order to improve the overall performance of Twig Query, this paper proposes a new algorithm named TwigPipe which is a premiere pipelining solution of XML holistic Twig Query. TwigPipe uses a new data partitioning algorithm and a new query algorithm, and is successfully combined with a simple representation format of the data and a new early-enumeration-mechanism. On the other hand, according to the characteristics of XML data, this paper presents a variety of optimization methods which are used to support complex queries for different data sources. The experimental results show that TwigPipe algorithm can reduce memory requirement and improve query performance.