计算机应用

• 数据库技术 • 上一篇    下一篇

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

张鹏 冯建华 房志峰   

  1. 清华大学计算机科学与技术系 清华大学计算机科学与技术系 山东政法学院信息科学技术系
  • 收稿日期:2008-03-19 修回日期:1900-01-01 发布日期:2008-09-01 出版日期:2008-09-01
  • 通讯作者: 张鹏

New XML document coding scheme based on complete binary tree

ZHNAG Peng FENG Jian-Hua FANG Zhi-Feng   

  • Received:2008-03-19 Revised:1900-01-01 Online:2008-09-01 Published:2008-09-01
  • Contact: ZHNAG Peng

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

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

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