Journal of Frontiers of Computer Science and Technology ›› 2010, Vol. 4 ›› Issue (11): 1049-1056.DOI: 10.3778/j.issn.1673-9418.2010.11.010

• 学术研究 • Previous Articles    

Structural Join Order Optimization for XPath

LI Dong1+, KUANG Zimin2   

  1. 1. School of Software, South China University of Technology, Guangzhou 510006, China
    2. School of Computer Science and Engineering, South China University of Technology, Guangzhou 510006, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-11-01 Published:2010-11-01
  • Contact: LI Dong


李 东1+, 邝子民2   

  1. 1. 华南理工大学 软件学院, 广州 510006
    2. 华南理工大学 计算机科学与工程学院, 广州 510006
  • 通讯作者: 李 东

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优化技术, 基于层次编码对结构连接的执行代价进行估算, 并用动态规划方法求解对于该路径表达式最佳的执行顺序; 根据计算结果对查询计划树进行重构得到优化的查询计划。对此算法进行了实验测试和分析, 结果表明该算法能得到较佳的查询优化效果。

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

CLC Number: