面向web规模RDF数据查询算法的研究与实现

发布时间：2018-04-15 00:08

本文选题：语义网 + RDF数据　；参考：《东北大学》2014年硕士论文

【摘要】：目前因特网发展出现瓶颈的原因之一是由于没有赋予网络上的全部资源足够的语义信息。最主要的原因在于,现在的网络主要是基于超链接实现的,网络只是知道如何显示资源,却不清楚资源的实际含义。而RDF (Resource Description Framework)正是由W3C提出的语义网的标准描述框架。随着信息提取技术的发展和语义网的不断进步,网络中涌现出大量的RDF数据,如何存储、管理以及检索如此庞大的RDF数据已经成为了一项棘手却亟待解决的问题。SPARQL查询是W3C提出的对RDF进行查询的标准查询语言。目前RDF查询算法面临的主要问题是：(1)不支持带有通配符的SPARQL查询。(2)不能支持实时在线更新。(3)可扩展性差。本文基于以上三个问题,提出了基于索引的查询算法以及分布式环境的查询算法。针对以上问题,首先在第三章基于索引的查询算法中做了如下工作：(1)采取基于图的模型来存储RDF数据。具体地讲,本文通过基于索引的邻接表存储RDF数据。(2)本文在原始RDF图的基础上,对每个实体和类顶点增加一个标记信息。随之,提出了一种新的索引结构VS*-tree。它可以对上述带有数字标记信息的RDF图进行快速索引,且维护代价较低,易于更新。(3)针对带有数字标记信息的数据图,本节提出了一种新的剪枝规则,这种剪枝规则可以完美的嵌入到本文提出的查询算法中,并且同时适用于普通SPARQL查询和带有通配符的SPARQL查询。其次,本文充分考虑了RDF数据本身的特点,在第四章分布式环境的算法中(1)提出了一种扩展性强的RDF数据系统,该系统可以通过Hadoop框架可以直接利用任何现有集中式算法。(2)提出的数据分割技术和存储技术可以显著的降低查询过程中的数据通信量。(3)给出了一种可以自动将查询分解成可并行执行片段的算法,使得大量独立执行片段可以在不进行通信的前提下,在数据存储节点独立获得查询子结果,进一步提高了算法的可扩展性。在本文的最后,通过大量实验验证了本文算法的有效性及高效性。
[Abstract]:One of the reasons for the bottleneck in the development of the Internet is that it does not give sufficient semantic information to all the resources on the network.The main reason is that the current network is mainly based on hyperlinks, the network only knows how to display resources, but not the actual meaning of resources.RDF Resource Description Framework is the standard description framework of semantic Web proposed by W3C.With the development of information extraction technology and the continuous progress of semantic web, a large number of RDF data emerge in the network, how to store,Managing and retrieving such huge RDF data has become a thorny and urgent problem. Sparql query is a standard query language proposed by W3C to query RDF.At present, the main problem of RDF query algorithm is that SPARQL query with wildcard character is not supported by SPARQL query.Based on the above three problems, this paper proposes an index-based query algorithm and a distributed environment query algorithm.In order to solve the above problems, we first do the following work in the third chapter indexing based query algorithm: 1) using graph based model to store RDF data.Specifically, this paper stores RDF data through an index-based adjacency table.) on the basis of the original RDF graph, this paper adds a marker information to each entity and class vertex.Then, a new index structure, VS- tree, is proposed.This section proposes a new pruning rule for data graphs with digital tag information, which can be indexed quickly and easily updated with low maintenance cost.This pruning rule can be perfectly embedded into the query algorithm proposed in this paper and can be applied to both normal SPARQL queries and SPARQL queries with wildcard characters.Secondly, this paper takes the characteristics of RDF data into full consideration, and in chapter 4, the algorithm of distributed environment, we propose a kind of RDF data system with strong expansibility.The system can directly use any existing centralized algorithm. The data segmentation technology and the storage technology can significantly reduce the data traffic in the query process through the Hadoop framework.An algorithm that decomposes into parallel execution fragments,A large number of independent execution fragments can obtain query sub-results independently in the data storage node without communication, which further improves the scalability of the algorithm.At the end of this paper, the effectiveness and efficiency of the proposed algorithm are verified by a large number of experiments.
【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.4

【相似文献】