第6章--关系数据库理论

1、第6章 关系数据库理论,6.1 关系数据模式的规范化理论 6.1.1 关系模式规范化的必要性 6.1.2 函数依赖及其关系的范式 6.1.3 多值依赖及关系的第四范式 6.2 关系模式的分解算法 6.2.1 关系模式分解的算法基础 6.2.3 判定分解服从规范的方法 6.2.4 关系模式的分解方法 6.3 关系系统及查询优化技术,概念回顾,概念模型与数据模型: 关系模型： 关系： 关系模式： 关系数据库：,第6章 关系数据库理论,关系数据库的理论是以数学理论为基础的，包括： 1、数据库设计理论： 关系规范化理论 关系模式分解理论 2、数据操作理论： 关系数据的查询理论(8个关系运算) 关系数据

2、的查询优化理论,6.1 关系数据模式的规范化理论,6.1.1关系模式规范化的必要性 数据库的设计核心是数据模型的设计，数据模型最基本内容就是数据结构，关系数据模型的数据结构是通过各关系模式来描述的，只有每个关系模式设计规范，才可能让整个关系模型合理，建立起来的数据库才合理、科学。什么样的关系模式才比较规范的呢？首先它就要必须满足一些基本要求：,1、关系模式应满足的基本要求 1）元组的每个分量必须是不可分的数据项。 2）数据库中的数据冗余应尽可能少。 3）关系数据库不能因为数据更新操作而引起数据不一致问题。 4）当执行数据插入操作时，数据库中的数据不能产生插入异常现象。 5）数据库中的数据不能在

3、执行删除操作时产生删除异常问题。 6） 数据库设计应考虑查询要求，数据组织应合理。,2. 关系不规范可能出现的问题,分析下面关系存在的问题:,冗余,（1）数据冗余大：,（2）更新异常：,（3） 插入异常：,（4） 删除异常：,上述关系模式是不合理的，或者说是不很规范的，不符合关系数据模式的规范化基本要求。,如某系换了系主任,如成立新系，但还没招生,某系所有学生已毕业，但还没招新生,上述关系虽然结构较简单，包含所需信息，但存在数据冗余大、 插入异常、 删除异常、 更新异常等问题。 （1）数据冗余大：很显然 （2） 插入异常：如成立新系，但还没招生，但没法录入系相关信息（主码为学号、课程号）。 （

4、3） 删除异常：某系所有学生已毕业，但还没招新生，该系相关信息删除。 （4） 更新异常：如某系换了系主任，则该系所有学生记录都要更改，遗漏一个将出现数据不一致 上述关系模式是不合理的，或者说是不很规范的，不符合关系数据模式的规范化理论要求。,3. 模式分解是关系规范化的主要方法 可以将一个不规范或较低规范的关系模式通过模式分解的方法转换成若干较为规范的关系模式的集合，这种过程叫关系模式的规范化。 上述的关系模式: 教学(学号，姓名，年龄，性别，系名，系主任，课程名， 成绩). 可以按“一事一地”的原则分解成“学生”、“教学系”和“选课”三个关系，其关系模式为： 学生(学号，姓名，年龄，性别，系

5、名称)； 教学系(系名，系主任)； 选课(学号，课程名，成绩).,教学(学号，姓名，年龄，性别，系名，系主任，课程名， 成绩).,可以按“一事一地”的原则分解成“学生”、“教学系”和“选课”：,教学系：,学生：,选课：,1、关系模式的简化表示法 对关系的描述称为关系模式，关系模式的完整表示是一个五元组： RU，D，Dom，F. 其中： R为关系名； U为关系的属性集合； D为属性集U中属性的数据域（类型）； Dom为属性到域的映射（长度） F为属性集U的数据依赖集。,6.1.2 函数依赖及其关系的范式,如选课关系：,R：选课,U：学号、课程名、成绩,D：字符型、整型,Dom： 学号：字符型，长

6、度5 课程名：字符型，长度20 成绩：整型,F：（学号，课程名）成绩，,数据依赖一般是指同一个关系中属性间的相互依赖和相互制约，包括函数依赖、多值依赖和连接依赖。 数据依赖是关系模式规范化理论的基础，其中： 函数依赖是1NF、2NF、3NF、BCNF的理论基础 多值依赖是4NF的理论基础 连接依赖是5NF的理论基础 一般我们主要关心的是R、U、F，为简化问题，一般关系模式可以用三元组来为： RU，F,2、函数依赖的概念 1) 定义：设RU是属性集U上的关系模式，X、Y是U的子集。若对于RU的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而Y上的属性值不等（X上值相同，则Y上值

7、必相同），则称X函数确定Y函数，或Y函数依赖于X函数，记作XY。,如教学：,教学关系模式：RU，F： R= U= F=,教学,学号，姓名，年龄，性别，系名，系主任，课程名，成绩,学号姓名，学号年龄，学号性别，学号系名，系名系主任，(学号，课程名)成绩,相关概念： XY，但Y X，则称XY是非平凡的函数依赖。若不特别声明，总是讨论非平凡的函数依赖。 XY，但YX，则称XY是平凡的函数依赖。 若XY，则X叫做决定因素（Determinant），Y叫做依赖因素（Dependent）。 若XY，YX，则记作XY。 若Y不函数依赖于X，则记作X Y。,(学号，课程名)成绩,(学号，姓名)学号,2)完全函

8、数依赖 定义：在RU中，如果XY，并且对于X的任何一个真子集X，都有X Y，则称Y对X完全函数依赖，记作：XY；若XY，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作： XY。,P,F,部分：(学号，姓名)年龄、(学号，课程名)姓名,F,P,F,F,完全：学号姓名、学号年龄、(学号，课程名) 成绩,P,结论： 决定因素是属性组时才有部分依赖 如：学号姓名，学号年龄都是完全函数依赖 在规范程度不高的关系中其它属性未必完全函数依赖于码。,F,F,3)传递函数依赖 定义：在RU中，如果XY，(Y X)，Y X，YZ，则称Z对X传递函数依赖。传递函数依赖记作X Z。 例如，在教学模式中： 因为：

9、学号系名，系名系主任； 所以：学号 系主任。,传递,传递,3、范式： 规范化的关系模式称为范式（Normal Form）。由满足最基本规范化条件的关系模式叫第一范式，第一范式的关系模式再满足另外一些约束条件就产生了第二范式、第三范式、BC范式等，分别记为：1NF、2NF、3NF、BCNF、4NF、5NF。一个可用的关系最低要满足3NF。,（1） 1NF的定义 定义：如果关系模式R，其所有的属性均为简单属性，即每个属性都是不可再分的，则称R属于第一范式，记作R1NF。 第一范式是最基本的范式，不满足第一范式条件就不能称为规范化关系，但仅满足第一范式的条件还不够，如教学关系： 教学(学号,姓名,年

10、龄,性别,系名,系主任,课程名,成绩) 仍存在数据冗余度大、插入、删除和更新可能产生异常的现象，需进一步规范：,（2）. 2NF的定义 （1）定义： 若R1NF，且每一个非主属性完全依赖于码，则R2NF。,姓名,年龄,性别,系名,系主任,成绩,学号,姓名,年龄,性别,系名,系主任,课程名,成绩.,属性集=,主码=,(学号,课程名).,非主属性=,例在教学模式中：,F=,显然，教学模式不服从2NF，即：教学2NF。,非主属性对码的函数依赖：,（2）关系模式分解，转化为第二范式： 学生_系(学号，姓名，年龄，性别，系名，系主任) 选课(学号,课程名，成绩),显然，学生_系2NF，选课2NF 。,学

11、生_系关系仍然存在冗余度大，更新、插入、删除异常等问题,（3）. 3NF的定义 (1)定义:关系模式RU，F中若不存在这样的码X、属性组Y及非主属性Z(Z Y)使得XY、Y X、YZ成立，则称RU，F3NF。 (2)含义: 每一个非主属性不部分函数依赖于码，所若R3NF,必有R2NF 证明:反证法 每一个非主属性不传递函数依赖于码(由定义知)。 换句话说：关系模式RU，F1NF ， 若XY且Y X （Y是非主属性）时，X必含有码，则称RU，F3NF。 即非主属性完全直接地依赖码。,考查学生_系关系： 学生_系(学号,姓名,年龄,性别,系名,系主任) 码= 主属性= 非主属性= 由于存在：学号系

12、名，系名系主任。 则： 学号 系主任。所以学生_系3NF。,传递,学号,学号,姓名，年龄，性别，系名，系主任,如果学生_系关系分解为： 学生(学号，姓名，年龄，性别，系名)； 教学系(系名，系主任) 选课(学号，课程名，成绩) 显然分解后的各子模式均属于3NF。 结论：3NF是一个可用关系模应满足的最低范式,（4）. BCNF的定义 (1)定义:关系模式RU，F1NF。若XY且Y X时X必含有码，则RU，FBCNF。 也就是说，关系模式RU，F中，若每一个决定因素都包含码，则RU，FBCNF。由BCNF的定义可以得到结论。,3NF另一种定义：关系模式RU，F 1NF ，若XY且Y X （Y是非

13、主属性）时，X必含有码，则称RU，F3NF。,与3NF定义的比较：,两种范式定义不同点：BCNF要求每一个非平凡的函数依赖中，决定因素X都要含有码，依赖因素Y包括是主属性和非主属性两情况 ，而3NF只要求依赖因素Y是非主属性时，决定因素X都要含有码。,BCNF和3NF的比较总结：,1) 3NF只强调非主属性对码的完全直接依赖，这样就可能出现主属性对码的部分依赖和传递依赖。 2) BCNF不仅强调非主属性对码的完全的直接的依赖，而且强调主属性对码的完全的直接的依赖，它包括3NF，即RBCNF，则R一定属于3NF。 所以BCNF比3NF的要求又进了一步，通常认为BCNF是修正的第三范式，有时也称为

14、扩充的第三范式。 因此BCNF要求任何属性都必须完全的直接的依赖于码， 任何属性不能完全函数依赖于非码的属性组。,例如，关系模式STJ(S，T，J)中，S表示学生，T表示教师，J表示课程。语义为：每一教师只能讲授一门课程，每门课程由若干教师讲授；每个学生选修某门课程就对应一个固定的教师。,由语义可以得到STJ模式的函数依赖为： F=(S，J)T， (S，T)J， TJ 显然： 码= 主属性集= 非主属性= 由于STJ模式中无非主属性，所以它属于3NF； 结论：无非主属性的关系都属于3NF 因为存在TJ，由于T不是码，故STJBCNF。,(S，J)和(S ，T),S，T，J,（空集）,可将它分解

15、为：ST（S，T）和TJ(T，J)，它们都BCNF,其它结论： 一个二目的关系属于BCNF 只有一个码的3NF关系属于BCNF (Armstrong公理的增广律可证明) 全码关系属于BCNF,6.1.3 多值依赖及关系的第四范式,1. 研究多值依赖的必要性例: 学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。 关系模式Teaching(C, T, B),用二维表表示Teaching,Teaching模式中存在的问题 (1)数据冗余度大：有多少名任课教师，参考书就要存储多少次. (2)插入操作复杂：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组. 例如物理课增

16、加一名教师刘关，需要插入三个元组： （物理，刘关，普通物理学） （物理，刘关，光学原理） （物理，刘关，物理习题集） (3) 删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组 (4) 修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组,关系分析： Teaching具有唯一码(C，T，B)， 即全码 TeachingBCNF 产生问题原因:存在多值依赖,2. 多值依赖的定义和性质,定义：设有关系模式RU，U是属性集，X、Y是U的子集, Z=U-X-Y 。如果R的任一关系r，对于一个确定值(x,z)，都存在Y的一组值与之对应，且Y的这组

17、值仅x相关,与z不相关，此时称Y多值依赖于X，或X多值决定Y，记为XY。例 Teaching（C, T, B） 对于C的每一个值，T有一组值与之对应，而不论B取何值,多值依赖具有以下性质：1) 多值依赖具有对称性。即若XY，则XZ，其中Z=U-X-Y。 2) 函数依赖可以看作是多值依赖的特殊情况。即若XY，则XY。这是因为当XY时，对X的每一个值x，Y有一个确定的值y与之对应，所以XY。3) 在多值依赖中，若XY且Z=U-X-Y，则称XY为非平凡的多值依赖，否则称为平凡的多值依赖。,3.多值依赖与函数依赖的区别 (1) 有效性:多值依赖的有效性与属性集的范围有关 函数依赖XY 的有效性只取决于

18、X，Y ，与其它属性无关。 多值依赖的定义中不仅涉及属性组 X和 Y，而且涉及U中其余属性Z。 (2) 多值依赖没有自反律 若函数依赖XY在R（U）上成立，则对于任何Y Y均有XY 成立 多值依赖XY若在R(U)上成立，不能断言对于任何Y Y有XY 成立,4.第四范式（4NF） 定义:关系模式R(U，F)1NF，如果对于R的每个非平凡多值依赖XY（Y X），X都含有码，则R4NF。 如果R 4NF， 则R BCNF 允许是函数依赖（非平凡多值含码就时函数依赖，函数依赖是多值依赖特例） 不允许有非平凡且非函数依赖的多值依赖 允许平凡多值依赖（ XY且Z=U-X-Y ）,例： Teaching(C

19、,T,B) 4NF 存在非平凡的多值依赖CT，且C不是码 用分解法把Teaching分解为如下两个关系模式： CT(C, T) 4NF CB(C, B) 4NF CT， CB是平凡多值依赖 若只考虑函数依赖，BCNF是最高范式，若考虑多值依赖，4NF是最高范式，或考虑连接依赖，5NF是最高范式.,6.1.4 连接依赖（JD）5NF,1、关系分解的无损连接,设U是关系模式R的属性域，R1，R2R为R分解后的子关系，若满足RR1 R2 R，则称该分解具有无损连接性。,关系规范化主要手段是分解，分解后的子关系可通过自然连接进行合并，连接依赖就是关于分解和自然连接的理论，第五范式就是关于消除子关系插入

20、和删除异常的理论,2、连接依赖的定义：,设U是关系模式R的属性域，x1，x2x为U的子集，满足U x1 x2x，Ri(xi)是R分解的一个子关系，如果R= RR1 R2 R对于R的每个关系r都成立，那么称R在该分解上具有n目的连接依赖。,因为R1分解为：,SP,PJ,JS,R1,R2=SP PJ JS 所以插入前该分解具有无损连接性,例：设R（SPJ）有一个分解（SP，PJ，JS）,如果R的关系中已有两个元组（S1，P1，J2）和（S1，P2，J1）,现在要插入一个元组（S2，P1，J1）：,SP,PJ,JS,R2=SP PJ JS 所以插入后该分解不具有无损连接性,插入后正确结果R2,如果关

21、系模式R的每个JD均由R的候选键隐含，那么称R是5NF。 含义：指子关系的自然连接的公共属性中含有码。,3、5NF的定义：, JD是现实世界中属性间的一种抽象，是语义的体现。但较之FD，MVD不直观，很难断定是一个模式是否是5NF。, 但R5NF，则R4NF。, 现在还没有完备的推理规则。, JD只有在关系的连接运算时才反映出来。,说明：,小结： 关系数据库的规范化理论是数据库逻辑设计的工具。 一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。 规范化程度可以有多个不同的级别，一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合 关系模

22、式规范化的基本步骤 1NF 2NF 3NF BCNF 4NF 5NF,消除决定属性集非码的非平凡函数依赖,消除非主属性对码的部分函数依赖,消除非主属性对码的传递函数依赖,消除主属性对码的部分和传递函数依赖FD,消除非平凡且非函数依赖的多值依赖MD,取消不是由候选码所蕴涵的连接依赖JD,6.2 关系模式的分解算法6.2.1 关系模式分解的算法基础,1. 函数依赖的逻辑蕴含设F是模式RU的函数依赖集，X和Y是属性集U的子集。如果从F中的函数依赖能推出XY，则称F逻辑蕴含XY，或称XY是F的逻辑蕴含。,如：F=A B，B C,那么：A B、B C、A C为F所逻辑蕴含,2. Armstrong公理系

23、统(1) Armstrong公理系统 设U为属性集，F是U上的函数依赖集，于是有关系模式RU，F。对RU，F来说，有以下的推理规则。 1) 自反律：若YXU，则XY为F所蕴含(平凡)。 2) 增广律：若XY为F所蕴含，且ZU，则XZYZ为F所蕴含。 3) 传递律：若XY及YZ为F所蕴含，则XZ为F所蕴含。,(2) Armstrong公理的三个推理 1) 合并规则：由XY，XZ，有XYZ。 2) 伪传递规则：由XY，WYZ，有XWZ。 3) 分解规则：由XY及ZY，有XZ。 根据合并规则和分解规则，可得XA1 A2Ak成立的充分必要条件是XAi成立（i=l，2，k）,证明： XY， X X Y

24、（增广律） Xz， XyYz（增广律） XYz（传递律）,证明： XY， XWYW（增广律） YWz， XWz（传递律）,(3) Armstrong公理的有效性和完备性 1)有效性:由F出发根据Armstrong公理推导出来的每一个函数依赖一定为F所蕴含的,即是正确的。 2)完备性：F所逻辑蕴含的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来. 建立公理系统体系目的：从已知的函数依赖推导出未知的函数依赖,3. 函数依赖集闭包F+和属性集闭包XF+ (1)函数依赖集闭包F+和属性集闭包XF+的定义 F+定义：在关系模式RU，F中，为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记

25、作F+。 XF+定义：设有关系模式RU，F，X是U的子集，称所有从F推出的函数依赖集XAi中Ai的属性集为X的属性集闭包，记作XF+。 即： XF+= Ai | AiU，XAiF+,(2) 属性集闭包XF+的求法1) 选X作为闭包XF+的初值XF(0)。2) XF(i+1)是由XF(i)并上集合A所组成，其中A为F中存在的函数依赖YZ，而AZ，YXF(i)。3) 重复步骤2)。一旦发现XF(i)= XF(i+1)，则XF(i)为所求XF+。,【例6-1】已知关系RU，F，其中U=A，B，C，D，E，F=ABC，BD，CE，ECB，ACB，求(AB)F+。 设X=AB XF(0)=AB XF(1

26、)=ABCD XF(2)=ABCDE XF(3)= XF(2)=ABCDE (AB)F+=ABCDE=A，B，C，D，E,求XF+提供了判断X Y是否为F所蕴含的方法，若Y XF+，则为F所蕴含 求XF+提供了判断码的方法,【例6-2】已知关系RU，F，其中U=A，B，C，D，E，F=AB，BCE，EDAB，求(ABC)F+。 设X=ABC XF(0)=ABC XF(1)=ABCE XF(2)=ABCE XF(2)= XF(1)=ABCE (ABC)F+=ABCE=A，B，C，E,4. 函数依赖集等价,如：F=A B，B C G=A B，B C, A C,因此：F与G等价,因为：A B、B C

27、 所以：A C,1)定义:设F和G 两个函数依赖集,如果G+=F+，就说函数依赖集F与G等价（F覆盖G，G覆盖F）。,2)定理:F+ = G+ 的充分必要条件是 : F G+ (G覆盖F)，G F+(F覆盖G) 3)判断F+ = G+ 的方法是根据2),具体做法: 判定F G+，只须逐一对F中的函数依赖XY，考察 Y 是否属于XG+ 就行了(Y XG+, XY G+ ),若全是,则F G+ 判定G F+，只须逐一对G中的函数依赖XY，考察 Y 是否属于XF+ 就行了(Y XF+, XY F+ ),若全是,则F G+,【例6-3】判断 F=ABC，BAC，CA与G=AB，BC，CA是否等价,（1

28、）判定F G+,因为：（A）G+=ABC，所以：ABCG+ 因为：（B）G+=ABC，所以： BACG+ 显然：CAG+ 因此： F G+,（2）判定G F+,因为：（A）F+=ABC，所以：ABF+ 因为：（B）F+=ABC，所以： BCF+ 显然：CAF+ 因此： G F+,（3）结论：F+ = G+,5. 函数依赖集的最小化,(1) 最小函数依赖集的定义 如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。1) F中任一函数依赖的右部仅含有一个属性(右边无多余的属性)。2) F中不存在这样的函数依赖XA，使得F与F-XA等价(无多余的函数依赖) 。3)

29、F中不存在这样的函数依赖XA，X有真子集Z使得F-XAZ A与F等价(左边无多余的属性) 。,(2) 最小函数依赖集的求法 逐一检查F中各函数依赖XY，若Y=A1A2Ak，k2，则用XAj|j=1，2，k来取代XY (保证右边无多余的属性) 。 逐一检查F中各函数依赖XA，令G=F-XA，若AXG+，则从F中去掉此函数依赖(保证无多余的函数依赖) 。 逐一取出F中各函数依赖XA，设X=B1B2Bm，逐一检查Bi（i=1，2，m），如果A(X-Bi)F+，则以X-Bi取代X。,【例6-4】设F=ABC，BAC，CA，对F进行极小化处理。 解：1) 根据分解规则把F中的函数依赖转换成右部都是单属性

30、的函数依赖集合，分解后的函数依赖集仍用F表示。 F=AB，AC，BA，BC，CA2) 去掉F中冗余的函数依赖。判断AB。设：G1= AC,BA,BC,CA 得：AG1+=AC BAG1+ AB不冗余判断AC。设：G2= AB,BA,BC,CA 得：AG2+=ABC CAG2+ AC冗余,判断BA。设：G3= AB，BC，CA，得：BG3+=BCA ABG3+ BA冗余判断BC。设：G4= AB，CA，得：BG4+=B CBG4+ BC不冗余判断CA。设：G5= AB，BC ， 得：CG5+=C ACG5+ CA不冗余 Fm= AB，BC，CA (3) 去掉各函数依赖左部冗余的属性: 左边都是单

31、属性,无多余的属性.,【例6-5】求F=ABC，AB，BA的最小函数依赖集Fm。 (1)右边已全是单属性,无需再分解 (2)去掉F中冗余的函数依赖。判断ABC是否冗余。设：G1= AB，BA，得：(AB)G1+=AB C (AB)G1+ ABC不冗余判断AB是否冗余。设：G2= ABC，BA，得：AG2+=A BABG2+ AB不冗余判断BA是否冗余。设：G3= ABC，AB ，得：BG3+=B ABG3+ BA不冗余经过检验后的函数依赖集仍然为F=ABC，AB，BA。,(3) 去掉各函数依赖左部冗余的属性。本题只需考虑ABC的情况。方法1：在决定因素中去掉B，若CAF+，则以AC代替ABC。

32、求得：AF+=ABC CAF+ 以AC代替ABC故：Fm=AC，AB，BA方法2：在决定因素中去掉A，若CBF+，则以BC代替ABC。求得：BF+=ABC CBF+ 以BC代替ABC故：Fm=BC，AB，BA,6.2.3 判定分解服从规范的方法 定义: 设= R1，R2，Rn， U=U1U2Un，且不存在 Ui Uj，则称是关系模式R的一个分解, m(r) Ri(r)， m(r)是r在中各关系的投影的连接。 判定分解服从规范考虑两个因素： 具有无损连接性 保持函数依赖 1. 关系分解的无损连接性 （1）定义： R1，R2 Rk是R上的一个分解，若对于R的任一关系r，均有r m(r)成立，则具有

33、无损连接性 。,例6.6 设有关系模式R(ABC)，分解成 =AB,AC (1) (a)是R上的一个关系r，(b)和(c)是r在模式AB和AC上的投影r1和r2。,显示对于此关系r,有r m(r),a,b :AB(r),c:AC(r),d:m(r),显示对于此关系r,有r m(r)，,（2）同样的模式分解，对于另外一个关系r：,a,不具有无损连接性 。,b =AB(r),c =AC(r),2、判断分解具有无损连接性的方法： （1）一般方法： 构造一张k行n列的表格，每列对应一个属性Aj(1jn)，每行对应一个模式Ri (1ik)。如果Aj在Ri中，那么在表格的第i行第j列处填上符号aj，否则填

34、上bij。 把表格看成模式R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的值。修改方法如下：对于F中一个FD XY，如果表格中有两行在X值上相等,在Y值上不相等,那么把这两行在Y值上也改成相等的值。 *如果Y值中有一个是aj，那么另一个也改成aj； * 如果没有aj，那么用其中一个bij替换另一个值（尽量把下标i改成较小的数）。 一直到表格不能修改为止。（这个过程称为chase过程） 若修改的最后一张表格中有一行是全a，即a1a2an，那么称相对于F是无损分解，否则称损失分解。,例6.7:设关系模式R(ABCD)，R分解成= AB, BC, CD.如果R上成立的函数

35、依赖集F1= BA,CD，那么相对于F1是否为无损分解？,(a) 初始表格,(b) 修改后的表格,b21,a2,a2,a3,a3,b24,a1,a4,a1,a4,（2）判断分解成两个关系且具有无损连接的方法： 定理：RU，F的一个分解= R1U1，F1，R2U2，F2具有无损连接性的充分必要条件是： U1U2U1-U2F+. 或 U1U2U2-U1F+.,初始化,例如： 设R=ABC， R1=AB，R2=AC， 则 U1U2=A， U1-U2=B，U2-U1=C,U1U2U1-U2 (AB),U1U2U2-U1 (AC),3. 判断分解保持函数依赖的方法 （1）定义： 设F是属性集U上的FD集

36、，Z是U的子集，F在Z上的投影用Z（F）表示，定义为： Z（F）= XY | XYF+，且XY Z 例：设：F= AB，BC ，C D，Z=ABD 求Z（F） 求得：Z（F）,=AB，BD,（2）定义：设U，F的分解=R1U1，F1，R2U2，F2，RkUK，FK，若F+=(Fi)+，则称分解保持函数依赖。 （3）判断一个分解是否保持FD，其方法是： 1）逐个求Fi= Ri (F) 2）求G= Fi= Ri (F) 3）判断是否有: F+=G+ 判定G F+：显然，不需判断 判定F G+：,逐步验证F中每个FD是否被G逻辑蕴涵,【例6-8】关系模式R=CITY，ST，ZIP，其中CITY为城市

37、，ST为街道，ZIP为邮政编码，F=(CITY，ST)ZIP，ZIPCITY。如果将R分解成R1和R2，R1=ST，ZIP，R2=CITY，ZIP，检查分解是否具有无损连接和保持函数依赖。 解：1) 检查无损连接性。 求得：R1R2=ZIP；R2-R1=CITY. (ZIPCITY)F+. 分解具有无损连接性 2) 检查分解是否保持函数依赖 求得：F1=R1(F)=；F2=R2(F)= ZIPCITY. G=R1(F)R2(F)= ZIPCITY (CITY，ST)ZIP （ ZIPCITY ）+ 该分解不保持函数依赖。,【例6-9】设关系模式R(WNO,WS,WG)的属性分别表示职工的工号、

38、工资级别和工资数目。如果规定每个职工只有一个工资级别，并且一个工资级别只有一个工资数目，则R上的FD有：F= WNOWS，WSWG 如果R分解成 =R1,R2，其中R1=WNO,WS，R2=WNO, WG，则这个分解是无损连接分解吗？是否保持FD吗？ 解：1) 检查无损连接性。 求得：R1R2=WNO；R1-R2=WS. (WNOWS)F+. 分解具有无损连接性 2) 检查分解是否保持函数依赖 求得：F1=R1(F)= WNOWS ； F2=R2(F)= WNOWG. G=F1F2=WNOWS， WNOWG WSWG G + 该分解不保持函数依赖。,【例6-10】设关系模式R（ABC），= A

39、B，AC 是R的一个分解。试分析分别在F1= AB ，F2= AC，BC ，F3= BA ，F4= CB，BA 情况下，是否具有无损分解和保持FD的分解特性。 相对于F1= AB ，分解是无损分解且保持FD的分解。 相对于F2= AC，BC ，分解是无损分解，但不保持FD。因为BC丢失了。 相对于F3= BA ，分解是损失分解但保持FD集的分解。 相对于F4= CB，BA ，分解是损失分解且不保持FD集的分解(丢失了CB) 因此是一关系模式分解是否为无损分解和是否保持函数依赖与具体的函数依赖集有关,无损连接反映了模式分解的数据等价原则。 依赖等价保证了分解后的模式与原有的模式在数据语义上的一致

40、性。,6.2.4 关系模式的分解方法,1. 将关系模式转化为3NF的保持函数依赖的分解1) 对RU，F中的F进行极小化处理。处理后的函数依赖集仍用F表示。2) 找出不再在F中出现的属性，把这样的属性构成一个关系模式，并把这些属性从U中去掉。3) 如果F中有一个函数依赖涉及R的全部属性（码含有n-1属性），则R不能再分解(已是3NF)。4) 如果F中含有XA，则分解应包含模式XA，如果XA1，XA2，XAn均属于F，则分解应包含模式XA1A2An（保证非主属性Ai对码X的直接依赖,且保证函数依赖没有丢失）。,【例6-11】设关系模式RU，F， U=C，T，H，R，S，G，X，Y，Z， F=CT，

41、CSG，HRC，HSR，THR，CX， 将R分解为3NF，且保持函数依赖。 解：该函数依赖集已经是最小化的，则分解为： R1=YZ，F1= R2= CTX ，F2= CT，CX R3= CSG ，F3= CSG R4= HRC ，F4= HRC R5= HSR ，F5= HSR R6= THR ，F6= THR =YZ，CTX，CSG，HRC，HSR，THR.,2. 将关系转化为3NF、且既具有无损连接性又能保持函数依赖的分解 对于给定的关系模式RU，F，将其转换为3NF，且既具有无损连接性又能保持函数依赖的分解算法为：1) RU，F先进行保持函数依赖的分解，结果为= R1U1，F1，R2U2

42、，F2，RkUk，Fk。2) X设是RU，F的码，若有某个Ui，X Ui，令=，否则令=R*X，Fx ，就是所求的分解。,【例6-12】有关系模式RU，F，U=C，T，H，R，S，G，F=CT，CSG，HRC，HSR，THR，将R分解为3NF，且既具有无损连接性又能保持函数依赖。解： (1)它的一个保持函数依赖的3NF为： =CT，CSG，HRC，HSR，THR. (2)求得关系模式R的码为HS HSHSR = CT，CSG，HRC，HSR，THR为满足要求的分解。,3. 将关系模式转换为BCNF的无损连接的分解,1) 令= RU，F。 2) 检查中各关系模式是否均属于BCNF。若是，则算法终

43、止。 3) 假设中RiUi，Fi不属于BCNF，那么必定有XAFi+，(AX)，且X非Ri的码。对Ri进行分解：=S1，S2，US1=XA（s1是属于BCNF ，且保持无损连接），US2= Ui-A，以代替RiUi，Fi，返回第2)步。 S1 S2=X，S1-S2=A，X A 每次分解都是无损分解，但不能保证保持函数依赖,【例】关系模式RU，F，U=CTHRSG，F= CT，HRC， HTR，CSG，HSR，把R分解成具有无损连接的BCNF。 解：令= CTHRSG 由于R的码为HS，选择CSG分解。 得出：=S1，S2. 其中：S1=CSG， F1= CSG； S2=CTHRS， F2= C

44、T，HRC，HTR，HSR S2不服从BCNF，需要继续分解。 2) 对S2分解。S2的码为HS，选择CT分解。 得出：= S1，S3，S4. 其中：S3=CT， F3= CT； S4=CHRS， F4= HRC， HCR ，HSR， S4不服从BCNF，还需要继续分解。,3) 对S4分解。码为HS，选择HRC分解： = S1，S3，S5，S6. 其中：S5=HRC， F5= HRC； S6=HRS， F6=HSR. 4) 最后的分解为：=CSG，CT，HRC，HRS. 可验证此分解仅具有无损连接性，而不保持函数依赖。,【例】设关系模式R(U,F),U=学号,课程号,成绩,教师名,教师所在系，

45、F=(学号,课程号) 成绩,课程号教师名,教师名教师所在系,将其分解为具有无损连接的BCNF 解：令= 学号,课程号,成绩,教师名,教师所在系 1) 由于R的码为（学号,课程号 ），选择教师名教师所在系分解。 得出：=S1，S2. 其中：S1=教师名,教师所在系 ， F1=教师名教师所在系； S2= 学号,课程号,成绩,教师名 ， F2=(学号,课程号) 成绩,课程号教师名. S2不服从BCNF，需要继续分解。2) 对S2分解。S2的码为（学号,课程号 ） ，选择课程号教师名分解。 得出：= S1，S3，S4. 其中：S3= 课程号，教师名 ， F3=课程号教师名； S4= 学号,课程号,成绩

46、， F4=(学号,课程号) 成绩. S1，S3，S4服从BCNF，无需继续分解。3) 最后的分解为： =（教师名,教师所在系）,（课程号,教师名）,（学号,课程号,成绩） 可验证此分解不仅具有无损连接性，而且还保持函数依赖。,3个结论 若分解保持函数依赖，分解一定可以达到3NF,但不一定能达到BCNF 若分解具有无损连接性，分解一定可以达到BCNF 若分解既保持依赖又具有无损连接性，分解一定可以达到3NF,但不一定能够达到BCNF,6.3关系系统与查询优化技术,6.3.1关系系统的定义与分类: 1.关系系统的定义: 能够在一定程度上支持关系模型的数据库管理系统是关系系统。 由于关系模型中并非每

47、一部分(数据结构、操作与完整性约束）都是同等重要的，所以并不苛求一个实际的关系系统必须完全支持关系模型。一个数据库管理系统可定义为关系系统，当且仅当它至少支持： （1）支持关系数据库（即关系数据结构）， 系统中只有表这种结构 （2） 支持选择、投影和（自然）连接运算 对这些运算不要求用户定义任何物理存取路径。 上面两条是对关系系统的最低要求。,说明： 不支持关系数据结构的系统显然不能称为关系系统。 仅支持关系数据结构，但没有选择、投影和连接运算功能的系统仍不能算作关系系统。 原因：不能提高用户的生产率 支持选择、投影和连接运算，但要求定义物理存取路径，这种系统也不能算作真正的关系系统 原因：就

48、降低或丧失了数据的物理独立性 选择、投影、连接运算是最有用的运算，它能解决大多数实际问题，所以一关系系统不一定要求支持关系代数的全部运算。,2 关系系统的分类 分类依据：支持关系模型的程度 表式系统：支持关系数据结构(即表)，不支持集合级的操作，不能算是关系系统。 (最小)关系系统：支持：关系数据结构，支持关系的选择、投影、连接关系操作 关系完备的系统：支持：关系数据结构，支持所有的关系代数操作。 全关系系统：支持：关系模型的所有特征（关系数据结构、关系操作和三个完整性）， 特别是:数据结构中域的概念。 现在的关系系统一般接近于全关系系统。,6.3.2 关系系统的查询优化,1 查询优化概述 (

49、1)查询优化的必要性: 查询优化极大地影响RDBMS的性能。 (2)查询优化的可能性 关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。 (3)由DBMS进行查询优化的好处 用户不必考虑如何最好地表达查询以获得较好的效率 系统可以比用户程序的优化做得更好,因为: 1) 优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息,2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。 在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 3)优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 4)优

50、化器中包括了很多复杂的优化技术,（4）查询优化的总目标 选择有效策略，求得给定关系表达式的值 （5）代价模型 集中式数据库 单用户系统 总代价 = I/O代价 + CPU代价 多用户系统 总代价 = I/O代价 + CPU代价 + 内存代价 分布式数据库 总代价 = I/O代价 + CPU代价+ 内存代价 + 通信代价,2 查询优化的必要性,例：求选修了课程2的学生姓名 SELECT 学生.姓名 FROM 学生, 选课 WHERE 学生.学号=选课.学AND 选课.课程号=C2 假设1：外存： 学生:1000条,选课:10000条, 选修C2号课程:50条 假设2：一个内存块装元组:10个学生

51、, 或100个选课, 内存中一次可以存放: 5块学生元组, 1块选课元组和若干块连接结果元组 假设3：读写速度：20块/秒 假设4：连接方法：基于数据块的嵌套循环法,执行策略1,1 姓名(学生.学号=选课.学号 选课.课程号=C2 (学生选课) 学生选课 读取总块数= 读学生表块数 + 读选课表遍数 *每遍块数 =1000/10+(1000/(105) (10000/100) =100+20100=2100 读数据时间=2100/20=105秒,中间结果大小 = 1000*10000 = 107 (1千万条元组) 写中间结果时间 = 10000000/10/20 = 50000秒 读数据时间

52、= 50000秒 总时间 =1055000050000秒 = 100105秒 = 27.8小时,执行策略2,2 姓名(选课.课程号= C2 (学生 选课) 读取总块数= 2100块 读数据时间=2100/20=105秒 中间结果大小=10000 （减少1000倍） 写中间结果时间=10000/10/20=50秒 读数据时间=50秒 总时间1055050秒205秒=3.4分,执行策略3,3. 3 姓名(学生 选课.课程号= C2 (选课) 读选课表总块数= 10000/100=100块 读数据时间=100/20=5秒 中间结果大小=50条 不必写入外存 读学生表总块数= 1000/10=100块

53、 读数据时间=100/20=5秒 总时间55秒10秒,执行策略4,4. 4 姓名(学生 选课.课程号=C2 (选课) 假设选课表在课程号上有索引，学生表在学号上有索引 读选课表索引:少 读选课表总块数= 50/1001块 读数据时间=1/20 中间结果大小=50条 不必写入外存, 读学生表索引:少 读学生表总块数= 50/10=5块 读数据时间 =5/20 总时间10秒,3 查询优化的一般准则,1）选择运算应尽可能先做 目的：减小中间关系,最重要、最基本的一条 2）在执行连接操作前对关系适当进行预处理 按连接属性排序 在连接属性上建立索引 3）投影运算和选择运算同时做：扫描关系同时，完成所有运

54、算。 目的：避免重复扫描关系 4）将投影运算与其前面或后面的双目运算结合 目的：减少扫描关系的遍数,5）某些选择运算在其前面执行的笛卡尔积 = 连接运算 例：学生.学号=选课.学号 (学生选课) 学生 选课 6）提取公共子表达式 公共表达式的结果不是一个很大的关系，且读此关系的时间比计算机表达式的时间少，则可先提取公共表达式。,4 关系代数等价变换规则,设E1、E2等是关系代数表达式，F是条件表达式 （l） 连接、笛卡尔积交换律 E1 E2 E2E1 E1 E2E2 E1 E1 F E2E2 F E1 （2） 连接、笛卡尔积的结合律 (E1E2) E3 E1 (E2E3) (E1 E2) E3

55、 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F F F F,（3） 投影的串接定律 A1,A2, ,An( B1,B2, ,Bm(E) A1,A2, ,An (E) 假设： 1)E是关系代数表达式 2)Ai(i=1，2，n), Bj(j=l，2，m)是属性名 3)A1, A2, , An构成Bl，B2，Bm的子集 （4） 选择的串接定律 F1 （ F2（E） F1 F2(E) 选择的串接律说明 选择条件可以合并 这样一次就可检查全部条件。,（5） 选择与投影的交换律 1)假设: 选择条件F只涉及属性A1，An F (A1,A2, ,An(E) A1,A2, ,An(F(E) 2)假设: F中有不属于A1, ,An的属性B1,Bm A1,A2, ,An ( F (E) A1,A2, ,An(F (A1,A2, ,An,B1,B2, ,Bm(E),（6） 选择与笛卡尔积的交换律 1) 假设：F中涉及的属性都是E1中的属性 F (E1E2)F (E1)E2 2) 假设：F=F1F2，并且F1只涉及E1中的属性，