Paper Info
Title
On the complexity of sampling query feedback restricted database repair of functional dependency violations.
Abstract
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 Σ2P-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 [1] 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.
Year
DOI
Venue
2016
10.1016/j.tcs.2015.02.010
Theoretical Computer Science
Keywords
Field
DocType
Repair sampling,Database,Complexity
Web query classification,Theoretical computer science,Query optimization,Discrete mathematics,Conjunctive query,Decision problem,Combinatorics,Query expansion,Sargable,Online aggregation,Mathematics,Database,Boolean conjunctive query
Journal
Volume
Issue
ISSN
609
P3
0304-3975
Citations 
PageRank 
References 
7
0.53
24
Authors
3
Name
Order
Citations
PageRank
Dongjing Miao1189.91
Xianmin Liu2125.00
Jianzhong Li33196304.46