一种可扩展的XPath查询最小化算法框架

计算机科学 ›› 2008, Vol. 35 ›› Issue (3): 58-60.

一种可扩展的XPath查询最小化算法框架

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
基金项目：本论文得到福建省科技计划项目的资助,资助号：2006F501050079.

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： XPath是XML的基本查询语言，XPath查询最小化对于提高XML数据库的查询性能具有重要意义。但是，由于XPath查询最小化是一个coNP完备问题，大部分已有的算法局限于处理简单的XPath片段。本文从一个新的角度入手，综合考虑完备性和高效性，提出了一个新的查询最小化框架，与已有算法“面向结点”，即逐个删除冗余结点的解决思路不同，本文提出“面向树模式”的方式，即通过计算树模式的自同态映射，寻找目标结点集最小的自伺态映射，进而求解最小等价查询树的方法。该方法具有较高的效率，而且在一定情况下是完备的，尤其

关键词: XPath 查询自同态最小化

Abstract: XPath is a standard language for XML queries, and XPath query minimization is very important for improving the performance of XML queries. However, XPath query minimization is a coNP-complete problem, and most previous algorithms are restricted to simple

Key words: XPath, Query, Endomorphism, Minimization

. 一种可扩展的XPath查询最小化算法框架[J]. 计算机科学, 2008, 35(3): 58-60. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed