第7章关系数据库理论

1、机械工业出版社n关系数据库理论n关系数据库设计的理论：关系规范化理论和关系模式分解方法n关系数据库操作的理论：关系数据的查询和优化的理论7.1 关系数据模式的规范化理论关系数据模式的规范化理论 7.1.1 关系模式规范化的必要性关系模式规范化的必要性 7.1.2 函数依赖及其关系的范式函数依赖及其关系的范式 7.1.3 多值依赖及关系的第四范式多值依赖及关系的第四范式7.2 关系模式的分解算法关系模式的分解算法7.3 关系系统及查询优化技术关系系统及查询优化技术 n 范式（Normal Form）是指规范化的关系模式。由满足最基本规范化的关系模式叫第一范式，第一范式的关系模式再满足另外一些约束

2、条件就产生了第二范式、第三范式、BC范式等等。一个低一级的关系范式通过模式分解可以转换成若干高一级范式的关系模式的集合，这种过程叫关系模式的规范化。 1. 关系模式应满足的基本要求1) 元组的每个分量必须是不可分的数据项。元组的每个分量必须是不可分的数据项。2) 数据库中的数据冗余应尽可能少。数据库中的数据冗余应尽可能少。3) 关系数据库不能因为数据更新操作而引起数据不一致问关系数据库不能因为数据更新操作而引起数据不一致问题。题。更新异常（更新异常（Update Anomaly） 4) 当执行数据插入操作时，数据库中的数据不能产生插入当执行数据插入操作时，数据库中的数据不能产生插入异常现象。异

3、常现象。插入异常（插入异常（Insert Anomaly） 5) 数据库中的数据不能在执行删除操作时产生删除异常问数据库中的数据不能在执行删除操作时产生删除异常问题。题。删除异常（删除异常（Delete Anomaly） 6) 数据库设计应考虑查询要求，数据组织应合理。数据库设计应考虑查询要求，数据组织应合理。n例：要求设计一个教学管理数据库，希望从该例：要求设计一个教学管理数据库，希望从该数据库中得到学生学号、学生姓名、年龄、性数据库中得到学生学号、学生姓名、年龄、性别、系别、系主任姓名、学生学习的课程和该别、系别、系主任姓名、学生学习的课程和该课程的成绩信息。课程的成绩信息。 n若将此信息

4、要求设计为一个关系，则关系模式若将此信息要求设计为一个关系，则关系模式为：为： 教学教学(学号，姓名，年龄，性别，系名，系主任，学号，姓名，年龄，性别，系名，系主任， 课程名，成绩课程名，成绩)学号姓名年龄性别系名系主任课程名成绩98001李华20男计算机系王民程序设计8898001李华20男计算机系王民数据结构7498001李华20男计算机系王民数据库8298001李华20男计算机系王民电路6598002张平21女计算机系王民程序设计9298002张平21女计算机系王民数据结构8298002张平21女计算机系王民数据库7898002张平21女计算机系王民电路8398003陈兵20男数学系赵敏

5、高等数学7298003陈兵20男数学系赵敏数据结构9498003陈兵20男数学系赵敏数据库8398003陈兵20男数学系赵敏离散数学87n此关系模式存在问题：此关系模式存在问题：n数据冗余大数据冗余大n插入异常插入异常n删除异常删除异常n更新异常更新异常上述的关系模式: 教学教学(学号，姓名，年龄，性别，系名，系主任，课程名，学号，姓名，年龄，性别，系名，系主任，课程名， 成绩成绩). 可以按“一事一地”的原则分解成“学生”、“教学系”和“选课”三个关系，其关系模式为： 学生学生(学号，姓名，年龄，性别，系名称学号，姓名，年龄，性别，系名称)； 教学系教学系(系名，系主任系名，系主任)； 选课

6、选课(学号，课程名，成绩学号，课程名，成绩).1. 关系模式的简化表示法关系模式的简化表示法关系模式的完整表示是一个五元组： RU，D，Dom，F.其中：R为关系名；U为关系的属性集合；D为属性集U中属性的数据域；Dom为属性到域的映射；F为属性集U的数据依赖集。关系模式可以用三元组来为： RU，F.1) 设RU是属性集U上的关系模式，X、Y是U的子集。若对于RU的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而Y上的属性值不等，则称X函数确定Y函数，或Y函数依赖于X函数，记作XY。学号姓名年龄性别系名系主任课程名成绩98001李华20男计算机系王民程序设计8898001李华

7、20男计算机系王民数据结构7498001李华20男计算机系王民数据库8298001李华20男计算机系王民电路6598002张平21女计算机系王民程序设计9298002张平21女计算机系王民数据结构8298002张平21女计算机系王民数据库7898002张平21女计算机系王民电路8398003陈兵20男数学系赵敏高等数学7298003陈兵20男数学系赵敏数据结构9498003陈兵20男数学系赵敏数据库8398003陈兵20男数学系赵敏离散数学87 例如，对于教学关系模式：教学U，F；U=学号，姓名，年龄，性别，系名，系主任，课程名，成绩；F=学号姓名，学号年龄，学号性别，学号系名，系名系主任，(

8、学号，课程名)成绩. XY，但Y X，则称XY是非平凡的函数依赖。 XY，但YX，则称XY是平凡的函数依赖。 若XY，则X叫做决定因素（Determinant），Y叫做依赖因素（Dependent）。 若XY，YX，则记作XY。 若Y不函数依赖于X，则记作X Y。学号学号学号，（学号，性别）学号，（学号，性别） 学号学号为便于理解，不妨假设X和Y均只包含一个属性，分别记为A，B。AB用数学图形表示如下：BBAAA函数决定B，A的每一个值对应B的唯一值A函数不决定B，A的某些值可能对应B的多个值n2) 在RU中，如果XY，并且对于X的任何一个真子集X ，都有X Y，则称Y对X完全函数依赖，记作：

9、XY；若XY，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作： XY。例如，在教学关系模式：(学号，课程名)成绩，(学号，课程名)姓名PFFPn3) 在RU中，如果XY，(Y X)，Y X，YZ，则称Z对X传递函数依赖。传递函数依赖记作X Z。传递例如，在教学模式中，因为：学号系名，系名系主任；所以：学号 系主任。 传递传递 如果关系模式R，其所有的属性均为简单属性，即每个属性都是不可再分的，则称R属于第一范式，记作R1NF。n在任何一个关系数据库系统中，第一范式都是一个最基本的要求。 若R1NF，且每一个非主属性完全依赖于码，则R2NF。在教学模式中： 属性集=学号，姓名，年龄，系名，

10、系主任，课程名，成绩.函数依赖集=学号姓名，学号年龄，学号性别，学号系名， 系名系主任，(学号，课程名)成绩.主码=(学号，课程名). F 非主属性=(姓名，年龄，系名，系主任，成绩)。非主属性对码的函数依赖： (学号，课程名)姓名，(学号，课程名)年龄，(学号，课程号)性别 ， (学号，课程名)系名，(学号，课程名)系主任；(学号，课程名)成绩.显然，教学模式不服从2NF，即：教学2NF。PPPPPFn前面已经讨论了该关系存在数据冗余问题、插入异常、异常和更新异常等问题。n为了消除这些部分函数依赖，可以将T关系分解为： 学生系(学号，姓名，年龄，性别，系名，系主任)；选课（学号，课程名，成绩

11、） 关系模式RU，F中若不存在这样的码X、属性组Y及非主属性Z(Z Y)使得XY、Y X、YZ成立，则称RU，F3NF。可以证明，若R3NF，则每一个非主属性既不部分函数依赖于码，也不传递函数依赖于码。 考查学生_系关系，由于存在：学号系名，系名系主任。则： 学号 系主任。所以学生_系3NF。如果分解为： 学生(学号，姓名，年龄，性别，系名)； 教学系(系名，系主任).显然分解后的各子模式均属于3NF。传递n关系模式RU，F1NF。若XY且Y X时X必含有码，则RU，FBCNF。也就是说，关系模式RU，F中，若每一个决定因素都包含码，则RU，FBCNF。由BCNF的定义可以得到结论，一个满足B

12、CNF的关系模式有：1) 所有非主属性对每一个码都是完全函数依赖。2) 所有的主属性对每一个不包含它的码，也是完全依赖。3) 没有任何属性完全函数依赖于非码的任何一组属性。 BCNF不仅强调其他属性对码的完全的直接的依赖，而且强调主属性对码的完全的直接的依赖，它包括3NF，即RBCNF，则R一定属于3NF。n例如：SNC(SNO,SN,CNO,SCORE)n假如SN无重名。一、一、 函数依赖的所有概念：函数依赖的所有概念：函数依赖、（非）平凡函数依赖、完全部分函数依赖、直接传递函数依赖函数依赖、（非）平凡函数依赖、完全部分函数依赖、直接传递函数依赖二、二、 规范化的过程：规范化的过程：1NF(

13、不可再分割的最小数据单元)消除非主属性对码的部分函数依赖后2NF：消除非主属性对码的传递函数依赖；3NF：消除主属性对码的部分和传递函数依赖BCNF;n 三、三、 规范化是关系到数据库设计的重要概念：规范化是关系到数据库设计的重要概念：n目的：规范化的目的是使结构合理，消除存储异常，使数据冗余尽量小，便于插入、删除和更新。n原则：遵从概念单一化“一事一地”原则，即一个关系模式描述一个实体或实体间的一种联系。规范的实质就是概念单一化。n方法：将关系模式投影分解成两个或两个以上的关系模式。n要求：分解后的关系模式集合应当与原关系模式“等价”，即经过自然联接可以恢复关系而不丢失信息。，并保持属性间合

14、理的联系。n1、设有如下所示的关系、设有如下所示的关系R（码为：课程名）（码为：课程名）问：（问：（1）该关系模式为第几范式？为什么？）该关系模式为第几范式？为什么？（2）是否存在删除操作异常？若存在，则说明在什）是否存在删除操作异常？若存在，则说明在什么情况下发生的？么情况下发生的？（3）将它分解为高一级范式，分解后的关系是如何）将它分解为高一级范式，分解后的关系是如何解决分解前可能存在的删除操作异常问题的？解决分解前可能存在的删除操作异常问题的？n关系关系R课程名 教师名 教师地址C1 王小强 D1 C2 李鸿雁 D2 C3 王小强 D1 C4 张言 D11. 研究多值依赖的必要性研究多值

15、依赖的必要性例如，给定一个关系模式JPW(产品，零件，工序)，其中每种产品由多种零件构成，每个零件在装配时需要多道工序。设产品电视机需要的零件和工序如图所示。 显像管电视机开关电源焊接调试测试装配调试焊接调试设有关系模式RU，U是属性集，X、Y是U的子集。如果R的任一关系，对于X的一个确定值，都存在Y的一组值与之对应，且Y的这组值又与Z=U-X-Y中的属性值不相关，此时称Y多值依赖于X，或X多值决定Y，记为XY。多值依赖具有以下性质：1) 多值依赖具有对称性。即若XY，则XZ，其中Z=U-X-Y。2) 函数依赖可以看作是多值依赖的特殊情况。即若XY，则XY。这是因为当XY时，对X的每一个值x，

16、Y有一个确定的值y与之对应，所以XY。3) 在多值依赖中，若XY且Z=U-X-Y，则称XY为非平凡的多值依赖，否则称为平凡的多值依赖。1. 函数依赖的逻辑蕴含设F是模式RU的函数依赖集，X和Y是属性集U的子集。如果从F中的函数依赖能推出XY，则称F逻辑蕴含XY，或称XY是F的逻辑蕴含。2. Armstrong公理系统(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所

17、蕴含。(2) Armstrong公理的三个推理1) 合并规则：由XY，XZ，有XYZ。2) 伪传递规则：由XY，WYZ，有XWZ。3) 分解规则：由XY及ZY，有XZ。 (1) 函数依赖集闭包F+和属性集闭包XF+的定义定义：在关系模式RU，F中，为F所逻辑蕴含的函数依赖的全体叫做F的闭包，记作F+。定义：设有关系模式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中存

18、在的函数依赖YZ，而AZ，YXF(i)。3) 重复步骤2)。一旦发现XF(i)= XF(i+1)，则XF(i)为所求XF+。n【例7-1】已知关系RU，F，其中U=A，B，C，D，E，F=ABC，BD，CE，ECB，ACB，求(AB)F+。设X=AB XF(0)=AB XF(1)=ABCD XF(2)=ABCDE XF(3)= XF(2)=ABCDE (AB)F+=ABCDE=A，B，C，D，E(1) 最小函数依赖集的定义如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。1) F中任一函数依赖的右部仅含有一个属性。2) F中不存在这样的函数依赖XA，使得F与

19、F-XA等价。3) F中不存在这样的函数依赖XA，X有真子集Z使得F-XAZ-A与F等价。(2) 最小函数依赖集的求法1) 逐一检查F中各函数依赖XY，若Y=A1A2Ak，k2，则用XAj|j=1，2，k来取代XY。2) 逐一检查F中各函数依赖XA，令G=F-XA，若AXG+，则从F中去掉此函数依赖。3) 逐一取出F中各函数依赖XA，设X=B1B2Bm，逐一检查Bi（i=1，2，m），如果A(X-Bi)F+，则以X-Bi取代X。解：1) 根据分解规则把F中的函数依赖转换成右部都是单属性的函数依赖集合，分解后的函数依赖集仍用F表示。 F=AB，AC，BA，BC，CA2) 去掉F中冗余的函数依赖。

20、判断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解：(1)去掉F中冗余的函数依赖。判断ABC是否冗余。设：G1= AB，BA，得：(AB)G1+=AB C (AB)G1+ ABC不冗余判断AB是否冗余。设：G2=

21、 ABC，BA，得：AG2+=A BABG2+ AB不冗余判断BA是否冗余。设：G3= ABC，AB ，得：BG3+=B ABG3+ BA不冗余经过检验后的函数依赖集仍然为F=ABC，AB，BA。(2) 去掉各函数依赖左部冗余的属性。本题只需考虑ABC的情况。方法1：在决定因素中去掉B，若CAF+，则以AC代替ABC。求得：AF+=ABC CAF+ 以AC代替ABC故：Fm=AC，AB，BA方法2：在决定因素中去掉A，若CBF+，则以BC代替ABC。求得：BF+=ABC CBF+ 以BC代替ABC故：Fm=BC，AB，BA1. 关系分解的无损连接性关系分解的无损连接性 设关系模式R，如果把它分

22、解为两个（或多个）子模式R1和R2，相应一个R关系中的数据就要被分成R1 、R2两个（或多个）子表。假如将这些子表自然连接，即进行R1R2操作，得到的结果与原来关系中的数据一致，信息并没有丢失，则称该分解具有无损连接性，否则如果RR1R2，则称该分解不具有无损连接性。2. 判断分解成两个关系具有无损连接性的方法判断分解成两个关系具有无损连接性的方法定理：RU，F的一个分解= R1U1，F1，R2U2，F2具有无损连接性的充分必要条件是： U1U2U1-U2F+. 或 U1U2U2-U1F+.3. 判断分解保持函数依赖的方法判断分解保持函数依赖的方法设U，F的分解=R1U1，F1，R1U2，F2

23、，RkUK，FK，若F+=(Fi)+，则称分解保持函数依赖。 n【例7-5】关系模式R=CITY，ST，ZIP，其中CITY为城市，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) 检查分解是否保持函数依赖求得：R1(F)=；R2(F)= ZIPCITY. R1(F)R2(F)= ZIPCITYF+. n 该分解不保持函数依赖。 1. 将

24、关系模式转化为3NF的保持函数依赖的分解1) 对RU，F中的F进行极小化处理。处理后的函数依赖集仍用F表示。2) 找出不再在F中出现的属性，把这样的属性构成一个关系模式，并把这些属性从U中去掉。3) 如果F中有一个函数依赖涉及R的全部属性，则R不能再分解。4) 如果F中含有XA，则分解应包含模式XA，如果XA1，XA2，XAn均属于F，则分解应包含模式XA1A2An。【例7-6】设关系模式RU，F，U=C，T，H，R，S，G，X，Y，Z，F=CT，CSG，HRC，HSR，THR，CX，将R分解为3NF，且保持函数依赖。解：设该函数依赖集已经是最小化的，则分解为： =YZ，CTX，CSG，HRC

25、，HSR，THR.对于给定的关系模式RU，F，将其转换为3NF，且既具有无损连接性又能保持函数依赖的分解算法为：1) 设X是RU，F的码，RU，F先进行保持函数依赖的分解，结果为= R1U1，F1，R2U2，F2，RkUk，Fk，令=R*X，Fx。2) 若有某个Ui，X Ui，将R*X，Fx从中去掉，就是所求的分解。【例7-7】有关系模式RU，F，U=C，T，H，R，S，G，F=CT，CSG，HRC，HSR，THR，将R分解为3NF，且既具有无损连接性又能保持函数依赖。解：求得关系模式R的码为HS，它的一个保持函数依赖的3NF为： =CT，CSG，HRC，HSR，THR. HSHSR = CT

26、，CSG，HRC，HSR，THR为满足要求的分解。 1) 令= RU，F。 2) 检查中各关系模式是否均属于BCNF。若是，则算法终止。 3) 假设中RiUi，Fi不属于BCNF，那么必定有XAFi+，(AX)，且X非Ri的码。对Ri进行分解：=S1，S2，US1=XA，US2= Ui-A，以代替RiUi，Fi，返回第2)步。【例7-8】关系模式RU，F，U=CTHRSG，F= CT，HRC， HTR，CSG，HSR，把R分解成具有无损连接的BCNF。解：令= CTHRSG1) 由于R的码为HS，选择CSG分解。得出：=S1，S2.其中：S1=CSG， F1= CSG； S2=CTHRS， F2= CT，HRC，HTR，HSR.S2不服从BCNF，需要继续分解。2) 对S2分解。S2的码为HS，选择CT分解。得出：= S1，S3，S4.其中：S3=CT， F3= CT； S4=CHRS， F4= HRC，HSR.S4不服从BCNF，还需要继续分解。3) 对S4分解。码为HS，选择HRC分解：= S1，S3，S5，S6.其中：S5=HRC， F5= HRC； S6=HRS， F6=HSR.4) 最后的分解为：=CSG，CT，HRC，HRS. n现有关系数据库如下：现有关系数据库如下：学号（学号（snosno）姓名姓名(sn