图模型XML数据上查询处理方法的研究

论文摘要

由于图结构具有强大的表示能力,它在许多方面有着广泛的应用。随着计算机技术和国际互联网络技术的迅速发展,图模型数据上的管理和查询操作领域受到了越来越多的重视。XML可以方便地表示复杂的图模型数据规范并已成为通用信息交换标准之一,从数据库的角度对其进行研究,最主要的研究问题是如何有效地存储和查询大规模的XML数据。图模型XML数据上的可达查询是其中一类重要的查询。为高效地回答查询,基于可达编码的方法被提出,并加入索引和其它辅助结构以提高效率,然而由于图上编码的时间复杂度太大,并且会过多地占用搜索和存储空间,现有基于编码的算法对大量数据上进行的可达查询并不适用。基于路径匹配的方法通常将一个查询分解为一组路径,然后连接原来分支连接处的节点,然而该类型的结构连接方法通常导致庞大的中间结果,从而将严重影响查询处理效率。本文提出了图模型XML数据上的一种存储策略,该存储模型由基于正向,反向两棵生成树的可达编码和一种高效的可达索引组成,利用它可以在很短的时间内判断图中任两点的可达关系。实验表明,在实际图模型数据上所占存储空间与图的节点数接近线形关系。基于此存储策略,本文提出一种针对图状查询的全局的查询处理方法,通过按照不同的拓扑序两趟遍历查询图的所有节点,而得到查询结果。该查询结果以查询结果节点集合的形式表示,占用很小的存储空间,但省略了结果中边的信息。本文还提出查询结果转换算法,在需要时,可以将结果节点集合转换为查询结果图。理论和实验证明,该查询处理方法的时间复杂度接近数据图节点数的线形关系,处理查询时中间结果和查询结果所占空间均很小。本文给出了图模型XML数据上可达查询,查询结果等的严格定义,还证明了存储策略和查询处理方法的正确性。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究的目的和意义
• 1.2 国内外研究现状
• 1.2.1 DBMS 支持复杂对象的研究
• 1.2.2 图模型数据库的研究现状
• 1.3 本文研究的内容
• 1.4 本章小结
• 第2章 预备知识
• 2.1 XML 数据
• 2.2 图模型XML 数据上的查询
• 2.3 XML 数据上的可达编码
• 2.4 本章小结
• 第3章 图模型XML 数据的编码与存储
• 3.1 图模型XML 数据的可达化简
• 3.2 双生成树
• 3.3 X-Index
• 3.3.1 X-Index 的建立
• 3.3.2 X-Index 的存储和查找
• 3.4 本章小结
• 第4章 查询处理
• 4.1 查询处理中的概念与定义
• 4.2 X-Scan 算法
• 4.2.1 两个节点集合间的节点筛选
• 4.2.2 两趟遍历
• 4.3 结果转换
• 4.4 本章小结
• 第5章 实验
• 5.1 存储空间
• 5.2 索引建立
• 5.3 查询效率
• 5.4 影响系统的参数
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 哈尔滨工业大学硕士学位论文原创性声明
• 哈尔滨工业大学硕士学位论文使用授权书
• 哈尔滨工业大学硕士学位涉密论文管理
• 致谢