Demythization of Structural XML Query Processing: Comparison of Holistic and Binary Approaches

2019 
XML query can be modeled by twig pattern query (TPQ) . This paper takes into account a TPQ model extended by a specification of output and non-output query nodes since it complies with the XQuery semantics. There are two approaches to process the TPQ: holistic joins and binary joins. Surprisingly, a thorough analytical and experimental comparison is still missing despite an enormous research effort in this area. In this paper, we try to fill this gap; we analytically and experimentally show that the binary joins used in a fully-pipelined plan can often outperform the holistic joins. The main contributions of this paper: (i) we introduce several improvements of existing binary join approaches allowing to build a fully-pipelined plan for a TPQ considering non-output query nodes, (ii) we prove that for a certain class of TPQs such a plan has the linear time complexity with respect to the size of the input and output as well as the linear space complexity with respect to the XML document depth, (iii) we show that our improved binary join approach outperforms the holistic join approaches in many situations, and (iv) we propose a simple combined approach that uses advantages of both types of approaches.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    31
    References
    1
    Citations
    NaN
    KQI
    []