Chinese Journal of Computers   Full Text
Title	A Fast Structural Join Algorithm Based on Partitioning
Authors	WANG Guo-Ren QIAO Bai-You HAN Dong-Hong WANG Bin
Address	(College of Information Science and Engineering, Northeastern University, Shenyang 110004)
Year	2008
Issue	No.1(77—90)
Abstract &   Background	Abstract Structural join is the core part of XML queries and has a significant impact on the performance of XML queries. Several structural join algorithms have been proposed such as Stack-Tree and XR-tree. This paper studies to solve the problem of structural join by partitioning. It first extends the relationships between nodes to the relationships between partitions and get some observations and properties about the relationships between partitions that can be exploited for improving the performance of the structural join algorithms. This paper then proposes a new partition-based structural join method and two optimized methods based on the properties derived from these observations. Extensive experiments show that the performance of the proposed algorithms is better than that of Stack-Tree and XR-tree algorithms. In order to store the partitioning results, the authors design a simple but efficient index structure. The experimental result shows that the index structure has less maintenance overhead than XR-tree. keywords XML; structural join; partitioning background XML is emerging as the dominant standard for representing information and exchanging data over the Internet, and a lot of research results have been published recently, including query languages, storage management, indexing, and query processing and optimization. Since structural join is the core part of XML queries, it has a significant impact on the performance of XML queries and several structural join algorithms have been proposed such as Stack-Tree and XR-tree. These algorithms mainly consider the relationships between two element codes to adjust the structural relationship between these two elements. In this paper, the authors first partition the element encoding space into several partitions, and extend the element structural relationship to the partition structural relationship, then exploit the partition structural relationships to speed up the performance of the structural join operations.