KREAG:基于实体三元组关联图的RDF数据关键词查询方法  

KREAG: Keyword Query Approach over RDF Data Based on Entity-Triple Association Graph

作　　者：李慧颖[1] 瞿裕忠[2] 

机构地区：[1]东南大学计算机科学与工程学院,南京210096 [2]南京大学计算机科学与技术系,南京210093

出　　处：《计算机学报》2011年第5期825-835,共11页Chinese Journal of Computers

基　　金：国家自然科学基金(60973024);江苏省自然科学基金(BK2008290)资助~~

摘　　要：语义网数据的大量增加使得RDF数据查询成为一个重要研究主题.关键词查询方式不需要掌握数据模式或查询语言,更适合普通用户使用.文中提出一种RDF数据关键词查询方法KREAG(Keyword query over RDF data based on Entity-triple Association Graph).为了支持用户对属性或关系名进行查询,将RDF数据建模为顶点带标签的实体三元组关联图.该模型保证了RDF数据中实体间关联转化为关联图中顶点间的通路,且文本信息全部封装到关联图顶点标签上.在此基础上,将关键词查询问题转化为关联图上查找有向斯坦纳树问题.在保证近似比为m的前提下(m为查询关键词的个数),利用近似算法实现快速查询响应.通过合理的评分方式衡量查询结果的相关性,支持top-k查询.算法的时间复杂度为O(m.|V|),其中|V|为实体三元组关联图中顶点个数.实验表明KREAG较其它方法具有更快的响应时间,同时能够有效地实现RDF数据的关键词查询.The increment in amount of Semantic Web data has made RDF data query an important research topic.key word query is regarded as an intuitive paradigm,especially for the users who are not familiar with the data and the RDF query language.In this paper,an approach named KREAG（Keyword query over RDF data based on Entity-triple Association Graph） is proposed,which enabling keyword-based query over RDF data.For supporting attribute and relation query,RDF data is modeled as a node-labeled Entity-Triple Association Graph,in which entity associations are translated into paths between nodes and all text information is encapsulated by nodes＇ label.Furthermore,the keyword query problem over RDF data is translated into a directed Steiner Tree problem in an Entity-Triple Association Graph.With an m-approximation ratio guarantee（m is the number of query keywords）,KREAG employs the Steiner Tree approximation algorithm to support rapid query response.Its time complexity is O（m·｜V｜）,where ｜V｜ is the number of nodes of the Entity-triple Association Graph.Moreover,KREAG introduces a reasonable ranking function and supports top-k queries.The experimental results show that KREAG has a faster response time than other keyword query approaches and is more effective.

关 键 词：关键词查询 RDF数据 TOP-K 实体 关联 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]