一种基于二叉树的Native XML数据库文档编码机制  

New XML document coding scheme based on complete binary tree

作　　者：张鹏[1] 冯建华[1] 房志峰[2] 

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]山东政法学院信息科学技术系,济南250014

出　　处：《计算机应用》2008年第9期2331-2334,共4页journal of Computer Applications

基　　金：浙江自然科学基金资助项目(Y105230);清华大学基础研究基金资助项目(JCqn2005022)

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

关 键 词：NATIVE XML数据库 编码机制 XML查询 完全二叉树 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]