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

BTCS: The Binary Traveling Coding Scheme for XML Document

作　　者：肖厚新[1] 唐常杰[1] 张婷[1] 金朋纬[1] 乔少杰[1] 

机构地区：[1]四川大学计算机学院,成都610064

出　　处：《四川大学学报（自然科学版）》2006年第3期532-537,共6页Journal of Sichuan University(Natural Science Edition)

基　　金：国家自然科学基金(60473071);高等学校博士学科点专项科研基金SRFDP(20020610007);四川省青年软件创新工程(2004AA0350)

摘　　要：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.

关 键 词：XML XML文档结构树 XML编码模式 正则路径表达式 XML查询 

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