  We introduce a general abstract framework for database repairing in which the
repair notions are defined using formal logic. We differentiate between
integrity constraints and the so-called query constraints. The former are used
to model consistency and desirable properties of the data (such as functional
dependencies and independencies), while the latter relates two database
instances according to their answers for the query constraints. The framework
also admits a distinction between hard and soft queries, allowing to preserve
the answers of a core set of queries as well as defining a distance between
instances based on query answers. We exemplify how various notions of repairs
from the literature can be modelled in our unifying framework. Furthermore, we
initiate a complexity-theoretic analysis of the problems of consistent query
answering, repair computation, and existence of repair within the new
framework. We present both coNP- and NP-hard cases that illustrate the
interplay between computationally hard problems and more flexible repair
notions. We show general upper bounds in NP and the second level of the
polynomial hierarchy. Finally, we relate the existence of a repair to model
checking of existential second-order logic.
