摘 要：针对结构连接[1]操作的高效问题，使用了GRP[2]标记来标记XML文档，应用GRJ算法了设计了查询处理系统，并通过实验证明，在大数据量的条件下，GRJ算法的性能要优于Stack-Tree-Desc[3]算法。
关键词：XML；结构连接；GRP
结构连接算法是XML查询的核心，对该算法的研究具有重要的理论意义和现实意义。我们利用了基于组的前缀标记模式，在此基础上实现了基于组的结构连接算法。通过实验证明了在无序无索引条件下该方法的查询性能有较大的改善。
一、 简单前缀标记模式SP和基于组的前缀标记模式GRP
简单前缀标记模式(SP)。可以通过前序遍历树来产生简单前缀标签。具体为：对任意新节点v，v的标签L（v）=L（u）（1…1）i-10，其中u是v的父节点，i是u的孩子数。
在GRP标记模式中任何标签都包含一个组ID和一个组前缀标签，其中组ID是一个整数而组前缀标签是一个二元串。在同一组中的所有节点有相同的组ID，通过它们的前缀标签进行区分。根节点有固定的标签（1，0）。为了避免一个组中的节点数无限增长，定义组i中的最大节点数为i，这表明：组1至多包含1个节点，组2至多包含2个节点…。如果一个组中的节点数达到最大值，则称此组已满。
二、 使用GRP标记的结构连接算法--GRJ算法[1]
GRJ的主要思想是把连接操作划分为两类，即组内部连接和组之间连接。
组内部连接：连接同组之间的元素。可以通过比较元素的前缀标签实现。
组之间连接：连接不同组之间的元素。这时需要用到GR树进行比较。
GR树。给定一棵用GRP标记的XML树T，在一棵GR树中，每个节点n表示T中的一个组并且用
算法1：GRJ算法
输入：A是祖先列表，D是后裔列表
输出：祖先后裔元素对
1 分别扫描A、D列表一次，把每个元素分配到各自的组所对应的桶中
2 初始化哈希表DgroupHash，其中关键字是Dlist的组ID，且每个哈希值被初始化为一个空集合
/*DgroupHash（i）存储组i的所有祖先节点的标签，即用GRP模式表示的节点标签*/
3 For i=2 到最大组 do
/*因为组1只包含根节点，所以i值从组2开始*/
4 根据DgroupHash，从祖先组和后裔组中直接输出祖先后裔对
6 对第i个组执行组内连接
/* 通过比较元素的前缀标签实现*/
7 对第i个组调用算法2执行组间连接
算法2: 组间连接
描述: 算法目的是找到组i的所有后代组，并把结果存储在哈希表DgroupHash中
输入 : 把组i中存在的祖先列表中的值放到Ai表中去,形成Ai表，哈希表DgroupHash, GR树
输出: 更新后的DgroupHash
对GR树中的每个组i的每个孩子c和Ai表中的每个元素a
//假设c被标记为 (c.groupID, c.parent-prefix-label),a被标记为(i, a.prefix-label)
1.1 如果a.prefix-label等于c.parent-prefix-label的前缀
/*表示元素a是组c的祖先 */
1.2 那么 { 把元素a加入集合Ancestor(c);
1.3 把c加入集合N中; }
/*在Ancestor(c)中的任何元素都是组c的祖先*/
2. 遍历GR树中每个节点c∈N的子树
2.1 对任意被访问的节点 v,
/* 假定v被标记为(v.groupID,v.parent-prefix-label)*/
2.2 如果哈希表Dgrouphash 包含关键字v.groupID
2.3 那么Dgrouphash(v.groupID) := Dgrouphash(v.groupID) ∪ Ancestor(c);
/* 这表示如果一个元素是组c的祖先，那它也是组v的祖先,因为c是v的祖先.*/
三、 使用GRJ算法的查询系统设计
3.1 系统实现图
（1）XML文档解析器
解析XML文档，采用java实现。因为系统要处理XML文档，因此要选择合适的XML语法解析器。作为java技术的两类不同的语法解析器，DOM和SAX各有其优点。本系统中采用DOM解析器。解析的同时给节点赋予标签，使用GRP标记模式。
利用GRP给节点赋值。
对任意新插入的节点n，GRP首先询问n的父亲所在的组是否已满，如果不满，则节点n被标记为与其父节点同一个组。然后，在这同一个组中，使用前缀标记模式来确定节点n的前缀标记。相反地，如果n的父亲所在的组已满，则GRP询问n的最近标记的兄弟所在的组是否满，如果不满，则n用此组进行标记。否则，应该用一个新组来标记n，且n的前缀标签为0。
对XML文档树中的每个节点进行编码并将编码存储在数据库中，即系统中的XML文档集中。
（2）XML文档索引构造器
索引结构的作用是在XML文档集中找到所有具有相同标签的节点（主要指元素和属性节点），为后面的结构连接提供输入节点集。
设计中采用了B+树索引，以元素标签名作为索引关键字建立索引。叶节点的指针域中存储指针值，该指针指向所有具有相同标签的节点所在的桶。
优点是当原XML树发生变化时（插入或删除），大部分操作是对B+树进行查找，找到指定叶节点后，在指针所指向桶中进行插入或删除即可。不需要频繁地对原B+树结构进行修改，即分裂和提升以及合并不会频繁发生，这样可以避免对磁盘的大量访问。只有当插入新的标签时，B+树结构才会修改。
（3）XML文档集
XML文档集存储采用GRP编码后的XML节点信息。
（4）XML查询器
执行用户查询。是系统中的中的重点部分。用户提出XPath查询，提交给XML查询处理器。查询处理器采用结构连接算法进行处理。具体如下：
先对XPath表达式进行分解，得到多个二元关系查询（即父子关系和祖先-后代关系）。
再对每一个二元关系采用组结构连接算法进行计算，得到查询的结果。
最后把上一步中得到的结果连接起来得到最终结果。
四、实验
通过实验测试GRJ算法的有效性以及效率。使用分析数据和真实数据集分别实验。包括DBLP[4]和XMark[5]以及IBM XML产生器。
当输入元素有序时，对SP模式使用算法Stack-Tree-Desc来测试。由于Stack-Tree-Desc是基于范围标记模式的（使用了区间编码），所以先修改它以适应SP标记模式。算法思想不变，只是编码方式变化。
实验结果分析：Stack-Tree-Desc是基于SP标记模式的，而GRJ是基于GRP模式的。因而SP标签的规模大于GRP。对GRP访问两次的时间可能仍然会小于访问SP一次的
时间。说明了标签规模大小更重要。
下图中横坐标表示参加连接的节点集中节点个数，纵轴表示连接运算所耗费的时间。从图中可以看到，虽然GRJ算法需要两次扫描元素列表，而Stack-Tree-Desc算法只需扫描一次，但在大数据量的条件下，GRJ算法的性能仍然要优于Stack-Tree-Desc算法。
参考文献
XMARK: The XML-benchmark project. http://monetdb.cwi.nl/xml 2002.
