About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SIGMOD/PODS 2015
Conference paper
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.