Title: Rewriting consistent answers on annotated data
Abstract: In this talk, I'll be discussing results on consistent query answering over databases annotated with values from naturally ordered positive semirings. We define consistent answers as the minimum of the semiring values achieved by evaluating the query over all database repairs. Focusing on self-join free conjunctive queries and key constraints, we introduce a variant of first-order logic with limited negation and suitable semiring semantics. The main result establishes that consistent answers are rewritable in this logic if and only if the query's attack graph is acyclic. This generalizes a classical result for standard databases and provides a unified framework for various semirings, including the bag, tropical, and fuzzy semirings. Furthermore, we show that self-join free conjunctive queries with cyclic attack graphs do not have a polynomial-time constant-approximation algorithm under bag semantics, unless P=NP.