Abstract: XQuery proposed by W3C is the standard query language for XML. XPath is the main part of XQuery. While using XQuery language, a large part of execution time is spent on the evaluation of XPath. This paper proposes a cost estimation based algorithm for XPath structural join order optimization. Experimental results show that this algorithm can get better effect of query optimization.

Key words: XPath, structural join, cost estimation, hierarchy encoding, dynamic programming

摘要： XQuery是由W3C提出的XML查询语言标准。XPath路径表达式是XQuery的基础, 其查询处理的效能在很大程度上决定着XQuery的处理效率。提出了一种基于代价估算的XPath优化技术, 基于层次编码对结构连接的执行代价进行估算, 并用动态规划方法求解对于该路径表达式最佳的执行顺序; 根据计算结果对查询计划树进行重构得到优化的查询计划。对此算法进行了实验测试和分析, 结果表明该算法能得到较佳的查询优化效果。

关键词: 可扩展路径, 结构连接, 代价估算, 层次编码, 动态规划