基于语义度量的RDF图近似查询

doi:10.3969/j.issn.0372-2112.2015.07.011

电子学报 ›› 2015, Vol. 43 ›› Issue (7): 1320-1328.DOI: 10.3969/j.issn.0372-2112.2015.07.011

基于语义度量的RDF图近似查询

章登义, 吴文李, 欧阳黜霏

武汉大学计算机学院, 湖北武汉 430072

收稿日期:2014-12-01 修回日期:2015-01-29 出版日期:2015-07-25
- 作者简介:
- 章登义 男,1955年2月出生于湖北省荆州市.现为武汉大学计算机学院教授、博士生导师.主要研究方向为安防、嵌入式和数据库. E-mail:dyzhang@whu.edu.cn;吴文李 女,1986年12月出生于广东省湛江市.现为武汉大学博士研究生.主要研究方向为语义网数据挖掘. E-mail:huihuigou@whu.edu.cn

Approximating Query with Semantic-Based Measure on RDF Graphs

ZHANG Deng-yi, WU Wen-li, OUYANG Chu-fei

School of Computer, Wuhan University, Wuhan, Hubei 430072, China

Received:2014-12-01 Revised:2015-01-29 Online:2015-07-25 Published:2015-07-25

摘要/Abstract

摘要：

近似查询是图数据库资源管理的操作之一.已有工作主要基于距离来度量查询语句与图的近似值,忽略了两者之间的语义近似性.对于语义图的近似查询,忽略图与查询的语义近似将难以有效完成查询.针对该问题,本文在考虑语义近似的基础上为RDF(Resource Description Framework,资源描述框架)图的近似查询提出基于语义距离的度量方法.同时,为提高查询效率,本文提出语义结构剪枝策略.最后,我们构造查询框架以实现查询的响应过程,并在该框架下设计实验以评价本文方法.实验表明,本文方法可高效执行RDF近似查询并有效返回top-k结果集.

关键词: RDF图, 近似查询, 图数据库, 查询处理

Abstract:

Approximating query is one of the operations for resource management in graph database.Existing works mainly based on the distance similarity to measure the query and graphs without considering the semantic similarity.For the approximating query on semantic graphs,disregarding the semantic similarity may fail the query.In this paper,we propose a semantic-based measure for approximating query on RDF graphs,considering the semantic similarity.In the meanwhile,we specify a semantic structural pruning strategy to ameliorate the efficiency of query process.Finally,we construct the query framework to answer approximating query,and design experiments to test our methods under this framework.Results show that the approaches in this paper can efficiently execute approximating query on RDF graphs and effectively return top-k results.

Key words: RDF graph, approximating query, graph database, query processing

中图分类号:

TP301

章登义, 吴文李, 欧阳黜霏. 基于语义度量的RDF图近似查询[J]. 电子学报, 2015, 43(7): 1320-1328.

ZHANG Deng-yi, WU Wen-li, OUYANG Chu-fei . Approximating Query with Semantic-Based Measure on RDF Graphs[J]. Acta Electronica Sinica, 2015, 43(7): 1320-1328.

参考文献

[1] RDF primer.W3C Recommendation[EB/OL].http://www.w3.org/TR/rdf-primer.
[2] Thomash N,Gerhard W.The RDF-3X engine for scalable management of RDF data[J].VLDB Journal,2010,19(1):91-149.
[3] Mihaela A B,et al.Building an efficient RDF store over a relational database[A].ACM Conference on Management of Data[C].New York:ACM,2013.121-132.
[4] Jiewen H,et al.Query optimization of distributed pattern matching[A].IEEE International Conference on Data Engineering[C].Washington:IEEE Press,2014.64-75.
[5] Jiewen H,et al.Scalable SPARQL querying of large RDF graphs[J].The Proceedings of the VLDB Endowment,2011,4(11):1123-1134.
[6] Weiguo Z,et al.Graph similarity search with edit distance constraint in large graph databases[A].ACM International Conference on Information and Knowledge Management[C].New York:ACM,2013.1595-1600.
[7] Haichuan S,et al.Connected substructure similarity search[A].ACM Conference on Management of Data[C].New York:ACM,2010.903-914.
[8] Haichuan S,et al.Similarity search on supergraph containment[A].IEEE International Conference on Data Engineering[C].Washington:IEEE Press,2010.637-648.
[9] Yuanyuan Z,et al.Finding top-k similar graphs in graph databases[A].International Conference on Extending DB Technology[C].London:Springer,2012.456-467.
[10] Yuan Y,et al.Efficient subgraph similarity search on large Probabilistic Graph Databases[J].Proceedings of the VLDB Endowment,2012,5(9):800-811.
[11] 姚绍文,余江,周明天.面向语义Web的逻辑描述原语扩展[J].电子学报,2002,30(S1):2115-2118. Yao Shaowen,Yu Jiang,Zhou Mingtian.Semantic web-oriented specification of logic descriptive primitives[J].Acta Electronica Sinica,2002,30(S1):2115-2118.(in Chinese)
[12] 王海,高岭,范琳,李增智.基于SPARQL-DL的语义Web服务查询[J].电子学报,2011,39(3A):52-56. Wang Hai,Gao Ling,Fan Lin,Li Zengzhi.Query for semantic Web service based on SPARQL-DL[J].Acta Electronica Sinica,2011,39(3A):52-56.(in Chinese)
[13] Xiang L,Lei.Efficient query answering in probabilistic RDF graphs[A].ACM Conference on Management of Data[C].New York:ACM,2011.157-168.
[14] Peixiang Z,Jiawei H.On graph query optimization in large networks[J].The Proceedings of the VLDB Endowment,2010,3(1):340-351.
[15] ARQ[EB/OL].http://incubator.apache.org/jena/ documentation/ query/index.html.

基于语义度量的RDF图近似查询

Approximating Query with Semantic-Based Measure on RDF Graphs

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 11

编辑推荐

Metrics

[1]	黄云, 洪佳明, 覃遵跃, 钟键, 李梦婷, 印鉴. ERSearch:一种高效的子图查询算法[J]. 电子学报, 2017, 45(2): 368-375.
[2]	章登义, 吴文李, 欧阳黜霏. 针对RDF概率图查询的基数估计方法[J]. 电子学报, 2015, 43(9): 1745-1749.
[3]	章登义, 吴文李, 欧阳黜霏. RDF图的Top-k最短路径查询[J]. 电子学报, 2015, 43(8): 1531-1537.
[4]	蒋涛, 高云君, 张彬, 周傲英, 乐光学. 不确定数据查询处理[J]. 电子学报, 2013, 41(5): 966-976.
[5]	刘亮, 秦小麟, 李博涵, 刘宇雷. 鲁棒的无线传感器网络空间范围聚集查询处理算法[J]. 电子学报, 2012, 40(7): 1465-1470.
[6]	李先通;安实. 基于频繁闭图的图包含查询算法[J]. 电子学报, 2010, 38(12): 2937-2943.
[7]	刘亮;秦小麟;戴华;严伟中;潘锦基. 能量高效的无线传感器网络时空查询处理算法[J]. 电子学报, 2010, 38(1): 54-59.
[8]	钱江波;王永利;陈征;陈华辉;金光. 数据流窗口连接查询处理器研究[J]. 电子学报, 2009, 37(2): 404-409.
[9]	蔚赵春;周水庚;关佶红. 无线传感器网络中数据存储与访问研究进展[J]. 电子学报, 2008, 36(10): 2001-2010.
[10]	衡星辰, 覃征, 邵利平, 曹玉辉, 高洪江. 基于两阶段查询重写的XML近似查询算法[J]. 电子学报, 2007, 35(7): 1271-1278.
[11]	阳国贵;吴泉源. 对象关系数据库中一类特定连接谓词的有效处理方法[J]. 电子学报, 2000, 28(11): 111-113.