Abstract: In this paper, a new coding scheme was proposed, which was based on the sequence of its complete binary tree. The scheme is easy to realize and only one positive integer is needed to express the position of the node in XML tree. The time-bounding of identifying the ancestor-descendant relationships is only O(log n). It also supports XML document update. In the scheme, the length of the code is short.

Key words: Native XML database, coding scheme, XML query, complete binary tree

摘要： 在对于现有编码机制进行综述的前提下,提出一种新的XML文档编码机制，该编码机制基于完全二叉树的结构顺序编码。在该XML文档编码机制下,判断节点之间祖先-后裔关系算法的时间复杂度仅为O(log n),完全支持更新,并且编码长度较短。

关键词: Native XML数据库, 编码机制, XML查询, 完全二叉树