论文部分内容阅读
关系数据库关键词搜索为不了解数据库模式、不具备结构化查询语言知识的普通用户提供了一种有效获取数据库信息的方式,越来越受到研究人员的关注。许多研究把关系数据转换成一个数据图,图中的节点和边可以关联文本内容。数据图能够还原数据原本的存在形式和数据间的关系,因此数据库关键词查询被转化为对数据图的检索。当前,随着海量数据不断涌现,数据库的规模与日俱增,元组之间关系也愈加复杂,关键词查询任务同时具备了数据密集型和计算密集型的特征。如何存储大规模数据图、如何高效检索大规模数据图以及如何保证海量数据环境下关键词查询的查全率等是值得研究的问题。本文针对上述问题提出了解决思路,主要工作体现在三个方面。目前关系数据的关键词查询普遍直接对RDBMS进行查询,查询效率受到数据库自身性能的限制,尤其是在海量数据场景下。本文根据关系数据库各个数据表记录之间的主外键约束关系将关系数据库中的数据转换成数据图并序列化存放在分布式文件系统HDFS中,HDFS具有良好的横向可扩展性,为实施大规模数据图搜索奠定了基础。目前对数据图检索算法的研究大多借鉴了BANKS中提出的逆向扩展搜索算法,后续的一些研究局限于对算法本身的微小改进,没有考虑到对数据图进行分布存储、并行搜索,而现有串行的算法在处理大规模数据图时不具备可扩展性。针对上述问题,本文引入分布式计算模型,把逆向搜索算法并行化,分别提出了基于Map Reduce和Spark的逆向搜索算法,并做了实验验证,为云计算环境下的数据图检索提出了思路。BANKS中提出的逆向搜索算法为了减少一定的搜索空间,在某个节点同时成为多棵结果树的根节点的情况下只会输出一棵结果树。在海量数据环境下这种策略带来的结果丢失问题会被成倍放大,本文在基于Spark的逆向搜索算法中对此做了改进。首先找出所有候选的根节点,然后从每个候选根节点出发进行前向搜索,只要根节点到包含关键词的叶子节点之间存在路径,就输出对应的结果树,而不考虑根节点是否已经包含在其它结果树中。这种方法在Spark内建的函数式转换中实现方便,且提高了上述情况下的查全率。