Holistic Twig Joins on Indexed XML Documents Haifeng Jiang, Wei Wang, Hongjun Lu, and Jeffrey Xu Yu   View Paper (PDF)   Return to XML Query Processing III (Session A7) Abstract Finding all the occurrences of a twig pat- tern specified by a selection predicate on multiple elements in an XML document is a core operation for efficient evaluation of XML queries. Holistic twig join algorithms were proposed recently as an optimal solution when the twig pattern only involves ancestor- descendant relationships. In this paper, we address the problem of efficient processing of holistic twig joins on all/partly indexed XML documents. In particular, we propose an algo- rithm that utilizes available indices on element sets. While it can be shown analytically that the proposed algorithm is as efficient as the ex- isting state-of-the-art algorithms in terms of worst case I/O and CPU cost, experimental results on various datasets indicate that the proposed index-based algorithm performs sig- nificantly better than the existing ones, espe- cially when binary structural joins in the twig pattern have varying join selectivities. ©2004 Association for Computing Machinery