试析图数据库查询处理技术的研究

《试析图数据库查询处理技术的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、博士学位论文图数据库查询处理技术的研究RESEARCHONTECHNIQUESFORQUERYPROCESSINGONGRAPHDATABASES张硕哈尔滨工业大学2010年6月国内图书分类号：TP309学校代码：10213国际图书分类号：681.324密级：公开工学博士学位论文图数据库查询处理技术的研究博士研究生：张硕导师：李建中教授申请学位：工学博士学科：计算机软件与理论所在单位：计算机科学与技术学院答辩日期：2010年6月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP309U.D.C.:681

2、.324DissertationfortheDoctoralDegreeRESEARCHONTECHNIQUESFORQUERYPROCESSINGONGRAPHDATABASESCandidate:ShuoZhangSupervisor:ProfessorJianzhongLiAcademicDegreeAppliedfor:DoctorofEngineeringSpecialty:ComputerSoftwareandTheoryAffiliation:SchoolofComputerScienceandTech

3、nologyDateofDefence:June,2010Degree-Conferring-Institution:HarbinInstituteofTechnology摘要摘要作为一种通用的数据结构，图可以用来表示数据对象之间的复杂联系。例如：图可以表示化合物的分子结构，蛋白质交互网络，社会网络等。随着科学与工程领域中图数据的大量出现和累积，图数据管理已成为数据管理领域一个重要和热点研究的子领域。图数据库查询处理是其中最重要的研究分支之一，其对图相关的绝大部分处理和应用（例如：图挖掘、化学数据库PubChem）

4、起着基础支撑作用。本文主要对图数据库中的查询处理技术进行深入研究，归纳总结了现有研究成果的主要思想和优缺点，提出了一些新的图数据库查询处理方法，主要研究成果如下：1.提出一种图数据库中高效处理超图包含查询的新方法。新方法综合的从图数据库的压缩组织、构造有效的特征索引以及基于压缩组织来处理查询三个方面着手考虑问题。(1)在图数据库的压缩组织方面，提出图数据库的有效组织方法，以提高整体查询处理效率。现有的采用过滤-验证机制的方法将图数据库中的图逐个的独立存放。提出方法将图数据库中图结构化的压缩组织起来。通过压缩组织方法

5、，产生一个逻辑数据结构GPTree，其中记录了数据库中图的公共子图的信息。为了优化的构造GPTree，形式化定义了最优诱导子图选择问题；证明了其是一个NP难问题，并提出了一个近似比为2的近似算法。(2)在构造有效的特征索引方面，提出高效而不依赖于历史查询的子图索引特征生成方法，以及两种索引结构CRGraph和FGPForest。首先基于分析，给出索引特征的显著性度量。提出了找出所有显著性不小于用户需求的索引特征的方法，即精确索引特征生成方法。为了适应需要更加快速的生成索引的应用场景，提出了特征索引构造的一个近似方法

6、。这两种方法都是基于图模式挖掘的方法。为了高效使用索引特征，对索引特征进行排序；并且基于理论分析给出了求解其最优排序的算法。(3)在基于压缩组织来处理查询方面，提出从多个图到一个图的子图同构检测的新方法，称为GPTreeTest。现有方法逐个的考察每个图对进行检测，新方法能够利用压缩组织中公共子图的信息，显著减少对多个图的子图同构检测的总时间。最后，在真实数据集和合成数据集上的实验结果表明，提出方法比目前最好方法高效1至2个数据量级。2.提出不确定图数据库上概率top-k子图匹配查询的新问题、以及一种查询处理方法。

7、首先给出不确定图数据模型，结合现实需求提出概率top-k子图匹配查–I–哈尔滨工业大学工学博士学位论文询问题。一个顶点的邻居子图是由其距离不大于给定阈值内的所有顶点和边构成的子图。基于图结构空间相关性的特点，以附带概率信息的邻居子图为基础，设计一种有效的索引结构NG-Index。NG-Index索引可以很容易实现于成熟的关系数据库中，具有强健壮性。提出一种高效的基于搜索树的算法来进行查询处理。其中运用了一种概率剪枝技术来提高性能。最后通过实验考察并证实提出方法具有良好的效率和可扩展性。3.提出结合概念分层的图统计信

8、息定义以及查询处理方法。具体地说，给出了结合顶点关联的概念分层，根据用户指定的搜索兴趣来高效地计算数据图中统计信息的方法。首先提出一种结合概念分层的图统计分布表示。本文将用户搜索兴趣建模为概念图，并以用户概念图的子图匹配计数为基础来表示图统计信息。其次，为了高效计算此统计分布信息，设计了一种基于子图密度的索引结构并提出两阶段的计算方法:(1)先基于索引快速地