XML数据更新编码机制——ITBI

ITBI: Labeling scheme for XML data update

编码技术是可扩展标记语言(XML)查询处理的基础,传统编码技术利用自然数进行编码,很难支持XML动态更新。提出了更新支持的编码方法———ITBI,该方法将整数映射到完全二叉树,利用二叉树的中序遍历定义整数新的序关系,通过新的序关系重排自然数序列将静态编码转化为动态编码。同时,基于ITBI前驱、后继、距离等定义,设计了最短位长动态编码分配算法,有效控制更新过程中编码位长的增加。最后通过实验验证了编码的有效性。

Labeling scheme is the basis for Extensible Markup Language （ XML） query processing. The traditional labeling schemes use numbers based on natural order, which is hard to support XML updating. A new labeling scheme, called ITBI （ Inorder Traversal Based Integer） , was proposed. ITBI created a mapping between integer and complete binary tree, and a new partial order based on inorder traversal of binary tree was defined, which just needed reordering the natural numbers to support dynamic XML. Meanwhile, based on the conceptions of previous ITBI, next ITBI, ITBI distance, the algorithm for assigning dynamic labels with the smallest size was presented, which controlled the increase in label size efficiently. The experimental results verify the validity of the proposed method.