Research On XML Twig Query Optimization

Because of the characteristics of self-description, extensibility and openness, XML has become the factual standard of the data representation and exchange in the web. With XML data rapidly increasing, especially with the large XML data emerging, XML query research is becoming the hotspot in both industry and academia. With the characteristic of semi-structure, the traditional sql query algorithms for the relational database are no longer applicable to XML data. So how to efficiently query XML data becomes a new study.In order to achieve the XML data query optimization, in recent years researchers have proposed a lot of algorithms, such as tree enumeration based on path indexes, approaches based on sequences, structural joins and holistic twig joins. Holistic twig join algorithms yield significantly less intermediate results than structural joins, so a lot of research has been made on this.In this paper, research has been done in the following aspects:(1) This paper proposes DBLSort algorithm, which decides the order for processing leaf query nodes and plays an important role in filtering XML elements which don't make contribution to query results.(2) This paper proposes TwigStackFast, a novel one-phase holistic twig join algorithm, which uses Extended Dewey encoding. It can support efficient evaluation of queries with P-C or A-D relationship. It is CPU and I/O optimal. It doesn't need to perform merge operation of the second phase that other algorithms do, which eliminates significant amounts of time and space overheads.(3) The experimental results show that TwigStackFast has better performance for XML twig queries than other typical algorithms such as TwigStack, HolisticTwigStack, Twig~2Stack and TJFast.