Structural joins: a primitive for efficient XML query pattern matching
Structural joins: a primitive for efficient XML query pattern matching
复制标题
DOI：
10.1109/icde.2002.994704
复制
发表时间：
2002-08
期刊：
影响因子：
--
通讯作者：
S. Al-Khalifa;H. V. Jagadish;Nick Koudas;J. Patel;D. Srivastava;Yuqing Wu
中科院分区：
文献类型：
--
作者：
S. Al-Khalifa;H. V. Jagadish;Nick Koudas;J. Patel;D. Srivastava;Yuqing Wu
XML查询通常在具有一些指定树结构关系的多个元素上指定选择谓词的模式。原始树结构化关系是父子和祖先 - 居民，在XML数据库中找到这些关系的所有出现是XML查询处理的核心操作。我们为此任务开发了两个结构性加入算法的家庭：树木和堆栈树。 Tree-Merge算法是传统合并连接和多个Predicate合并连接的自然扩展，而堆栈树算法在传统的关系加入处理中没有对应物。我们使用木材本机XML查询引擎建立在岸上的木材本机XML查询引擎上介绍了一系列数据和查询的实验结果。我们表明，虽然在某些情况下，树木混合算法的性能可以与堆栈树算法相当，但在许多情况下，它们的性能差得多。这种行为是通过分析结果来解释的，该结果表明，在分类的输入上，堆栈树算法具有最差的I/O和CPU复杂性，以输入和输出的大小的总和，而Tree-Merge算法则不是拥有相同的保证。
XML queries typically specify patterns of selection predicates on multiple elements that have some specified tree structured relationships. The primitive tree structured relationships are parent-child and ancestor-descendant, and finding all occurrences of these relationships in an XML database is a core operation for XML query processing. We develop two families of structural join algorithms for this task: tree-merge and stack-tree. The tree-merge algorithms are a natural extension of traditional merge joins and the multi-predicate merge joins, while the stack-tree algorithms have no counterpart in traditional relational join processing. We present experimental results on a range of data and queries using the TIMBER native XML query engine built on top of SHORE. We show that while, in some cases, tree-merge algorithms can have performance comparable to stack-tree algorithms, in many cases they are considerably worse. This behavior is explained by analytical results that demonstrate that, on sorted inputs, the stack-tree algorithms have worst-case I/O and CPU complexities linear in the sum of the sizes of inputs and output, while the tree-merge algorithms do not have the same guarantee.