20
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Cooking Lightweight XML Query Processor with Binary Joins and Comparing it with Holistic Joins: Technical Report

      Preprint
      , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          XML queries can be modeled by twig pattern queries (TPQs) specifying predicates on XML nodes and XPath relationships satisfied between them. A lot of TPQ types have been proposed; 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 and, in many cases, it leads to a more efficient query processing. In general, there are two approaches to process the TPQ: holistic joins and binary joins. The holistic joins have been developed as a generalization of the binary joins, and they have been considered as a state-of-the-art TPQ processing method. 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 (i.e., the plan where each join operation does not wait for the complete result of the previous operation) can often overcome the holistic joins even without any cost-based optimizer, especially for TPQs with a higher ratio of non-output query nodes. The main contributions of this paper can be summarized as follows: (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 (i.e., the same complexity as the holistic join approaches), (iii) we show that our improved binary join approach overcomes the holistic join approaches in many situations.

          Related collections

          Most cited references20

          • Record: found
          • Abstract: not found
          • Book Chapter: not found

          XMark

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            XRel: a path-based approach to storage and retrieval of XML documents using relational databases

              Bookmark
              • Record: found
              • Abstract: not found
              • Conference Proceedings: not found

              On boosting holism in XML twig pattern matching using structural indexing techniques

                Bookmark

                Author and article information

                Journal
                2017-03-28
                Article
                1703.09539
                5098f247-a136-483f-9d33-b7b545493c51

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                cs.DB

                Databases
                Databases

                Comments

                Comment on this article