Xml Structural Join Algorithm

As the rapid development of Internet, website and static HTML pages also expand dramatically. With the wide application of web, it has more and more limitations and cannot take up more complex tasks in the future. How to improve the correctness and efficiency of information retrieval becomes a critical problem in the future web development. Appearance of XML changes the basic outlook of Web. XML will become the criterion of information release and exchange of Web. The in-depth research of XML will encourage the development of company's information and e-commerce and will bring in the immense application and massive profits. In this case the XML databases break out fast. Nowadays the research about the storage, index and querying of XML documents becomes a hot point gradually. Many researchers have carried out a lot of researches on these topics. And the key component of querying XML documents is XML containment joins.The XML containment join algorithm is proposed based on XML encoding. Many researchers have proposed all kinds of encoding and relevant containment join algorithms. The most famous researches include region encoding and Anc_Desc_B+ algorithm, PBiTree encoding and VPJ algorithm. But Anc_Desc_B+ algorithm cannot deal with the nodes without sorting or indexes while VPJ algorithm cannot handle the nodes with sorting and indexes. And there is no such algorithm which can deal with the nodes without sorting or indexes based on region encoding. Also there is no algorithms which can deal with the nodes with sorting and indexes based on PBiTree encoding.This paper proposes EXN-Tree encoding. At first, this paper proposes the concept of EXN-Tree. Then the nodes of XML document tree are mapped to nodes of EXN-Tree. Finally it creates nodes' data structure of XML document tree according to node encoding of EXN-Tree. These nodes' data structures contain structural information of XML document tree. The relation of any two nodes can be judged fast by their nodes' data structure. Compare with the existing encodings, this encoding can...