基于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 purposes.At 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