第13讲模式分解

第5章关系模式的规范化设计——模式分解第13讲模式分解2关系模式的规范化设计•所要解决的问题–什么是“好”的关系数据模式–如何评价一个好的关系数据模式–如何设计一个“好”的关系数据模式第13讲模式分解3关系模式的规范化设计•主要内容–关系模式的设计问题–关系模式规范化的基本概念和理论–关系模式分解的理论基础和算法第13讲模式分解4回顾1NF2NF3NFBCNF去除非主属性对于候选键的部分函数依赖去除非主属性对于候选键的传递函数依赖去除主属性对于候选键的部分和传递函数依赖去除不被候选键所蕴涵的非平凡的多值依赖4NF－－－－消除决定因素非码的非平凡函数依赖第13讲模式分解5•Armstrong公理系统–逻辑蕴涵–Armstrong公理系统推理规则–FD的逻辑蕴涵–函数依赖集F的闭包F+–属性集闭包–函数依赖集等价和最小函数依赖集•候选码及其求解方法回顾第13讲模式分解6•主要内容–模式分解的概念–分解的无损连接性和保持函数依赖性–模式分解算法模式分解第13讲模式分解7•分解的概念设有一关系模式R（U,F），若用一关系模式的集合ρ={R1（U1,F1），R2（U2,F2），…，Rn（Un,Fn）}来取代，其中U=∪Ui，并且没有Ui⊆Uj，1≤i,j≤n，Fi是F在Ui上的投影。则关系模式的集合ρ为R的一个分解ρ={R1，R2，…，Rn}模式分解的概念第13讲模式分解8•分解的概念–F在Ui上的投影Fi={X→Y|X→Y∈F+∧XY⊆Ui}模式分解的概念思考：设有关系模式R（A，B，C，D），F是R上成立的FD集F={AB→C，D→B}，则F在模式ACD上的投影为________；F在模式AC上的投影为_________。AD→C空第13讲模式分解9•分解的概念模式分解的概念【例】R(编号，连队，连长，科目，成绩),F={编号→连队，连队→连长，(编号，科目)→成绩}【例】R(学生学号，学生姓名，所在系，系主任，课程名称，成绩}，F={学生学号→学生姓名，学生学号→所在系，所在系→系主任，（学生学号，课程名称）→成绩}第13讲模式分解10•分解的概念模式分解的概念1NF2NF3NF去除非主属性对于键的部分函数依赖去除非主属性对于键的传递函数依赖R（学生学号，学生姓名，所在系，系主任，课程名称，成绩）R1（学生学号,课程名称,成绩）R2（学生学号，学生姓名，所在系，系主任）R1（学生学号,课程名称,成绩）R3（学生学号，学生姓名，所在系）R4（所在系，系主任）第13讲模式分解11•分解的概念模式分解的概念R（{学生学号，学生姓名，所在系，系主任，课程名称，成绩}{学生学号→学生姓名，学生学号→所在系，所在系→系主任，（学生学号，课程名称）→成绩}ρ1={R1({学生学号，课程名称，成绩},{（学生学号，课程名称）→成绩}),R3({学生学号，学生姓名，所在系},{学生学号→学生姓名，学生学号→所在系}),R4({所在系，系主任},{所在系→系主任})}第13讲模式分解12•分解的概念模式分解的概念R（{学生学号，学生姓名，所在系，系主任，课程名称，成绩}{学生学号→学生姓名，学生学号→所在系，所在系→系主任，（学生学号，课程名称）→成绩}ρ2={R1（学生学号）,R2（学生姓名）,R3（所在系）,R4（系主任）,R5（课程名称）,R6（成绩）}U=∪Ui，并且没有Ui⊆Uj，1≤i，j≤nFi是F在Ui上的投影不存在非平凡的函数依赖。不具有无损连接性第13讲模式分解13•分解的概念模式分解的概念R（{学生学号，学生姓名，所在系，系主任，课程名称，成绩}{学生学号→学生姓名，学生学号→所在系，所在系→系主任，（学生学号，课程名称）→成绩}ρ3={R1({学生学号，课程名称，成绩},{（学生学号，课程）→成绩}),R2({学生学号，学生姓名，所在系},{学生学号→学生姓名，学生学号→所在系}),R3({学生学号，系主任},{学生学号→系主任})}U=∪Ui，并且没有Ui⊆Uj，1≤i,j≤nFi是F在Ui上的投影。没有保持函数依赖第13讲模式分解14•分解的概念–一个关系模式的分解并不是唯一的。–理想的分解应该是既具有无损连接性又保持函数依赖，这样的分解是等价分解。–等价分解•分解具有无损连接性，即数据等价•分解保持函数依赖，即语义等价•分解既具有无损连接性又保持函数依赖，即数据等价并且语义等价模式分解的概念第13讲模式分解15无损连接分解•无损连接分解–设ρ={R1（U1,F1），…，Rk（Uk,Fk）}是R（U,F）的一个分解，r是R（U,F）的一个关系，则πRi(r)={t.Ui|t∈r}为r在子模式Ri上的投影，mρ(r)=πR1(r)⋈πR2(r)⋈…⋈πRk(r)是r在ρ中各关系模式上投影的连接。–若对RU,F的任何一个关系r均有r=mρ(r)成立，则称分解ρ具有无损连接性。分解ρ是无损分解第13讲模式分解16•算法：检验一个分解是否是无损分解–输入：关系模式R（U，F），U={A1,A2,…,An}；R上的分解ρ={R1（U1,F1）,R2（U2,F2）,…,Rk（Uk,Fk）}。设F是最小函数依赖集。–输出：判断ρ相对于F是否具有无损分解特性。无损连接分解第13讲模式分解17无损连接分解•检验一个分解是否无损的算法–步骤A1…AnR1（U1,F1）a1：Rk（Uk,Fk）bkn1）建立一张k行n列的表，每行对应分解中的一个关系模式Ri，每列对应一个属性Aj，若属性Aj∈Ui，则在i行j列处填aj，否则填bij。A1∈U1AnUk第13讲模式分解18无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F={A→C，B→C，C→D，DE→C，CE→A}。ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}是R的一个分解。试判断ρ是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b23b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b53b54a5初始状态1）建立一张k行n列的表，每行对应分解中的一个关系模式Ri，每列对应一个属性Aj，若属性Aj∈Ui，则在i行j列处填aj，否则填bij。第13讲模式分解19无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F={A→C，B→C，C→D，DE→C，CE→A}。ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}是R的一个分解。试判断ρ是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b23b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b53b54a5初始状态2）把表格看成模式R的一个关系，反复检查F中的每个函数依赖在表格中是成立，若不成立，则修改表格中的值。第13讲模式分解20无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F={A→C，B→C，C→D，DE→C，CE→A}。ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}是R的一个分解。试判断ρ是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b23b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b53b54a5初始状态2）对每一形如X→Y的FD做如下操作：检查X中的属性所对应的列，找出X相等的行，将这些行中对应的Y中的属性列所对应的符号改为一致。即若其中之一为aj，则都改成aj；否则，将其都改成这些列中行号最小的符号bij。对F的一次扫描第13讲模式分解21无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F={A→C，B→C，C→D，DE→C，CE→A}。ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}是R的一个分解。试判断ρ是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b23b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b53b54a5A→C第13讲模式分解22无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F={A→C，B→C，C→D，DE→C，CE→A}。ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}是R的一个分解。试判断ρ是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b13b54a5A→C第13讲模式分解23无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F={A→C，B→C，C→D，DE→C，CE→A}。ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}是R的一个分解。试判断ρ是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13b24b25R3(BE)b31a2b33b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b13b54a5A→CB→C第13讲模式分解24无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F={A→C，B→C，C→D，DE→C，CE→A}。ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}是R的一个分解。试判断ρ是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13b24b25R3(BE)b31a2b13b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b13b54a5A→CB→C第13讲模式分解25无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F={A→C，B→C，C→D，DE→C，CE→A}。ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}是R的一个分解。试判断ρ是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13b24b25R3(BE)b31a2b13b34a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b13b54a5A→CB→CC→D第13讲模式分解26无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F={A→C，B→C，C→D，DE→C，CE→A}。ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}是R的一个分解。试判断ρ是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13a4b25R3(BE)b31a2b13a4a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b13a4a5A→CB→CC→D第13讲模式分解27无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F={A→C，B→C，C→D，DE→C，CE→A}。ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}是R的一个分解。试判断ρ是否为无损分解。ABCDER1(AD)a1b12b13a4b15R2(AB)a1a2b13a4b25R3(BE)b31a2b13a4a5R4(CDE)b41b42a3a4a5R5(AE)a1b52b13a4a5A→CB→CC→DDE→C第13讲模式分解28无损连接分解【例】设有关系模式R(U，F)，U=ABCDE，F={A→C，B→C，C→D，DE→C，CE→A}。ρ={R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)}是R的一个分解。试判断ρ是否为无损分解。ABCDER1(AD)a1b12a3a4b15R2(A