一句话：对带封闭谓词的本体中介查询进行数据复杂度分类，在DL-Lite、EL与ALCHI中建立可处理与不可处理边界。
本文研究描述逻辑本体中介查询中，部分谓词可被封闭（OMQC）时的数据复杂度。作者采用非一致性分析，对轻量级 DL-Lite、EL 及表达力较强的 ALCHI 本体给出可处理与不可处理的分类。本体层面：DL-Lite 呈现 FO 可重写与 coNP 完全之间的二分，EL 呈现 PTime 与 coNP 完全之间的二分，判定可处理性的元问题属于 PTime。OMQC 层面：若概念名和角色名均可封闭，则不存在二分（除非 NP=PTime）；若只封闭概念名，查询求值复杂度与满射 CSP 复杂度紧密关联。还识别出一类基于 DL-Lite 本体的 OMQC 保证可处理甚至 FO 可重写。
In the context of ontology-mediated querying with description logics (DLs), we study the data complexity of queries in which selected predicates can be closed (OMQCs). We provide a non-uniform analysis, aiming at a classification of the complexity into tractable and non-tractable for ontologies in the lightweight DLs DL-Lite and EL, and the expressive DL ALCHI. At the level of ontologies, we prove a dichotomy between FO-rewritable and coNP-complete for DL-Lite and between PTime and coNP-complete for EL. The meta problem of deciding tractability is proved to be in PTime. At the level of OMQCs, we show that there is no dichotomy (unless NP equals PTime) if both concept and role names can be closed. If only concept names can be closed, we tightly link the complexity of query evaluation to the complexity of surjective CSPs. We also identify a class of OMQCs based on ontologies formulated in DL-Lite that are guaranteed to be tractable and even FO-rewritable.
@article{paperbot763,
title = {The Data Complexity of Ontology-Mediated Queries with Closed Predicates},
author = {Carsten Lutz and Inanc Seylan and Frank Wolter},
journal = {Logical Methods in Computer Science},
volume = {Volume 15, Issue 3},
year = {2019},
doi = {10.23638/lmcs-15(3:23)2019}
}