• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Knowledge and Data Engineering, IEEE Transactions on >Processing and Evaluating Partial Tree Pattern Queries on XML Data
【24h】

Processing and Evaluating Partial Tree Pattern Queries on XML Data

机译：处理和评估XML数据上的部分树模式查询

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

XML query languages typically allow the specification of structural patterns using XPath. Usually, these structural patterns are in the form of trees (Tree-Pattern Queries—TPQs). Finding the occurrences of such patterns in an XML tree is a key operation in XML query evaluation. The multiple previous algorithms presented for this operation focus mainly on the evaluation of tree-pattern queries. Recently, requirements for flexible querying of XML data have motivated the consideration of query classes that are more expressive and flexible than TPQs for which efficient nonmain-memory evaluation algorithms are not known. In this paper, we consider a class of queries, called Partial Tree-Pattern Queries (PTPQs), which generalize and strictly contain TPQs. PTPQs represent a broad fragment of XPath which is very useful in practice. In order to process PTPQs, we introduce a set of sound and complete inference rules to characterize structural relationship derivation. We provide necessary and sufficient conditions for detecting query unsatisfiability and node redundancy. We also show that PTPQs can be represented as directed acyclic graphs augmented with the “same-path” constraints. In order to leverage existing efficient evaluation algorithms for less expressive classes of queries, we design two approaches that evaluate a PTPQ by decomposing it into a set of simpler queries: algorithm IndexTPQGen, exploits a structural summary of the XML data and evaluates a PTPQ by generating an equivalent set of TPQs and unioning their answers. Algorithm PartialPathJoin decomposes the PTPQ into partial-path queries, and merge-joins their solutions. We also develop PartialTreeStack, an original polynomial time holistic algorithm for PTPQs. To the best of our knowledge, this is the first algorithm to support the evaluation of such a broad structural fragment of XPath in the inverted lists evaluation model. We provide a theoretical analysis of our algorithm- and identify cases where it is asymptotically optimal. An extensive experimental evaluation shows that it is more efficient, robust, and stable than the other two and it outperforms a state-of-the art XQuery engine on PTPQs.
机译：XML查询语言通常允许使用XPath规范结构模式。通常，这些结构模式采用树的形式（树模式查询TPQ）。查找XML树中此类模式的出现是XML查询评估中的关键操作。为此操作提供的多个先前算法主要集中在对树型查询的评估上。近来，对XML数据进行灵活查询的需求促使人们考虑以下查询类，这些查询类比不知道有效的非主内存评估算法的TPQ更具有表达性和灵活性。在本文中，我们考虑一类称为“部分树模式查询”（PTPQs）的查询，该查询可以泛化并严格包含TPQ。 PTPQ代表XPath的广泛片段，在实践中非常有用。为了处理PTPQ，我们引入了一组完善的推理规则来表征结构关系推导。我们提供了检测查询不满足和节点冗余的必要和充分条件。我们还表明，PTPQs可以表示为有向路径的无环图，并用“相同路径”约束进行了扩充。为了将现有的高效评估算法用于表达较少的查询类，我们设计了两种方法来评估PTPQ，方法是将其分解为一组更简单的查询：算法IndexTPQGen，利用XML数据的结构摘要，并通过生成PTPQ来评估一组等价的TPQ并合并它们的答案。算法PartialPathJoin将PTPQ分解为部分路径查询，并将它们的解决方案合并。我们还开发了PartialTreeStack，这是用于PTPQ的原始多项式时间整体算法。据我们所知，这是第一个支持在反向列表评估模型中评估如此广泛的XPath结构片段的算法。我们对算法进行了理论分析，并确定了渐近最优的情况。广泛的实验评估表明，它比其他两个更为有效，强大和稳定，并且它优于PTPQ上最先进的XQuery引擎。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号