APP下载

支持更新的XML编码方案

2012-11-30申石磊

计算机工程与设计 2012年4期

杨 扬,申石磊

(河南大学 计算中心,河南 开封475004)

0 引 言

XML作为互联网上一种功能强大的标记语言,已经成为数据表示和交换的一个主要标准,受到越来越多的业内人士的关注,如何高效的索引和查询XML数据是目前XML研究领域的重要课题。为了加速结构连接,提高查询和文档更新维护的效率,目前主流方法是通过对XML文档树编码,依靠编码快速判断结点间的结构关系。研究人员提出了很多编码方案来加速结构连接,但是大多没有考虑编码更新问题。当XML文档更新时,更多的编码方法不能很好地支持更新操作。当XML数据频繁地发生删除、插入等更新XML数据时,需要调整相应结点的编码,以维持结点间的结构关系。但重新建立索引或重新编码的代价是非常高的,有时甚至需要给整棵树重新编码。若采用预留空间的编码方案,在一定程度上解决了动态更新问题,但当插入结点过多,超出预留空间时,仍然需要重新遍历XML文档树,造成二次编码。因此,本文提出了一种新的支持XML数据更新的编码方案IPEU (improved prefix encoding of supporting updates),该编码方案可快速判断结点间的结构关系,当XML文档树中插入或删除结点时,已有结点不存在二次编码问题,降低了更新代价,查询性能得以提高。

1 相关研究

1.1 区间编码

区间编码是树T中的每一个结点被赋予一个编码区间[start,end],并且满足:一个结点的区间编码包含它的后裔结点的区间编码[1]。区间编码能有效地支持XML查询,但它不能适应XML文档动态更新,当在XML文档中插入和删除结点时,有时甚至会导致整个文档树的重新编码。……

登录APP查看全文