基于模式匹配的路径表达式查询优化  

Optimize query of path expression on the basis of matched-pattern

作　　者：朱虹[1] 王纲[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《华中科技大学学报（自然科学版）》2005年第4期4-6,共3页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：湖北省科技攻关项目(2002AA103A06).

摘　　要：针对目前路径表达式的查询,提出了一种自顶向下基于模式匹配的查询策略.利用延迟结构连接,减少了目前比较费时的结构连接操作次数;另外在自顶向下基于模式匹配的计算过程中,为了尽可能减小中间结果集,引入一个子模式栈来保存已匹配的子模式,并利用子模式的出栈动作判断当前要处理的子模式和子模式栈的栈顶元素之间的关系(相连或者相交) ,从而可以删掉无用的的中间结果,一定程度上优化了空间复杂度.而且,本查询策略不依赖于特定的索引结构.通过对本查询策略进行理论分析和证明,可以看出,自顶向下基于模式匹配的查询方法是有效的.A top-down method to evaluate path expression based on matched-pattern was proposed in this paper. Using delayed structure joint can decrease expensive joint operations. Meanwhile, during the course of evaluating path expression, in order to decrease the size of intermediate result set we used sub-pattern stack to save the matched sub-pattern, then deleted useless intermediate result by judging the relationship between top element of stack and currently processing sub-pattern. Therefore obtained some optimization of space complexity in some degree. Moreover, the query policy didn′t depend on special index structure, so we could combine it with all kinds of index structure. Finally, the effectiveness of the query method was proved by theory.

关 键 词：XML查询 路径表达式 子模式栈 延迟结构连接 

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