计算机工程 ›› 2010, Vol. 36 ›› Issue (8): 40-42.doi: 10.3969/j.issn.1000-3428.2010.08.014

• 软件技术与数据库 • 上一篇    下一篇

基于扩展模式树匹配的XConquer算法

张子鋆,何震瀛,汪 卫   

  1. (复旦大学计算机科学技术学院,上海 200433)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-04-20 发布日期:2010-04-20

XConquer Algorithm Based on Extended Pattern Tree Matching

ZHANG Zi-jun, HE Zhen-ying, WANG Wei   

  1. (School of Computer Science, Fudan University, Shanghai 200433)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-04-20 Published:2010-04-20

摘要: 针对XQuery全文扩展中合取语义ftcontains表达式的计算问题,提出基于扩展模式树匹配的XConquer算法。树形结构索引DataSkeleton为查询节点静态过滤初始数据节点流,最小最低公共祖先动态阻止无效节点入栈,避免无用栈操作。实验结果表明,XConquer算法的查询性能优于DeweyPathStack算法。

关键词: XQuery全文扩展标准, 扩展模式树, 模式匹配

Abstract: Aiming at the evaluation of conjunctive semantic of conjunctive ftcontains expression in XQuery Full-Text extended, this paper proposes an XConquer algorithm based on extended pattern tree matching. Tree form structural index DataSkeleton statically filtrates initializing data node stream for query node. Smallest Lowest Common Ancestor(SLCA) dynamically prevents futile node into stack to avoid useless stack operation. Experimental results show that XConquer algorithm is superior to DeweyPathStack algorithm on query performance.

Key words: XQuery Full-Text(XQFT) extended standard, extended pattern tree, pattern matching

中图分类号: