Holistic twig joins: optimal XML pattern matching
Holistic twig joins: optimal XML pattern matching
复制标题
DOI：
10.1145/564691.564727
复制
发表时间：
2002-06
期刊：
影响因子：
--
通讯作者：
Nicolas Bruno;Nick Koudas;D. Srivastava
中科院分区：
文献类型：
--
作者：
Nicolas Bruno;Nick Koudas;D. Srivastava
XML采用树结构的数据模型，而且XML查询自然会指定树结构相关的多个元素上的选择谓词模式。在XML数据库中查找所有出现这种小枝模式的情况是XML查询处理的核心操作。先前的工作通常将树枝模式分解为二进制结构（父-子和祖先-后代）关系，树枝匹配通过以下方式实现：（i）使用结构连接算法将二进制关系与XML数据库匹配，以及（ii）将这些基本匹配拼接在一起。这种方法的一个局限性匹配树枝模式是，中间结果的大小可以得到大，即使当输入和输出的大小是更manageable.In本文中，我们提出了一种新的整体树枝连接算法，TwigStack，匹配XML查询树枝模式。我们的技术使用一个链的链接堆栈competencies表示部分结果根到叶的查询路径，然后组成，以获得匹配的小枝模式。当twig模式只使用元素之间的祖先-后代关系时，TwigStack在所有读取整个输入的顺序算法中是I/O和CPU最优的：它在输入列表和最终结果列表的大小之和上是线性的，但与中间结果的大小无关。然后，我们展示了如何使用（修改）B树，沿着与TwigStack，匹配查询小枝模式在次线性时间。最后，我们补充我们的分析与实验结果的范围内的真实的和合成数据，查询小枝模式。
XML employs a tree-structured data model, and, naturally, XML queries specify patterns of selection predicates on multiple elements related by a tree structure. Finding all occurrences of such a twig pattern in an XML database is a core operation for XML query processing. Prior work has typically decomposed the twig pattern into binary structural (parent-child and ancestor-descendant) relationships, and twig matching is achieved by: (i) using structural join algorithms to match the binary relationships against the XML database, and (ii) stitching together these basic matches. A limitation of this approach for matching twig patterns is that intermediate result sizes can get large, even when the input and output sizes are more manageable.In this paper, we propose a novel holistic twig join algorithm, TwigStack, for matching an XML query twig pattern. Our technique uses a chain of linked stacks to compactly represent partial results to root-to-leaf query paths, which are then composed to obtain matches for the twig pattern. When the twig pattern uses only ancestor-descendant relationships between elements, TwigStack is I/O and CPU optimal among all sequential algorithms that read the entire input: it is linear in the sum of sizes of the input lists and the final result list, but independent of the sizes of intermediate results. We then show how to use (a modification of) B-trees, along with TwigStack, to match query twig patterns in sub-linear time. Finally, we complement our analysis with experimental results on a range of real and synthetic data, and query twig patterns.