BigDansing: A System for Big Data Cleansing论文笔记

这是BigDansing这篇论文的一些笔记，希望对您有所帮助。

**1.**基础

1. ****Semantics

Detect GenFix

v v

->UDF->Violation->Possible Fixes

****UDF

U:用户自定义的关系

D:拒绝约束(t1,t2=>f(t1,t2) = 1)

F:函数依赖(F(x)=y)

****动作

Dirty Database + Rules

=>A repair => D’

D’ 不会违反规则，或者只存在无法修复（不存在possible fixes）的规则违反

****架构
1. 逻辑层
允许用户以简单的方式表达各种数据质量规则
有五个逻辑运算符：
1. Scope：定义了规则的相关数据
2. Block：定义了可能发生冲突的数据单元组
3. Iterate：枚举了候选冲突
4. Detect：决定了候选冲突是否是真的冲突
5. GenFix：为每一个冲突生成一个可能的修复集合

用户定义逻辑运算符以及运算顺序，或者提供声明性的规则

2. 物理层 

这一层，BD收到一个逻辑计划，然后转化成物理操作组成的优化过的物理计划。
实现方式有基于散列、基于范围。
主要优化步骤：计划整合／数据访问优化

3. 执行层 

决定了如何在底层的并行数据处理框架中执行物理计划，将物理计划转换为执行计划，它由一系列依赖于系统的操作组成，如Spark或MapReduce作业。
BD在底层系统上运行生成的执行计划，然后收集所有的违规行为和这个执行产生的可能的修复，因此通过为逻辑运算符提供几行代码，用户可以获得并行数据处理框架的优势。

2. ****其他
   1. BD一旦收集了一系列违规和可能的修复，就会继续修复（清楚）脏数据，此处修复过程和规则数量以及其语义无关，因为修复算法只考虑了一组违规行为及可能的修复。
   在Chap5，论文提出了两种不同的方法来实现分布式设置中的现有算法，扩展中保留了原始算法的正确性和中止属性，专业的用户可以插入自己的修复算法。在扩展算法中，每个修复步骤都可以通过possible fixes贪心地消除冲突，并最小化成本函数（见2.1节）。
   注意，修复步骤可能会引入新的违规，并且新的步骤可能决定再次更新这些单元，所以为了确定终止，算法在迭代了固定次数以后（用户自定义），在这种单元上放置一个特殊变量，从而消除未来在同一个数据上产生新的冲突的可能性。

2.Rule Specification

1. 前言
   1. 五个逻辑运算符：Scope，Block，Iterate，Detect，GenFix
   后两个是为数据清洗过程建模的两个通用运算符
   前三个确保了BD高效、可扩展地执行。
   1. Scope减少了必须处理的数据量
   2. Block减少了候选冲突生成的搜索空间
   3. Iterate有效地便利已经被缩小的搜索空间，从而生成所有候选冲突

注意，这五个运算符本身不修改修复过程，系统将这些操作符与生成的或用户提供的BD作业转化成逻辑计划。

2. Logical Operators
   1. 如前所述，DB通过数据单元Us来定义输入的数据，逻辑操作符也是运行在这上面的。它虽是个细粒度的模型，但是它允许以高度并行的方式应用运算符减少成本。
   2. 五个运算符的定义（系统会自动为声明性规则声称表）：
   Scope：从数据集中删除不相关的数据单元（prune？）
   1. 如论文图2中，Scope根据φF，将原数据库进行删减仅仅保留了zipcode和city的数据。
   2.

Block：将共享了相同的blocking key的数据进行分组
1. 对每个数据单元U，Block会输出一个阻塞键
2. Block运算符可以增加BD的可扩展性，因为它可以缩小可能发生违规的数据单元数量。如论文图2中，Block根据属性zipcode对元组进行分组，使得三个块拥有不同的zipcode。这样分组后，冲突仅可能发生在块内，而不会跨块。
3.

Iterate：定义如何组织数据单元产生候选冲突
1. 数据单元列表组成的列表将作为输入，输出一个U，或者一个U组成的列表
2. 此运算符可以避免以O(n^2)的复杂度产生候选冲突。如图二中，Iterate通过每个块内的两个元组的每个唯一组合，仅仅产生四对，而不是13对。
3.

Detect：将单个U／一对U或一个列表oUs作为输入，输出一个冲突列表，可能为空。
1. 上述三种输入类型可以用来区分输入的不同粒度，以此实现更好的并行化。
2.

GenFix：为冲突计算一个可能的修复集合。
1. 如，若只能修改右侧值，GenFix会为每个检测到的违规产生一个可能的修复：t2 [city] = t4 [city]，t6 [city] = t4 [city].
2.

3. 另外，为了更好的指定不同运算符之间的数据流，我们引入一个标签来标记数据项并跟踪它的处理方式。
4. 和DBMS相反，BD的操作符实UDF，允许用户插入任何逻辑，因此我们不限制特定的数据模型。但为了便于说明，我们所有的例子都基于关系数据模型。

3. 规划过程
   1. BD的逻辑层将一组标记的逻辑运算符与作业一起作为输入，并输出逻辑计划。通过检查是否定义了所有被引用的逻辑运算符并且至少一个Detect被指定来确定提交的工作是否正确，以此启动系统。
   2. 在验证了提交的作业之后，BD生成一个逻辑计划：
   必须至少有一个输入数据集Di
   可能有一个或多个Scope运算符
   可能有一个Block操作符或更多链接到Iterate操作符
   必须至少有一个可能产生冲突集合的Detect操作符
   可以为每一个检测运算符设置一个GenFix运算符以生成每个冲突的可能修复

3. BD会为每个Detect指定匹配的Iterate，如果没有指定Iterate，BD会根据Detect操作器所需的输入产生一个。然后它使用Iterate运算符的输入标签，**以相反的顺序找到其他可能的迭代运算符。** 每个新检测到的Iterate都将添加到与其输入标签相关的Block运算符的计划中，一旦它处理了所有的Iterate运算符，它可以找到Scope运算符。
4. 如果缺少Scope或Block运算符，BD将输入数据集推送到逻辑计划中的下一个运算符，如果没有GenFix运算符，则会将Detect操作符的输出写入磁盘。

3.Physical Operators

1. 物理操作符
   1. wrapper和enhancers
   包装器简单地调用一个逻辑运算符，增强器替换包装器以利用不同的优化。
   调用逻辑运算符以及相应的物理细节，例如输入数据集合模式细节（后续将丢弃这些物理细节）。
   和逻辑层相反，BD为数据单元的集合D而不是单个单元调用物理操作符，这可以在单个函数中完成多个单元的运算过程。
   对每个逻辑运算符，我们将定义一个wrapper。

2. 五个不同的wrapper 

PScope(D) → {D′}
PBlock(D) → map⟨key, list⟨U ⟩⟩
PIterate(list⟨list⟨U⟩⟩) → list⟨U⟩ | list⟨Pair⟨U⟩⟩
PDetect(list⟨U ⟩ | list⟨Pair⟨U ⟩⟩) → list⟨V violation⟩
PGenFix(list⟨V iolation⟩) → list⟨{P ossibleF exes}⟩
上述过程就是图2的过程

3. 通过声明规则，一个数据集上的运算是已知的，这让算法得以提升性能。或者我们也可以通过UDF的代码分析来发现这些运算。然而，我们将此扩展留到以后。
4. BD通过三种增强器来利用这个优化的机会：CoBlock, UCrossProduct, and OCJoin。 

CoBlock是允许通过给出key来对多个数据集进行分组的物理运算符。
UCrossProduct和OCJoin基本上就是PIterate运算符的另外两种不同的实现方式。

2. 从逻辑计划到物理计划
   1. 如前所述，我们可以通过静态分析（计划整合）和插入增强器（运算符翻译）来实现逻辑计划的优化。
   计划整合
   1. 每当逻辑运算符对同一数据集使用不同的标签，BD将它们转换成不同的物理运算符。BD必须创建相同数据集的多个副本，并把它们广播到不同的节点上。因此，计算节点上的内存占用和网络流量都将会增加。为了解决这个问题，BD将冗余的逻辑运算符合并成一个逻辑运算符，因此，通过共享扫描的方法，在同一组数据集上多次应用同一运算符，可以让BD增加数据的局部性并减少I/O的开销。
   2. 算法1详细说明了对输入的逻辑计划的整合过程。对每个运算符lopi，算法寻找匹配的运算符lopj。如果lopi和j具有相同的数据集，那么BD将它们整合成lopc。这个新的合并运算符从lopi,j中获取标签、函数和数据集，接下来，BD将lopc添加到逻辑计划构建器lpb中，然后移除原来的lopi和j即可。最后，如果有任何运算符被合并，那么它将非合并运算符添加到lpb并返回同一个逻辑计划，否则依然返回lp（lp没变）

运算符翻译
1. 一旦逻辑计划被合并，BD将整合的逻辑计划转化成物理计划，它将每个逻辑运算符映射到其对应的包装器，该包装器又映射到一个或多个物理运算符。对增强器，BD利用数据清理过程中的一些特点的信息。
2. 三种增强器：
1. CoBlock
1. 需要多个输入数据集D，并在给定的关键字上应用一个分组。这将限制比较操作仅仅在来自不同数据集、具有相同的key值的块中发生。类似于CoGroup，来自两个输入的所有键都被收集到bags中。此运算符的输出是从键值到共享该键值的数据单元列表的映射。
2. 输入->输出为CoBlock（D）→map⟨key，list⟨list⟨U⟩⟩⟩
3. 如果两个非合并块运算符的输出到了同一个Iterate，然后到了一个单独的PDetect，BD会把它们翻译到同一个CoBlock，使用Block允许我们减少检测的候选违规数量，这是因为Iterate只在内部而不是CoBlocks中产生候选冲突。
4. CoBlock (D) → map⟨key, list⟨list⟨U ⟩⟩⟩

  2. UCrossProduct 
    1. 接收单个输入数据集并在这上面应用自向量积。这个操作一般在清洁过程中进行，输出忽视了Detect的输入顺序的相同的冲突。
    2. UCP避免了冗余比较，减少了从n^2到n*(n-1)/2的比较数，n是我们输入的Units的数量。详见图2，有四对而不是13对就是因为有UCP的运算。
    3. UCrossProduct(D) → list⟨Pair⟨U⟩⟩  

    4. 如果对于单个数据集，声明性规则仅仅包含对称比较，例如=和!=，则元组传递到PDetect（或下一个逻辑运算符（如果有的话））的顺序并不重要。这种情况下，BD使用UCP避免实现许多不必要的数据单元对，如图2中的Iterate运算符。
    5. 其它使用UCP的情况： 
      1. 用户不为Iterate运算符提供匹配的Block运算符
      2. 用户不提供任何Iterate或Block运算符。

  3. OCJoins 
    1. OCJoins在一个或多个排序比较（大于小于等等）上执行自联接，这个操作在Denial Constraints上很常见。  

    2. 它是一个用来处理连接排序比较的高效运算符，需要输入数据集D，并应用多个连接条件，返回连接U对的列表。
    3. OCJoin(D) → list⟨Pair⟨U⟩⟩  

    4. 每次BD都会识别通过PDetect中的排序比较定义的连接条件比如φD，在定义连接条件时，将Iterate转换为OCJoin实现，然后将OCJoin输出传递给一个PDetect运算符（或下一个运算符）

3. 排序比较下的快速连接
   1. 现有系统通过使用向量积和后选择谓词（post-selection predicate）进行排序比较处理连接，从而导致性能下降。BD提供了一个高效的临时连接运算符，称为OCJoin来处理这种情况。OCJoin的主要目标时通过并行排序 比较来提高处理连接的能力 ，并且减少算法的搜索空间来降低复杂度。简而言之，OCJoin的第一范围分割一组数据单元并对每个结果分区进行排序，以便以分布式方式验证不等式连接条件。OCJoin分为四个主要的阶段：分区partitioning，排序sorting，修剪pruning和加入joining。
   2. Partitioning
   OCJoin首先选择属性PartAtt，并在该属性上对输入D进行分区。假设所有的连接条件都具有相同的输出基数。（这可以用基数估计进行改进，但超纲了）
   OCJoin选择第一个条件涉及的第一个属性，例如对φD来说，OCJoin将PartAtt设置为rate。
   然后OCJoin将D分割为基于PartAtt的nvParts范围分区，作为此分区的一部分，OCJoin会将所生成的分区分发到所有可用的计算节点 。注意，OCJoin并行运行范围分区，接下来，OCJoin为每个范围分区ki分配一个并行进程，然后运行后续的三个阶段。

3. Sorting 

对每个分区，OCJoin创建与规则中的不等式条件一样多的排序列表（也就是Sorts）。例如，OCJoin为φD创建两个排序列表：一个按比例排序，另外一个按工资排序。每个列表都包含排序顺序所属的属性值和元组标识符。
注意，OCJoin仅在此阶段执行本地排序，因此不需要跨节点 进行任何数据传输，由于分区的多个副本可能存在于多个计算节点中，因此我们在prune和join阶段之前应用排序，以确保每个分区最多排序依次。

4. Pruning 

一旦所有分区ki∈K被内部排序，OCJoin可以基于不等式连接条件开始连接这些分区。然而，这将需要将大量数据从一个节点转移到另一个节点。为了避免这种开销，OCJoin会检查每个分区的最小和最大值，以避免在最小和最大范围加入不重叠的分区。非重叠分区不产生任何连接结果，如果不等式条件的选择性值已知，OCJoin可以相应地排序不同的连接。

5. Joining 

最后继续加入重叠的分区并输出连接结果。为此，它将在分类好的列表中应用分布式排序来归并连接，其中一些分区广播到其他机器，同时保持本地的状态。
通过pruning，OCJoin告诉分区将加入的底层分布式处理平台，选择最佳方式来最小化广播分区的数量由该平台决定。

5.DISTRIBUTED REPAIR ALGORITHMS

1. 大多数现有的修复技术都是集中的，我们提出在BD中实现修复算法的两种算法。BD系统可以并行运行集中式的数据修复算法，而不用改变算法。BigDansing会将该算法视为Black Box，而且作者设计了广泛使用的等价类算法的分布式版本。

2. 将数据修复缩放到黑盒中
   1. 前言
   总体来说，我们将修复任务分成独立的较小的维修任务。为此我们将违规图表表示为包含冲突行为及其可能修复的超图。节点表示元素，每个超边覆盖了一组违反规则的元素以及可能的修复方法。然后划分超图，分成更小的独立子图，也就是联通分量，并且将每个连接的组件传递到独立的数据修复实例。

2. 联通分量（Connected components） 

给定一组违规作为输入，形成至少一个规则，BD首先以分布式的方式创建其可能修复的分布式方式。然后用GraphX在超图中查找所有的联通分量。接下去，GraphX又使用Bulk Synchronous Parallel (BSP)图处理模型并行处理超图。因此BD会为每个超边获取连接的组件ID。然后，通过连接的组件ID分组超边。
图7显示了超图中的连接的组件的示例。要注意的是，冲突v1和v2，可能由不同的规则引起。冲突v1和v2被分组在单个联通分量CC1中，因为它们共享同一个元素c2。相反v3倍分配给另外一个联通分量CC2，因为它和v1，v2没有共享的元素。

3. 独立数据修复实例 

一旦计算了所有的联通分量，BD将它们中的每一个分配给独立的数据修复实例，并以分布式方式运行这些修复实例。当所有数据修复实例生成所需的修补程序时，BD将更新输入数据集并将其再次传递给RuleEngine，以检测修复算法引入的潜在的违规。修复所有违规行为所需的迭代次数取决于输入规则、数据集和修复算法（具有一定的迭代次数，是否能够自定义？）

4. 解决较大的联通分量 

如果连接的组件不适合内存，BD使用k****路多级超图划分算法 将其分成k个相等的部分，并在不同的机器上运行。不幸的事，简单地执行这个过程可能导致修复中的不一致和矛盾的选择。此外，它可能在两台机器中独立地修复相同的违规行为，从而引起不必要的修复。
比如[t1](a1, b1, c1), [t2](a1, b2, c1)的数据集（属性为ABC）和两个FD A->B,C->B的FD。
1. 所有数据值全都违反，一共六个，如果计算节点只能放下5个值，那么需要在两个不同的节点上做修复，比如第一个修复属性A上的，修复第二个属性为b2，另外一个修复属性C上的，修复第二个属性为b2，那么久出现了两个变化，而且最终的实例结果不一致。

我们通过讲Master的角色分配给一台机器，其它机器座位Slave的方法解决这个问题。
1. 每一台机器都各自进行修复，但是我们在联合结果时进行额外的测试。对于Master解决的冲突，我们将其标记为不可变，这样可以防止我们多次更改元素。如果Slave提出的变更与涉及Master选择的可能的修复相矛盾，那么Slave的修复被撤销，并且触发新的迭代。因此，算法总是达到一个固定点来产生一个干净的数据集，因为在随后的迭代中更新的不能改变。
2. BD目前使用这种方法提供了两种修复算法：等价类算法和一般的超像素算法。如果与BD的修复界面兼容，用户还可以实现自己的修复算法。

3. 可扩展的等价类算法
   1. 基于等价类的算法首先将所有应该等效的元素组合在一起，然后决定如何为每个组分配值。等价类由形式(t, A)的对组成，其中t是数据单元，A是元素。在数据集D中，t中的每个数据单元单位t和每个元素A具有由等式(t, A)表示的相关等价类。在修复过程中，将唯一的目标值分配给每个等价类E，用targ(E)表示。也就是说，对所有的（t，A）∈E，t[A]具有相同的targ(E)。该算法为每个等价类选择目标值以获取最小总成本的修复。
   2. 接下去将等价类算法扩展为分布式设置，通过将其作为基于map和reduce函数的分布式字计数算法进行建模。然而，与标准的word counting algorithm相反，我们用两个map-reduce序列。
   第一个map函数将每个联通分量的可能的修复程序映射到形式为⟨⟨ccID,value⟩,count⟩。其中key ⟨ccID,value⟩是一个复合键，包含了联通分量ID和可能的修复值。值count表示元素值的频率，初始化为1。
   第一个reduce函数计算共享相同连接组件ID和元素值的键值对的出现次数。它输出形式为⟨⟨ccID,value⟩,count⟩的键值对。要注意的是，如果一个元素存在于多个修复中，我们仅仅对它的值计数一次。
   在第一次map-reduce之后，另一个map函数将reduce函数的输出结果组合成⟨ccID,⟨value,count⟩⟩形式的新键值对。key是联通分量的ID，值是每个元素值的频率。
   最后一个reduce选择要分配给联通分量ccID中所有元素的频率最高的元素值。

6.EXPERIMENTAL STUDY

1. 前言
   1. 我们使用拥有各种规则的真实的或者人造的数据集来评估BD。有以下场景来评估系统并回答以下问题：
   和单个节点设置的baseline系统相比性能如何？
   和最先进的分布式系统相比，它面对不同的数据集大小的性能有多好？
   它面对不同的节点数量，性能有多好？

其抽象性能如何支持各种数据清理任务，例如冲突数据删除？
其不同的技术如何改善性能以及修复的精度如何？

2. 以下数据集： 

TaxA。代表美国的个人税务信息。每行包含一个人的姓名，联系方式和税务信息。对于该数据集，我们使用表3中的FD规则φ1。我们通过以10％的速率向城市和州添加随机文本来引入错误。

TaxB。我们通过在TaxA的Rate属性上添加10％的数值随机错误来生成TaxB。

TPCH。从TPC-H基准数据，我们加入了lineitem和customer表，并在地址上应用了10％的随机错误。

Customer。在重复数据删除实验中，我们使用具有450万行的TPC-H客户端生成具有3倍精确重复数据的表customer1，并且具有5倍精确重复项的customer2。然后，我们在两个关系中随机选择元组总数的20％，并在属性名称和电话上随机编辑它们。
NCVoter。这是一个包含北卡罗来纳州选民信息的真实数据集。我们在名称和手机属性中添加了随机编辑的20％随机重复行。

Healthcare Associated Infections (HAI)。该实际数据集包含医院信息和治疗期间发现的感染的统计测量。

3. 只有一个完整的数据清理系统可以支持**表****3** 中的所有规则： 

NADEEF：支持声明和用户定义的质量规则的开源单节点平台。
PostgreSQL v9.3：由于声明性质量规则可以表示为SQL查询，因此我们还将与PostgreSQL进行比较以进行违规检测。 为了最大限度地利用大型主内存，我们使用pgtune进行配置。

4. 我们还考虑两个并行的数据处理框架 

Shark：这是一个可扩展的数据处理工具，用于快速的数据分析。由于其可扩展性优于现有的分布式SQL引擎，所以我们选择了Shark
Spark SQL v1.0.2：它是Spark v1.0的实验扩展，允许用户使用SQL或HiveQL在Spark上本机运行关系查询。我们选择了这个系统，就像BigDansing一样，它运行在Spark之上。

5. ******在两个不同的设置中运行了实验：** 

使用带有两个64位四核Intel Xeon X5550**（8物理核和16CPU线程）和58GBRAM的Dell Precision T7500的单节点配置
**

使用17台Shuttle SH55J2机器（1名拥有16名worker的主机）的计算集群的多节点设置，该计算机配备了构成星形网络的16GB RAM的Intel i5**处理器。**

2. 单节点实验
   1. 在这些实验中，我们对比BD和NADEEF的清洁的时间，可以看到BD有高度优势，来自主要：
   提供了更精细的粒度抽象，允许用户更有效地指定规则。（原因1）
   以有效的方式执行不平等的规则（使用OCJoin）（原因2）
   另外：NADEEF向底层的DBMS发出了数千个SQL查询用语检测冲突，并且NADEEF无法为1M个数据项运行修复过程。

2. 我们观察到：**整个数据清理过程中，违规检测是最重要的部分** 。 

在1M行 TaxA规则φ1实验中，90%的时间在做违规检测。特别是，就算错误率达到了50%，也就是错误数量极多的时候，违规检测依然主导了清洁过程。
因此BD的优化主要继续关注与违规检测阶段的实验。

3. 总体来说，性能上，小数据集上，PostgreSQL贼快，大数据集上，BD贼快。优势的原因如下： 

BD只读入数据集一次，而PostgreSQL和Shark由于自连接，会读取两次
BD不会产生重复违规，而SQL引擎在比较使用自连接的元组时，例如TaxA和TPCH的FD，会产生重复的冲突。
总结：BD在100k行的所有其他系统快一个数量级。对200k和300k，比baseline系统快至少两个数量级。这种性能优势主要是通过利用baseline系统不支持的不等式连接实现的。

3. 多节点实验
   1. 将BD与Spark SQL和Shark在多节点设置中进行比较。我们还在Hadoop MapReduce之上实现了一个较轻的BD版本，以显示BD独立性w.r.t. 底层框架。我们将TaxA的大小设置为10M，20M和40M rows。
   2. 对于图10a中的等式规则，BigDansing-Spark略快于Spark SQL。尽管BD-Spark和Shark都是在Spark上实现的，但是BD-Spark比Shark高出三个数量级。甚至BigDansing-Hadoop都比Shark好，这是因为Shark不能有效的处理join操作。
   3. 在处理不平等规则的时候，BD相比于baseline系统的性能更加出色了。而且Spark和Shark都不能有效的处理不等式DC。
   4. 在更加的数据集TPCH上测试，Shark已经不能用了，BigDansing-Spark比BigDansing-Hadoop快16到22倍，比Spark SQL快6到8倍（图10（c））。 BigDansing-Spark显着优于Spark SQL，因为它具有较低的I / O复杂性和优化的数据清理物理执行计划。BDH和BDS的差距是内存和磁盘的差距。

4. Scaling BigDansing Out
   1. 大型数据集上，BDSpark的性能优于Spark SQL

5. BigDancing中的去重
   1. UDF无法在Spark SQL中直接实现。
   2. BD支持重复数据删除任务，且效率不错。

6. BigDansing In-Depth
   1. 物理优化
   着重展示了UCrossProduct和OCJoin操作符的性能优势。

2. 抽象优点 

现在研究BD抽象的好处，发现使用完整的BD API运行UDF比仅仅使用Detect快了三个数量级。这清楚地显示了五个逻辑运算符的好处，即使是单节点设置。

3. 可扩展的数据修复 

研究BD使用的修复算法的运行时效率。并行版本比集中式的（如NADEEF）更优，除了错误率非常小以外，对于更高的速率，BD显然更快，因为修复过程中处理的联通分量的数量随着违规数量的增加而增加，从而并行化提高了。当然，BD系统随着违规的数量的增加而好转。

4. 修复的准确率 

用精确度和召回率来评估准确程度，发现DB拥有和NADEEF一样的准确率和召回率。
特别的，即使在同时运行多个规则时修复所有的数据冲突的情况下，BD也只需要与NADEEF相同的迭代次数。
我们还用黑盒和可扩展修复实现来测试BD中的等价类，都得到了类似的结果。
φD中可能的解决方案的搜索空间是巨大的，超图算法使用二次规划来近似φD中的修复。

总的来说，BD实现了与单个节点配置情况下， 相同的修复质量，这通过提供比baseline更好的数据清理运行时和可扩展性来实现。

**7.**相关工作

1. 数据清洗已经是学术界和业内数十年的研究课题。给定一些脏数据集，目标是找到最可能的错误和可能的方式来修复这些错误以获得干净的数据集。在本文中，我们对通过UDF表达可能错误的检测和可能修复的产生的设置感兴趣。
2. 传统的约束，比如FD，CFD，DCs在BD中很容易表达，因此在BD中会检测到这些约束检测到的任何错误。然而，我们的目标不是提出新的数据清洗算法 ，而是提供一个可以使用灵活的基于UDF的抽象来进行数据清理的框架。
3. 业内，IBM，SAP，Oracle等公司主要侧重于使用低级的ETL规则，这些系统不像BD这样可扩展。
4. 当前还有DCs和其他片段（如FD和CFD）的清洁算法，和其他比如FD和CFD的。
5. 另一类修复算法使用机器学习工具清理，包括SCARE和ERACER，还有几个算法试图将用户也纳入清洁过程（众包）。这两个研究领域和BD正交。
6. 比较接近的工作是NADEEF，它是一个通用的数据清洗系统，可能在一个通用的编程界面检测各种数据质量规则的情况。但BD提供了更加丰富的编程接口，以实现高效和可扩展的冲突检测，而且通过planning过程实现了多项优化，也是开创了第一种分布式数据修复方法。
7. SampleClean旨在通过对源数据的小样本执行清理来提高聚合查询的准确性，并专注于以置信区间获得没有bias的查询结果。但事实上，在需要整个输入数据集的传统查询处理中，不能使用SampleClean。
8. 这一段逼逼了一下在分布式系统上coding很枯燥，然后大家可以实现一个声明式的系统。
9. 在数据库社区，很多人在研究如何实现高效的θ连接。研究和低级别的技术不同，比如通过采样来选择分区来最小化磁带访问，如何将任意的连接条件映射到Map-Reduce函数。后面的看不懂了。。
10. Dekdoop使用Hadoop来检测关系数据中的重复，它利用数据阻塞和并行执行来提高性能。Dedoop不支持UDF认证，也不会修复算法。

**8.**总结

1. 总结一下：BD是个快、可扩展的大数据清洗系统，易于使用。

2. 用户使用逻辑运算符来定义执行多个优化时被转换为物理执行计划的规则。

3. BD很强，比baseline牛逼很多，执行时间上提升两个数量级，修复质量很高。

4. 重要的是，BD还是可扩展的，可以在几小时内检测到300GB的违规行为（58G内存，你说什么都对）

5. 有这些未来的方向：
   1. 一个是通过逻辑运算符，就像违规检测那样，这是比较有挑战性的，因为大多数现有的修复算法一般用启发式的方法来找到“最优”修复。
   2. 另一个是利用多个数据质量规则优化的机会。