A Dichotomy in Consistent Query Answering for Primary Keys and Unary Foreign Keys
Miika Hannula, Jef Wijsen · 2022
Since 2005, significant progress has been made in the problem of Consistent Query Answering (CQA) with respect to primary keys. In this problem, the input is a database instance that may violate one or more primary key constraints. A repair is defined as a maximal subinstance that satisfies all primary keys. Given a Boolean query q, the question then is whether q holds true in every repair.