The complexity and approximation of fixing numerical attributes in databases under integrity constraints
- 作者：Leopoldo Bertossi ; Loreto Bravo ; Enrico Franconi ; Andrei Lopatenko
- 关键词：Integrity constraints ; Inconsistent databases ; Consistent query answering ; Database repairs
- 刊名：Information Systems
- 出版年：2008
- 期刊代码：64_03064379
- 类别：cp
- 出版时间：June-July 2008
- 卷：33
- 期：4-5
- 页码：407-434
- 文件大小：462 K
摘要
Consistent query answering is the problem of characterizing and computing the semantically correct answers to queries from a database that may not satisfy certain integrity constraints. Consistent answers are characterized as those answers that are invariant under all minimally repaired versions of the original database. We study the problem of repairing databases with respect to denial constraints by fixing integer numerical values taken by attributes. We introduce a quantitative definition of database repair, and investigate the complexity of several decision and optimization problems. Among them, Database Repair Problem (DRP): deciding the existence of repairs within a given distance to the original instance, and CQA: deciding consistency of answers to simple and aggregate conjunctive queries under different semantics. We provide sharp complexity bounds, identifying relevant tractable and intractable cases. We also develop approximation algorithms for the latter. Among other results, we establish: (a) The d=retrieve&_udi=B6V0G-4RM1M0G-2&_mathId=mml1&_user=1067359&_cdi=5646&_rdoc=6&_acct=C000050221&_version=1&_userid=10&md5=be4edab2f106edabc1b4b4f65997b80b">
direct.com/cache/MiamiImageURL/B6V0G-4RM1M0G-2-4/0?wchp=dGLbVtz-zSkWW" alt="View the MathML source" title="View the MathML source" align="absbottom" border="0" height=19 width="20"/>-hardness of CQA. (b) That DRP is MAXSNP-hard, but has a good approximation. (c) The intractability of CQA for aggregate queries for one database atom denials (plus built-ins), and also that it has a good approximation.