在Cache替换策略中的XPath Fragment包含算法  

Containment Algorithm for XPath Fragment in Cache Replacement Strategy

作　　者：詹欣[1] 李建中[1] 熊蜀光[1] 王宏志[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机科学》2004年第10期146-149,共4页Computer Science

摘　　要：在基于查询的XML cache环境中,查询包含算法对于cache替换策略的性能来说是很重要的。XML查询通常用XPath表达式来表达,XPath表达式等价于树模式。本文研究了Xpath查询语言片段的包含问题,实际上我们研究了树模式的一个特殊例子,证明了一个模式包含的声音和完全的PTIME算法。我们也分析了它的时间复杂度,实验结果也证实了我们的分析。In the environment of query-based XML cache,the query containment algorithm is important to the performance of cache replacement strategy. XML queries are usually expressed by means of XPath expressions,which are equivalent to tree patterns. This paper studies the containment problems for a fragment of the XPath query language. In particular, we study a special case of tree patterns, and provide a sound and complete PTIME algorithm for pattern containment. We also analyze its time complexity,and experimental results verify our analysis.

关 键 词：XP 替换策略 算法 XML查询 查询包含 查询语言 时间复杂度 等价 表达式 证明 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论] TP316[自动化与计算机技术—计算机科学与技术]