XML查询优化模型XQO的研究设计

1 2 0 2 0 0 9 4 5 ( 1 9 ) C o m p u t e r E n g i n e e r i n g a n d A p p l i c a t i o n s 计算机工程与应用 X ML查询优化模型 X QO的研究设计 范新灿 F AN Xi n c a n 深圳职业技术学院 电信学院， 广东 深圳 5 1 8 0 5 5 El e c t r o ni c s & I n f o r ma t i o n En g i ne e r i n g， S he nz he n Po l y t e c h n i c， Sh e n z h e n， Gua n g do n g 5 1 8 0 5 5， Ch i n a F A N X i n c a n R e s e a r c h a n d d e s i g n o f o p t i mi z a t i o n mo d e l XQ O b a s e d o n X ML q u e r y C o mp u t e r E n g in e e r i n g a n d A p p l i c a t i o n s ， 2 0 0 9 ， 4 5 ( 1 9 ) ： 1 2 0 - 1 2 2 A b s t r a c t ：X M L q u e r y o p t i m i z a t i o n h a s b e c o m e a h o t a n d d i ff i c u l t r e s e a r c h t o p i c T h i s p a p e r p r e s e n t s a mo d e l o f X Q O f o r X M L q u e r y o p t i m i z a t i o n ， w h i c h c o m b i n e t h e q u e ry p r o c e s s i n g ， i l l u s t r a t i n g a n d d e s i g n i n g X Q O f r o m s e v e r a l o p t i m i z i n g q u e ry p a e ： L o g i c a l o p t i m i z a t i o n 、 p h y s i c a l o p t i m i z a t i o n ， q u e ry e x e c u t i o n A t l a s t ， t h r o u g h t h e e x p e r i me n t a l d a t a t o v a l i d a t e X Q O， w h i c h c a n e f f e c t i v e l y r ed u c e t h e c o s t o f pr a c t i c a l e x e cu t i o n a nd i mp r o v e q u e ryi n g s pe e d Ke y wo r d s ：XML； q u e ry a l g e b r a ； q u e ry t r e e ； r e g u l a r p a t h e x p r e s s 摘要： X ML现有的查询技术不够成熟， 效率低下， 精确度不高， 如何优化查询成为业界热点和难点问题。结合 -3今查询优化算法 技术， 设计了一个查询优化模型X Q O， 从查询过程的各个阶段进行优化查询解析、 逻辑优化、 物理优化， 设计执行策略和算法， 并 从 实验结果验证优 化的效果。 关键词 ： X M L ； 查询代数 ； 查询树 ； 路径表 达式 D OI ： 1 0 3 7 7 8 i s s n 1 0 0 2 8 3 3 1 2 0 0 9 1 9 0 3 6 文章编号 ： 1 0 0 2 8 3 3 1 ( 2 0 0 9 ) 1 9 0 1 2 0 0 3 文献标识码 ： A 中图分类 ： T P 3 1 1 1 引言 作为现今网络信息描述和信息交换的标准， X ML数据是 自描述的， 内容与结构混杂在一起， 数据具有完整的嵌套层次， 当X ML数据以文档进行存储时， 常使用关键字进行查询。 由于 缺乏系统的存储和查询机制的支持， 造成查询能力低， 不能满 足复杂条件的查询。 与传统的查询需求相比， 现有的 X M L数据 处理通常把 X ML查询转变为数据库查询表达，由查询优化器 优化查询并执行， 再将查询的结果转变为 X ML数据， 但这种多 级转换造成效率的降低和查询语义的混淆。X ML查询具有以 下特点： ( 1 ) 以长路径表达式为查询的核心语句 ， 路径复杂， 包含分 支路径 ； ( 2 ) 查询表达式中加入了编程语言的嵌套和条件判断思想； ( 3 ) 路径 中包含不确定因素 ； ( 4 ) 查询对象和返回结果类型不确定。 X M L数据的存储和查询已经成为迫切需要解决的问题 ， 对 X M L 查询的优化更是 X M L 的热点研究方向。结合 X M L 查 询优化的最新研究 ，设计了一个 X ML查询优化模型 ： X Q O ( X ML Q u e ry O p t i m i z a t i o n ) ， 结合 X M L查询的过程， 对于每个 查询阶段设计优化策略和算法进行优化。 2 X QO模型结构设计 在 X Q O模型中，将 XM L查询优化过程分为4个步骤： 查 询解析、 逻辑优化、 物理优化和查询执行， 查询优化过程的模型 作者简介： 范新灿( 1 9 7 8 一 ) ， 男， 讲师， 研究方向： X ML 、 We b 服务。 收稿 1 3 期 ： 2 0 0 8 0 4 1 7 修回 口期 ： 2 0 0 8 0 8 0 4 及采用的相应优化技术如图 1 所示。 就技术及结果 _ - 一 一 一 一一 一 一 一 一 - 查询代 数( 奄 1 询树 ) ： _- - 一 -_-一_l 规范、 简化内 ； 部表达式( 查 询树最小化) ： 蕾 ： ： ： ： ： ： ： ： ： ： ： ： 复杂路径表达 式( 表达式分解 为执行片段)； ： ： ： ： ： ： ： ： ： ： ： ： ： 访问数据， 得到 查询结果 ： 查询解析 f l代数表达式 曼 i I 模 型 信 息 - 4 逻 辑 优 化 l i 信 I统 计 信 息 ： 缔 ” L 数 据， 索引 图 1 XQ O 询优化处理 查询解析阶段，将 X MI 查向转换为某种内部表达式， 即 X ML代数。 X ML代数是对遵循一定数据模型的X ML文档集合 的操作集， 提供根据请求在文档集合巾选择一个或多个文档或 者文档片段的能力， 并支持对查询结果的重构。此阶段以一种 抽象语法树或者查询树的形式出现， 为下一步的优化过程铺平 道路。 逻辑优化阶段， 利用模式信息， 规范和简化内部表达式。 对 于同一查询淆求， 转换成不同的等价表达方式。X M L代数表达 式求解时， 操作顺序是影响效率的关键， 逻辑优化的重点在于 对操作顺序的调整。在查询解析阶段， 将路径表达式转换成查 范新灿 ： X ML查询优 化模 型 X Q O的研 究设计 询树， 查询效率依赖于查询树的规模， 查询树的最小化是 X ML 逻辑优化的重点。 物理优化阶段 ， 利用代价模型和统计信息计算不同的表达 式、 不同算法的执行代价， 选择最低代价的查询计划。 确定表达 式的执行顺序和决定每步操作的具体算法。对逻辑优化最小 化的查询树 ， 将需要查询的表达式分解为可执行的片段， 选择 合适的执行顺序和执行算法并执行。确定执行顺序的主要因 素是中间结果集的大小，采用并优化复杂路径表达式选择性 分析 。 查询执行阶段，根据物理优化确定的执行策略和算法， 访 问数据并得到查询结果。 3 X ML查询代数优化 3 1 代数定义 路径表达式是 目前各种 X ML查询语言和过滤语言的核 心，这主要是根据 XM L文档具有树状或者图状的逻辑结构决 定的。X Q O首先定义一个代数模型， 在这个模型的基础上给出 路径表达式的语法定义以及它的有限自动机表示方法。 与关系代数类似 ， X ML查询代数也需要定义一系列的操 作符： 选择 、 抽取 、 序列 、 连接、 分组、 聚集、 排序、 消重、 构造。 这些操作符可以分为 3类： ( 1 ) 结构相关 ： 抽取( 模式树匹配 ) 、 连接、 构造； f 2 ) 数值相关： 选择( 渭词) 、 分组、 聚集 、 消重、 排序； ( 3 ) 混合： 集合、 序列。下面列举出各操作符的含义： 选择操作符： ， P E ( X) = x l x r 二 r ! = 。 数学函数 ： 指数、 对数 、 幂 函数 、 三角函数等。 3 2 路径表达式 一 个 X ML文档 X T r e e 模型示意如图 2所示。路径表达式 是 X ML查询的基本建筑单元。正则路径表达式，是指能够以 L i k e S Q L语言的方法表示查询的内容，但却可以结合一些特 殊字元或一些特殊符号 ，来描述 XM I 文件的阶层式及树状资 料内容， 如树状结构子孙关系的描述等。在利用正则路径表达 式来下达一些 l i k e S Q L的指令时 ，不一定要完全知道 目前所 查询的 X ML文件资料的全貌 ， 只要针对所查询的资料条件， 加 以利用正则路径表达式的一些符号或特殊字元来与条件结合 描述， 就可以轻易的查询所要寻找的X ML文件内容。 A 图 2 一个 X ML文档 X T r e e模型示意图 针对模型 X T r e e ， 路径表达式的形式化定义 如下 ： ( 1 ) f 表示一棵空树 ； ( 2 ) = 表示一棵树 ， 它的根有一条标记为 l 的输出边 ， 下面附着一棵子树 ， 其中 可以表示叶节点， 此时 等于某 文字值或空元素。由于 z = 只表示单一一棵树， 可省略括号 ， 简写为 Z = ； ( 3 ) l t = T t ， z = ， z = 也表示一棵树 ， 它有 n个由同 一 节点发出的、 分别标记为 f _ ， f 2 ， ， z 的输出边 ， 每个输出边分 别附着子树 。 ， ， ， ； ( 4 ) 无论是边标签 l ， 还是子树 ( 包括叶节点 ) ， 都可以用 变量表示； ( 5 ) 2 ， 3或 2 ， 3的组合成为路径表达式。 目前的 X ML查询语言如 X P a t h 、 X Q u e r y等， 这些查询语言 都是基于正则路径表达式。 路径表达式分解根据一定的转换规 则， 把用查询语句表达的、 复杂的、 不确定的路径表达式转换为 简单的、 明确的、 系统可识别的方式 ， 如 X ML代数。路径表达 式的分解释查询优化重要的环节。路径分解的原则是能够产 生有限的代价空Ih J ，有利于利用分解的结果搜索代价最小的 执行方案。 L o r e 是 S t a n f o r d大学的研究者提出的能有效存储和查询 X ML数据的系统，在系统中为了提高查洵效率设计了 4种不 同的索引结构 ，分别为 v a l u e i n d e x 、 t e x t i n d e x 、 l i n k i n d e x和 p a t h i n d e x 。 v a l u e i n d e x是针对 P C D A T A为原子对象建立的， 利 用 P C D A T A作为搜索键值 ，建立对应的 B “T r e e 结构。t e x t i n d e x则是针对 P C D A T A为 t e x t 对象建立的 ， 利用 i n v e rt e d l i s t 结构， 对 P C D A T A 中较为重要的关键字作索引， 并传回所对应 的标签名称。l i n k i n d e x则是为了解决在 O E M 图中不支持逆 向指针问题，利用 h a s h i n g的方法来记录所有标签名称的父标 签。最后 ， p a t h i n d e x则是记录了部分重要的路径结构及其在 O E M 图的查询结果的对应关系。 用户在查询时 ， 系统动态地选 择所需要的索引结构， 来完成查询。 L o r e只能针对简单路径进行查询计算， 用户使用正则路径 表达式进行查询时， 系统选择索引通常需要同时使用多个索引 结构 ， 当正则路径表达式相当复杂时， 将会增加查询的负担。 可 针对正则路径表达式查询来设计索引机制 D a t a G u i d ， 利用有限 状态自动机的技术来解决正则路径表达式查询的问题 ， 减少了 使用正则路径表达式必须大量地检查文件中所有可能的路径 ， 达到加快查询的目的。 针对 D a t a G u i d e只能支持单个正则路径 1 2 2 2 0 0 9 ， 4 5 ( 1 9 ) C o m p u t e r E n n e e r i n g a n d A p p l i c a t i o n s 计算机工程与应用 表达式查询的局限性进行了改进 ，提出了一种索引机制 B i n d e x 。 此索引机制通过所定义的路径模板( p a t h t e m p l a t e )， 利 用等价关系将 X ML数据包含的对象分成若干组 ， 再通过构建 有限状态自动机来实现， 即通过定义路径模板来实现对复杂的 查询建立索引。 4 X ML查询树的最小化 查询树的最小化是逻辑优化的研究重点。 X ML查询树的 优化从语法层次和语义层次两个层次。X Q u e r y查询表达式 如下 ： f o r$ a i n r e f e r e n c e b o o k， f 0 r$ b i n $ a a u t h o r ， $ c i n $ a a u t h o r n a m e ， $ d i n $ a a u t h o r e ma i l w h e r e S b a n d $ c a n d $ d r e t u r n b o o k $ a b o o k 其 P a t t e r n T r e e ( P T Q) 如图 3 ( a ) 所示， 其中， 实心圆为查询返回 结点。若数据满足$ c ， 同时必然满足$ b ， $ b分支对查询返回结 果没有任何影响， 是冗余结点， 称这种冗余结点为语法冗余结 点。经语法优化后的 P T Q 。 如图 3 ( b ) 所示， 若从模式可知任一 a u t h o r均有 n a me ， 则 6为冗余结点， 称这种冗余结点为语义冗余结点， 经语义优化 后的 P T Q 如图 3 ( c ) 所 示。 1 o ( a ) ( b ) 图 3查询树的语法优化和语义优化过程 【 J R e f e r e n e e ! B o o k l o A u t h 0 r ； O E - m a i l ( c ) 5 复杂路径表达式选择性分析 本文设计的 X Q O查询优化模型经过逻辑优化后，结果是 一 个或多个查询树。 下一步的操作需要确定不同查询片段的执 行次序， 即中间结果集的大小。采用复杂路径表达式的选择性 分析来估计结果集规模。 X Q L查询优化器通过统计 X ML数据 分布情况，基于一定假设估计路径目标结点的中间结果集的 大小。 需要进行代价模型14 1的定义： f d = f ( Q ， ) ， i = 1 ， 2 ， n ， 这 里 Q 是一 X ML查询， 毗是其权重， 反映它在负载 w k l d中的重 要程度。 权重高说明该查询经常发生， 或执行的优先级较高。 在 不同的索引模式下， 查询负载的查询代价是不同的。查询负载 代价等于在一定索引模式 s下，查询负载 w k l d中各查询代价 与其权重乘积的和， 计算公式如下： c o s t ( w k l d ， s ) = w i * c o s t ( Q ， S j l ：l 这里S是索引模式， 即路径索引的集合， 其初始值为 。 给 定索引存储空间限制和查询负载 w k l d ，选择最优索引模式 S ， 在不超过存储空间限制的前提下， 使得 e o s t ( w k l d ， S ) 最小。要 找到这个最优解 ，如果从 n 个路径索引中选择索引模式， 就要 搜索 2 n 个候选索引模式，这是一个 N P 难问题。因此采用贪 心算法来找到一个近最优的索引模式( N O I S ) ， 在一定的磁盘 空间约束下，该索引模式可最大限度地提高给定查询负载的 查询效率。并不关心 c o s t ( w k l d ， s ) 的精确计算， 因为只需要比 较不同索引模式( s 和 s ： ) 下查询负载的查询代价( c o s t ( w k l d ， S ， ) 和 c o s t ( w k l d ， S 2 ) ) 的差异。若 c o s t ( w k l d ， S 1 ) 小于 c o s t ( w k l d ， S ) ，则表明索引模式 S 比 5 ： 带来的查询收益大。索引模式 S 的收益计算公式如下： S ) = c o s t ( w k l d ， 咖) 一 c o s t ( w k l d ， S ) 更进一步的计算公式为： 二 5 ) = ( S ) =1 其中 二 是使用索引 模式S 后查询Q 所产生的 查询收益， 它 的定义如下 ： ( s ) = d b c ( ) Q 是 Q的一部分 是指为查询 Q 中的任一路径查询构建路径索引的 S Q L语 句， d b C O S t ( ， ) 是指执行 Q所需的查询代价， 该代价由R D B M S 的优化器估算 ( 大多数商业化 R D B M S 都提供对此统计功能 的支持， 如 D B 2 ) 。 d b _ s & e ( p) 表示执行查询 Q所得结果所占的 存储空问。这样在执行查询 Q时， 就可用路径索引取代原来的 部分的查询， 降低 Q的查询代价。 通过以上公式计算路径索引的代价 ，进行设计基于代价 的路径索引选择构建算法。X ML代价估计中， 路径表达式选择 性代价估计是核心问题 ， 可将其视为一棵树， 其中一个分支为 从起点到目标点的主路径 ，其余分支为约束主支的谓词条件， 表示为： P = t 【 P t z p d I t J 其中t 为结点名； p 为谓词， 默认存在量词布尔表达式。路径表 达式的选择性估计是对满足分支条件的主支数据个数的估计。 对 X ML路径表达式的估计需要数据结构的统计信息与分布 在结构内部的值的统计信息的结合， 以计算路径的选择性。 6 XQO查询优化实验 基于 X Q O模型优化查询机制， 对使用仅 X Q u e r y语言和结 合 X Q O模型进行优化后的X MI 文档进行查询测试比较。 测试 平台为 P 4 2 8 G H z 处理器，5 1 2 M内存， Wi n d o w s 2 0 0 0操作 ， J D K 1 5编程进行具有大量信息的X ML文档查询。 墨 7 5 鲁6 0 45 是 3 0 娶 15 0 1 5 O 3 0 0 4 5 0 6 0 0 7 5 0 9 0 0 X ML文件大小， K B 图 4 X Q O查询优化实验结 果 选取不同大小的X ML文档， 对比采用 X Q O优化模型和只 采用 X Q u e r y 查询语言进行查询。 在给定代价参数后， 从图中可 ( 下转 1 3 3页) 廉佐 政， 王海珍 ， 邓 文新 ， 等 ： 应用记 忆演化 学习的 A g e n t 协商研 究 2 0 0 9 4 5 ( 1 9 ) 1 3 3 存储长度 ， 即保留前 次 o ff e r 协商的实时奖励值。 利用公式( 5 ) 计算延迟奖励值 值， 定义计算公式为 ： ， J q ( ， ， ) = a + ( 1 - 0 ) R q ( ， ， a ) + 0 tT ma x D q c _ l ( ， ， a ) ( 5 ) aEA ( 4 ) 利用延迟奖励 值修正短期记忆得到的实时奖励 ， 根据公式( 1 ) 计算 A g e n t 行动选择概率， 再根据式( 2 ) 计算选择 概率最高的行动， 产生最佳的 o f f e r 值， 并保存。 如果 A g e n t 对当 前对方 o f f e r 满意， 则接受 ， 否则 ， 根据式( 2 ) 更新信念模型 ， 开 始下一轮 o ff e r 交互。 5 实验分析 将上面提出的基于记忆演化的强化学习算法和标准强化 学习算法使用 S w a r m I 嚏 模仿真实验。S w a r m是研制仿真复杂 适应系统的多 A g e n t 系统软件平台， 它提供了离散事件仿真事 务交互的基本类库， 可以在其上开发模拟任何物理系统与社会 系统， 而不受模型和模型要素之间交互的约束。 算法设计的基本参数为 ： 短期记忆存储长度为 1 ， 长期记 忆存储长度为 1 0 ； 算法初始值为 ： Q 0 ( )= 1 ， 8 o = 1 ， y = 0 5 ， z = 0 0 2 ， P o=0 1 8 00 7 00 6 00 5 00 4 0 0 3 00 2 0 0 1 0 0 0 5 1 0 1 5 2 O 2 5 3 0 3 5 4 O 4 5 5 0 5 5 6 0 6 5 7 O 7 5 8 O 8 5 9 O 9 51 0 0 学 习次数 图 1 基于记忆演化 的强化学 习算法实验 由图 1 可以看出基于记忆演化的学习和传统的 Q学习都 能随着交互提议的次数增加而很陕收敛， 适应环境变化。实验 结果显示， 两类 A g e n t 的学习性能较为相似 ， 表明基于记忆演 化的强化学习算法在 A g e n t 协商中的学习是有效的， 并且通过 适当的设定， 算法也收敛。 6 结束语 综合以上实验数据 ， 可以得出结论： 在系统中采用基于记 忆演化的强化学习算法是有效的， 且通过设定， 算法也收敛。 在 MA S系统中， 随着协商任务负载的加大 ， 与传统 Q学习相比， 具有一定优势。在电子商务领域，可以有效地提高智能 A g e n t 的协商效率。 对于本文提出的算法 ，由于需要保存记忆阶段的数据， 所 以学习算法需要较多的存储空间，记忆结构的设计较复杂， 同 时 ， 对系统的资源需求较大。因此 ， 在今后的工作中， 还需要设 计更加合适的记忆结构，并进一步研究相关的强化学习方法， 使之能够与其配合使用， 使模型与算法更加完善。 参考文献 ： f 1 K a z u o M L e a r n i n g s c h e d u l i n g c o n t r o l k n o w l e d g e t h r o u g h r e i n f o r c e m e n t s J I n t e r n a t i o n a l T r a n s a c t i o n s i n O p e r a t i o n a l R e s e a r c h ， 2 0 0 0， 7 ( 2 ) ： 1 2 5 1 3 8 【 2 F a t i ma S S ， Wo o l d r i d g e M， J e n n i n g s N R A n a g e n d a - b a s e d fl a m e w o r k f o r mu l t i i s s u e n e g o t i a t i o n J A r t i fi c i a l I n t e l l i g e n c e ， 2 0 0 4 ， 1 5 2 ： 1 - 4 5 【 3 1 王立春， 高阳， 陈世福 A O D E中基于强化学习的A g e n t 协商模型 J _ 南京大学学报 ， 2 0 0 1 ， 3 7 ( 2 ) ： 1 3 5 1 4 1 4 彭志平， 李绍平 分层强化学习研究进展 J I _计算机应用研究， 2 0 0 8 ， 4 ( 2 5 ) ： 9 7 5 9 7 8 【 5 L a i G u o m i n g ， L i C u i h o n g ， S y c a r a K E ff i c i e n t mu l t i - a t t r i b u t e n e g o t i a t i o n w i t h i n c o mp l e t e i n f o r m a t i o n J G r o u p D e c i s i o n a n d N e g o t i a t i o n ， 2 0 0 6 ， 1 5 ( 5 ) ： 5 1 l - 5 2 8 6 Me d i n D L ， R o s s B H， Ma r k ma n A B C o g n i t i v e p s y c h o l o g y M 3 r d Ed Ch i c h e s t e r ： W i l e y， 1 9 9 9 7 长乐 基于记忆演化的多 A g e n t 系统强化学习f D 1 北京： 清华大学 ， 2 0 0 2 【 8 杨明， 鲁瑞华， 邱玉辉_ 多A g e n t 自 动协商中机器学习的应用研究 J _ 通讯和计算机 ， 2 0 0 4 ， 1 ( 1 ) ： 2 2 2 7 【 9 马彦， 刘莉基于A g e n t 的双边多议题协商算法叨 计算机工程与应 用 ， 2 0 0 8 ， 4 4 ( 1 ) ： 2 1 6 2 2 8 f 1 0 S t e f a n s s o n B S w a r m： An o b j e c t o ri e n t e d s i mu l a t i o n p l a t f o rm a p p l i e d t o ma r k e t s a n d o r g a n i z a t i o n s C L NC S 1 2 1 3 ： E v o l u t i o n a r y Pr o g r a mmi n g VI B e r l i n： S p r i n g e 卜 Ve r 1 g ， 1 9 9 7： 5 9 7 1 ( 上接 1 2 2页) 以看出