admin 管理员组文章数量: 1087139
2024年3月10日发(作者：asp脚本命令包括内容有哪些)
基于schema的xquery查询优化
摘要：基于schema的查询优化是一种语义优化策略，通过对xml
schema的预处理，来实现xpath路径的优化，或xquery查询时冗
余分支的减少，从而达到优化目的。目前主要有以下几类的优化方
式：（1）利用区间编码建立schema索引；（2）利用schema简化小
枝匹配，从而优化xquery；（3）建立等价路径图，缩短路径长度和
直接判断路径是否满足。
关键词：schema；xquery；优化
中图分类号：tp311.11 文献标识码：a 文章编号：1007-9599
(2011) 22-0000-01
xquery query optimization based on the schema
li xuekai
(beijing university of technology,beijing 100193,china)
abstract:based on the schema is a semantic query
optimization optimization strategy,through the xml schema of
the pre-treatment,to achieve the optimal path xpath or xquery
query to reduce the redundant branches,so as to achieve
optimization present there are ways to optimize
the following categories:(1)to establish the use of interval
coding schema index;(2)the use of schema matching to simplify
sprig,thus optimizing xquery;(3)the establishment of
equivalent road map,reduce the path length and path to
determine whether direct to meet.
keywords:schema;xquery;optimization
一、区间编码建立索引
这种方法采用两种区间编码方式dietz编码和li-moon编码，
分别对xml schema和xml文档进行编码，并采用编码方式和逆序
列表相结合的方式分别对xml schema和xml文档分别建立索引。
xquery查询时根据建立好的索引，在xml schema寻找匹配结构，
然后在xml文档中查询。下图是索引示例图：
这种方法通过编码的方式明确节点间的结构关系，对于每一个
节点可以方便的知道它在xml文档中的父子信息，对于任意查询，
首先在schema文档中进行结构匹配，如果不匹配则直接去掉，如
果匹配，则在索引表中以schema节点为关键字查询对应的xml节
点集合。进行谓词验证。
优点：利用编码表示节点的结构关系，建立索引达到节点集查
询的效率优化，这种方法主要减少了在大的xml文档中每次查询的
遍历时间，只要建立一次索引就可以在以后的查询中重复利用。
缺点：只适用于单一schema多xml的情况，对于xml的修改，
数据变动，需要更新索引，索引维护代价大。
二、小枝匹配查询
小枝查询是xml查询处理的核心操作，其主旨是搜索xml文档
树并从中找到与小枝模式相匹配的元素序列。一个小枝查询可以用
一个带有结点标注信息的树来表示，其中，边表示所连接的节点之
间的关系：父子（pc）关系或者是祖先后代（ad）关系。例如下图
所示，对于xpath查询//a[//c]//d来说，包含了符合如下条件的
模式匹配要求，即a节点必须有后代节点c，同时必须有后代节点
d。这种树模式匹配的查询被称为小枝查询。
xpath通过schema建立一棵类似的小枝匹配树，称作路径制导
树（pdt），在xquery查询时对查询节点进行pdt的匹配，直到返
回查询结果。利用pdt能够为xml文档遍历提供必要的路径信息，
只访问与pdt模式匹配成功的xml节点，对于那些与pdt无法匹配
的xml节点，不进行与查询模式的匹配操作，因此缩小了路径匹配
的范围，减少了对无用节点的访问。
路径制导树（v，e），是一棵节点和边都做了标记的树，其中：
（1）v是xml节点的有限集合。（2）每个节点都是一个四元组（tag，
parent，rightsibling，children），其中tag是元素的标签，代
表了xml文档树中节点的类型；parent是其双亲节点；rightsibling
是其右兄弟节点；children是其所有孩子节点。（3）e是边的有限
集合。（4）每条边表示连接两个节点之间的关系是父子关系（pc）。
优点：这种优化方法减少了xquery查询时对无效路径的访问，
优化了xpath。
缺点：算法开销大，而且对每个节点都要进行匹配，造成一些
不必要的开销。
三、等价路径图
这种方法的核心是路径优化，即通过等价路径图来缩短路径长
度和直接判断路径是否满足。并保证该等价路径类只与schema相
关，与具体的xml文档及其物理存储方式无关。对于某个具体xquery
查询中的路径表达式我们使用所得的等价路径类对其进行优化处
理，包括去除冗余路径、简化谓词表达式、判断谓词冲突等等。上
述过程，我们可以分为以下几步进行处理：（1）schema分析处理。
首先分析与待查询文档相对应的xml schema，从中得出各元素之间
的关系，如相关、蕴含、矛盾（这些概念在下文中会有详细介绍与
定义），并构建元素关系表ert；（2）路径分析处理。根据上一步中
所得的ert表中元素之间的各种关系以及xml schema，分析并找出
所有的可能路径，并构建全路径表apt；（3）等价路径类求解。分
析全路径表apt，找出所有的等价路径，并找出所有的等价路径类，
记录于cic（class implication and contradiction graph）图中；
（4）xquery查询语句中路径抽取处理。以解析后的xquery语句为
输入，xquery中的路径表达式为输出。抽取出的路径表达式用于下
一步的优化处理；（5）路径优化处理。根据cic图，对查询语句中
的路径表达式进行优化处理；（6）语法树中的路径还原处理。将优
化所得的路径表达式还原至语法树中。
优点：能够删除冗余分支，还能够缩短路径长度和直接判断路
径是否满足，减少了查询的开销。
缺点：建立等价路径表占用大量优化时间；其次，需要不确定
路径的确定化，这实际上也是一种路径膨胀，难以保证优化的结果
小于优化之前.
参考文献：
[1]王鑫.原生xml数据库存储与索引关键技术研究[d].南开大
学,2009
[2]苏航.xquery语言的部分求值技术[d].北京工业大学,2009
版权声明：本文标题：基于schemaxquery查询优化论文 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1710020780a553969.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论