Efficient Processing of Complex Twig Pattern Matching
Efficient Processing of Complex Twig Pattern Matching
复制标题
DOI：
10.1109/waim.2008.54
复制
发表时间：
2008-07
期刊：
影响因子：
--
通讯作者：
Jinqing Zhu;Wei Wang;Xiaofeng Meng
中科院分区：
文献类型：
--
作者：
Jinqing Zhu;Wei Wang;Xiaofeng Meng
XML作为Internet上信息表示和交换的事实标准，在许多应用中得到了广泛的应用。而XML查询技术也越来越受到数据管理研究界的关注。标准的XML查询语言，例如XML和XQuery，使用小枝模式作为基本单元来匹配给定XML文档中的相关片段。然而，在大多数现有的工作中，只有简单的包含关系中涉及的树枝模式，这使得它在许多情况下是不可行的。在本文中，我们扩展了原来的树枝模式复杂树枝模式（CTP），它可以包含查询节点之间的有序关系。我们给出了一个详细的分析，阻止我们找到一个有效的解决方案，CTP匹配的硬坚果，然后提出了一种新的整体连接算法，LBHJ，处理CTP高效和有效。我们在实验结果中表明，LBHJ可以大大减少中间结果的大小，从而提高查询性能显着根据各种指标时，处理CTP与有序轴。
As a de facto standard for information representation and exchange over the Internet, XML has been used extensively in many applications. And XML query technology has attracted more and more attention in data management research community. Standard XML query languages, e.g. XPath and XQuery, use twig pattern as a basic unit to match relevant fragments from a given XML document. However, in most existing work, only simple containment relationships are involved in the twig pattern, which makes it infeasible in many cases. In this paper, we extend the original twig pattern to complex twig pattern (CTP), which may contain ordered relationship between query nodes. We give a detailed analysis of the hard nuts that prevent us from finding an efficient solution for CTP matching, and then propose a novel holistic join algorithm, LBHJ, to handle the CTP efficiently and effectively. We show in experimental results that LBHJ can largely reduce the size of intermediate results and thus improve the query performance significantly according to various metrics when processing CTP with ordered axes.