Cleaning data with Swipe

修复功能依赖的问题是指需要修改输入数据库，以满足所有功能依赖关系并使得与原始数据库的差异最小。输出数据库被称为最优修复。如果允许的修改只有值更新，那么寻找最优修复是NP难问题。寻找最优修复的一个著名方法是构建一个Chase树，其中每个内部节点解决一个功能依赖关系的违反，而叶节点表示修复。这种方法的一个关键性质是，控制Chase树的分支因子可以控制修复质量和计算效率之间的权衡。在本文中，我们探讨了这个想法的一个极端变体，即Chase树只有一条路径。为了构建这个路径，我们首先创建一个属性分区，使得类可以按顺序逐个修复。我们只修复每个类一次，并通过修复依赖关系的顺序来实现。这个原则被称为优先修复，我们提供了一个简单的启发式来确定优先级。属性分区和优先修复的技术被结合在Swipe算法中。对四个真实数据集的实证研究表明，Swipe比基于多序列Chase的方法快一到三个数量级，而修复质量相当或更好。此外，Swipe算法的可扩展性分析表明，Swipe在元组数量增加时具有良好的可扩展性。

本论文旨在解决函数依赖修复问题，即需要修改输入的数据库以满足所有函数依赖关系，且与原始数据库的差异最小。如果允许的修改仅为值更新，则寻找最优修复是NP难的。

本文提出了Swipe算法，通过优先级修复和属性分区的组合来解决函数依赖修复问题。Swipe算法构建一个仅有一条路径的Chase树，通过属性分区将类逐个修复，优先级修复确定修复顺序。相比于现有的多序列Chase算法，Swipe算法可以提高一到三个数量级的计算效率，且修复质量相当甚至更好。

本文使用了四个真实数据集进行实验，Swipe算法的结果表明其计算效率比现有算法更高，且修复质量相当甚至更好。同时，Swipe算法的可扩展性分析表明，其可以处理逐渐增加的元组数量。值得深入研究的是Swipe算法的优先级修复和属性分区的组合思路，以及如何将其应用到其他数据库问题中。

在函数依赖修复领域，还有许多相关研究。例如，"A Comprehensive Study of Data Repair Approaches"，"Functional Dependency Preservation in Database Schema Refactoring"等。