闫文刚，常 亮，于莉莉，刘 义，孙淑莉

(佳木斯大学，黑龙江 佳木斯154007)

0 引 言

为了加快XML 文档的检索效率，已经出现很多XML 文档的索引技术，而这些技术的核心是对XML 文档进行合理的编码，这在XML 文档检索过程中起到了十分重要的作用，对于XML 文档的索引编码技术一般分为两种方式，一种是建立XML文档树的路径索引，这种方式对XML 结构查询具有较快的响应速度，另一种是对XML 文档树中的节点或边进行编码，此种方式可以快速的判断节点之间的关系，从而避免对整个XML 文档的扫描.XML 文档编码包括三种类型:基于路径的编码、基于节点序号的编码和混合编码方式［1］.

在设计XML 编码方案时需要考虑的因素包括:

(1)编码应能够体现出XML 文档的结构特征，能够正确描述判断节点间关系，即支持祖先/子孙、双亲/孩子、节点位置等关系的结构查询.

(2)插入和删除操作导致的编码重置的代价及其算法的复杂度也必须予以考虑.

(3)编码必须要和采用的数据模型相一致，且编码的最大长度或平均长度也应加以考虑.

(4)XML 文档树的检索效率也应加以考虑.

考虑到DOM 节点树和XXDM 文档树中所有的属性节点和文本节点都是叶节点故进行如下定义.

定义1 XML 文档树是一颗树，且该树满足如下条件:

(1)树中任意一个内部节点iNode，对应XML文档中的一个元素，表示为E(iNode);

(2)树中任意一个外部节点oNode，对应XML文档中的一个属性或文本，当oNode 是一个属性节点时表示为A(oNode)，当是一个文本节点时表示为T(oNode).

该定义的主要特点是将属性节点和文本节点作为外部节点，这样就可以更加清晰的描述XML文档的结构，从而以更加高效的方式组织这些叶子节点［2］.

1 实验方案

本实验的目的在于在发生动态更新的XML 文档中比较SUC 编码方案与其他编码方案进行重建编码的效率.设计思路如下:首先利用DOM 解析器将XML 文档解析为DOM 文档树，然后针对DOM 文档树进行编码，将编码结果存储到关系数据库中.实验系统体系结构图如图1 所示.

图1 实验系统体系结构图

其中SUC 编码器类包括下列成员函数［3］:

在数据库中建立两个表，其中一个描述内部节点，另外一个描述外部节点.内部节点包含4 个属性.对于外部节点，因其是用来描述属性和文本的，而文本可以看做是一个特殊的属性节点，故属性节点包含两个属性:属性名和属性值，其中文本作为特殊的属性节点，其属性名固定为“文本”.两个表单结构模式如下:

内部节点表nNodeTable(Xno，Level，Parent，Part);

外部节点表wNodeTable(Wno，Name，Value，Xno);

其中Xno，Level，Parent 为32 位二进制向量;因此在数据库中和Java 环境下数据类型皆设置为整型.

为保证每个Part 编码逻辑块拥有足够的空间，将Part 设置成8 个字节的二进制位，每个Part逻辑块占8 位二进制位(即一个字节)，因此共有8个Part 编码逻辑块.因而Part 在PostgreSQL 中的数据类型为int8，在Java 中数据类型为long.

需要说明的是，以上的数据库设计不能完全描述实际应用中遇到的所有XML 文档树，该描述方法只能描述一颗文档树.由于本实验的主要目的是验证不同编码方式在编码性能和处理插入操作时的时间性能上的区别，不需要同时管理多颗文档树，因此上述数据库设计可以满足本实验的实验需要.

2 实验过程及结果

在测试编码的动态调整性能时，操作对象为初始化SUC 编码实验中用dom4j 解析的XML 文档树，在该文档树中随机插入n 个节点，每个节点的插入位置在文档树中随机挑选(即随机选定n 个节点的Xno 作为待插入节点的左兄弟节点的Xno)然后使用DSUCcode()函数确定需要重新编码的节点个数，并对这些节点进行重新编码，然后将重新编码后的节点编码写入数据库中，对每次插入操作重复5 次，取5 次重新编码所花费的时间的平均值作为其插入时间消耗.

在完成对本文提出的SUC 编码实验测试的同时，实验中还对前缀编码和Zhang 编码一并进行了测试.

表1 三种编码动态调整性能比较

图2 M=2 时的时间消耗比

图3 M=10 时的时间消耗比

在对长度为2M 和10M 的两个XML 文档分别进行五次插入试验后的三种编码动态调整过程中重新生成编码的时间消耗如表1 所示.

为了说明问题，设tp 为前缀编码动态调整时间消耗与SUC 编码动态调整时间消耗的比值，tz为Zhang 编码动态调整时间消耗与SUC 编码动态调整时间消耗的比值.

分析表1 结果可知:

(1)XML 文档较小时(文档长度小于2M)，当插入结点个数较少时(插入节点的个数小于10个)，三种编码方式的动态调整时间消耗相差不多，但随着插入结点个数的增加，当插入节点个数大于100 时，SUC 编码与前缀编码和Zhang 编码相比，其动态调整时间消耗相差10 倍左右，如图2 所示.

(2)XML 文档较大时(文档长度大于等于10M)，无论插入节点个数为多少，SUC 编码与前缀编码和Zhang 编码相比，其动态调整时间消耗相差10 倍之多.如图3 所示.

因此，本文提出的SUC 编码方法在进行对XML 文档做插入操作时在处理XML 文档插入式编码时的动态调整性能具有显著优势.由于在SUC编码初始化过程中引入了均衡调整思想，有效地避免了缺位冲突，当出现缺位冲突时采用i 次块增位调整进行快速编码，因此并没有出现随着插入结点个数大量增加而引起的编码重构次数的激增.

3 优点与不足

SUC 编码优点如下:

(1)编码的动态调整性能较好.由实验结果可知该种编码方法对XML 文档的更新具有快速的调整能力.

(2)编码效率高.SUC 编码的Part 部分采用位向量的方式定址，其结构与操作系统的段式存储管理相类似，所有的操作都是基于位运算的，故编码效率较高.

(3)编码方式灵活.由于位向量定址方式，每个逻辑块的二进制位数可以根据XML 文档的大小动态调整，因此SUC 编码方式较为灵活.

不足与需改进的地方如下所述:

SUC 编码对包含关系的结构连接支持有限，这主要是由于该编码中不含XML 文档树的全局路径信息，而只含有局部的路径信息，因此在使用SUC编码的文档树中无法通过编码判断节点间的包含关系.今后将进一步研究在编码过程中如何合理引入全局路径信息.

［1］ 周爱武，李孙长，程博，等.XML 数据库的研究与应用［J］.计算机技术与发展.2009，9(9):218－224.

［2］ Joe Marini.The Document Object Model［M］.The McGraw－Hill Companies，Inc.2002.

［3］ 闫文刚，李晶.一种XML 文档树节点编码的动态调整算法的研究［J］.佳木斯大学学报(自然科学版)，2010，28(3):360－362.