论文部分内容阅读
子图匹配(Basic Subgraph Pattern Matching)是RDF图数据管理中的一种基本查询类型,又称子图同构(Subgraph Isomorphism),是一个NP-Complete问题。随着语义网的发展和开放链接数据运动的发展,越来越多的数据通过RDF格式发布出来。高时间复杂度和巨大的数据规模给RDF图数据的管理带来了巨大挑战。目前的单机查询算法由于受限与子图匹配问题的特性,往往会引入大量的连接操作,效率较低;基于MapReduce的分布式查询方案受限于MapReduce的迭代机制,查询效率很难提升。因此,如何高效地在大规模的RDF图数据上解决子图匹配问题,成为一个具有挑战性的工作。本文提出了集中式和分布式两种RDF图数据查询方案。在集中式查询方案中,数据图根据顶点度数的大小拆分成星状的小规模子图,并将这每个子图编码成一个二进制串。将子图匹配的部分操作转换成二进制位的“与”和“或”操作。使用该二进制串来过滤出可能的子结果。然后将子结果拼接成完整的查询结果。该方案避免了大多数的连接操作,使得每次访问索引获得一条三元组信息优化到每次访问索引获得一组三元组信息。这种查询方案提高了每次查询获得的信息量,大大减少了连接操作数量。在分布式查询方案中,将RDF图中的每个顶点都视为可执行计算的单元,将整个图映射成可互相传递消息的顶点集。这种模型基于BSP计算模型设计,充分利用了图的特点,使用消息传递的方式逐步完善查询图,逐一减少变量数量,最终得到查询结果,避免了迭代的MapReduce计算模型在解决图计算问题时存在的很多限制,查询效率明显提高。本文设计的实验从索引的空间代价和查询响应时间等方面对上述两种方法做了评价,集中式查询方案在查询响应时间上优于目前性能最好的通用RDF集中式查询引擎RDF-3X和gStore,分布式查询方案也较MapReduce框架下实现的查询方案有较大的性能提升。综上所述,本文针对RDF图数据上的子图匹配问题提出了单机集中式查询和集群分布式查询两种查询方案,在索引结构、数据编码、查询算法等方面提出了具体解决方案。有效地降低了查询时间复杂度。