作业解析-python闭包算法

目录

1. 作业题目 ………………………………………………………………

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

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

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

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

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

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

作业辅导解析

LAB_WORKSHEET_WEEK[作业标题]

4th April,2018[日期]

1.作业题目:[Assignment 上面随便复制一点]

  1. 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’]]] ]
  2. 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.运行效果: [运行结果截图]

image 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 中英文 注释]

核心代码如下图所示:

image

参考源码图 1.1

image

参考源码图 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→AX 有真子集 Z 使得 F-{X→A}

{Z→A}F 等价。

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

1、函数依赖的闭包

定义:若 F 为关系模式 R(U)的函数依赖集,我们把 F 以及所有被 F 逻辑蕴 涵的函数依赖的集合称为 F 的闭包,记为 F+。 即:F+={X→Y|X→YF应用 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 个点]

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