BTCS:基于二叉遍历的XML文档编码模式

BTCS: The Binary Traveling Coding Scheme for XML Document

XML文档数据的编码模式与索引技术决定了基于纯XML数据库的XML查询效率,在正则路径表达式实现方面有重要意义.基于树遍历的XML文档编码在更新与结构关系判断方面存在不足.为了解决此类问题,作者作了如下工作:(1)提出一种新的基于二叉树遍历的XML文档编码模式BTCS(Binary Traveling Coding Scheme);(2)实现了BTCS编码算法,支持XML文档更新,提高了编码更新效率;(3)在常数复杂度的时间内快速准确判断XML文档结构树中任意两个结点之间的父子以及祖孙关系,并能计算它们的辈数差(Distance of Genera-tions);(4)通过详细实验证明了BTCS编码模式的良好性能.

The coding scheme and indexing of XML document data plays an important role in the efficiency of XML query, especially for the implementing of regular path expression in the XML structural query. The current popular, XML coding scheme based on tree traversal is weak to support update of XML documents and to determine the structural relationship. In this paper, a new coding scheme for XML document called BTCS （Binary Traveling Coding Scheme for XML Document） is proposed and the algorithm is aiso given. With this coding scheme, XML document update is also supported and its efficiency is improved greatly. The structural relationship including ancestor-descendant and parent-child, and the distance of generation of two nodes in the binary tree of XML document, can be identified rapidly and correctly in constant time-bounding. By a series of extensive experiments demonstrate the effectiveness of the BTCS coding scheme.