Games for query inseparability of description logic knowledge bases
Games for query inseparability of description logic knowledge bases
复制标题
描述逻辑知识库查询不可分性的博弈
DOI：
10.1016/j.artint.2016.01.010
复制
发表时间：
2016
影响因子：
14.4
通讯作者：
Botoeva E
中科院分区：
文献类型：
--
作者：
Botoeva E
我们认为合取查询不可分性的描述逻辑知识库相对于一个给定的签名知识库版本，模块提取，遗忘和知识交换的一个基本问题。我们给出了一个统一的博弈论特征的知识库合取查询的不可分离性和最坏情况下的最优决策算法的片段的霍恩ALCHI，包括描述逻辑支撑OWL 2 QL和OWL 2 EL。我们还确定了决定查询不可分离性的数据和组合复杂度。虽然所有这些逻辑的查询不可分性对于数据复杂性来说都是P-完全的，但组合的复杂性范围从P-到ExpTime-到2 ExpTime-完全。我们使用这些结果来解决两个主要的开放问题，OWL 2 QL的TBox查询的不可分性和知识交换中的通用合取查询解决方案的成员资格问题都是ExpTime完成的组合复杂性。最后，我们引入了一个更灵活的概念的不可分割性比较答案的合取查询在一个给定的签名在一组给定的个人。在这种情况下，检查查询不可分离性对于数据复杂性来说是NP完全的，但是ExpTime和2 ExpTime完全性组合的复杂性结果被保留。
We consider conjunctive query inseparability of description logic knowledge bases with respect to a given signature—a fundamental problem in knowledge base versioning, module extraction, forgetting and knowledge exchange. We give a uniform game-theoretic characterisation of knowledge base conjunctive query inseparability and develop worst-case optimal decision algorithms for fragments of Horn-ALCHI, including the description logics underpinning OWL 2 QL and OWL 2 EL. We also determine the data and combined complexity of deciding query inseparability. While query inseparability for all of these logics is P-complete for data complexity, the combined complexity ranges from P-to ExpTime-to 2 ExpTime-completeness. We use these results to resolve two major open problems for OWL 2 QL by showing that TBox query inseparability and the membership problem for universal conjunctive query solutions in knowledge exchange are both ExpTime-complete for combined complexity. Finally, we introduce a more flexible notion of inseparability which compares answers to conjunctive queries in a given signature over a given set of individuals. In this case, checking query inseparability becomes NP-complete for data complexity, but the ExpTime-and 2 ExpTime-completeness combined complexity results are preserved.
登录
查看更多内容
使用 ABox 的 ALC 本体的遗忘和均匀插值
DOI：
--
发表时间：
2014
期刊：
Description Logics
影响因子：
--
作者：
P. Koopmann;R. Schmidt
通讯作者：
R. Schmidt
影响因子：
5
作者：
Grau, Bernardo Cuenca;Horrocks, Ian;Sattler, Ulrike
通讯作者：
Sattler, Ulrike
DOI：
10.1007/978-3-319-10587-1_5
发表时间：
2014
期刊：
SIGART Bull.
影响因子：
--
作者：
R. Kontchakov;M. Zakharyaschev
通讯作者：
M. Zakharyaschev
具有隐藏内容的本体推理：查询导入方法
影响因子：
5
作者：
B. C. Grau;B. Motik
通讯作者：
B. Motik
DOI：
10.1613/jair.3552
发表时间：
2012-05
期刊：
J. Artif. Intell. Res.
影响因子：
--
作者：
B. Konev;Michel Ludwig;Dirk Walther;F. Wolter
通讯作者：
B. Konev;Michel Ludwig;Dirk Walther;F. Wolter