Tree logical classes for efficient evaluation of XQuery
Tree logical classes for efficient evaluation of XQuery
复制标题
DOI：
10.1145/1007568.1007579
复制
发表时间：
2004-06
期刊：
影响因子：
--
通讯作者：
Stelios Paparizos;Yuqing Wu;L. Lakshmanan;H. V. Jagadish
中科院分区：
文献类型：
--
作者：
Stelios Paparizos;Yuqing Wu;L. Lakshmanan;H. V. Jagadish
XML 因其允许重复和缺失子元素的灵活性而受到广泛赞誉。然而，这种灵活性使得开发体代数变得具有挑战性，体代数通常操纵具有相同结构的对象集。一组 XML 元素（例如书籍类型）可能具有结构差异很大的成员，例如作者子元素的数量。这种异质性可能以递归方式渗透到整个文档：例如，同一本书或不同书籍的不同作者在结构上可能会有很大差异。即使文档符合模式，XML 模式的灵活性仍然允许集合中的元素之间的结构发生如此显着的变化。这种异构集合的批量处理是有问题的。在本文中，我们引入了模式树节点的逻辑类（LC）的概念，并将模式树匹配的概念推广到处理节点逻辑类。这种抽象的效果显着，它允许我们以统一、同质的方式对本质上异构的元素集合进行推理。基于此，我们定义了一个树逻辑类（TLC）代数，它能够处理 XML 查询处理中出现的异构性，同时避免冗余工作。我们提出了一种从 XQuery 语句（对于 XQuery 的大片段）获取 TLC 代数表达式的算法。我们展示了如何有效地实现 TLC 代数，引入嵌套连接作为 XML 查询处理的重要物理运算符。我们表明，使用 TLC 代数生成的评估计划不仅比竞争方法生成的评估计划更简单，而且性能更好。 TLC 是密歇根大学开发的 Timber [8] 系统中使用的代数。
XML is widely praised for its flexibility in allowing repeated and missing sub-elements. However, this flexibility makes it challenging to develop a bulk algebra, which typically manipulates sets of objects with identical structure. A set of XML elements, say of type book, may have members that vary greatly in structure, e.g. in the number of author sub-elements. This kind of heterogeneity may permeate the entire document in a recursive fashion: e.g., different authors of the same or different book may in turn greatly vary in structure. Even when the document conforms to a schema, the flexible nature of schemas for XML still allows such significant variations in structure among elements in a collection. Bulk processing of such heterogeneous sets is problematic.In this paper, we introduce the notion of logical classes (LC) of pattern tree nodes, and generalize the notion of pattern tree matching to handle node logical classes. This abstraction pays off significantly in allowing us to reason with an inherently heterogeneous collection of elements in a uniform, homogeneous way. Based on this, we define a Tree Logical Class (TLC) algebra that is capable of handling the heterogeneity arising in XML query processing, while avoiding redundant work. We present an algorithm to obtain a TLC algebra expression from an XQuery statement (for a large fragment of XQuery). We show how to implement the TLC algebra efficiently, introducing the nest-join as an important physical operator for XML query processing. We show that evaluation plans generated using the TLC algebra not only are simpler but also perform better than those generated by competing approaches. TLC is the algebra used in the Timber [8] system developed at the University of Michigan.