一种基于图的DL-Lite本体最小不可满足保持子集的计算方法

doi:10.3969/j.issn.0372-2112.2016.09.002

电子学报 ›› 2016, Vol. 44 ›› Issue (9): 2040-2045.DOI: 10.3969/j.issn.0372-2112.2016.09.002

一种基于图的DL-Lite本体最小不可满足保持子集的计算方法

付雪峰¹, 漆桂林², 张勇²

1. 南昌工程学院信息工程学院, 江西南昌 330099;
2. 东南大学计算机科学与工程学院, 江苏南京 210096

收稿日期:2015-06-24 修回日期:2015-12-03 出版日期:2016-09-25
- 作者简介:
- 付雪峰 男,江西高安人,1978年出生.南昌工程学院信息工程学院讲师,主要研究方向:本体调试与修正,不一致性处理.E-mail:fxf@seu.edu.cn;漆桂林 男,江西宜丰人,1977年出生.东南大学计算科学与工程学院教授,博士生导师,主要研究方向:知识表达,语义网,不一致推理等.E-mail:gqi@seu.edu.cn;张勇男,山东蓬莱人,1989年出生.东南大学计算机科学与工程学院硕士研究生,主要研究方向:本体映射与调试.E-mail:zhangyong@seu.edu.cn
- 基金资助:
- 国家“八六三”高技术研究发展计划基金项目 (No.2015AA015406）; 国家自然科学基金 (No.61272378）; 江西省教育厅青年科学基金项目 (No.GJJ12643）

A Graph-Based Approach for Calculating Minimal Unsatisfiability-Preserving Subsets of Ontology in DL-Lite

FU Xue-feng¹, QI Gui-lin², ZHANG Yong²

1. School of Information Engineering, Nanchang Institute of Technology, Nanchang, Jiangxi 330099, China;
2. School of Computer Science and Engineering, Southeast University, Nanjing, Jiangsu 210096, China

Received:2015-06-24 Revised:2015-12-03 Online:2016-09-25 Published:2016-09-25
- Supported by:
- Program supported by National High-tech R&D Program of China (863 Program) (No.2015AA015406); National Natural Science Foundation of China (No.61272378); Youth Science Foundation Project of Education Department of Jiangxi Province (No.GJJ12643)

摘要/Abstract

摘要：

演变中的本体常出现不一致性问题，这将导致标准推理失效.针对不一致性问题，最小不可满足保持子集能够提供本体中概念不可满足的解释.计算最小不可满足保持子集是本体工程中的一项重要的非标准推理任务，但多数计算方法须借助外部的推理机，导致计算的效率不高.为了减少对推理机的依赖，本文提出了一种基于图的最小不可满足保持子集的计算方法.新的方法面向DL-Lite描述逻辑家族，将DL-Lite本体转换成图，将本体中的最小不可满足保持子集转换成图上的最小不可满足保持路径对.对比实验表明，基于图的方法提高了计算的效率和稳定性.

关键词: 本体, 描述逻辑, 不一致处理, 最小不可满足保持子集

Abstract:

Inconsistency often occurs during ontology evolution,and leads to the invalidity of standard reasoning.Minimal unsatisfiablility-preserving sub-TBox (MUPS) can provide an explanation of the unsatisfiability of a concept in an ontology.Finding all MUPS is an important nonstandard reasoning task in ontology engineering.Most of the approaches for calculating MUPS are built on external description logic reasoners.However,a reasoner-based method can hardly achieve positive efficiency and stability.In this paper,we propose a reasoner-independent approach to calculating MUPS using graph representation.We first transform DL ontologies to graphs,and find MUPS by computing the minimal unsatisfiability-preserving path-pair (MUPP) based on the transformed graphs.We implement and evaluate our approach.The experimental results demonstrate that our approach performs well in efficiency and stability.

Key words: ontology, description logic, inconsistency handling, minimal unsatisfiablility-preserving sub-TBox

中图分类号:

TP391

付雪峰, 漆桂林, 张勇. 一种基于图的DL-Lite本体最小不可满足保持子集的计算方法[J]. 电子学报, 2016, 44(9): 2040-2045.

FU Xue-feng, QI Gui-lin, ZHANG Yong . A Graph-Based Approach for Calculating Minimal Unsatisfiability-Preserving Subsets of Ontology in DL-Lite[J]. Acta Electronica Sinica, 2016, 44(9): 2040-2045.

参考文献

[1] Console M,Lenzerini M.Data quality in ontology-based data access:the case of consistency[A].Proceedings of the 28th AAAI Conference on Artificial Intelligence[C].Québec:AAAI Press,2014.1020-1026.
[2] Carnielli W A,Marcos J.Ex contradictione non sequitur quodlibet[J].Bulletin of Advanced Reasoning and Knowledge,2001,27(1):89-109.
[3] de la Banda M J,Stuckey P J,Wazny J.Finding all minimal unsatisfiable subsets[A].Proceedings of the 5th ACM SIGPLAN International Conference on Principles and Practice of Declaritive Programming[C].Uppsala:ACM,2003.32-43.
[4] Schlobach S,Cornet R.Non-standard reasoning services for the debugging of description logic terminologies[A].Proceedings of the 18th International Joint Conf.on Artificial Intelligence[C].San Francisco:Morgan Kaufmann Publishers,2003.355-362.
[5] Kalyanpur A,Parsia B,Horridge M,et al.Finding all justifications of OWL DL entailments[A].Proceedings of the 6th International Semantic Web Conference[C].Berlin:Springer,2007.267-280.
[6] Suntisrivaraporn B,Qi G,Ji Q,et al.A modularization-based approach to finding all justifications for OWL DL entailments[A].Proceedings of the 3rd Asian Semantic Web Conference[C].Berlin:Springer,2008.1-15.
[7] Qin B,Wang S,Du X,et al.Graph-based query rewriting for knowledge sharing between peer ontologies[J].Information Science,2008,178(18):3525-3542.
[8] Lembo D,Santarelli V,Savo D F.Graph-based ontology classification in OWL 2 QL[A].Proceedings of the 26th International Workshop on Description Logics[C].Ulm:CEUR-WS,2013.747-759.
[9] Qi G,Wang Z,Wang K,et al.Approximating model-based ABox revision in DL-Lite:theory and practice[A].Proceedings of the 29th AAAI Conference on Artificial Intelligence[C].Menlo Park:AAAI Press,2015.254-260.
[10] Calvanese D,De Giacomo G,Lembo D,et al.Tractable reasoning and efficient query answering in description logics:the DL-Lite family[J].Journal of Automated Reasoning,2007,39(3):385-429.
[11] Fu X,Zhang Y,Qi G.A graph-based approach to antology debugging in DL-Lite[A].Proceedings of the 4th Joint International Conference on Semantic Technology[C].Berlin:Springer,2014.33-46.
[12] Sharir M.A strong-connectivity algorithm and its applications in data flow analysis[J].Computers and Mathematics with Applications,1981,7(1):67-72.
[13] 周丽平,黄厚宽,漆桂林,等.一种在DL-Lite中计算本体最小不可满足保持子集的算法[J].计算机研究与发展,2011,48(12):2334-2342. Zhou Li-ping,Huang Hou-kuang,Qi Gui-lin,et al.An algorithm for calculating minimal unsatisfiability-preserving subsets of ontology in DL-Lite[J].Journal of Computer Research and Development,2011,48(12):2334-2342.(in Chinese)
[14] Baader F,Aloza R P N,Suntisrivaraporn B.Pinpointing in the description logic EL[A].Proceedings of the 2007 International Workshop on Description Logics[C].Berlin:Springer,2007.52-67.
[15] Du J,Qi G.Decomposition-based optimization for debugging of inconsistent OWL DL ontologies[A].Proceedings of the 4th International Conference on Knowledge Science,Engineering and Management[C].Berlin:Springer,2010.88-100.

一种基于图的DL-Lite本体最小不可满足保持子集的计算方法

A Graph-Based Approach for Calculating Minimal Unsatisfiability-Preserving Subsets of Ontology in DL-Lite

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王东升, 王卫民, 祁云松, 王石, 曹存根. 基于错误驱动的语义文法自动扩展学习方法研究[J]. 电子学报, 2021, 49(2): 248-259.
[2]	黄颖, 何克清, 冯在文, 黄贻望. 基于本体的业务流程适应性配置方法研究[J]. 电子学报, 2016, 44(3): 699-708.
[3]	苏雪阳, 左万利, 王俊华. 基于本体与模式的网络用户兴趣挖掘[J]. 电子学报, 2014, 42(8): 1556-1563.
[4]	薛涵, 秦兵, 刘挺. 基于Folksonomy的本体构建综述[J]. 电子学报, 2014, 42(4): 791-797.
[5]	黄霞. 基于本体和奇异值分解的图像数据索引查询算法[J]. 电子学报, 2014, 42(2): 288-291.
[6]	张波, 向阳, 黄震华. 基于本体的决策问题语义理解及精炼方法[J]. 电子学报, 2012, 40(8): 1603-1608.
[7]	刘秀磊, 廖建新, 朱晓民, 杨迪, 徐童. 本体匹配中基于词义组合的词法分析算法[J]. 电子学报, 2012, 40(8): 1624-1630.
[8]	杨汝涛, 张绍谦, 窦万春. 一种基于QoS剪枝的Top-k自动服务组合方法[J]. 电子学报, 2012, 40(7): 1489-1491.
[9]	刘磊;张鹏;吕帅;张睿. 基于演化传播模型的本体内聚程度分析[J]. 电子学报, 2011, 39(8): 1845-1851.
[10]	周栩;刘磊;范任宏. 基于模式结构分类的本体映射方法[J]. 电子学报, 2011, 39(4): 882-886.
[11]	翟社平;魏娟丽;李增智. 基于概念语义协商的服务Agent划分[J]. 电子学报, 2010, 38(9): 2030-2034.
[12]	万长林;韩旭;牛温佳;王文杰;史忠植. 基于动态描述逻辑的服务组合及质量模型[J]. 电子学报, 2010, 38(8): 1923-1928.
[13]	叶育鑫;欧阳丹彤. 混合语义约简和选择估值优化SPARQL[J]. 电子学报, 2010, 38(5): 1205-1210.
[14]	孙明;陈波;周明天. 结合DL-safe规则发现日志本体频繁模式的方法[J]. 电子学报, 2010, 38(2): 376-381.
[15]	张大鹏;;王文杰;史忠植;. 一种基于主体的可信网构软件设计方法[J]. 电子学报, 2010, 38(11): 2523-2528.