基于更新代价的XML文档区间编码方案研究

• 作 者: 徐娟;李战怀;王彦龙;
• 机 构: 西北工业大学计算机学院,西安,710072
• 出 处: 第二十三届中国数据库学术会议(NDBC2006)
• 发表日期: 2006年期

XML已经成为互联网上数据表示和交换的标准,大量的XML文档出现在网络中,有效地存储XML数据并提供高效的XML数据查询,成为当今急需解决的问题.目前,大部分有关XML数据的索引和查询技术都是基于某种对XML文档树的编码技术,区间编码是一种主流的编码方式.
XML编码技术,就是按照一定规则给XML文档树中的每一个结点分配唯一的编码.通过编码,可以在不遍历XML文档树的前提下,直接判断两个结点之间的关系.区间编码采用深度优先遍历XML文档树的方式给树中的每个结点赋予一对整数值,祖先结点的编码区间包含其后裔结点的编码区间,这样对结点间结构关系的判断就等价于区间包含关系的判断.本文对现有的区间编码方案进行分析比较,研究了XML文档树中结点的位置特性,提出一种基于更新代价的XML区间编码方案。
本文分析了现有的几种XML文档区间编码方法,研究了在XML文档树不同位置插入结点或子树造成重新编码结点的数量,即更新代价,提出了一种新的区间编码方式,给出了明确的结点编码的计算表达式.该方法对更新代价较大的结点预留较大的空间,而对于更新代价较小的结点预留较小的空间.通过分析证明,采用本文提出的编码方法,在常数复杂度的时间内实现任意两个元素间父子、祖先/后裔、兄弟等关系的判断,同时,本编码方法便于XML文档更新,与现有XML文档的区间编码方式相比,可以更好地解决更新操作所造成的结点重新编码的问题。