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

C ourse P ro f essor
Math

C ourse P ro f essor
CS John Mary

CS Frank M ath John

On the basis of these alternative repairs, what is consistently true is that ' John '
is the teacher the course ' Math ' and that there is a course named ' CS '.

The approach for handling inconsistency described in the example above shares
many similarities with the problem of updating a database seen as a logical the-
ory by means of a set of sentences (the integrity constraints). Specifically, given a
knowledge base K and a revision

α

, belief revision theory is concerned with the
properties that should hold for a rational notion of updating K with

α

.If K

∪ α

is
inconsistent, then belief revision theory assumes the requirement that the knowledge
should be revised so that the result is consistent. In the database case, the data are
flexible, subject to repair, but the integrity constraints are hard, not to be given up.
The “revision” of a database instance by the integrity constraints produces new
database instances, i.e. repairs for the original database. Therefore, what is consis-
tently true is what is true with respect to every repaired database. The notion of a fact
which is consistently true corresponds to the notion of inference, called counterfac-
tual inference , used in the belief revision community. In the database community,
the concept of fact which is consistently true has been formalized with the notion
of consistent query answer , i.e. an answer to a query which results true in every
repaired database. Consistent query answer provides a conservative “lower bound”
on the information contained in a database.

Example 1.1 (continued). Consider the query Q which intends

to retrieve the names of courses with their relative teachers. Obviously, if Q is di-
rectly posed on the inconsistent database it returns answers which are consistent
with the key constraints and others which are not. On the other hand, the consistent
query answers for Q are those which would be returned posing the query in every
repaired database, i.e. the tuple

( x , y )= Teaches ( x , y )

Math , John .

Different repairing primitives can be used for restoring database consistency in
reasonable ways. For instance, in the example above, repairs are obtained by per-
forming minimal sets of insertion and deletion of (whole) tuples on the original
database, so that the resulting database satisfies the integrity constraints. Another
possible notion of repair is that allowing updates of values within some tuples. Con-
sidering the example above, this means that the value of the attribute Pro f essor in
one of the two conflicting tuples must be changed in such a way that a consistent
status is obtained. Specifically, we may update either the value ' Mary 'to' Frank '
in the tuple CS , Mary or the value ' Frank 'to' Mary ' in the tuple CS , Frank ,

obtaining again the two repairs shown in Example 1.1.
In general, different set of repairs can be obtained under different repair notions.
Further, since the set of consistent answers to a query posed on an inconsistent
database depends on the set of repairs for the database, the repair semantics also
alters the set of consistent query answers.