XML编码及其结构连接算法的研究

摘要

XML,查询处理技术,目前普遍采用的是路径分解和一次一集合的匹配方式,这种处理方式在效率上明显优于传统的导航式遍历方式。在这种处理方式中,节点编码和结构连接是非常重要的两种技术,在查询处理中起到决定性作用。为提高查询处理的效率,本文提出了一种新的XML编码方案,即BTB编码,并在此基础上提出了基于BTB编码的结构连接新算法——BTBContainJoin。
　　 论文分析了已有编码的不足,借鉴了哈夫曼编码的思想,提出了一种新的基于二叉树的编码形式。这种编码形式用一个二进制位保存一条边的路径信息,每个父节点编码都是其子节点编码的前子串。因此,可以根据编码的字符串操作判断节点的关系,并且可以根据节点长度判断它在二叉树中的层次,不需要另外保存层次信息。新的BTB编码把XMI。文档树转化为二叉树,并按路径编码。编码采用二进制串形式,每个二进制位代表了二叉树中的一条边,以保存节点的路径,支持包含关系的结构判定。优化的BTB编码引入了下移标识字符,来支持父子结构关系和兄弟结构关系的判定。BTB编码具有类似于前缀编码的性质,保存了节点的路径信息,但在存储代价上明显优于前缀编码。实验表明,BTB编码具有较好的CPU性能,且编码长度较短。
　　 论文通过分析已有的结构连接算法的不足,利用划分的思想,分析了对BTB编码空间的划分方法,提出了一种新的基于划分的结构连接算法BTBContainJoin。新算法基于BTB编码提出,以划分为核心思想,先对编码空间进行划分,然后以此为依据对输入集合进行划分。划分后的结构连接操作在子集合间执行,子集合的连接结果合并起来即为整个结构连接的结果。该算法不需要对输入数据排序,节省了时间和空间开销。实验表明,BTBContainJoin算法具有较好的CPU性能。