摘要
路径选择性代价估计是XML查询优化的基础,也是研究的热点·目前的方法采用大量正态分布和独立性分布假设是造成误差的根本原因·定义了一种新颖的值-位置直方图用于统计XML数据中的结构和值的分布情况,并提出了6种直方图运算·在此基础上,给出用直方图计算估计路径中任一结点选择性的方法·实验证明,这种方法无需独立性分布假设,也能在数据结构和数值分布不均匀的情况下,精确地估计路径选择性代价·
Selectivity estimation of path expressions is the basis of XML query optimization and also intense research interest. A path expression may contain multiple branches with value predicates. Some of the values and the nodes of the XML data are highly correlated. Previous methods of selectivity estimation rarely take that relation into consideration, and assume, instead, that the selectivity of attribute values on different nodes and structures is independent and uniform. In this paper, a novel value histogram is proposed, which captures the correlation between the structures and the values in the XML data. Also defined are six operations on the value histograms as well as on the traditional histograms that capture nodes positional distribution. Based on such operations, the selectivity of any node （or branch） in a path expression can be estimated. Experimental results indicate that the method provides accuracy especially in cases where the distribution of the value or structure of the data exhibit a certain correlation without any independent assumption.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2006年第2期288-294,共7页
Journal of Computer Research and Development
基金
国家自然科学基金项目(60073014
60273018)
国家"八六三"高技术研究发展计划基金项目(2002AA116030)
教育部科学技术重点基金项目(03044)
河北大学博士科研启动基金项目(Y2005050)~~
关键词
XML
查询优化
选择性
直方图
谓词
XML
query optimization
selectivity
histogram
predicate
