Counting subset repairs with functional dependencies

Abstract We study the problem of counting the repairs of an inconsistent database in the case where constraints are Functional Dependencies (FDs). A repair is then a maximal independent set of the conflict graph, wherein nodes represent facts and edges represent violations. We establish a dichotomy in data complexity for the complete space of FDs: when the FD set has, up to equivalence, what we call a “left-hand-side chain,” the repairs can be counted in polynomial time; otherwise, the problem is ♯ P -complete. Moreover, the property of having a left-hand-side chain up to equivalence coincides with the condition that the conflict graph of every inconsistent database for the schema is P 4 -free, and it is polynomial-time decidable.