东北大学学报:自然科学版  2017, Vol. 38 Issue (1): 22-26  
0

引用本文 [复制中英文]

林晓庆 , 马宗民 . 基于压缩实体摘要图的RDF数据关键词查询[J]. 东北大学学报:自然科学版, 2017, 38(1): 22-26.
[复制中文]
LIN Xiao-qing , MA Zong-min . RDF Keyword Search by the Condensed Entity Summary Graph[J]. Journal Of Northeastern University Nature Science, 2017, 38(1): 22-26. DOI: 10.3969/j.issn.1005-3026.2017.01.005.
[复制英文]

基金项目

国家自然科学基金资助项目(61370075); 教育部新世纪优秀人才支持计划项目(NCET-05-0288)

作者简介

林晓庆(1979-), 女, 辽宁丹东人, 东北大学博士研究生; 马宗民(1965-), 男, 山东金乡人, 东北大学教授, 博士生导师。

文章历史

收稿日期: 2015-09-13
Contents              Abstract              Full text              Figures/Tables              PDF
基于压缩实体摘要图的RDF数据关键词查询
林晓庆1,2, 马宗民1    
1.东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
 2.辽东学院 信息工程学院, 辽宁 丹东 118003
收稿日期: 2015-09-13
基金项目: 国家自然科学基金资助项目(61370075); 教育部新世纪优秀人才支持计划项目(NCET-05-0288)。
作者简介: 林晓庆(1979-), 女, 辽宁丹东人, 东北大学博士研究生; 马宗民(1965-), 男, 山东金乡人, 东北大学教授, 博士生导师。
摘要: 提出一种将关键词查询转换为SPARQL查询的方法来进行RDF数据的搜索.首先, 根据RDF本身的关联特点, 构建一个压缩实体摘要图; 然后, 借助关键词与所在实体的索引, 将所查询的关键词在该摘要图上进行定位, 通过图双向搜索算法找出包含关键词实体的前k子图, 获得查询实体之间的关系, 再联合最初的关键词及他们的属性, 构建SPARQL查询; 最后使用SPARQL搜索引擎执行查询.实验结果表明, 所提方法较其他方法有更快的响应时间及更高的准确率.
关键词：RDF    SPARQL    OPS索引    压缩实体摘要图    双向搜索    
RDF Keyword Search by the Condensed Entity Summary Graph
LIN Xiao-qing1,2, MA Zong-min1    
1.School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
 2.School of Information Engineering, Eastern Liaoning University, Dandong 118003, China.
Corresponding author: LIN Xiao-qing, E-mail:linda164@163.com
Abstract: A method of translating keyword queries to SPARQL queries was presented to implement RDF (resource description framework) keyword search. Firstly, a condensed entity summary was constructed according to connections of RDF data. Then, keywords were located on the designated nodes of the summary graph by the OPS (object predicate subject) index. Top-k subgraphs connecting all keyword entities would be found by a bidirectional search algorithm. Finally, SPARQL queries were obtained by incorporating inter-entity relationships of top-k subgraphs, keywords and their properties, and SPARQL queries were executed by a SPARQL search engine. The experimental results show that a faster response time and a higher accuracy than the existing ones are achieved.
Key Words: RDF (resource description framework)    SPARQL    OPS (object predicate subject) index    condensed entity summary graph    bidirectional search    

资源描述框架(resource description framework,RDF),是对万维网上信息进行描述的一个框架[1],RDF已成为语义数据描述的标准,被广泛应用于元数据、本体及语义网的描述中,如Yago,DBLP,wikipedia等.近几年来,由于可用RDF数据的大量增加,用户对RDF数据查询的需求日益强烈.随着SPARQL的广泛使用,SPARQL已经被W3C推荐为RDF查询的标准语言[2],但是RDF数据的查询语言对于普通用户过于复杂,大多数用户掌握不了查询语言及待查询数据的模式,所以形式简单的关键词查询备受欢迎.如何能够准确、高效地进行RDF数据查询仍是当前研究的主题,如果能将关键词查询转换为SPARQL查询,就会大幅度提高查询结果的准确率.因此本文提出一种关键词查询转换为SPARQL查询的方法,根据RDF实体间关联特点,提出了压缩实体摘要图的模型,封装实体类型到实体顶点上,该摘要图在规模上远远小于传统的数据图,降低了RDF数据图索引大小,减少了索引建立的时间,通过该摘要图转换关键词查询.本文方法的执行过程: 首先对输入的关键词通过OPS索引定位于压缩实体摘要图的指定实体上; 再在该摘要图上进行双向搜索,找出包含这些关键词实体的前k子图; 最后根据子图与SPARQL查询的映射将关键词查询转换为SPARQL查询,由用户选择一个SPARQL查询执行,获得最终结果.

1 相关研究

RDF数据关键词查询根据其存储结构的不同主要有下面几类方法: 一是将RDF数据以三元组的形式存储在关系数据库中[3-4]; 二是基于XML格式的关键词查询[5]; 三是目前较为流行的基于图的搜索方法[6-10],利用图的结构索引和有效的搜索、剪枝算法,在RDF数据图上查找匹配的子图.文献[10]将大图划分为若干个小的子图或块,建立子图(块)内和子图(块)间的路径索引.文献[11]则先利用摘要图缩小搜索的空间,再在小的数据范围内使用向后搜索查找包含关键词的子图,从而在搜索性能上有了很大的提高.以上几种方法都属于直接查询方法,即直接从RDF数据图中找到满足条件的子图,数据图匹配方法存在的主要问题是图索引开销较大,建索引时间过长,匹配的结果不全或匹配结果不够准确等.文献[11]将关键词查询转换为形式化查询语句,再借助相应的搜索引擎进行查询.本文提出压缩实体摘要图模型,减少了搜索空间,构建SPARQL查询,减少了查询响应时间,并得到了较高的准确率.本文的系统框架如图 1所示.

图 1 系统框架图 Fig.1 System architecture
2 RDF与SPARQL 2.1 RDF三元组和RDF图

RDF三元组是一个(S,P,O)的元组,S代表主语,P代表谓词,O代表宾语,其中,主语使用国际化的资源标识符IRIs(internationalized resource identifiers),谓词表示主语和宾语之间关系,宾语为另一实体或对应的属性值.

2.2 SPARQL查询

SPARQL是为RDF开发的一种查询语言和数据获取协议,可以对任何以RDF表示的信息资源进行查询,已经被W3C推荐为RDF查询的标准语言.下面是SPARQL查询语句的格式.

SPARQL: SELECT varlist WHERE (graph pattern)

其中,varlist=(v1,v2,…,vn)是查询变量的列表,查询变量由符号 “?” or “$”标记; WHERE子句是查询条件,复杂的SPARQL查询还包括用于过滤条件的正则表达式等.

3 关键词查询向SPARQL查询转换 3.1 压缩的实体摘要图(condensed entity summary graph,CESG)

RDF数据图是一个描述实体与实体或者实体与值关系的连接图.SPARQL查询的构建需要实体之间的关系,因此为了实现查询转换,本文提出一种具有实体关系的压缩摘要图模型.

封装节点所属类型到节点上有助于提高查询转换效率,不必再利用索引或搜索算法查找实体类型,压缩实体[9]将实体类型和关键词都封装到实体节点.图 2是根据表 1数据构建的一个压缩实体摘要图实例.文献[11]将同一种类型的所有实体绑定在一个类型上,缺少了一些实体关系.本文通过RDF数据构建只有实体及其关系的摘要图CESG.图 2中“pro1/Project”节点表示实体为“pro1”其类型为“Project”.简单描述一下构建过程,表 1为RDF数据的三元组形式,其中实体节点为“pro1”,“pub1”,“rest1”,“rest2”,“inst1”.简单描述一下CESG的构建过程,将表 1中包含实体关系的三元组,即1,3,5,10行保留; 包含谓词“type”的三元组,即2,4,6,9,11行也要保留.属于实体与值关系的三元组则不需要.根据表 1数据构建的CESG数据如图 2所示,CESG定义如下.

定义1 CESG=(V,L,E),其中节点集合V=V(E,type),VE表示实体节点,它所属类型(type)封装在实体节点上,边标签集L=LR(表示两个实体间关系),边集E中的元素为e(v1,v2) ,而且e∈L.e(v1,v2) ∈E,当且仅当RDF数据图中存在边italic>e(v1′,v2′)∈E′.对于大规模的RDF数据图是不切实际的,本文构建的CESG图在规模上远远小于数据图,所以单层索引的双向搜索算法[10]适合本文.本文通过OPS索引,查找CESG前k子图,预先建立向后搜索链表,LEN(v),向前搜索矩阵,MNE(vi,vj),LEN(v)链表存储所有能够到达v的节点,并按它们到达v的距离排序.MNE存放任意一个实体节点到达其他实体节点的最短路径,MNE(vi,vj)为返回节点vi到达节点vj的最短路径.

表 1 RDF三元组 Table 1 RDF triples
图 2 压缩的实体摘要图 Fig.2 Condensed entity summary graph

在计算top-k子图过程中,本文通过向前搜索,同时利用MNE(vi,vj),返回任何两实体节点间的距离disti,距离和sumDist=,MNE(vi,vj)是通过运行Floyd算法获得的.为了减少搜索范围,本文设置一个剪枝条件,把第k个子图的路径长度和记为Tprune,在搜索过程中剪掉sumDist大于Tprune的子图,每次访问一个节点时检查更新一下Tprune,算法的伪代码显示在表 2.

3.2 关键词与所在实体索引

既然CESG中不包括关键词,怎么找到关键词所在的实体呢？本文使用OPS[4]索引将关键词定位于它所在的实体(S),结构如图 3所示, P表示属性,O表示宾语(值的节点,主要指关键词),S代表主语(表示实体),每个宾语Oi(关键词)对应一组属性(P)的列表,每一个(Oi,Pj)的组合指向一个实体(S)的列表,例如,在表 1数据上建立OPS索引后,“2015”会指向一个属性P向量,这个P向量包含一个属性,即“year”,在这里,该属性只对应一个相关的主语S列表,“pub1”.对输入的每一个关键词,通过OPS索引可以找到一组对应关键词的属性列表,然后再联合各自的关键词属性,获得关键词所在的主语.

表 2 双向搜索算法 Table 2 Bidirectional search algorithm
图 3 OPS索引 Fig.3 OPS index
3.3 关键词查询向SPARQL查询转换

关键词查询转换为SPARQL查询的关键在于查询变量间的关系获得,CESG包含着所有实体关系,通过双向搜索可以快速找到包含关键词实体的top-k子图.表 3算法将top-k子图翻译成SPARQL查询.简单描述一下该算法,由表 2输出的top-k子图向量A中的每个元素结构为 ＜root,dist1,dist2,…,distm>,其中root是一个关联节点,连接所有的关键词实体,假设图 4a是获得的一个子图,节点rest2是root节点,root节点连接pub1和rest1节点,边的权值表示实体关系,表 3的第2行将子图向量A中的每一个顶点映射到SPARQL查询变量,如图 4b所示,再根据关联节点与各个关键词的路径生成SPARQL的查询模式,即表 3的3,4行,最后将生成的SPARQL查询存放于R向量当中,返回转换后的top-k SPARQL查询R.对于k的取值,如图 5所示,取查询长度(lenth)为2~4的20个查询,分别计算top-10,top-15,top-20的平均查询时间,查询时间随着k增加,逐渐变长,从图 5可见,查询性能在k=10时,查询长度对查询结果的影响最小,因此本文测试时取k=10.

表 3 Top-k SPARQL查询翻译 Table 3 Top-k SPARQL query translation
图 4 子图到SPARQL查询映射 Fig.4 Mapping of subgraph to SPARQL query (a)—子图; (b)—SPARQL查询图.
4 实验

本文使用Lehigh大学的开放基准数据集LUBM(Lehigh university benchmark,http://swat. cse.leghigh.edu/projects/lubm/.)和 DBLP(http://dblp.uni-trier.de/xml/)进行测试,LUBM(50,0) 是由Lehigh大学提供的UBA生成器产生的50个有关大学、部门、教师、等之间关系的本体数据.DBLP是对计算机领域内的国际会议和期刊出版物进行描述的数据集.本文使用Jena来存储和查询RDF数据,表 4是本文构建的针对LUBM数据集的10个关键词查询,图 6和图 7是使用表 4查询作的对比实验结果.

图 5 查询性能受不同k影响程度 Fig.5 Query performance with different k
图 6 Q1~Q10在不同数据集上的排序倒数 Fig.6 Q1~Q10 reciprocal rank on different databases
图 7 Q1~Q10在不同数据集上的查询处理时间 Fig.7 Q1~Q10 processing time on different datasets

本文使用国际上通用的对搜索算法进行评价的机制,MRR(mean reciprocal rank)=1/n,即如果返回的第一个结果匹配,分数为1,第二个匹配分数为0.5,第n个匹配分数为1/n,如果没有匹配的结果,分数为0.在保证结果正确的前提下,本文没有与文献[11]方法进行比较,因为该方法的摘要图缺少了部分实体间的关系.本文查询响应时间包括查询转换的时间加上查询执行的时间.随着RDF数据的增加,构建的CESG具有更完备的实体关系,因此得到更高的MRR值,如图 6所示; 本文取10次查询时间的平均值作为查询时间,从图 7可以看出,随着数据的增加,查询时间也随之变长,原因是OPS索引及CESG的大小都随之变大.程序的循环次数因关键词数量增加而变多,所以Q9处理时间较其他查询更长些.本文采用文献[10]中的10个查询,与文献[7]及几个利用图索引的方法,1000BFS,1000METIS,300BFS,300METIS进行查询性能比较,实验结果如图 8所示,本文的方法都优于文献[7]方法.

表 4 查询示例 Table 4 Query examples
图 8 在DBLP上的查询性能对比 Fig.8 Query performance comparison on DBLP
5 结论

本文提出了一种利用压缩实体摘要图模型来实现关键词查询转换为SPARQL查询的方法.该方法通过建立压缩实体摘要图缩减top-k子图的搜索范围,并引入了用户交互,在生成的SPARQL查询上,用户选择最适合的一个查询执行,得到了较高的准确率.未来希望采取更有效的算法来更新该实体摘要图,考虑除了路径以外,融合更多因素来选择前k子图,比如,节点间的相关性、节点的受欢迎度、利用本体信息及尝试概率模型等.

参考文献
[1] Beckett D.RDF/XML syntax specification [EB/OL].(2004-02-10) [2015-09-02].http://www.w3.org/TR/2004/REC-rdf-syntax-grammar-20040210/
[2] Prud′hommeaux E,Seaborne A,Harris S,et al.SPARQL query language for RDF [EB/OL].(2013-03-21) [2015-9-13].http://www.w3.org/TR/2013/REC-sparql11-query-20130321/
[3] Chen Y,Wang W,Liu Z.Keyword-based search and exploration on databases[C]// Proceedings of the 2011 IEEE 27th International Conference on Data Engineering.Washington D C:IEEE Computer society,2011:1380-1383.
[4] Weiss C,Karras P,Bernstein A.Hexastore:sextuple indexing for semantic web data management[C]// Proceedings of the VLDB Endowment.Berlin:Springer-Verlag,2008:1008-1019.
[5] Chen Y,Wang W,Liu Z,et al.Keyword search on structured and semi-structured data[C]// Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data.New York:ACM,2009:1005-1010.
[6] Kargar M,An A.Keyword search in graphs:finding r-cliques[C]// Proceedings of the VLDB Endowment.Berlin:Springer-Verlag,2011:681-692.
[7] Kacholia V,Pandit S,Chakrabarti S,el al.Bidirectional expansion for keyword search on graph databases[C]// Proceedings of the 31st International Conference on Very Large Data Bases.Trondheim,Norway,2005:505-516.
[8] Zou L,Mo J,Chen L,et al.gStore:answering SPARQL queries via subgraph matching[C]// Proceedings of the VLDB Endowment.Berlin:Springer-Verlag,2011:482-493.
[9] Le W, Li F, Kementsietsidis A, et al. Scalable keyword search on large RDF data[J]. IEEE Transactions on Knowledge and Data Engineering , 2014, 26 (11) : 2774–2788. DOI:10.1109/TKDE.2014.2302294
[10] He H,Wang H,Yang J,et al.Blinks:ranked keyword searches on graphs[C] // Proceedings of the 2007 ACM SIGMOD International Conference on Management of data.New York:ACM,2007:305-316.
[11] Tran T,Wang H,Rudolph S,et al.Top-k exploration of query candidates for efficient keyword search on graph-shaped (RDF) data[C]// IEEE International Conference on Data Engineering.Washington D C:IEEE Computer Society,2009:405-416.