达梦数据库的XQuery查询优化

1、达梦数据库的XQuery查询优化XML（eXtensible Markup Language可扩展标记语言）数据的自我描述性使其具有高度的结构化，良好 的存储格式等特点，而且XML文档和HTML 一样便于网络传输。因此，XML被广泛应用而成为数据定义， 数据交换和数据共享的主要标准。目前XML数据库主要研究的方向分为两大块，一是Native XML数据库系统，也称原生或纯XML数 据库，如Tamino、Ipedo等；二是XMLenabled数据库系统，即在已有的关系数据库系统或面向对象 数据库系统的基础上扩充对XML的支持，这种数据库的优点在于可以充分利用已有的非常成熟的关系数据 库技术。在关

2、系数据库系统上扩展对XML支持的一个重要部分就是实现XQuery查询。达梦关公司的DM XML支持项目是以达梦关系数据库为平台，扩展了对XML的支持，研究和实现基 于关系数据库XQuery查询优化技术，实现了高效的XQuery查询。XQuery相关概念XQuery是XML的查询语言，XQuery与XML文档的关系相当与SQL与关系数据的关系。与XQuery 紧密相关的一个概念是XPath，他们都是W3C的推荐规范。XPath是XML文档的路径语言，用来在XML 文档中对文档数据进行寻址XQuery是XPath的扩展。目前这两个规范的最新版本是XPath 2.0和XQuery 1.0，前者是后者

3、的严格句法子集，并已成为推荐标准。XPath表达式通过若干“路径步”在XML文档中进行定位（navigate）。对于每一步（step），一个轴” （axes）用来描述本步中的中间结果森林所包含文档节点（以及这些节点的子树），XPath表达式中包含13 种轴，其中通常使用的children和descendant-or-self轴缩写为/和/。FLWOR表达式是XQuery对XPath的重要扩展之一，即for，let，where，order，return表达式的组 合。for，let表达式以不同的方式将一个序列绑定到一个变量，这个序列可以是XPath路径表达式返回的 节点序列，where，orde

4、r表达式对这些序列的输出进行过滤和排序，return表达式输出结果序列，这个序 列可以是带有绑定变量的路径表达式，而且return表达式支持XML片断的构造。XML查询优化的概况传统的数据优化已有成熟的理论和方法：其中普遍采用的是基于代价的优化。如果把这种思想应用到 XML的XQuery查询优化，我们就可以看到一些问题。（1）没有完善的查询代数标准；反观关系数据库的优化理论，正是因为有非常成熟的关系代数语言， 能很好的支持查询语义和查询优化，所以关系数据库能成为主流的数据管理方式。（2）没有精确的代价估计；由于XML数据和关系数据的本身结构和分布特点上的差别决定了探索适 合于XML查询代价估计

5、模型的必要性。（3）没有足够的统计信息；足够精确的统计信息是保证查询优化有效性的基础；缺乏足够的统计信息， 是造成估计与实际情况产生误差的重要因素。目前的XML查询优化主要有下面一些技术：然后编写关于这2个大字段的Java对象文件TestLob.java，分别定义类型为CLOB和BLOB属性字 段为String和byte类型，其中由于CLOB是处理大文本类型所以它对应了 Java中的String类型，BLOB 是处理一些以二进制流形势存储的没有严格定义的大文件所以让它使用byte类型，然后分别定义这2个 属性的Getter和Setter方法，相关代码如下：1 .表达式重写通常XML查询用树的形

6、式表达，也称为树模式查询（Pattern Tree Query PTQ）。查询的最小化就是 对查询树化简的过程。孟小峰等中提出XQuery的PTQ优化分为两个步骤：首先是不依据任何外部信息的 语法优化，然后是根据XML文档的外部信息，如DTD，schema等，进行的语义优化。基于这种处理步骤， 优化技术可以分为基于DTD的或独立于DTD的。重写表达式的基本思想是在等价的前提下，按照一定的 规则转换XQuery表达式，得到效率更高的表达式，实际上就是对查询模式树的化简。研究认为独立于DTD 的优化能力很有限，引入DTD能有更大的优化空间，但目前的算法在优化的彻底性和效率上还有改进的余 地。2 .

7、构造查询代数目前国内外学者已经提出了很多种XML查询代数。这些查询代数或多或少借鉴了关系代数里的一些思 想。如Timber的TAX，国内的OrientXA，还有XAL，XOM，OPAL，SAL等。目前的XML代数的着重 点还在于查询语义的表达上，没有或很少考虑基于代数之上的查询优化，而且没有统一的标准，各种代数 之间少有通用性。3. XQuery查询向SQL查询的转换基于关系数据库的XQuery查询最终都是转化为存储了 XML数据的关系表上的SQL查询。这个过程 分为两步，首先是XML数据解析载入到关系表，然后是将对XML文档数据的查询转换为关系表上的SQL 查询。对XML解析后需要对数据编码

8、用于在关系数据库中唯一标志每个数据。目前提出的编码方案分为基 于区间的编码和基于路径的编码两大类。两种编码各有优点，区间编码能很好的表示文档数据间的位置关 系，而路径编码能很好支持节点间的包含关系。各种实现上的编码都有自己的特色，如Torsten Grust提出 的二元组编码，SQL Server 2005的ORDPATH技术标记。XQuery查询优化是一个综合性比较强的研究点，还包括很多其它的课题研究，比如基于代数的优化策 略，分解查询语句策略，代价估计的研究等。DM的XQuery优化与实现DM XML项目从以下两个方面实现了 XQuery查询优化。XPath路径表达式的优化。一是实现XPa

9、th的优化，在DM XML存储方案基础上生成最优的SQL 查询计划，另一方面是充分利用XML文档树的特点，并结合相关的XML外部信息，比如DTD文档，减 少SQL的搜索范围。FLWOR表达式的优化。FLWOR表达式本身的复杂性提供了优化的余地。在XQuery语义实现过 程中充分考虑FLWOR表达式的语义特点来尽可能的减少不必要的变量绑定，重复寻址等计算过程，来达 到优化的目的。采用的技术方案1. XPath路径表达式实现基本思想以表达式A/B/CD.10/E/FG/H为例：首先将查询路径用树模式进行描述并进行化简，路径的初始树模式如下左1图。XPath树模式化简示意图节点之间的链表示节点之间的

10、连接方式，其中F是目标节点，H和E是叶节点，D是包含谓词的节点， 算法通过两个步骤对树模式进行简化：1、去掉多余的主干分支；去掉C节点以上的部分，因为通过schame表的rangge列可以直接定位 路径中各节点的ID范围，没有谓词的主干部分可以省去不考虑。2、去掉多于的中间节点；去掉多于的中间节点C，C节点只相当中间连接节点，它两边的D和F节 点可以直接通过PID进行关联。通过这两个步骤后得到上面的第3个模式图。接下来将化简后树模式进行嵌套的形式化描述。方法是从最终的查询目标开始，递归地向下收集每个 节点的约束，直到叶子节点为止。与节点相关的每个链代表一个约束，本身如果是谓词节点，谓词条件也

11、约束之一，节点的所有约束的AND操作描述了节点。上面右图中的树模式得到的嵌套形式化描述为：ID ?(F.PIDg(D.PIDAF.IDg(G.PID)D.PID (D.IDg(E.PIDAP)PID (G.IDg(H. PID)最后根据这个形式化的描述生成嵌套的SQL语句：Select F.ID From infosettab FWhere F.ID=? AND? F.IDAND F.PID IN(Select D.PID From infosettab D ? where? D.Value10 AND D.ID IN(Select E.PID Form infosettab E? Where

12、 (E.ID=?) AND (E.IDAND F.ID IN(Select G.PID From infosettab G where? G.ID IN? ( Select H.PID Form infosettab H WhereID=?)AND(H.ID2. XQuery表达式的编译求解的实现方案：递归下降法的语法求解。XQuery的文法符合LL (1)文法的条件，可以对其进行无回溯的自上而下的 分析。采用模拟循环的方式？实现嵌套的FLWOR语句的求解。DM XML从下面两个方面实现了 FWLOR的进一步优化，在实际应用中很多情况可以用这两种策略综 合处理。简单FLWOR表达式的简化处理；

13、这里简单FLWOR表达式指的是只有一个循环变量的单重forwherereturn表达式,where和return 表达式中的关于路径的选择是基于绑定到变量的路径，一般描述为：FOR？ $a？ IN？ P1WHERE? predicate($a/P20, $a/P21.)RETURN? $a/P3其中P表示不含变量的路径表达式，pradivate(p)表示基于路径p的谓词。形如这种简单的FOR表达 式可以转换为：FOR? $a? IN? P1predicate(/P20,/P21.)/P3RETURN $a表达式返回结果不变，但是转换后的表达式简化了很多，转化为关系上的SQL查询也会简单得多。例

14、 如：FOR $a IN /site/regions/namerica/itemWHERE? $aid =item20748RETURN $a/name/text()可以转换为FOR $a ?IN ?/site/regions/namerica/itemid=item20748 /name/text()RETURN ?$a转换的好处是减少了寻址次数，原表达式在绑定变量的时候进行第一个XPath表达式求值，即 /site/regions/namerica/item的值，将其值的序列绑定到a变量，然后对序列里的每个项目计算一次where 表达式，若返回为真，在计算当前绑定值下的return表达式的值。简化之后的表达式值需计算一次XPath 表达式，而且省去了变量路径迭代的中间过程，明显可以减少计算量。FLWOR子表达式中路径常量的提取复杂的FLWOR表达式通常可以用这个策略进行优化。对于复杂的嵌套FOR循环，如果子循环里存 在循环变量绑定的是固定路径表达式，即该表达式中不含有其他的变量，则可以将FOR $p IN /site/people/personLET $a :=FOR $t in /s