作业解析-python闭包算法
目录
1. 作业题目 ………………………………………………………………
2. 作业目的……………………………………………………………….
3. 运行效果……………………………………………………………….
4. 实现过程……………………………………………………………….
5. 知识点巩固 …………………………………………………………..
6 知识拓展………………………………………………………………..
7 学习建议………………………………………………………………..
作业辅导解析
LAB_WORKSHEET_WEEK[作业标题]
4th April,2018[日期]
1.作业题目:[Assignment 上面随便复制一点]
- 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.运行效果: [运行结果截图]

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、在后续巩固中可以加强列表的学习,并要学以致用,举一反三。