计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2012年
4期
767-785
,共19页
程经纬%马宗民%严丽%张富
程經緯%馬宗民%嚴麗%張富
정경위%마종민%엄려%장부
描述逻辑%查询蕴涵%合取查询%知识库%语义Web
描述邏輯%查詢蘊涵%閤取查詢%知識庫%語義Web
묘술라집%사순온함%합취사순%지식고%어의Web
大规模领域本体的快速发展对语义Web领域的数据访问提出了更高的要求,而基本的本体推理服务已不能满足数据密集型应用中处理复杂查询(主要是合取查询)的迫切需要.为此,大量的研究工作集中在本体和描述逻辑知识库合取查询算法的设计实现上,并开发出了很多知识库存储和查询的实用工具.近来模糊本体和模糊描述逻辑的研究,特别是它们在处理语义Web中模糊信息方面,得到了广泛关注.文中重点研究了模糊SH这一族极富表达能力的描述逻辑知识库的合取查询问题,提出了相应的基于推演表的算法,证明了算法对于f-SHOIQ的真子逻辑的可靠性、完备性和可终止性.证明了算法对于f-SHOIQ是可靠的,并分析了导致算法不可终止的原因.对于该问题的数据复杂度,证明了当查询中不存在传递角色时其严格的CONP上限.对于联合复杂度,汪明了算法关于知识库和查询大小的CO3NEXPTIME时间复杂度上限.
大規模領域本體的快速髮展對語義Web領域的數據訪問提齣瞭更高的要求,而基本的本體推理服務已不能滿足數據密集型應用中處理複雜查詢(主要是閤取查詢)的迫切需要.為此,大量的研究工作集中在本體和描述邏輯知識庫閤取查詢算法的設計實現上,併開髮齣瞭很多知識庫存儲和查詢的實用工具.近來模糊本體和模糊描述邏輯的研究,特彆是它們在處理語義Web中模糊信息方麵,得到瞭廣汎關註.文中重點研究瞭模糊SH這一族極富錶達能力的描述邏輯知識庫的閤取查詢問題,提齣瞭相應的基于推縯錶的算法,證明瞭算法對于f-SHOIQ的真子邏輯的可靠性、完備性和可終止性.證明瞭算法對于f-SHOIQ是可靠的,併分析瞭導緻算法不可終止的原因.對于該問題的數據複雜度,證明瞭噹查詢中不存在傳遞角色時其嚴格的CONP上限.對于聯閤複雜度,汪明瞭算法關于知識庫和查詢大小的CO3NEXPTIME時間複雜度上限.
대규모영역본체적쾌속발전대어의Web영역적수거방문제출료경고적요구,이기본적본체추리복무이불능만족수거밀집형응용중처리복잡사순(주요시합취사순)적박절수요.위차,대량적연구공작집중재본체화묘술라집지식고합취사순산법적설계실현상,병개발출료흔다지식고존저화사순적실용공구.근래모호본체화모호묘술라집적연구,특별시타문재처리어의Web중모호신식방면,득도료엄범관주.문중중점연구료모호SH저일족겁부표체능력적묘술라집지식고적합취사순문제,제출료상응적기우추연표적산법,증명료산법대우f-SHOIQ적진자라집적가고성、완비성화가종지성.증명료산법대우f-SHOIQ시가고적,병분석료도치산법불가종지적원인.대우해문제적수거복잡도,증명료당사순중불존재전체각색시기엄격적CONP상한.대우연합복잡도,왕명료산법관우지식고화사순대소적CO3NEXPTIME시간복잡도상한.