Introduction - Repairing and Querying Databases under Aggregate Constraints - page 8

which is avoided if only value updates are allowed. On the other hand, a repairing
strategy using tuple insertions suffers from the problem that often there is no reason-
able way to guess the values which should be assigned to the non-measure attributes
in the tuples to be inserted.
This topic provides a study of the problem of extracting reliable information from
databases violating a set of aggregate constraints in a setting where an attribute-level
repairing strategy is adopted. Before presenting the organization of the topic, a brief
overview on the main issues and results in the area of inconsistent databases is
provided.
1.3 Overview of Inconsistency Handling in Databases
Although first theoretical approaches to the problem of dealing with incomplete and
inconsistent information date back to 80s, these works mainly focus on issues re-
lated to the semantics of incompleteness [37]. The semantics of queries posed on
inconsistent integrated databases was first investigated in [3], where an extension of
relational algebra (namely flexible algebra ) was proposed to evaluate queries on data
inconsistent w.r.t. key constraints. An extension of the the flexible relational model,
called integrated relational model , was proposed in [19] where it was argued that
the semantics of integrating inconsistent data is captured by the maximal consis-
tent subset (with null values) of the integrated data. In [42] a different semantics
(namely, merging by majority rule ) based on the cardinality of the source databases
containing the same tuples was introduced in order to manage data inconsistent w.r.t.
first-order integrity constraints.
The first proof-theoretic notion of consistent query answer was introduced in [14],
expressing the idea that tuples involved in an integrity violation should not be con-
sidered in the evaluation of consistent query answers. In [4] a different notion of
consistent answer was introduced, based on the notion of repair : a repair of an in-
consistent database D is a database D , on the same scheme as D , satisfying the
given integrity constraints and which is minimally different from D . Thus, the con-
sistent answer of a query q posed on D is the answer which is in every result of q
posed on each repair D . In particular, in [4] the authors show that, for quantifier-free
conjunctive queries and binary universal constraints, consistent answers can be eval-
uated without computing repairs, but by looking only at the specified constraints and
rewriting the original query q into a query q such that the answer of q on D is equal
to the consistent answer of q on D . The query-rewriting technique introduced in [4]
was further developed in [16] where an implementation of the rewriting operator is
also presented. Later the query-rewriting technique was extended in [31, 29] to work
for a subclass of conjunctive queries with existential quantification in the presence
of key constraints. Recently, the this technique was further studied in [51, 52].
Starting from the notions of repair and consistent query answer introduced in [4],
the problems of repairing and querying inconsistent databases were investigated in
several works where more expressive classes of queries and constraints were con-