论文标题
有限的开放世界查询回答数字限制
Finite Open-World Query Answering with Number Restrictions
论文作者
论文摘要
开放世界的查询回答是确定的问题，给定一组事实，约束的结合以及查询，是否暗示着事实和约束。这等于在包括事实并满足约束的所有情况下的推理。我们研究有限的开放世界查询答案（FQA），该查询假设基础世界是有限的，因此仅考虑了实例的有限完成。 FQA的主要可确定情况是从以下内容中得出的：一阶逻辑的保护片段，可以表达参考约束（一个位置的数据点在另一个位置的数据点），但无法表达数字限制，例如功能依赖性；而且受保护的碎片具有数字限制，但仅具有两个签名。在本文中，我们给出了FQA的第一个可确定性结果，该结果结合了任意签名的参考约束和数量限制：我们表明，对于一般包含依赖性和功能依赖性，可以将FQA的有限假设提升到依赖依赖性的有限含义关闭。我们的结果依靠新技术来构建此类约束的有限通用模型，以最大查询大小为界限。
Open-world query answering is the problem of deciding, given a set of facts, conjunction of constraints, and query, whether the facts and constraints imply the query. This amounts to reasoning over all instances that include the facts and satisfy the constraints. We study finite open-world query answering (FQA), which assumes that the underlying world is finite and thus only considers the finite completions of the instance. The major known decidable cases of FQA derive from the following: the guarded fragment of first-order logic, which can express referential constraints (data in one place points to data in another) but cannot express number restrictions such as functional dependencies; and the guarded fragment with number restrictions but on a signature of arity only two. In this paper, we give the first decidability results for FQA that combine both referential constraints and number restrictions for arbitrary signatures: we show that, for unary inclusion dependencies and functional dependencies, the finiteness assumption of FQA can be lifted up to taking the finite implication closure of the dependencies. Our result relies on new techniques to construct finite universal models of such constraints, for any bound on the maximal query size.
