Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics

Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics
复制标题

单子析取数据记录、MMSNP 和表达描述逻辑中的遏制

DOI：
--
复制
发表时间：
2016
期刊：
International Conference on Principles of Knowledge Representation and Reasoning
影响因子：
--
通讯作者：
C. Lutz
C. Lutz
中科院分区：
--
文献类型：
--
作者：
P. Bourhis;C. Lutz

文献摘要

被引文献

相似文献

我们研究查询包含在三个密切相关的形式主义：一元析取数据集（MDDLog），MMSNP（一个逻辑概括的约束满足问题），本体介导的查询（OMQs）的基础上表达描述逻辑和工会的合取查询。由于Feder和Vardi的结果，MMSNP中的遏制被认为是可判定的，但其确切的复杂性仍然是开放的。我们证明了2NExpTime-完全性，并将这一结果推广到一元析取数据库和OMQs。
We study query containment in three closely related formalisms: monadic disjunctive Datalog (MDDLog), MMSNP (a logical generalization of constraint satisfaction problems), and ontology-mediated queries (OMQs) based on expressive description logics and unions of conjunctive queries. Containment in MMSNP was known to be decidable due to a result by Feder and Vardi, but its exact complexity has remained open. We prove 2NExpTime-completeness and extend this result to monadic disjunctive Datalog and to OMQs.