论文标题
Monadic析取数据，MMSNP和表达描述逻辑中的遏制
Containment in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics
论文作者
论文摘要
我们研究了三种密切相关的形式主义中的查询遏制：基于表达性的逻辑和结合质量的逻辑，Monadic析取数据（MDDLOG），MMSNP（约束满意度问题的逻辑概括）和本体论介导的查询（OMQ）。由于费德和瓦尔迪的结果，已知MMSNP中的遏制是可决定的，但其确切的复杂性仍然开放。我们证明了2nexptime的完整性，并将此结果扩展到Monadic析取数据和OMQ。
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.
