论文部分内容阅读
XML(eXtensible Markup Language)已经成为Web上数据表达和数据交换的新标准。XML文档的大量出现,产生了XML数据管理的需求。XML所描述的Web数据所具有的半结构化特性对传统的数据管理方式提出了挑战:传统的基于关系数据库的信息查找及信息检索方式不能为具有树状层次结构的XML数据提供令人满意的查询效果。由此基于XML的信息查询便成为一个研究重点。为了有效支持XML查询,特别是结构查询,目前已经提出了XML数据的各种编码方案。对于XML结构查询,可以通过编码将XML结构查询的计算转化为结构连接的计算,因此有效的支持结构连接对XML查询的有效实现是解决问题的关键。本文主要对基于区间编码的小枝模式结构连接算法进行了研究和分析。1.在对现已提出的基于前序、后序遍历值的XML编码方法及几种扩展方法进行分析比较的基础上,提出了一种扩展的Zhang编码方法Ext-Zhang,该编码方案的特点是可以在常数复杂度内判定结点间的祖先/后代或双亲/孩子关系,易判定一个给定结点的后代结点或孩子结点的数目,易判定一个给定结点是否为叶子结点。同Dietz编码方案相比编码过程简单,只需按前序遍历一次XML文档树即可得到其编码;同Li-Moon编码方案相比,该编码方案要节约存储空间;同Zhang编码方案相比,虽然该编码方案扩展于Zhang编码方案,但对于XML文档树的任意结点,Ext-Zhang编码可以根据其编码得出该结点的后裔结点个数,且若将结点信息存入关系数据库中,其编码中pre值是连续的,这在关系数据库中将大大提高查询效率。2.研究了基于Ext-Zhang编码方案在关系数据库中的存储策略及数据管理,采用结点模型映射方法,用一个关系表xml(docid,pre,bigPre,level,value)即可存储多个XML文档。XML文档树中的每个结点分别在表中对应一个元组,以表xml的主键是(docid,pre)或(docid,bigPre)来相互区别。从而在基于关系数据库的XML数据的查询过程中,可以高效的找到XML文档树中的任意结点。3.在Ext-Zhang编码方案的基础上,提出了一种基于该编码方案的小枝模式结构连接算法StruContact,该算法不必考虑模式查询中是否包含分支,并利用编码的一些特性省去了对结点的重复扫描。实验数据表明,基于Ext-Zhang编码的小枝模式结构连接算法是正确的,且在效率上较PathStack和TwigStack算法有很大提高。