在拒绝约束下近似最优的软修复方法

《IEEE Transactions on Knowledge and Data Engineering》：Approximating Optimal Soft Repairs for Denial Constraints

　　

摘要：

针对函数依赖关系下的不一致关系数据库，计算最优的软修复问题属于NP难问题。目前已有针对该问题的常数比率近似算法被广泛研究。不过，对于存在拒绝约束的不一致关系数据库的最优软修复问题，是否存在相应的常数比率近似算法仍需进一步探讨。本文提出了一个基于线性规划的框架来近似解决该问题。基于该框架，我们得到了一个多项式时间复杂度的(λ+1)的近似算法，其中该常数λ表示与给定拒绝约束集合相关的违规事务的最大数量。此外，当λ=2时，该近似比率可降至2，从而显著提升了现有针对函数依赖关系的3近似算法的性能。我们的框架还可用于计算存在拒绝约束的不一致时序数据库的最优软修复问题。我们证明，基于该框架以及一个多项式时间复杂度的λ近似算法，可以轻松地为所有拒绝约束均为硬约束的时序数据库的该问题得出多项式时间复杂度的解。在五个真实世界数据集上的实验表明，基于我们框架得到的算法，其修复成本比现有方法低多达21%，同时还能保持稳定的运行时间，并提升查询回答的准确性。

I. 引言

如果数据库违反了任何给定的完整性约束，无论是函数依赖关系还是拒绝约束，那么该数据库就是不一致的。为了解决不一致数据库的问题，Arenas等人提出了修复的概念[1]。关系数据库的修复计算受到了广泛关注，它在数据修复[2]、一致性查询回答[1]以及数据库不一致性检测[3]、[4]等方面都有应用。以往的大多数研究都集中在计算（最优的）硬修复，即能够满足所有给定完整性约束的数据库修复。然而，从数据中发现的完整性约束往往存在噪声或不可靠性[5]、[6]，严格遵循所有约束可能会导致信息丢失。这就促使人们开始研究软子集修复[7]，即允许部分约束被违反。