杨 扬，李海歌

（1.河南大学 计算中心，河南 开封475004；2.开封市建筑设计院有限公司，河南 开封475004）

0 引 言

XML作为互联网中一种数据表示与交换的标准，具有高效结构连接算法的查询方法成为XML数据库的研究热点。当前，为优化XML数据查询和更新，AList和DList列表之间的结构连接操作构成了结构查询的核心，为了加速结构连接，研究人员首先对XML文档树结点编码来判断结点之间的结构关系，而无需遍历整棵XML文档树。再者通过高效的结构连接算法提高查询效率。高效的XML查询重在优化的结构连接算法，与之相关的有益算法大多基于归并思想，根据XML文件格式的特点和编码规则减少或避免了无效的结构连接。为了能够规避不参与结构连接的结点，一些算法思想采用索引结构进一步减少连接的扫描代价，但索引的维护又需要额外的时间和空间开销。为解决上述问题，本文给出的扩展的Dewey编码，加速了结点的结构关系判断，在此基础上，论文改进了Stack－Tree－Desc（STD）算法，提出了一种不依赖于索引结构的优化算法，利用栈进行缓存来减少连接次数，在查找下一个需要参与连接的结点时引入二分查找，有效地跳过了不必要的结构连接，无需顺序扫描，最坏情况下AList和DList列表只需各遍历一次。实验结果表明，论文所用编码方案和改进算法具有较好的查询效果。

1 相关研究

当前，多数结构连接算法基于归并结构，根据XML文件格式的特点和编码规则减少或避免了无效的结构连接。C.Zhang和J.Naughton等提出了一种执行性能优于关系查询引擎的结构连接算法MPMGJN，该算法能有效地实现包含连接，但多次重复地扫描内表会影响算法性能。为了避免对内表重复扫描，S.Al－Khalifa和 H.V.Jagadish等提出了STD算法，该算法维护了一个用于存放可能需要连接的祖先结点栈，需对AList和DList列表分别顺序扫描一次即可实现包含关系的结构连接。Shu－Yao Chien、Z.Vagena和Donghui Zhang等提出的Anc－Desc－B＋算法，根据两个列表中有些结点能够事先判断出不必参与结构连接，为减少扫描代价，算法中的B＋树索引成功地跳过了不必要的结点，优化了Stack－Tree算法。而B＋树索引维护时需要额外的时间和空间开销，本文从另一角度，不建立索引，在查找下一个需要参与结构连接的AList列表中的a结点与DList列表中的d结点时，采取了二分查找来跳过不需参与连接的结点，最坏情况下AList和DList列表仅需扫描一次即可实现结构连接。

2 IPE编码方案

XML结构查询，通常先将XML文档中的结点按照某种编码方案编码，利用结点间的编码规律来判定AList和DList列表结点对（a，d）的结构关系。

2.1 IPE编码（improved prefix encoding）

IPE编码，本质上是一种扩展的Dewey编码，由字母、整数、点（.）组成，双亲结点的编码作为该结点编码的前缀。

定义1 编码映射：集合N＝｛1，2，3，4，5，6，7，8，9｝与集合C＝｛A，B，C，D，E，F，G，H，I｝，规定f＝｛＜1，A＞，＜2，B＞，＜3，C＞，＜4，D＞，＜5，E＞，＜6，F＞，＜7，G＞，＜8，H＞，＜9，I＞｝，f：N→C，对唯一n∈N，有唯一的c∈C与之对应。

定义2 IPE编码：设XML文档树中结点u的IPE编码为p（u），则结点u的孩子结点v的IPE编码c（v）＝p（u）Nv，其中c（v）编码的层次数称为层级L；每一层的区别编码Nv代表了结点v在结点u的所有孩子结点中位置关系，各层的结点编码之间用数字唯一表示，Nv是个位数，以Nv原数值表示，若Nv大于10，除个位数不变，其它位的转换均使用定义1的编码映射来实现。

图1为IPE编码片段。例如，Dewey编码“2.31.3.2”，取消原 Dewey编码中各层之间的“.”分隔符，改进为IPE编码“2C132”，节省了存储空间，也可清晰地判断各层编码的分隔。

图1 IPE编码片段

2.2 IPE编码的XPath查询

本文给出的基于IPE编码的结构连接算法在进行结构关系判断时，需要比较结点的编码大小，比较规则为：父小于子，前驱兄弟小于后继兄弟，后裔大于前驱兄弟且小于后继兄弟。

例如，图1中所示的编码，“2C1”＜“2C11”＜“2C12”＜“2C122”＜“2C13”＜“2C131”。

利用IPE编码直接判断结点之间的结构关系，加速了结构连接，表1给出了基于IPE编码的XPath查询的判别方法。

表1 IPE编码的XPath查询

3 B－S算法（binary－stack）

3.1 B－S算法思想

基于栈的结构连接算法在效率上高于直接归并算法，IPE编码支持基于栈的连接算法，因此提出的基于IPE编码的B－S算法也是基于栈的。B－S算法中输入列表是对XML文档树前序遍历有序，输出结果按后裔有序。STD算法的I/O代价是对AList和DList列表各顺序扫描一遍，BS算法改进了STD算法，采取了二分查找来跳过不需参与连接的结点，有效地减少了扫描结点的数量。

B－S算法的基本思想是：设参加结构连接的两个列表AList和DList，如果a和d均不是栈顶元素的后裔，则将栈顶元素出栈。若a是d的祖先，将a入栈，同时将a指向AList列表中下一个参与结构连接的结点。若上述两个条件均不满足，则将栈内所有与当前d形成祖先/后裔关系的结点对输出，并将d指向DList列表中下一个参与结构连接的结点。AList和DList列表为静态有序表，按IPE编码升序排列。在静态有序表AList和DList中查询符合结构连接条件的结点，采用了查找效率很高的二分查找方法，避开了AList与DList列表中结点的逐个扫描。B－S算法中的第（7）到（18）步是在AList列表中查找下一个参与结构连接的a结点，第（23）步与第（7）到（18）步相似，调用BinarySearch（d，first，last，a），在 DList列表中查找下一个参与结构连接的d结点。

3.2 B－S算法

（1）a ＝AList.firstNode ＆＆ d ＝DList.firstNode＆＆stack s is empty；

（2）while（AList and DList are not empty or stack s is not empty）｛

（3） if（neither a or d is the descendant of the s.top）｛

（4） s.pop（s.top）；｝

（5） else if（the IPE of a is the substring of the IPE of d）｛//a is the ancestor of d

（6） s.push（a）；

（7） BinarySearch（a，first，last，d）｛//to search next a which participates in structural join

（8） mid＝（first＋last）/2；

（9） if（first＞last）

（10） return false；

（11） else if（d＜a［mid］）

（12） return BinarySearch（a，first，mid－1，d）

（13） else if（d＞a［mid］）//a is the ancestor of d

（14） return BinarySearch（a，mid＋1，last，d）

（15） else if（d＞a［mid］＆＆the IPE of a is the substring of the IPE of d）

（16） return a［mid］；//a［mid］is the target

（17） ｝//to search next a which participates in structural join using BinarySearch

（18） ｝

（19） else｛

（20） for（t＝s.bottom；t！＝null；t－－）｛

（21） append（a，d）to output；

（22） ｝

（23） BinarySearch（d，first，last，a）//to search next d which participates in structural join

（24） ｝

（25）｝

3.3 算法分析

在查找下一个进行结构连接的结点时，STD算法为有序表的顺序查找，平均查找长度较大，特别是当列表中结点很多时，查找效率较低，时间复杂度为O（n）。B－S算法在查找下一个有效结构连接的结点时，采用了有序表的二分查找，时间复杂度最好情况O（1），最坏情况O（logn），平均情况O（logn）。并且当结点分布紧凑且嵌套较多时，引入的二分查找效率较高。可见B－S算法在处理下一个能够参与结构连接问题上优于STD算法。

4 实 验

4.1 实验环境

本文实验环境为：英特尔酷睿2双核T5870@2.00GHz笔记本处理器，2GB内存，160GB硬盘，Windows XP 专 业 版（32 位/SP2/DirectX 9.0c） 操 作 系 统，NetBeans IDE 6.8for Java。

实验所用数据集的DTD如图2所示，根据该DTD利用XML文档生成器自动生成一个XML文档。该测试文档大小为67.3MB，共有元素和属性结点1648372个，其中toy元素2498个、grade元素402113个、production元素6243个、assembling元素393370个、instruction元素157641个。实验对基于IPE编码的B－S算法进行性能分析。

图2 实验测试所用DTD

实验测试查询用例，见表2。查询Q1为最常见的查询，父结点仅有一个孩子结点，且孩子结点又为叶子结点；查询Q2较为复杂，可多次出现的父结点拥有多个孩子结点，孩子结点可零次或多次出现，而且孩子结点又存在嵌套关系；查询Q3反映双亲结点嵌套；查询Q4是一个常见查询，它没有明确指定连接的孩子结点的标记名。

表2 查询用例

4.2 实验分析

实验通过保持孩子结点数量不变而双亲结点的百分比改变的方法，对STD算法与B－S算法的性能进行测试，分别验证算法结构连接时扫描结点的数量和算法所耗用的时间。

（1）算法连接结点数：即符合某种结构关系的结点配对时扫描的元素结点的数量，这是算法跳过不参加结构连接结点的优越性的体现。表3表现了维持原有孩子结点的百分比，随机按比例删除父结点的情况，将STD算法与BS算法依据论文中DTD生成的XML文件进行实际扫描结点数比较。由表3可知，在相同的百分比下，B－S算法扫描的结点数量少于STD算法；当按比例减少XML文件中父结点的百分比时，两种算法实际参与扫描、形成相应结构关系结点对的数量均有所降低，但B－S算法扫描结点数量少于STD算法。在跳过不相关结点的能力上，B－S算法优于STD算法。

表3 STD算法与B－S算法扫描元素结点数量的对比

（2）结构连接耗用时间：反映了算法的性能优劣。图3中，两种算法的查询耗用时间均随双亲结点百分比的降低而减少，但B－S算法耗用的时间要少于STD算法。B－S算法的优点在于不必将结点逐一比较、全部访问，AList和DList中的元素利用二分查找方法每次进行折半查找处理，提高了查询效率。当双亲结点的数量减少时，B－S算法由于能够减少被扫描元素结点，因此它的性能优于顺序扫描的STD算法，这在图3（a）、（b）、（d）中均可体现。

图3 两种算法运行时间比较

5 结束语

本文基于Dewey编码给出了IPE编码方案，它加速了XPath查询轴的结构关系的判断，有效地辅助了B－S算法的执行。为跳过无益的结点扫描，B－S算法对STD算法进行了改进，通过二分查找，每次将查找折半处理，缩小了查找范围，从而提高了结构连接的效率。实验结果表明改进后的B－S算法比STD算法具有较好的查询效率。结构连接作为XML查询中的关键，因此，下一步的研究工作是在此基础上研究如何进一步优化查询操作。

［1］KONG Ling－bo，TANG Shi－wei，YANG Dong－qing，et al.Querying techniques for XML data［J］.Journal of Software，2007，18（6）：1400－1418（in Chinese）.［孔令波，唐世渭，杨冬青，等.XML数据的查询技术［J］.软件学报，2007，18（6）：1400－1418.］

［2］HUANG Yuan，YANG Wei－wei.Structural join algorithm in XML query［J］.Computer Aided Engineering，2007，16（1）：74－75（in Chinese）.［黄渊，杨薇薇.XML查询的结构连接算法［J］.计算机辅助工程，2007，16（1）：74－75.］

［3］WANG Shi－fu，HAO Zhong－xiao.Efficient structural join for XML based on region encoding［J］.Journal of Harbin University of Science and Technology，2008，13（2）：53－56（in Chinese）.［王仕福，郝忠孝.基于区间编码的有效XML结构连接［J］.哈尔滨理工大学学报，2008，13（2）：53－56.］

［4］ WAN Chang－xuan，LIU Xi－ping.XML database technology［M］.2nd ed.Beijing：Tsinghua University Press，2008（in Chinese）.［万常选，刘喜平.XML数据库技术［M］.2版.北京：清华大学出版社，2008.］

［5］QIN Zun－yue，CAI Guo－min，HUANG Yun.Sibling structural join for XML document based on extensible region coding［J］.Journal of Nantong University（Natural Science Edition），2009，8（1）：26－28（in Chinese）.［覃遵跃，蔡国民，黄云.基于扩展区间编码的XML兄弟关系结构连接［J］.南通大学学报（自然科学版），2009，8（1）：26－28.］

［6］XU Juan，LI Zhan－huai，LOU Ying.Novel position－based prefix encoding approach to reduce update cost for dynamic XML data［J］.Computer Science，2009，36（2）：167－171（in Chinese）.［徐娟，李战怀，娄颖.基于节点位置信息的降低更新代价前缀编码方案研究［J］.计算机科学，2009，36（2）：167－171.］

［7］XU Liang，LING T W，WU Hua－yu，et al.DDE：From Dewey to a fully dynamic XML labeling scheme［C］.Proceedings of the ACM Conference on SIGMOD，2009：719－730.

［8］JI Cong－rui，DENG Zhi－hong，TANG Shi－wei.An XML keyword retrieval algorithm based on nearest pair［J］.Journal of Software，2009，20（4）：910－917（in Chinese）.［吉聪睿，邓志鸿，唐世渭.基于Nearest Pair的XML关键词检索算法［J］.软件学报，2009，20（4）：910－917.］

［9］ZHANG Bo，GENG Zhi－hua，ZHOU Ao－ying.Adaptive structural index for efficient processing of XML path queries［J］.Journal of Software，2009，20（7）：1812－1824（in Chinese）.［张博，耿志华，周傲英.一种支持高效XML路径查询的 自 适 应 结 构 索 引［J］.软 件 学 报，2009，20（7）：1812－1824.］

［10］QIN Zun－yue，HUANG Yun.A structural joins algorithm based on extended region coding［J］.Computer Systems ＆Applications，2009，19（4）：61－64（in Chinese）.［覃遵跃，黄云.一种基于扩展区间编码的XML结构连接算法［J］.计算机系统应用，2009，19（4）：61－64.］

［11］JIANG Mei－xian，LU Yan.A new encoding－based XML structural join algorithm［J］.Journal of Shandong University of Science and Technology（Natural Science），2009，28（2）：92－96（in Chinese）.［蒋美仙，路燕.一种新的基于编码的XML结构连接算法［J］.山东科技大学学报（自然科学版），2009，28（2）：92－96.］

［12］WEN Si，WEN Gui－hua.Left child and right sibling structural join algorithm based on extended prefix－coding［J］.Computer Engineering and Design，2010，31（10）：2312－2319（in Chinese）.［文思，文贵华.基于扩展前缀编码的左孩子右兄弟结构连接算法［J］.计算机工程与设计，2010，31（10）：2312－2319.］

［13］ZHU Xiao－juan.XML structural join algorithm based on extended region coding［J］.Computer Engineering，2010，36（22）：49－51（in Chinese）.［朱晓娟.基于扩展区间编码的XML结构连接算法［J］.计算机工程，2010，36（22）：49－51.］

［14］YANG Yang，YIN Ke.A path query based on XML prefix encoding［J］.Journal of Henan University（Natural Science），2010，40（1）：85－89（in Chinese）.［杨扬，尹柯.一种基于XML前缀编码的路径查询［J］.河南大学学报（自然科学版），2010，40（1）：85－89.］

［15］ZHENG Hong－hui，GUO Hong.XML keyword search algorithm based on efficient LCA［J］.Journal of Computer Applications，2010，37（12）：120－124（in Chinese）.［郑弘晖，郭红.基于有效最低公共祖先的XML关键字查询算法［J］.计算机应用，2010，37（12）：120－124.］

［16］ZHAO Sheng－meng，ZHAO Lei.Extended Dewey encoding algorithm of Twig pattern query without merging［J］.Journal of Chinese Computer Systems，2011，32（5）：837－839（in Chinese）.［赵圣猛，赵雷.一种采用扩展Dewey编码非归并的小枝模式查询算法［J］.小型微型计算机系统，2011，32（5）：837－839.］