Making More Out of an Inconsistent Database

摘要

Repairing a database means making the database consistent by applying changes that are as small as possible. Nearly all approaches to repairing have assumed deletions and insertions of entire tuples as basic repair primitives. A negative effect of deletions is that when a tuple is deleted because it contains an error, the correct values contained in that tuple are also lost. It can be semantically more meaningful to update erroneous values in place, called update-based repairing. We prove that a previously proposed approach to update-based repairing leads to intractability. Nevertheless, we also show that the complexity decreases under the rather plausible assumption that database errors are mutually independent. An inconsistent database can generally be repaired in many ways. The consistent answer to a query on a database is usually defined as the intersection of the answers to the query on all repaired versions of the database. We propose an alternative semantics, defining the consistent answer as being maximal homomorphic to the answers on all repairs. This new semantics always produces more informative answers and ensures closure of conjunctive queries under composition.