一句话：研究单个描述逻辑本体在合取查询等查询下的数据复杂度，给出 PTime/coNP 二分与不可判定性结果。
本文研究 ALC 族描述逻辑本体的数据复杂度，查询包括合取查询、正存在查询与无环合取查询。作者采取非一致视角，逐一分析单个本体：在查询上量化，判断相对于给定本体是否所有查询都可在多项式时间内求值。主要结果包括：深度为一的 ALCFI 本体存在 PTime/coNP 二分；无深度限制的 ALC 与 ALCI 本体同样如此；ALCF 本体则不存在此类二分。对 ALCF，作者还证明给定本体是否允许 PTime 查询求值不可判定，并考察 PTime 求值与重写为（一元）Datalog 的联系。
We analyze the data complexity of ontology-mediated querying where the ontologies are formulated in a description logic (DL) of the ALC family and queries are conjunctive queries, positive existential queries, or acyclic conjunctive queries. Our approach is non-uniform in the sense that we aim to understand the complexity of each single ontology instead of for all ontologies formulated in a certain language. While doing so, we quantify over the queries and are interested, for example, in the question whether all queries can be evaluated in polynomial time w.r.t. a given ontology. Our results include a PTime/coNP-dichotomy for ontologies of depth one in the description logic ALCFI, the same dichotomy for ALC- and ALCI-ontologies of unrestricted depth, and the non-existence of such a dichotomy for ALCF-ontologies. For the latter DL, we additionally show that it is undecidable whether a given ontology admits PTime query evaluation. We also consider the connection between PTime query evaluation and rewritability into (monadic) Datalog.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{LutzW16,
title = {The Data Complexity of Description Logic Ontologies},
author = {Carsten Lutz and Frank Wolter},
journal = {Logical Methods in Computer Science},
volume = {Volume 13, Issue 4},
year = {2017},
doi = {10.23638/lmcs-13(4:7)2017}
}