On boosting holism in XML twig pattern matching using structural indexing techniques
On boosting holism in XML twig pattern matching using structural indexing techniques
复制标题
DOI：
10.1145/1066157.1066209
复制
发表时间：
2005-06
期刊：
影响因子：
--
通讯作者：
Ting Chen;Jiaheng Lu;T. Ling
中科院分区：
文献类型：
--
作者：
Ting Chen;Jiaheng Lu;T. Ling
在XML查询处理中，查找XML文档中所有出现的小枝模式是一个重要的操作。最近一个整体的方法TwigStack。[2]已经被提议了。该方法避免了产生大量的中间结果，这些结果对最终答案没有贡献，并且当小枝模式只有祖先-后代关系时，该方法是CPU和I/O最优的。XML查询处理的另一个重要方向是在XML文档上构建结构化索引[3][8][13][15]，以避免对源文档进行不必要的扫描。本文将XML结构索引作为一种对XML文档进行划分的技术，称之为流方案。在本文中，我们开发了一种方法来执行整体树枝模式匹配的XML文档分区使用各种流方案。我们的方法避免了不必要的扫描不相关的部分的XML文档。更重要的是，根据不同的流方案使用，它可以处理一个大类的树枝模式组成的祖先后代和父子关系，并避免产生冗余的中间结果。我们的实验证明了我们的方法的适用性和性能优势。
Searching for all occurrences of a twig pattern in an XML document is an important operation in XML query processing. Recently a holistic method TwigStack. [2] has been proposed. The method avoids generating large intermediate results which do not contribute to the final answer and is CPU and I/O optimal when twig patterns only have ancestor-descendant relationships. Another important direction of XML query processing is to build structural indexes [3][8][13][15] over XML documents to avoid unnecessary scanning of source documents. We regard XML structural indexing as a technique to partition XML documents and call it streaming scheme in our paper. In this paper we develop a method to perform holistic twig pattern matching on XML documents partitioned using various streaming schemes. Our method avoids unnecessary scanning of irrelevant portion of XML documents. More importantly, depending on different streaming schemes used, it can process a large class of twig patterns consisting of both ancestor-descendant and parent-child relationships and avoid generating redundant intermediate results. Our experiments demonstrate the applicability and the performance advantages of our approach.