摘要

1. 函数依赖关系

所有算法的目标相同，即发现给定数据集中所有最小的、非平凡的函数依赖关系。

分析：怎么理解最小，非平凡

贡献：我们按其主要概念对七种FD算法进行了分类，并对最新的发展进行了概述。我们重新审视所有的算法，并为它们的实际实现提供额外的描述，因为它们的原始出版物很少。我们比较了不同数据集的算法，并评估运行时和内存使用情况。从我们的实验结果，我们得出了具体的建议，何时使用哪种算法。我们还将所有实施、数据和评估框架在线提供

结构：第2节给出了FD发现的概述，讨论了常见概念、替代方法以及我们对发现算法的分类。第3节描述了算法的实现。第4节给出了我们的评估结果，第5节总结了每种发现算法的优缺点

2. FD算法概述

2.1 准备工作

FD的定义：X->A ；如果X的子集并不确定A，则函数依赖性X→A是最小的。如果A不是X的子集，则它是非平凡的。为了发现数据集中的所有函数依赖性，只要发现所有最小的、非平凡的FDs就足够了，因为所有的左侧（lhs）子集都是非依赖性的，而所有的左侧（lhs）超集都是逻辑推理的依赖性。

子集和超集：

2.2 分类

为了更好地理解这七种函数依赖性发现算法及其性质，我们将它们分为三类。第3节以下是对每种算法的详细讨论。

2.3 其他算法

3. 七种FD发现算法

3.1 TANE

有参考资料

基于三个概念：

• 分区细分（partition refinement）检查函数依赖是否成立
• 先验-基因（apriori-gen）确保找到所有且只有最小的函数依赖被发现
• 剪枝规则（pruning rules）动态缩小搜索空间
  与所有的格遍历算法一样，TANE将搜索空间建模为Hasse图，如第2.1节所述。

2.1节讲了什么

图1描述了关系式r ={A,B,C}的Hasse图。

晶格被划分为级别，其中Li级别包含大小为i的所有属性组合。TANE没有开始计算整个晶格，而是从第1级（大小为1 属性集）开始，然后逐级向上移动（示例中的粗体）。

In each level Li, the algorithm tests all attribute combinations X ∈ Li for the functional dependency X A → A for all A ∈ X.

X A表示差集

在每一级别中Li中算法对X∈Li的所有的属性组合进行测试，进行函数依赖X A→A的测试

如果一个测试交付一个新的函数依赖项，那么 Tane 会使用一组剪枝规则修正所有已发现 FD 的超集。当向上移动到下一个级别时，apriorigen 函数[2]只计算前一个级别中尚未裁剪的属性组合。

请注意，图1显示了一个示例，我们将在本节的最后更详细地描述这个示例。

TANE’s search space pruning is based on the fact that for a complete result only minimal functional dependencies need be discovered. To prune efficiently, the algorithm stores a set of right-hand-side candidates C+(X) for each attribute combination X. The set C+(X) = {A ∈ R | ∀B ∈ X : X {A, B} → B does not hold} contains all attributes that may still depend on set X. C+(X) is used in the following three pruning rules:

TANE’s的搜索空间修剪是基于这样一个事实，即对于一个完整的结果，只需要发现最小的函数依赖性。为了有效地修剪，该算法为每个属性组合X存储一组右侧候选对象C+(X)。

集合C+(X)={A∈R|∀B∈X：X {A，B}→B不成立}, 集合C+(X)包含仍然可能依赖于集合X的所有属性

问题：C+（X）为什么包含的是可能依赖于X的所有属性？ 对C+（X）这个集合的概念理解起来有点困难

以下三个修剪规则中使用了C+(X)：

• 最小性剪枝：如果一个函数依赖项XA→A成立，则可以从C+(X)中删除A和所有B∈C+(X)X。换句话说，如果X包含FD XA→A，则任何FD X→B都不能是最小值，因为A使X成为非最小值。请注意，此定义还包括A=B。

  问题：为什么要删除这里的B？ 如果存在 XA→A说明 X→ A不是最小的，为啥说明X→B也不是最小的。

• 右侧剪枝：如果C+(X)=∅，则可以从格中修剪属性组合X，因为没有最小函数依赖性的右侧候选对象。

• 键剪枝：如果属性组合X是键，可以从格中修剪。键X是一种属性组合，它确定关系R中的所有其他属性RX。因此，X的所有超集都是超键，根据定义是非最小的。

  理解：这里说X的所有超码需要剪到候选码

3.2 FUN

有参考资料

3.3 FD Mine

3.4 DFD

3.5 Dep-Miner

3.6 FastFDs

3.7 FDEP

4. 评价

4.1 实验装置

4.2 行可扩展性实验

4.3 列可扩展性实验

4.4 对不同数据集的实验

4.5 内存实验

4.6 实验结果外推

5. 总结

最后

以上就是欣喜斑马为你收集整理的【文献翻译】七种FD发现算法（未完成）摘要1. 函数依赖关系2. FD算法概述3. 七种FD发现算法4. 评价5. 总结的全部内容，希望文章能够帮你解决【文献翻译】七种FD发现算法（未完成）摘要1. 函数依赖关系2. FD算法概述3. 七种FD发现算法4. 评价5. 总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。