Write a function min covers that takes two parameters, a schema and a set of functional dependencies, and returns all minimal covers reachable from the set of functional dependencies. The set of results is represented as a list of pairs of lists. Your report consists of up to one page explanation of the algorithm you devise to compute all minimal covers. For example, min_covers([’A’, ’B’, ’C’], [[[’A’, ’B’], [’C’]],[[’A’], [’B’]], [[’B’], [’A’]]]) = [[[[’A’], [’C’]], [[’A’], [’B’]], [[’B’], [’A’]]], [[[’B’], [’C’]], [[’A’], [’B’]], [[’B’], [’A’]]] ]
Write a function all min covers that takes two parameters, a schema and a set of functional dependencies, and returns all minimal covers. The set of results is represented as a list of pairs of lists. Your report consists of up to one page explanation of the algorithm you devise to compute all minimal covers.

2.作业目的：[作业的目的 1-3 个点都可以]

1、掌握求解函数依赖集的闭包算法；

2、掌握关系规范化的最小函数依赖集的求解方法；

3、掌握 Python 操作列表的使用方法。

3.运行效果： [运行结果截图]

1. 对于 R = [‘A’, ‘B’, ‘C’]，FD = [[[‘A’, ‘B’], [‘C’]],[[‘A’], [‘B’]], [[‘B’], [‘A’]]]， min_covers 结果为： [[[[‘A’], [‘C’]], [[‘A’], [‘B’]], [[‘B’], [‘A’]]], [[[‘B’], [‘C’]], [[‘A’], [‘B’]], [[‘B’], [‘A’]]]] all_min_covers 结果为： [[[[‘A’], [‘B’]], [[‘B’], [‘A’]], [[‘A’], [‘C’]]], [[[‘A’], [‘B’]], [[‘B’], [‘A’]], [[‘B’], [‘C’]]]] 2. 对于 R = [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]，FD = [[[‘A’, ‘B’],[‘C’]], [[‘D’],[‘D’, ‘B’]], [[‘B’],[‘E’]], [[‘E’],[‘D’]], [[‘A’, ‘B’, ‘D’],[‘A’, ‘B’, ‘C’, ‘D’]]]， min_covers 结果为： [[[[‘D’], [‘B’]], [[‘B’], [‘E’]], [[‘E’], [‘D’]], [[‘A’, ‘D’], [‘C’]]]] all_min_covers 结果为： [[[[‘B’], [‘E’]], [[‘D’], [‘E’]], [[‘E’], [‘D’]], [[‘D’], [‘B’]], [[‘A’, ‘B’, ‘D’, ‘E’], [‘C’]]], [[[‘B’], [‘E’]], [[‘D’], [‘E’]], [[‘E’], [‘D’]], [[‘E’], [‘B’]], [[‘A’, ‘B’, ‘D’, ‘E’], [‘C’]]], [[[‘B’], [‘E’]], [[‘D’], [‘E’]], [[‘E’], [‘D’]], [[‘D’, ‘E’], [‘B’]], [[‘A’, ‘B’, ‘D’], [‘C’]]], [[[‘B’], [‘E’]], [[‘D’], [‘E’]], [[‘E’], [‘D’]], [[‘D’, ‘E’], [‘B’]], [[‘A’, ‘B’, ‘D’], [‘C’]]], [[[‘B’], [‘E’]], [[‘D’], [‘E’]], [[‘E’], [‘D’]], [[‘D’, ‘E’], [‘B’]], [[‘A’, ‘B’, ‘E’], [‘C’]]], [[[‘B’], [‘E’]], [[‘D’], [‘E’]], [[‘E’], [‘D’]], [[‘D’, ‘E’], [‘B’]], [[‘A’, ‘E’, ‘D’], [‘C’]]]]

4.实现过程：[部分核心代码截图, 截图部分的代码 prefer 中英文注释]

核心代码如下图所示：

参考源码图 1.1

参考源码图 1.2

本次作业主要通过以下步骤实现：

对于问题（b），求解方法如下：输入：单属性列表 R，一个函数依赖集 FD

输出：FD 的所有等价的最小函数依赖集

步骤：

① 用分解法则，使 F 中的任何一个函数依赖的右部仅含有一个属性；

② 去掉多余的函数依赖：从第一个函数依赖 X→Y 开始将其从 F 中去掉，然后在剩下的函数依赖中求 X 的闭包 X+，看 X+是否包含 Y，若是，则去

掉 X→Y；否则不能去掉，依次做下去。直到找不到冗余的函数依赖；

③ 去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖。例如 XY→A，若要判 Y 为多余的，则以 X→A 代替 XY→A 是否等价？若 A(X)+，则 Y 是多余属性，可以去掉。

对于问题（c），求解方法如下：输入：单属性列表 R，一个函数依赖集 FD

输出：FD 的所有等价的最小函数依赖集

步骤：

① 对于单属性列表 R 的所有子集，计算每个子集的闭包；

② 对于每个子集的闭包，计算闭包的子集，作为新的函数依赖的右边部分，与左边部分的属性构成新的所有函数依赖集 FD+；

③ 对于新的所有函数依赖集 FD+，用（b）中的方法求得所有等价的最小函数依赖集。

5.知识点巩固：[相关知识点 1-3 点总结]

1、等价和覆盖

定义：关系模式 R<U,F>上的两个依赖集 F 和 G，如果 F+=G+，则称 F 和 G 是等价的，记做 F≡G。若 F≡G，则称 G 是 F 的一个覆盖，反之亦然。两个等价的函数依赖集在表达能力上是完全相同的。

2、最小函数依赖集

定义：如果函数依赖集 F 满足下列条件，则称 F 为最小函数依赖集或最小覆盖。

① F 中的任何一个函数依赖的右部仅含有一个属性；

② F 中不存在这样一个函数依赖 X→A，使得 F 与 F-{X→A}等价；

③ F 中不存在这样一个函数依赖 X→A，X 有真子集 Z 使得 F-{X→A}∪

{Z→A}与 F 等价。

6.知识拓展：[拓展知识点 1-3 点总结]

1、函数依赖的闭包

定义：若 F 为关系模式 R(U)的函数依赖集，我们把 F 以及所有被 F 逻辑蕴涵的函数依赖的集合称为 F 的闭包，记为 F+。即：F+={X→Y|X→Y∈F∨“应用 Armstong 公理从 F 中导出的任何 X→Y”}

△ F 包含于 F+，如果 F=F+，则 F 为函数依赖的一个完备集。

△ 规定：若 X 为 U 的子集，X→Φ 属于 F+。

2、求解函数依赖集的闭包

关系模式 R<U,F>若有 n 个属性，则在模式 R 上可能成立的函数依赖有 4n 个，其中 n 个属性中组合成 X 有 2n 个,组合成 Y 有 2n 个。则可以首先求出各个单一属性的闭包，这样的话，我们就得到了两组属性（泛化地说），将左边看成

一组，将右边看成另一组，然后对左边的属性集进行排列组合，产生所有的可能情况，然后对左边的每个组合相对应的右边的属性的集合也进行排列组合，最后得出所有的函数依赖，也就是要求的函数依赖集的闭包。

7.学习建议：[根据学习 IT 的经验，写 1-3 点, prefer 3 个点]

1、Python 对列表的操作是最基本的，要熟练使用； 2、本次作业涉及到闭包、函数依赖集等知识，需要将理论知识转化为代码； 3、在后续巩固中可以加强列表的学习，并要学以致用，举一反三。

作业解析-python闭包算法

作业解析-python闭包算法

目录

2. 作业目的……………………………………………………………….

3. 运行效果……………………………………………………………….

4. 实现过程……………………………………………………………….

5. 知识点巩固 …………………………………………………………..

6 知识拓展………………………………………………………………..

7 学习建议………………………………………………………………..

作业辅导解析