图数据上可达性查询关键技术研究

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

1、万方数据分类号UDC密级学位论文图数据上可达性查询关键技术研究作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：薛鹏聂铁铮副教授东北大学信息科学与工程学院硕士学科类别：工学计算机软件与理论2014年6月论文答辩日期：2014年6月2014年7月答辩委员会主席：于戈寇月宋宝燕东北大学2014年6月万方数据AThesisinComputerSoftwareandtheoryResearchonKeyTechniquesofReachabilityQueryofGraph

2、DatabyXuePengSupervisor：AssociateProfessorNieTiezhengNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：日期：妒／埠．6．2乙学位论文版权使用授权书薅

3、峨本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行索引、交流。作者和导师同意网上交流的时间为作者获得学位后：半年衫一年口一年半口两年口学位论文作者签名：番嘲签字日期：上of牛．6．LL导师签名：翼毒艇蟹签字日期：工D竹。6．2乙万方数据东北大学硕士学位论文摘要图数据上可达性查询关键技术研究摘要可达性查询是图查询中一个主要的研究方向，引

4、发了越来越多人的关注。随着大数据时代的来临，数据规模的不断扩大，越来越多的复杂结构数据需要用图的结构表示，因此对于图的研究就显得越来越有必要。可达性查询目的是判断在有向图中是否存在一条路径使得两点相互连接。关于可达性查询方面的研究已经进行了二十多年，而且一直是数据库领域研究的热点。目前可达性查询研究已经广泛应用于各个领域：在社交网络中，将每个人表示成图中的顶点，可达性查询有助于确定两个人之间的关系；在蛋白质网络中，顶点可以表示成分子，边则表示为分子间的反应关系，可达性体现了不同分子之间的反应特性。此

5、外，引文网络和图的模式匹配也都能看到可达性查询的影子。如何提高查询效率一直是可达性查询研究的主要问题，很多研究围绕这点进行展开。随着研究的不断深入，己经出现了可达性查询的变形，如标签约束可达性查询等。本文主要针对当前图数据的特征，研究不同数据可达性定义下的优化方法。首先综合路径划分和区间标记的思想，提出了一种路径区间标记的可达性查询方法。现有的多重区间标记方法需要不断的迭代进行查询，特别是对于两点存在真实可达性关系的情况，查询时间代价约等于深度优先遍历，在很大程度上不够优化。因此本文添加了路径的相关

6、信息，该方法能够有效地减少迭代次数，迅速判断不可达关系，缩短查询时间。基于不同路径之间的关系，本文给出了一种ESQ查询策略。不同的路径之间可以通过等价的边相互连接，记录不同路径之间的等价边信息，相比传递闭包减少了空间的消耗，获得了更好的时间效率。其次，基于约束可达性研究的内容，提出了一种有向图权重约束可达性的概念。目前的研究只有无向图上权重约束查询，在此基础上解决了加权有向图可达性查询的问题。对于有向图附加的权值信息，本文从传递闭包的角度出发为有向图建立索引，给出了一种优化的传递闭包算法。最后，借鉴

7、无环图的思想，将加权有向图转化为等价的加权无环图。按照反拓扑序列进行传递闭包的计算，有效的减少了顶点对重复边的搜索，能够在更短的时间内完成传递闭包的建立。本文对研究内容中所提出的理论进行了必要的证明，对相关算法进行了详细描述。在此基础上，基于真实数据集和模拟数据集对算法进行了验证，实验结果显示本文方法能够提高可达性查询的执行效率。关键词：有向图；可达性查询：路径划分；区间标记；权重约束一II—万方数据东北大学硕士学位论文AbstractResearchonKeyTechniquesofReachab

8、ilityQueryofGraphDataAbstractReachabilityqueryisoneofthemainresearchdirectionsongraphdata，andreceivesmoreattentionfromcurrentresearchers．Withcomingofbigdataandtheexpansionofthescaleofdata，moreandmorecomplexstructureddataarerepresentedas