Research And Implementation Of Twig Join Algorithm

As XML is self-descriptive and extensible, which can meet the demand for data description and storage on the WEB, XML is widely used in the field of data presentation and exchange. With the rapid growth and widely used of XML data, the study of XML data query and storage received widespread attention. It’s a direct and effective way by using database to manage XML data. The query processing technology is a very important research area in the XML database, which directly affects the XML query efficiency, and structure join is the current research focus.The current structure join algorithms can be divided into two categories: binary structural join and twig pattern structural join, which is also called Twig join. Binary structural join decomposes the XML query into binary structures connected to get the middle results. Then the middle results are decomposed into binary structures to connect until get the final result. As the middle results may not contribute to the final result, a lot of useless middle results are producted. Twig join can reduce them by designing rational multi-join logic, and improve XML query efficiency. But traditional twig join algorithms can just deal with the simple XML query, less study results for the query involving complex expressions and ID/IDREF references, so it’s necessary to further study for twig join.This paper investigated the current popular twig join algorithms and some typical of them are implemented in XSQS, the native XML database system our labortory designed. Then a new twig join algorithm, called Twig Expand, is proposed, which can process the query involving attribute nodes or predicates within expressions and filter a lot of useless elements for both the PC(parent-child) relationship and AD(ancestor-descendant) relationship, that makes the query speed significantly improved. In addition, Twig Graph is proposed on the basis of Twig Expand, which can process the query with ID/IDREF references, and it’s much faster than binary structural join proved by experimental study.