第13讲模式分解ppt课件.ppt

《第13讲模式分解ppt课件.ppt》由会员分享，可在线阅读，更多相关《第13讲模式分解ppt课件.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5章 关系模式的规范化设计模式分解模式分解第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物2关系模式的规范化设计关系模式的规范化设计 所要解决的问题什么是什么是“好好”的关系数据模式的关系数据模式如何评价一个好的关系数据模式如何评价一个好的关系数据模式如何设计一个如何设计一个“好好”的关系数据模式的关系数据模式第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物3

2、关系模式的规范化设计关系模式的规范化设计 主要内容关系模式的设计问题关系模式的设计问题关系模式规范化的基本概念和理论关系模式规范化的基本概念和理论关系模式分解的理论基础和算法关系模式分解的理论基础和算法第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物4回顾回顾1NF2NF3NFBCNF去除非主属性对于候选键的部分函数依赖去除非主属性对于候选键的部分函数依赖去除非主属性对于去除非主属性对于候选候选键的传递函数依赖键的传递函数依赖去除主属性对于去除主属性对于候选候选键的部分和传递函

3、数依赖键的部分和传递函数依赖去除不被候选键所蕴涵的非平凡的多值依赖去除不被候选键所蕴涵的非平凡的多值依赖4NF消除消除决定决定因素因素非码非码的非的非平凡平凡函数函数依赖依赖第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物5Armstrong公理系统 逻辑蕴涵逻辑蕴涵 Armstrong公理系统推理规则公理系统推理规则 FD的逻辑蕴涵的逻辑蕴涵 函数依赖集函数依赖集F 的闭包的闭包F+ 属性集闭包属性集闭包 函数依赖集等价和最小函数依赖集函数依赖集等价和最小函数依赖集 候选码及

4、其求解方法候选码及其求解方法 回顾回顾 第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物6主要内容 模式分解的概念模式分解的概念 分解的无损连接性和保持函数依赖性分解的无损连接性和保持函数依赖性 模式分解算法模式分解算法 模式分解模式分解第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物7分解的概念 设有一关系模式设有一关系模式R（U,F），若用一关系），若用一关

5、系模式的集合模式的集合= R1（U1,F1），），R2（U2,F2），Rn（Un,Fn） 来取代，其中来取代，其中U=Ui，并且没有并且没有UiUj，1i, jn，Fi是是F在在Ui上的上的投投影影。则关系模式的集合。则关系模式的集合为为R的一个分解的一个分解 = R1，R2，Rn模式分解的概念模式分解的概念第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物8分解的概念 F在在Ui上的投影上的投影 Fi =XY | XYF+XY Ui 模式分解的概念模式分解的概念思考：思考： 设

6、有关系模式设有关系模式R（A，B，C，D），），F是是R上成立上成立的的FD集集F=ABC，DB ，则，则 F在模式在模式ACD上的投上的投影为影为_；F在模式在模式AC上的投影为上的投影为_。 ADC 空空第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物9分解的概念 模式分解的概念模式分解的概念【例】R(编号，连队，连长，科目，成绩), F= 编号连队，连队连长，(编号，科目)成绩 【例】R(学生学号，学生姓名，所在系，系主任，课程名称，成绩 ， F=学生学号学生姓名，学生学

7、号所在系，所在系系主任，（学生学号，课程名称）成绩第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物10分解的概念 模式分解的概念模式分解的概念1NF2NF3NF去除非主属性对于键的部分函数依赖去除非主属性对于键的部分函数依赖去除非主属性对于键的传递函数依赖去除非主属性对于键的传递函数依赖R R（学生学号学生学号，学生姓名，所在系，系主任，学生姓名，所在系，系主任，课程名称课程名称，成绩，成绩 ） R1（学生学号学生学号,课程名称课程名称,成绩） R2（学生学号学生学号，学生姓名

8、，学生姓名， 所在系，系主任所在系，系主任）R1（学生学号学生学号,课程名称课程名称,成绩） R3（学生学号学生学号，学生姓名，学生姓名， 所在系所在系）R4（所在系所在系，系主任，系主任）第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物11分解的概念 模式分解的概念模式分解的概念R（ 学生学号学生学号，学生姓名，所在系，系主任，学生姓名，所在系，系主任，课程课程名称名称，成绩，成绩 学生学号学生学号学生姓名，学生学号学生姓名，学生学号所所在系，所在系在系，所在系系主任，（学生

9、学号，课程名称）系主任，（学生学号，课程名称）成绩成绩 1= R1 (学生学号，课程名称学生学号，课程名称，成绩，成绩, （学生学号，课程（学生学号，课程名称）名称）成绩成绩) , R3 (学生学号学生学号，学生姓名，所在系，学生姓名，所在系, 学生学号学生学号学生学生姓名，学生学号姓名，学生学号所在系所在系) , R4 (所在系所在系，系主任，系主任, 所在系所在系系主任系主任)第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物12分解的概念 模式分解的概念模式分解的概念R（

10、学生学号学生学号，学生姓名，所在系，系主任，学生姓名，所在系，系主任，课程名课程名称称，成绩，成绩 学生学号学生学号学生姓名，学生学号学生姓名，学生学号所在系，所在系，所在系所在系系主任，（学生学号，课程名称）系主任，（学生学号，课程名称）成绩成绩 2=R1（学生学号）（学生学号）, R2（学生姓名）（学生姓名）, R3（所在系）（所在系）, R4（系主任）（系主任）, R5（课程名称）（课程名称）, R6（成绩）（成绩） U=Ui，并且没有，并且没有UiUj，1i， jn Fi是是F在在Ui上的投影不存在非平凡的函数依赖。上的投影不存在非平凡的函数依赖。不具有无损连接性不具有无损连接性第第1

11、3讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物13分解的概念 模式分解的概念模式分解的概念R（ 学生学号学生学号，学生姓名，所在系，系主任，学生姓名，所在系，系主任，课程名称课程名称，成绩成绩 学生学号学生学号学生姓名，学生学号学生姓名，学生学号所在系，所在所在系，所在系系系主任，（学生学号，课程名称）系主任，（学生学号，课程名称）成绩成绩 3= R1 (学生学号，课程名称学生学号，课程名称，成绩，成绩, （学生学号，课程）（学生学号，课程）成绩成绩) , R2 (学生学号学生学号

12、，学生姓名，所在系，学生姓名，所在系, 学生学号学生学号学生姓学生姓名，学生学号名，学生学号所在系所在系) , R3 (学生学号学生学号，系主任，系主任, 学生学号学生学号系主任系主任) U=Ui，并且没有，并且没有UiUj，1i, jn Fi是是F在在Ui上的投影。上的投影。没有保持函数依赖没有保持函数依赖第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物14分解的概念 一个关系模式的分解并不是唯一的。一个关系模式的分解并不是唯一的。 理想的分解应该是既具有无损连接性又保持理想

13、的分解应该是既具有无损连接性又保持函数依赖，这样的分解是等价分解。函数依赖，这样的分解是等价分解。 等价分解等价分解分解具有无损连接性，即数据等价分解具有无损连接性，即数据等价分解保持函数依赖，即语义等价分解保持函数依赖，即语义等价分解既具有无损连接性又保持函数依赖，即数据分解既具有无损连接性又保持函数依赖，即数据等价并且语义等价等价并且语义等价模式分解的概念模式分解的概念第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物15无损连接分解无损连接分解 无损连接分解 设设= R1（

14、U1,F1），），Rk（Uk,Fk）是是R（U,F）的一个分解，）的一个分解，r是是R（U,F）的一个关系，）的一个关系，则则 Ri ( (r) )=t.Ui|tr为为r在子模式在子模式Ri上的投影，上的投影， m( (r) )=R1( (r) ) R2( (r) ) Rk( (r) )是是r在在中各关系模式上投影的连接。中各关系模式上投影的连接。 若对若对R的任何一个关系的任何一个关系r均有均有r= m( (r) )成成立，则称立，则称分解分解具有无损连接性具有无损连接性。分解是无损分解第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢

15、？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物16 算法：检验一个分解是否是无损分解 输入：输入： 关系模式关系模式R（U，F），）， U=A1,A2 ,An； R上的分解上的分解= R1（U1,F1）, R2（U2,F2）, ,Rk（Uk,Fk） 。 设设F是最小函数依赖集。是最小函数依赖集。 输出：输出： 判断判断相对于相对于F是否具有无损分解特性。是否具有无损分解特性。无损连接分解无损连接分解第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物17无损连接分解无

16、损连接分解 检验一个分解是否无损的算法 步骤步骤A1AnR1（U1,F1） a1 ：Rk（Uk,Fk）bkn1 1）建立一张建立一张k行行n列的表，列的表，每行对应分解中的一个关每行对应分解中的一个关系模式系模式Ri，每列对应一个，每列对应一个属性属性Aj，若属性，若属性AjUi，则在则在i行行j列处填列处填aj，否则，否则填填bij。A1U1An Uk第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物18无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F

17、=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b23b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b53b54a5初始状态1 1）建立一张建立一张k行行n列的表，列的表，每行对应分解中的一个关每行对应分解中的一个关系模式系模式Ri，每列对应一个，每列对应一个属性属性Aj，若属性，若属性AjUi，则在则在i行行j列处填列处填aj，否则，否则填填bij。第第13讲

18、讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物19无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b23b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b53b54a5初始状态2 2

19、）把表格看成模式）把表格看成模式R R的一个关系，反复检的一个关系，反复检查查F F中的每个函数依赖中的每个函数依赖在表格中是成立，若在表格中是成立，若不成立，则修改表格不成立，则修改表格中的值。中的值。第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物20无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。

20、ABCDER1(AD)a1b12 b13 a4b15R2(AB)a1a2b23 b24 b25R3(BE)b31a2b33 b34 a5R4(CDE)b41b42 a3a4a5R5(AE)a1b52 b53 b54 a5初始状态2 2）对每一形如对每一形如XY 的的FD做如下做如下操作：操作： 检查检查X中的属性所对应的列，找中的属性所对应的列，找出出X相等的行，将这些行中对应的相等的行，将这些行中对应的Y中的属性列所对应的符号改为一中的属性列所对应的符号改为一致。致。即若其中之一为即若其中之一为aj，则都改成，则都改成aj；否则，否则，将其都改成这些列中行将其都改成这些列中行号最小的符号号最

21、小的符号bij。对F的一次扫描第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物21无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b23b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)

22、a1b52b53b54a5AC第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物22无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)

23、a1b52b13b54a5AC第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物23无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)

24、a1b52b13b54a5ACBC第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物24无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13b24b25R3(BE)b31a2b13b34a5R4(CDE)b41b42a3a4a5R5(A

25、E)a1b52b13b54a5ACBC第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物25无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13b24b25R3(BE)b31a2b13b34a5R4(CDE)b41b42a3a4a5R5

26、(AE)a1b52b13b54a5ACBCCD第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物26无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。 =R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13a4b25R3(BE)b31a2b13a4a5R4(CDE)b41b42a3a4a

27、5R5(AE)a1b52b13a4a5ACBCCD第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物27无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13a4b25R3(BE)b31a2b13a4a5R4(CDE)b41b42a3a4

28、a5R5(AE)a1b52b13a4a5ACBCCDDEC第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物28无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。 =R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12a3a4b15R2(AB)a1a2a3a4b25R3(BE)b31a2a3a4a5R4(CDE)b41b42a3

29、a4a5R5(AE)a1b52a3a4a5ACBCCDDEC第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物29无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12a3a4b15R2(AB)a1a2a3a4b25R3(BE)b31a2a3a4a5R4(CDE)b41b42a3

30、a4a5R5(AE)a1b52a3a4a5ACBCCDDECCEA第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物30无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12a3a4b15R2(AB)a1a2a3a4b25R3(BE)a1a2a3a4a5R4(CDE)a1b42a

31、3a4a5R5(AE)a1b52a3a4a5ACBCCDDECCEA第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物31无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。 =R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1（AD）a1b12a3a4b15R2（AB）a1a2a3a4b25R3（BE）a1a2 a3 a4 a5R4（CDE）a

32、1b42a3a4a5R5（AE）a1b52a3a4a5ACBCCDDECCEA第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物32无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(BE) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13a4b25R3(BE)a1a2 a3 a4 a5R4

33、(CDE)a1b42a3a4a5R5(AE)a1b52a3a4a53 3）若表有变化，则返）若表有变化，则返回步骤回步骤2)2)，否则算法，否则算法终止。终止。 若某次修改后，有若某次修改后，有一行全为一行全为a a1 1,a,a2 2, ,a,an n，则算法结束。则算法结束。第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物33无损连接分解无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F=AC，BC，CD，DEC，CEA。=R1(AD)，R2(AB) ，R3(B

34、E) ，R4(CDE) ，R5(AE)是R的一个分解。试判断是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13a4b25R3(BE)a1a2 a3 a4 a5R4(CDE)a1b42a3a4a5R5(AE)a1b52a3a4a5定理：定理： 为无损连接分解的充为无损连接分解的充分必要条件是算法终止分必要条件是算法终止时，表中有一行为时，表中有一行为a1,a2,an。第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物34 判断一个关系模式分解

35、成两个关系模式是否为无损分解的方法定理：定理： 设设=R1( (U1) )，R2( (U2) )是是R( (U) )的一个分解，的一个分解，则则为无损分解的充分必要条件为为无损分解的充分必要条件为 （U1U2）（U1-U2）F+ 或或 （U1U2）（U2-U1）F+ 无损连接分解无损连接分解第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物35无损连接分解无损连接分解证明：用检验分解无损算法构造的如下初始表。表中a和b的下标都已省略充分性充分性 因为（因为（U1U2）（U1-U2

36、），则算法），则算法8-2终止时终止时，对应于，对应于( (U1-U2) )的的bbb全为全为a，因此，因此，=R1( (U1) )，R2( (U2) )是是R（U）的一个无损连接分解。）的一个无损连接分解。必要性必要性 若若=R1( (U1) )，R2( (U2) )是是R（U）的一个无损连）的一个无损连接分解，则算法终止时，表中必有一行全为接分解，则算法终止时，表中必有一行全为a，假设，假设R1行行全为全为a，则（，则（U1-U2）所对应的元素都应变为）所对应的元素都应变为a。由于在。由于在表中，只有（表中，只有（U1U2）所对应的列的元素相同。设）所对应的列的元素相同。设U1-U2中有一

37、个属性中有一个属性Ai，则根据算法将，则根据算法将Ai所对应的元素都改所对应的元素都改为为a，则必有，则必有SAi F+，且，且S （U1U2）。根据自反律）。根据自反律有（有（U1U2）S；根据传递律有（；根据传递律有（U1U2）Ai，即，即Ai ( (U1U2) )+。所以（。所以（U1-U2） ( (U1U2) )+ 即（即（U1U2） ( (U1U2) )是是( (U1U2) )所对应的元素都变为所对应的元素都变为a的必要条件。的必要条件。U1U2U1U2U2U1R1aaaaaabbbR2aaabbbaaa-第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把

38、它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物36【例5-13】 设有关系模式R（U，F），U=A,B,C,D,E，F=A BC，CDE，B D，E A 。 R的两个分解为1= R1(A,B,C)，R2(A,D,E)，2=R1(A,B,C)，R2(C,D,E)。试判断1、2是否为无损分解。无损连接分解无损连接分解解：对于分解对于分解1= R1（A,B,C），），R2（A,D,E） 因为因为U1U2=A，U1-U2=BC，且，且A BCF 所以所以U1U2U1-U2，1为无损分解。为无损分解。 对于分解对于分解2= R1（A,B,C），），R2（C,D,

39、E） 因为因为U1U2=C，U1-U2=AB，U2-U1=DE， 且且C AB F+ ，C DE F+ （如何来判断？）（如何来判断？） 即即U1U2U1-U2 F+ 或或U1U2U2-U1 F+， 所以所以2为有损分解。为有损分解。第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物37保持函数依赖分解保持函数依赖分解 保持函数依赖 对于关系模式对于关系模式R（U,F），设），设= R1（U1,F1），），R2（U2,F2）,Rn（Un,Fn） 是是R的一个分解，的一个分解，若若

40、F+=(Fi)+，则称分解，则称分解保持函数依赖。保持函数依赖。 引理5.3 F+=G+的充分必要条件是FG+且G F+判断分解是否保持函数依赖的方法： 令G=Fi，即只需判断FG+且GF+是否成立。而要判定FG+或GF+ ，只需逐一对F或G中的函数依赖XY考察Y是否属于XG 或X就行了。第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物38分解的保持函数依赖性分解的保持函数依赖性 【例】 设关系模式R(ABCD)，F=AB，BC，CD，DA，试判断分解=R1(AB)，R2(BC

41、)，R3(CD)是否保持函数依赖。解答：解答：1）要先根据分解的定义，确定分解后的函数依赖，然后）要先根据分解的定义，确定分解后的函数依赖，然后再加以判断。利用再加以判断。利用Armstrong公理的传递律，可将公理的传递律，可将分解分解为为= R1(A,B，AB， BA), R2(B,C，BC， CB), R3(C,D，CD， DC)第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物39分解的保持函数依赖性分解的保持函数依赖性 【例】 设关系模式R(ABCD)，F=AB，BC，

42、CD，DA，试判断分解 =R1(AB)，R2(BC)，R3(CD)是否保持函数依赖。解答：解答： 2）判断）判断DA是否为是否为G所覆盖即可所覆盖即可 G= AB，BA ，BC，CB ，CD ，DC 求得求得D=A，B，C，D 因为因为A D ，所以，所以DA G+，故，故保持函数依赖。保持函数依赖。第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物40模式分解算法模式分解算法 关系模式的规范化就是将低一级的关系模式分解为若干高一级的范式。 对数据库应用设计而言，违反数据等价或依

43、赖等价的分解很难说是一个好的模式设计。 在函数依赖范畴内，希望分解的结果能达到BCNF，并且能保持无损连接性和函数依赖性。 第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物41模式分解算法模式分解算法 这三个目标有时不能同时满足，一般只能做到如下几点： 若分解保持函数依赖，那么模式总可以分解若分解保持函数依赖，那么模式总可以分解到到3NF，但不一定能达到，但不一定能达到BCNF； 若分解具有无损连接性，那么模式一定能分若分解具有无损连接性，那么模式一定能分解到解到BCNF； 若

44、分解既保持函数依赖，又具有无损连接性若分解既保持函数依赖，又具有无损连接性，那么模式可以分解到，那么模式可以分解到3NF，但不一定能达到，但不一定能达到BCNF。第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物42模式分解算法模式分解算法低一级范式高一级范式分解保持函数依赖无损连接保持函数依赖无损连接3NF不一定BCNFBCNF 关于模式分解的几个重要事实：第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉

45、快，证实我的猜测没有错：表里边有一个活的生物43模式分解算法模式分解算法 数据库设计者在设计关系数据库时，应权衡利弊，尽可能使数据库模式保持最好的特性。 一般尽可能设计成一般尽可能设计成BCNF模式集；模式集； 如果设计成如果设计成BCNF模式集达不到保持函数依赖模式集达不到保持函数依赖的特性，那么只能降低要求，设计成的特性，那么只能降低要求，设计成3NF模式模式集，以求达到保持依赖和无损分解的特性。集，以求达到保持依赖和无损分解的特性。第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个

46、活的生物44模式分解算法模式分解算法 分解关系模式为满足3NF的一个无损且保持函数依赖的分解算法输入：关系模式输入：关系模式R（U，F）输出：输出：R的一个具有无损连接性且保持函的一个具有无损连接性且保持函数依赖的满足数依赖的满足3NF的分解的分解第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物45模式分解算法模式分解算法 分解关系模式为满足3NF的一个无损且保持函数依赖的分解算法1）求）求F的最小覆盖的最小覆盖Fm，令，令F= Fm。2）若有）若有XAF，且，且XA=U，输出

47、，输出=R，算法结束。，算法结束。3）对）对F按具有相同左部的原则分组，即按具有相同左部的原则分组，即F中所有形如中所有形如XA1,XA2,，XAn的函数依赖为一组。每一分组的函数依赖为一组。每一分组中包含的函数依赖子集中包含的函数依赖子集Fi所涉及的全部属性组成一个属所涉及的全部属性组成一个属性集性集Ui。若。若UiUj（ij）就去掉）就去掉Ui。4）将）将R中不在中不在F中出现的属性，单独构成一属性集中出现的属性，单独构成一属性集Ui。第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一

48、个活的生物46模式分解算法模式分解算法 分解关系模式为满足3NF的一个无损且保持函数依赖的分解算法5）将）将Ui及及F在在Ui上的投影上的投影Fi构成一个关系模式构成一个关系模式Ri( (Ui,Fi) )，由于由于F是最小函数依赖集，是最小函数依赖集，Ri( (Ui,Fi) )一定是属于以一定是属于以X为候为候选键的选键的3NF。并且。并且Fi一定被一定被Fi所包含，因此各关系模式所包含，因此各关系模式Ri( (Ui,Fi) ) 组成的分解组成的分解是保持函数依赖的。是保持函数依赖的。 6）若某个若某个Ui中已包含中已包含R中的候选键，则该分解也就具有无中的候选键，则该分解也就具有无损连接性。

49、损连接性。若若Ui中均不包含中均不包含R中的候选键，则在分解中的候选键，则在分解的的结果上再并入一个关系模式结果上再并入一个关系模式Rk( (K,FK) )，其中，其中K为为R的某一的某一候选键，候选键，FK为为F在在K上的投影。上的投影。 第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物47模式分解算法模式分解算法【例】关系模式R（U，F），其中U= E，G，H，I，J ，F= EI，JI，IG，GHI，IHE ，将R分解为3NF，并使之具有无损连接性和保持函数依赖特性。解答

50、：解答：（1）F已为最小函数依赖集。已为最小函数依赖集。（2）没有类似）没有类似XAF，且，且XA=U的函数依赖。的函数依赖。（3）对）对F按具有相同左部的原则分组，得到每组所对应的属按具有相同左部的原则分组，得到每组所对应的属性集性集U1= EI、U2= IJ、U3= GI、U4= GHI、U5= EHI。因为。因为U1 U5、U3 U4，所以去掉，所以去掉U1、U3。（4）R中的所有属性均在中的所有属性均在F中出现。中出现。第第13讲讲 模式分解模式分解我吓了一跳，蝎子是多么丑恶和恐怖的东西，为什么把它放在这样一个美丽的世界里呢？但是我也感到愉快，证实我的猜测没有错：表里边有一个活的生物4