摘要 Abstract
本文研究了在用自然有序正半环注释的数据库上查询的一致答案。在这种情况下,查询的一致答案被定义为查询在不一致数据库的所有修复上取值的半环值的最小值。主要关注的是无自连接的连接查询和键约束,这是标准数据库上一致查询回答研究得最多的案例。我们引入了一种具有有限形式否定的一阶逻辑变体,定义了适当的半环语义,并建立了论文的主要结果:在键约束下,无自连接的连接查询的一致查询答案可以在此逻辑中重写当且仅当查询的攻击图不含循环。这个结果推广了Koutris和Wijsen对于普通数据库的类似结果,但也为许多半环(包括包半环、热带半环和模糊半环)得到了新的结果。此外,对于包半环,我们证明了计算任何攻击图具有强循环的无自连接的连接查询的一致答案不仅NP困难,而且即使近似计算一致答案也难以保证常数相对近似度。
We embark on a study of the consistent answers of queries over databases annotated with values from a naturally ordered positive semiring. In this setting, the consistent answers of a query are defined as the minimum of the semiring values that the query takes over all repairs of an inconsistent database. The main focus is on self-join free conjunctive queries and key constraints, which is the most extensively studied case of consistent query answering over standard databases. We introduce a variant of first-order logic with a limited form of negation, define suitable semiring semantics, and then establish the main result of the paper: the consistent query answers of a self-join free conjunctive query under key constraints are rewritable in this logic if and only if the attack graph of the query contains no cycles. This result generalizes an analogous result of Koutris and Wijsen for ordinary databases, but also yields new results for a multitude of semirings, including the bag semiring, the tropical semiring, and the fuzzy semiring. Further, for the bag semiring, we show that computing the consistent answers of any self-join free conjunctive query whose attack graph has a strong cycle is not only NP-hard but also it is NP-hard to even approximate the consistent answers with a constant relative approximation guarantee.