关皓元，朱 斌，李冠宇，赵 玲

(大连海事大学 信息科学技术学院，辽宁 大连 116026)(*通信作者电子邮箱rabitlee@163.com)

0 引言

资源描述框架(Resource Description Framework, RDF)是经W3C认证的用来描述语义Web中机器信息的标准数据模型，SPARQL是面向RDF图的标准图查询语言[1-2]。模式匹配是SPARQL查询处理中的核心问题，其目的是在复杂的RDF图数据中快速地搜索符合查询请求的结果。也就是说，面向RDF图的模式匹配是在RDF数据图中搜索到同构于查询图的数据子图的遍历过程(图1)，因此，该问题也可以称为子图匹配问题[3]。随着RDF数据量不断地增加，RDF数据模型对语义数据的表示也更加复杂，由于查询图的复杂性以及RDF数据的海量性，在查询处理的过程中时间效率很难得到保证，因此，本文提出一种基于RDF图结构切分的高效子图匹配方法。

在关系模型中，一条RDF数据被定义为三元组〈s,p,o〉,其中，s(subject)是主题，p(predicate)是谓词，o(object)是宾语，谓词表示主题与宾语之间的语义关系。一个RDF数据集以图的形式表示，图中的顶点表示主题与宾语，而谓词被映射到连接两个顶点的有向边(主题指向宾语)上作为顶点之间语义关系的表示(图1数据图G)。

在SPARQL查询中，查询语句以三元组模式表示，一个三元组模式就是一个限制条件，与三元组类似，但顶点标签可以是变量(谓词为变量的情况极其罕见，因此在本文的讨论中被忽略)，而一组包含多个限制条件的SPARQL查询则以查询图的形式表示(图1查询图Q)。在简单的SPARQL查询中，可以将RDF图分为3种基本结构[4]，如图2所示，分别为链形结构、环形结构与星形结构，然而随着RDF数据大量被发布，SPARQL查询也随之变得越来越复杂，一个复杂的RDF图往往是由以上3种结构交互连接而成的。……