Fast structural join algorithm based on partitioning

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.