Dichotomies in the Complexity of Preferred Repairs

Abstract

The framework of database repairs provides a principled approach to managing inconsistencies in databases. Infor- mally, a repair of an inconsistence database is a consistent database that differs from the inconsistent one in a "mini- mal way." A fundamental problem in this framework is the repair-checking problem: given two instances, is the second a repair of the first? Here, all repairs are taken into account, and they are treated on a par with each other. There are situations, however, in which it is natural and desired to pre- fer one repair over another; for example, one data source is regarded to be more reliable than another, or timestamp in- formation implies that a more recent fact should be preferred over an earlier one. Motivated by these considerations, Sta- worko, Chomicki and Marcinkowski introduced the frame- work of preferred repairs. The main characteristic of this framework is that it uses a priority relation between con- icting facts of an inconsistent database to define notions of preferred repairs. In this paper we focus on the globally- optimal repairs, in the case where the constraints are func- tional dependencies. Intuitively, a globally-optimal repair is a repair that cannot be improved by exchanging facts with preferred facts. In this setting, it is known that there is a fixed schema (i.e., signature and functional dependencies) where globally-optimal repair-checking is coNP-complete. Our main result is a dichotomy in complexity: for each fixed relational signature and each fixed set of functional dependencies, the globally-optimal repair-checking problem either is solvable in polynomial time or is coNP-complete. Specifically, the problem is solvable in polynomial time if for each relation symbol in the signature, the functional de- pendencies are equivalent to either a single functional de- pendency or to a set of two key constraints; in all other cases, the globally-optimal repair-checking problem is coNP- complete. We also show that there is a polynomial-time al- gorithm for distinguishing between the tractable and the in- tractable cases. The setup of preferred repairs assumes that preferences are only between conicting facts. In the last part of the paper, we investigate the effect of this assump- tion on the complexity of globally-optimal repair checking. With this assumption relaxed, we give another dichotomy theorem and another polynomial-time distinguishing algo- rithm. Interestingly, the two dichotomies turn out to have quite different conditions for distinguishing tractability from intractability.