2 前期工作和问题陈述

2.1 基于规则的修复方法

定义1一个集合被定义为正确集合当且仅当集合中所有的值均正确。如果这两个集合不可以同时都是正确集合，我们说这两个集合之间存在冲突（Conflict）。

基于规则的修复方法依赖预定义的质量规则检测数据之间的冲突，并希望通过
清洗引起冲突的错误达到解决这些冲突的目的。本文以FD/CFD为例来展示我们的方法是如何执行的。为了便于理解，给出一个运行示例。

例1如图1(a)所示，对于给定的一个个人联系方式数据表，每个元组不仅包含一个人的Name和Inst,还包含这个人的地址信息如City、State、Country和Zip。我们在表中标出了错误数据。图1(b)中显示的是一组约束条件(FD/CFDs)。

（1）冲突检测根据给定的FD/CFDs,表中的许多冲突数据可以被检测出来。例如，根据规则φ2，t1和t3的Inst(UQ)相同，但t1City和t3City不一致，所以这两个City的值是互相冲突的。图2(a)显示了根据约束条件找出的表1(a)中的26个冲突，图中每一个节点表示表中的一个属性值（错误的数据已被标出），两个节点间的连线表示这两个节点发生了冲突。

（2）冲突解决当属性值之间发生冲突时，为了解决冲突我们就需要修改一些值。为了解决数据库中所有的冲突，有些方法偏向于对数据集做尽量少的修改[2,4]，有些方法倾向于用一些简单的预测模型做最有可能正确的修改[1,3]。例如图2(a)所示，因为t4Inst和其他三个值(UQ)都冲突，为了解决这三个冲突，我们可以把t4Inst改成UQ(代价是1)，也可以把三个UQ改成QUT(代价是3)。这两种方法都倾向于选择第一种修改方案，实际情况中第一种修正是正确的。

但是在以下三种情况中，这些方法会做出错误的决定。

（3） 修复的置信度估计基于规则修复的准确率是由FD/CFD和推导中用到的值共同决定的。因此，一个修复的质量是由用于推导的值和使用的FD/CFD的置信度决定的，即

2.2 交互过程中的问题陈述

我们仍然使用FD/CFDs来发现数据之间的冲突，但在确认和修正这些冲突中的错误数据时，考虑将众包加入这个过程中，以达到在一个有效的交互方式下提高修复质量的目的。需要说明的是在本文中我们暂时忽略众包修复可能带来的错误修复，在未来工作中会再考虑这个问题。

最基本的交互过程描述如下：首先设置一个质量约束条件，并根据这一质量约束对那些冲突做基于规则的修复。然后选择一些值进行众包修复，使更多的值能够用被规则修复或推导。我们迭代地进行这种交互式修复，直至没有更多的值可以被修改为止。