一句话：通过区分守卫原子与侧签名的元数，改进守卫 TGDs 开放世界查询应答的复杂度上界。
本文研究由初始事实集和守卫 TGDs 描述的不完整数据集上合取查询的开放世界查询应答问题。该问题已知可判定但复杂度高达 2EXPTIME 完全，固定元数时降一指数。作者将守卫原子的元数与其余原子组成的 side signature 的元数分开分析，基于 Gottlob、Manna 与 Pieris 的守卫 TGDs 线性化技术，并使用作者近期提出的受限 chase 变体给出新的线性化过程。结果表明：若固定 side signature 的元数，即使守卫关系元数任意，开放世界查询应答可在 EXPTIME 内求解；若固定 side signature 并限制依赖宽度，复杂度进一步降至 NP。
We consider the complexity of the open-world query answering problem, where we wish to determine certain answers to conjunctive queries over incomplete datasets specified by an initial set of facts and a set of guarded TGDs. This problem has been well-studied in the literature and is decidable but with a high complexity, namely, it is 2EXPTIME complete. Further, the complexity shrinks by one exponential when the arity is fixed. We show in this paper how we can obtain better complexity bounds when considering separately the arity of the guard atom and that of the additional atoms, called the side signature. Our results make use of the technique of linearizing guarded TGDs, introduced in Gottlob, Manna, and Pieris. Specifically, we present a variant of the linearization process, making use of a restricted version of the chase that we recently introduced. Our results imply that open-world query answering with guarded TGDs can be solved in EXPTIME with arbitrary-arity guard relations if we simply bound the arity of the side signature; and that the complexity drops to NP if we fix the side signature and bound the width of the dependencies.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{AmarilliB26,
title = {Tighter Bounds for Query Answering with Guarded TGDs},
author = {Antoine Amarilli and Michael Benedikt},
journal = {Logical Methods in Computer Science},
volume = {Volume 22, Issue 2},
year = {2026},
doi = {10.46298/lmcs-22(2:8)2026}
}