模糊描述逻辑知识库查询蕴涵的判定方法  

Deciding Query Entailment for Fuzzy Description Logic Knowledge Bases:The f-SH Family

作　　者：程经纬[1] 马宗民[1] 严丽[2] 张富[1] 

机构地区：[1]东北大学信息科学与工程学院计算机应用技术研究所,沈阳110819 [2]东北大学软件学院软件工程研究所,沈阳110819

出　　处：《计算机学报》2012年第4期767-785,共19页Chinese Journal of Computers

基　　金：国家自然科学基金(60873010;61073139);教育部新世纪优秀人才支持计划(NCET-05-0288)和教育部中央高校基本科研业务费专项(N090504005;N090604012;N100604017)资助~~

摘　　要：大规模领域本体的快速发展对语义Web领域的数据访问提出了更高的要求,而基本的本体推理服务已不能满足数据密集型应用中处理复杂查询(主要是合取查询)的迫切需要.为此,大量的研究工作集中在本体和描述逻辑知识库合取查询算法的设计实现上,并开发出了很多知识库存储和查询的实用工具.近来模糊本体和模糊描述逻辑的研究,特别是它们在处理语义Web中模糊信息方面,得到了广泛关注.文中重点研究了模糊#0这一族极富表达能力的描述逻辑知识库的合取查询问题,提出了相应的基于推演表的算法,证明了算法对于f-#0123的真子逻辑的可靠性、完备性和可终止性.证明了算法对于f-#0123是可靠的,并分析了导致算法不可终止的原因.对于该问题的数据复杂度,证明了当查询中不存在传递角色时其严格的CONP上限.对于联合复杂度,证明了算法关于知识库和查询大小的CO3NEXPTIME时间复杂度上限.Recently,the rapid evolution of large-scale domain ontologies brought about higher requirements for data access in the Semantic Web community.The basic reasoning services for ontologies,however,cannot meet the needs of dealing with complex queries（mainly conjunctive queries） in data-intensive applications.For that purpose,significant research efforts are recently directed toward the design and implemrntatuon of query answering algorithms for ontologies and description logic（DL） knowledge bases（KBs）.Many practical tools capable of storing a knowledge base,and also performing queries on it,were constructed.Fuzzy extensions to ontologies and DLs have recently gained considerable attention especially for the purposes of handling vague information in the Semantic Web.In this study,we focus on fuzzy conjunctive queries over fuzzy DL KBs of the expressive f-SH family.We show soundness,completeness and termination of fuzzy query entailment in proper sublogics of f-SHOTQ by providing a corresponding tableau-based algorithm.We show the algorithm is sound for f-SHOTQ,and analyse the reason leading to nontermintion.We close the open problem of the complexity for answering fuzzy conjunctive queries in expressive fuzzy description logics by establishing two complexity bounds： for data complexity,we prove a CONP upper bound,as long as only simple roles occur in the query;Regarding combined complexity,we prove a CO3NEXPTIME upper bound in the size of the knowledge base and the query.

关 键 词：描述逻辑 查询蕴涵 合取查询 知识库 语义WEB 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]