On the complexity of sampling query feedback restricted database repair of functional dependency violations

摘要

An inconsistent database is a database instance violating integrity constraints. A repair of an inconsistent database is a maximal consistent subset. Sampling from the repair space is an alternative approach meeting the needs of many applications. In this paper, we introduce a new class of repair, query feedback restricted repair, based on the feedback on user's witness query. We first map out a picture of both data and combined complexities of repair existence problems under different cases to identify the intractable cases. Especially, we show that if the query is a projection or a union query, then the decision problem is NP-complete; even worse, if the query is a conjunctive query, the decision problem becomes Sigma(p)(2)-complete. However, we prove that the combined complexity of the repair existence problem is in LOGSPACE when the witness query is a selection-join query, and this conclusion also implies that the combined complexity of side-effect free deletion propagation problem under group-deletion is in LOGSPACE which is not considered in previous works. Additionally, we provide a polynomial random repair sampling algorithm under combined complexity. At last, we revisit the key preserving condition PI and show that it will simplify the problem, i.e., some cases become tractable for certain key preserving views, as opposed to their counterparts that are not key preserving. (C) 2015 Published by Elsevier B.V.