Efficient Consistent Query Answering Based on Attribute Deletions
Jie Liu, Fei Huang, Dan Ye, Tao Huang · 2008
Data integrated from multiple sources may contain inconsistencies. A consistent query answer (CQA) in a possibly inconsistent database is an answer which is true in every minimal repair of the database. It is proved that for most constraints and queries CQA is a NP problem based on repairing by tuple deletions, therefore there are little applications based on CQA. Under closed world assumption, only attributes of tuples violating constraints are inconsistent and repair by deleting tuples will lose information. So we present a new repair semantic based on attribute deletions which can preserve consistent values in the tuple and we prove CQA can be computed in PTIME with respect to this repair semantic. Aided by well designed repair index table, we can compute CQA efficiently by SQL rewriting. We study the performance of our new approach for CQA by detailed experiments.