Abstract: In order to determine rapidly the ancestor-descendant and parent-child relationships between nodes in XML querying, some labeling schemes have been proposed. However, relabeling and recalculation will happen when a new node is inserted in order-sensitive XML document, which leads the label update cost to be high. A novel labeling scheme, called BSEPS（Binary String Encoding based on Path Scheme）, which supports order-sensitive updates without relabeling or recalculation, is proposed based on the path labeling. The experimental results show that the order-sensitive queries and leaf node/subtree updates can be processed efficiently by BSEPS.

Key words: XML document, inserting update, BSEPS（Binary String Encoding based on Path Scheme） labeling

摘要： 摘  要：在XML查询中，为了快速判断节点之间祖先后裔关系和双亲孩子关系，提出了一些编码方案，然而，当对顺序敏感的有序XML文档进行插入更新操作的时候，现有的编码方案必须重新对存在的节点进行编码或者重新计算节点编码的值，导致了很高的更新代价。在路径编码方法的基础上，提出了一种新的编码方案BSEPS（Binary String Encoding based on Path Scheme），该方案支持在不重新编码或者重新计算的情况下完成顺序敏感的插入更新操作。实验结果表明，BSEPS编码能有效处理顺序敏感查询和叶节点/子树更新。

关键词: XML文档, 插入更新, BSEPS编码