REWRITABILITY IN MONADIC DISJUNCTIVE DATALOG, MMSNP, AND EXPRESSIVE DESCRIPTION LOGICS
REWRITABILITY IN MONADIC DISJUNCTIVE DATALOG, MMSNP, AND EXPRESSIVE DESCRIPTION LOGICS
复制标题
DOI：
10.23638/lmcs-15(2:15)2019
复制
发表时间：
2019-01-01
影响因子：
0.6
通讯作者：
Lutz, Carsten
中科院分区：
文献类型：
--
作者：
Feier, Cristina;Kuusisto, Antti;Lutz, Carsten
我们研究了基于ALC族的表达性描述逻辑和连接查询的一元析取数据程序、MMSNP句子的补语和本体中介查询（omq）的可重写性。我们证明了可重写到FO和可重写到一元Datalog （MDLog）是可决定的，并且当原始查询满足一定的与相等相关的条件时，可重写到Datalog是可决定的。除了可重写到MDLog之外，我们对所有研究的问题都建立了2NEXPTIME-完备性，因为2NEXPTIME和3EXPTIME之间仍然存在差距。我们还分析了改写的形状，在MMSNP的情况下，它对应于障碍，并给出了一个比现有的更基本的规范Datalog程序的新结构，也适用于非布尔查询。
We study rewritability of monadic disjunctive Datalog programs, (the complements of) MMSNP sentences, and ontology-mediated queries (OMQs) based on expressive description logics of the ALC family and on conjunctive queries. We show that rewritability into FO and into monadic Datalog (MDLog) are decidable, and that rewritability into Datalog is decidable when the original query satisfies a certain condition related to equality. We establish 2NEXPTIME-completeness for all studied problems except rewritability into MDLog for which there remains a gap between 2NEXPTIME and 3EXPTIME. We also analyze the shape of rewritings, which in the case of MMSNP correspond to obstructions, and give a new construction of canonical Datalog programs that is more elementary than existing ones and also applies to non-Boolean queries.