Title :
Efficient Holistic Twig Join Algorithm on XML Documents with Optimization Rules and Index
Author :
Jiang, Jinhua ; Chen, Gang ; Shou, Lidan ; Chen, Ke
Author_Institution :
Colleage of Comput. Sci. & Technol., Zhejiang Univ., Hangzhou
Abstract :
Efficiently finding all occurrences of a twig pattern is a core operation of XML query processing. In this paper, we first propose a generic twig join algorithm TJFGeneric which only scans the leaf query nodes using a cursor interface to return elements. And then we present TJFGeneric+ algorithm incorporating two optimization rules into TJFGeneric to explore potential benefit of disk read and CPU cost. In particular, available indices (such as B+-tree) are applied to skip the elements that do not participate in final results. Experimental results on various datasets indicate that our algorithms outperform previous approaches significantly.
Keywords :
XML; optimisation; query processing; tree data structures; B+-tree; CPU cost; TJFGeneric generic twig join algorithm; XML documents; disk read; holistic twig join algorithm; index; leaf query nodes; optimization rules; query processing; twig pattern; Algorithms; Computer science; Cost function; Labeling; Query processing; XML; Index; Optimization; XML Twig join;
Conference_Titel :
Cyberworlds, 2008 International Conference on
Conference_Location :
Hangzhou
Print_ISBN :
978-0-7695-3381-0