关系数据理论(上海电力学院).ppt

《关系数据理论(上海电力学院).ppt》由会员分享，可在线阅读，更多相关《关系数据理论(上海电力学院).ppt（68页珍藏版）》请在三一办公上搜索。

1、第四章 关系数据理论(之一),推荐参考书:(美)Abraham Silberschatz Henry F.Korth S.Sudarshan 著 杨冬青 唐世渭等译 机械工业出版社,学习要点:（1）了解数据库逻辑设计中关系模式的异常问题。（2）掌握规范化理论，各种范式及规范化过程。（3）掌握函数依赖和多值依赖的相关理论及推理规则。（4）掌握闭包及计算算法。（5）掌握最小函数依赖集计算算法。（6）掌握候选码求解算法。（7）掌握关系模式分解算法。,内容提要：4.1基本知识点4.2规范化4.3数据依赖公理系统4.4模式分解4.5总结,4.1基本知识点概念回顾关系：描述实体、属性、实体间的联系。从形式

2、上看，它是一张二维表，是所涉及属性的笛卡尔积的一个子集。关系模式：关系名（属性1，属性2，属性n）。例如：学生（学号，姓名，性别，出身年月，系）关系数据库：基于关系模型的数据库，利用关系来描述现实世界。从形式上看，它由一组关系组成。关系数据库的模式：定义这组关系的关系模式的全体。,关系的基本性质（二维表是关系的约束条件）：（1）表中的每一个分量须是不可分的数据项。例如（2）表中的每一列须出自同一个域。（3）行、列无序，但每行须唯一。（4）关系中的任意两个元组不能相同。,问题的提出一、关系数据库逻辑设计（1）目的：针对实际问题，构造出合适的数据模式。（2）数据库逻辑设计的工具关系数据库的规范化理

3、论,二、实例分析例1、某同学设计的学校数据库的一个关系st：,返回,关系模式如下：st(sno,sname,sdept,dname,cname,grade)Sno:学号 sname:学生姓名 sdept:所在系 dname:系主任名 Cname:课程名(不重名)grade：成绩 主码为：(sno,cname)由现实世界的已知事实得知：（1）一个系有若干学生，但一个学生只属于一个系；（2）一个系只有一位系主任。,（3）一个学生可以选修多门课程，每门课程有若干学生选修。（4）每个学生学习每一门课程获得一个成绩。三、这个关系模式存在的问题如下：数据冗余：由于一个学生，可以选修多门课程，导致sname

4、学生姓名,sdept系名、dname系主任名也需重复多次存储。插入异常（Insertion Anomalies）：若一学生，一门课程都未选，该学生的信息将无法插入（因为主码不能为空或部分为空）。（该插入的数据插入不进去）,删除异常（Deletion Anomalies）：当某系的学生全毕业时，系及系主任的信息也一并将删除，无法得到保存。（不该删除的数据不得不删除）更新异常（Update Anomalies）（数据不一致性）：由于数据冗余过多，如对一选了多门课程的一学生的姓名做修改，可能仅修改部分相关的记录，造成了数据不正确，存储的数据不一致。,四、结论：（1）st关系模式不是一个好的模式。（2

5、）“好”的模式：体现客观世界的信息，不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。（3）模式“不好”的原因：由于模式中存在某些数据依赖引起的。（4）解决方法：通过分解关系模式来消除关系模式中不合适的数据依赖。如将st分解为学生信息：学生(sno,sname,sdept)系信息：sd(sdept，dname)学生选课信息：sc(sno,cname,grade),是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系；是现实世界属性间相互联系的抽象；是数据内在的性质；是语义的体现。,数据依赖一、定义数据依赖：实体内部各属性间的联系。,二、数据依赖的分类（1）函数依赖（Functi

6、onal Dependency，简记为FD）（2）多值依赖（Multivalued Dependency，简记为MVD）（3）其他数据依赖（略）,关系模式的形式化定义定义：关系模式由五部分组成，即它是一个五元组：R(U,D,DOM,F)说明：R：关系名；U：组成该关系的属性名集合；D：属性组U中属性所来自的域；DOM：属性到域的映象集合；F：属性间数据的依赖关系集合。,关系模式R（U,D,DOM,F）简化为一个三元组：R当且仅当U上的一个关系r满足F时，r称为关系模式R的一个关系。,函数依赖一、函数依赖定义及相关术语定义1：设有关系模式R(A1,A2,An)或简记R(U)，X，Y是U的子集，r

7、是R的任一可能关系。如果对于r的任意两个元组t1、t2,由t1X=t2X，可导致t1Y=t2Y,则称X函数确定Y，或Y函数依赖于X，记作XY。X称为这个函数依赖的决定属性集(Determinant)。若XY，YX，则记作XY。若Y不函数依赖于X，则记作XY。空集可依赖于任何一个属性集。,实例,二、函数依赖与属性关系属性间的关系（通过取等值体现出来）有3种，但并不是每一种关系中都存在函数依赖。设关系模式R（U），属性集X、Y是U的子集，则有：（1）若X和Y之间是“1：1”关系，则存在函数依赖：XY和YX。如上例中st关系模式中，系名和系主任（若一个系只有一个系主任，一个系主任只对应一个系）则存在

8、函数依赖：sdeptdname或dnamesdept,实例,（2）若X和Y之间是“m：1”关系，则存在函数依赖：XY。如上例中st关系模式中，系名和学生学号（若一个系有若干学生，一个学生只对应一个系），则存在函数依赖：snosdept（3）若X和Y之间是“m：n”关系，则不存在函数依赖。如上例中st关系模式中，课程号和学生学号（若一个课程可被若干学生选修，一个学生可选修多门课程）。snocno或cnosno,实例,说明：1、函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。2、函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。例如“

9、姓名年龄”这个函数依赖只有在不允许有同名人的条件下成立。3、数据库设计者可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖“姓名年龄”成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在，则拒绝装入该元组。,例如:（参见实例1）St(Sno,Sname,Sdept,dname,cname,grade)按前面所给出的语义得出函数依赖为：F Sno Sdept,SnoSname,Sdept dname,(Sno,Cname)Grade,三、平凡函数依赖与非平凡函数依赖定义2：设XY是一个函数依赖，若YX,则称XY是一个平凡函数依赖。若YX，则称XY是一个非平凡函数依赖。例如：在

10、关系SC(Sno,Cno,Grade)中，非平凡函数依赖：(Sno,Cno)Grade 平凡函数依赖：(Sno,Cno)Sno(Sno,Cno)Cno注：平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别声明，我们总是讨论非平凡函数依赖。,四、完全函数依赖和部分函数依赖定义3：设XY是一个函数依赖，并且对于任何XX，XY都不成立，则称XY是一个完全函数依赖。即Y函数依赖于整个X，记作X F Y。若有XX，XY成立，则称Y部分函数依赖于X，记作X P Y。例如：参见例1st(sno,sname,sdept,dname,cname,grade)主码：(sno,cname)snosdept(

11、sno,cname)p sdeptsnograde,cnamegrade(sno,cname)F grade,五、传递函数依赖定义4：设R（U）是一个关系模式，X,Y,ZU,如果XY，YZ且YX，Z-Y，Y-X 成立，则称Z传递函数依赖于X，记作X T Z。注:如果YX，即XY，则Z直接依赖于X。例:在关系St(Sno,sname,Sdept,dname,cname,grade)中，有：Sno Sdept，Sdept dname Sno T dname,4.2 规范化（Normalization）p172-183规范化理论正是用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决

12、插入异常、删除异常、更新异常和数据冗余问题。码定义5：设关系模式R,如果函数依赖XU在R上成立，且不存在任何X X，使得X U也成立(即X F U)，则称X是R的一个候选码（Candidate Key）。主属性（prime atrribute）：候选码中包含的属性。,例,非主属性(非码属性)(Nonprime attribute)：不包含在候选码中的属性。若候选码多于一个,可以选定其中一个为主码（primary key）。定义6：关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外码（Foreign key）。全码（All-key）：关系模式R中整个属性集U都是码。,

13、范式是符合某一种级别的关系模式的集合。用以防止异常的关系和技术称作范式。关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。范式的种类：第一范式(1NF)第二范式(2NF)第三范式(3NF)BC范式(BCNF)Codd和Boyce第四范式(4NF)Fagin第五范式(5NF),范式（Normal Forms）,各种范式之间存在联系：某一关系模式R为第n范式，可简记为RnNF。用途：设计数据库;验证设计结果的合理性，用其指导优化过程。规范化：一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这一转换过程称为规范化。,一、第一范式（1NF）（1）1N

14、F的定义如果一个关系模式R的所有属性都是不可分的基本数据项，则R1NF。（要求属性是原子的）（2）不满足第一范式的数据库模式不能称为关系数据库。（3）但是满足第一范式的关系模式并不一定是一个好的关系模式。（4）第一范式不能排除数据冗余和更新异常等问题，因为存在非主属性部分依赖于码。,实例,二、第二范式（2NF）（1）2NF的定义若R1NF，且每一个非主属性完全函数依赖于码，则R2NF。注：不能部分依赖于码例如:关系模式sc(sno,cno,sname,sdept,grade)主码:(sno,cno)，包含有函数依赖：(sno,cno)F grade snosname snosdept（sno,

15、cno）P sname（sno,cno）P sdept所以，sc2NF,sc1NF,产生冗余及插入、删除、更新异常的原因：sname,sdept部分函数依赖于候选码。解决方法：将SC分解为两个关系模式，以消除部分函数依赖：sc（Sno，Cno，Grade）sx（Sno，sname,sdept）所以：sc2NF,sx2NF,例如:库存(仓库号,设备号,数量,地点)F=(仓库号,设备号)数量,仓库号地点,则该关系属于第几范式?,解答:(仓库号,设备号)地点,存在非主属性对码的部分函数依赖,所以不属于2NF,属于1NF,解决办法:模式分解:库存(仓库号,设备号,数量)仓库(仓库号,地点),P,三、第

16、三范式（3NF）（1）3NF的定义若R2NF，且每一个非主属性都不传递函数依赖于码，则R3NF。注：不能传递函数依赖于码例如:关系模式student(sno,sname,sdept,dept_manager)主码：sno存在函数依赖：snosname,sdept sdeptdept_manager则有传递函数依赖：snodept_manager所以，student 2NF,student 3NF,产生冗余及插入、删除、更新异常的原因：dept_manager传递函数依赖于候选码。解决方法：将student分解为两个关系模式，以消除传递函数依赖：student（sno,sname,sdept）d

17、m（sdept，dept_manager）所以：student3NF,dm3NF,3NF的另一种表达方式:若对F+中所有形如的函数依赖,其中R,R,下面至少有一个成立:是平凡的函数依赖包含候选码-中的每个属性A都包含在R的候选码中,说明：若R3NF，则R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。如果R3NF，则R也是2NF。采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、更新异常等问题。将一个2NF关系分解为多个3NF的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。,四、BC范

18、式（BCNF）（1）BCNF的定义对于关系R，若R1NF，且对于所有非平凡的函数依赖，其决定因素都含候选码，（即若XY且YX时，X必含候选码）则RBCNF。注：若RBCNF 每一个决定属性集（因素）都包含（候选）码;R中的所有属性（主，非主属性）都完全函数依赖于码;R3NF;(但若R3NF,则R不一定BCNF),BCNF的另一种表达方式:若对F+中所有形如的函数依赖,其中R,R,下面至少有一个成立:是平凡的函数依赖包含候选码或者说:如果R是3NF,而且不存在主属性对非主属性的函数依赖,则R是BCNF,例如:关系模式例STC（S，T，C）中，S表示学生姓名，T表示教师姓名，C表示课程名称。语义：

19、每一教师只教一门课，每门课由若干教师教。某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师就确定了所选课的名称。存在函数依赖如下：(S，C)T，(S，T)C，TC候选码:(S,C)或(S,T);S、T、C都是主属性。,因为TC，T不是候选码。所以，STC BCNF，STC3NF。,解决方法：将STC分解为二个关系模式：SC(S，C)BCNF，TC(T，C)BCNF 没有任何属性对码的部分函数依赖和传递函数依赖。最高范式BCNF是基于函数依赖的最高范式；但不是数据库模式设计的最高范式。,S,C,SC,T,C,TC,如果关系模式RBCNF，必定有R3NF。如果R3NF，且R只有一个候

20、选码，则R必属于BCNF。BCNF的关系模式所具有的性质：所有非主属性都完全函数依赖于每个候选码。所有主属性都完全函数依赖于每个不包含它的候选码。没有任何属性完全函数依赖于非码的任何一组属性。（课后阅读）,例:关系模式:管理(仓库号,设备号,职工号)一个仓库可以有多个职工一个职工仅在一个仓库工作每个仓库一种设备仅由一名职工保管,但每名职工可以保管多种设备则:F=职工号仓库号,(仓库号,设备号)职工号问:该关系的码?属于第几范式?,解答:key:(仓库号,设备号)、(职工号,设备号),属于3NF（因为没有非主属性）,但不属于BCNF,四、多值依赖与第四范式（4NF）（了解）1、实例分析例:关系模

21、式Teaching(C,T,B)课程C、教师T 和 参考书B语义：学校的某一门课程由多个教师讲授，每门课使用相同的一套参考书。每个教师可以讲授多门课程，每种参考书可以供多门课程使用。,用非关系的表格来表示：,用关系二维表格来表示teaching：,back,Teaching具有唯一候选码(C，T，B)，即全码。所以TeachingBCNF。Teaching模式中存在的问题（1）数据冗余度大：有多少名任课教师，参考书就要存储多少次。（2）插入操作复杂：当某一课程增加一名任课教师时，该课程有多少本参照书，就必须插入多少个元组。例如：物理课增加一名教师刘东，需要插入三个元组：（物理，刘东，普通物理学

22、）（物理，刘东，光学原理）（物理，刘东，物理习题集）,实例,（3）删除操作复杂：某一门课要去掉一本参考书，该课程有多少名教师，就必须删除多少个元组。（4）修改操作复杂：某一门课要修改一本参考书，该课程有多少名教师，就必须修改多少个元组。产生原因：存在多值依赖的数据依赖。,实例,2、多值依赖（1）定义7：设R(U)是一个属性集U上的一个关系模式，X、Y和Z是U的子集，并且ZUXY，多值依赖 XY成立，当且仅当对R的任一关系r，r在（X，Z）上的每个值对应一组Y的值，这组值仅仅决定于X值而与Z值无关。（设关系模式R（U），X、Y是U的子集，对于R的任一关系r,当一个给定的X值，就有一组Y属性值与之

23、对应，而与其他的属性U-X-Y没有关系。则称“Y多值依赖于X”或“X多值决定Y”，记作XY。）,实例,例如：关系模式 Teaching（C,T,B）对于C的每一个值，T有一组值与之对应，而不论B取何值。即CT。（2）多值依赖的另一等价的形式化定义：在R（U）的任一关系r中，如果存在元组t、s，使得tX=sX，那么就必然存在元组 w，v r，（w，v可以与s，t相同），使得wX=vX=tX，而wY=tY，wZ=sZ，vY=sY，vZ=tZ（即交换s，t元组的Y值所得的两个新元组必在r中），则Y多值依赖于X，记为XY。这里，X，Y是U的子集，Z=U-X-Y。,实例,或者:若,则:对关系模式R(U)

24、上的任意合法关系r,对r中任一元组对t1和t2,若t1=t2,则r中对存在元组t3和t4,使得:t1=t2=t3=t4,t3=t1,t3U-=t2U-t4=t2,t4U-=t1U-,（3）平凡多值依赖和非平凡的多值依赖 对于一个关系模式R，若XY，而Z，Z=U-X-Y,则称XY为平凡的多值依赖。否则称XY为非平凡的多值依赖（4）多值依赖的性质：A、多值依赖具有对称性 若XY，则XZ，其中ZUXY 多值依赖的对称性可以用完全二分图直观地表示出来。,多值依赖对称性完全二分图,多值依赖对称性完全二分图具体实例,B、多值依赖具有传递性 若XY，YZ，则XZ Y。,（5）多值依赖与函数依赖的区别(注意)

25、A、有效性 多值依赖的有效性与属性集的范围有关若XY在U上成立，则在W（X Y W U）上一定成立；反之则不然，即XY在W（W U）上成立，在U上并不一定成立。多值依赖的定义中不仅涉及属性组 X和 Y，而且涉及U中其余属性Z。一般地，在R（U）上若有XY在W（W U）上成立，则称XY为R（U）的嵌入型多值依赖。,函数依赖：只要在R（U）的任何一个关系r中，元组在X和Y上的值满足函数依赖的定义，则函数依赖XY在任何属性集W（X Y W U）上成立。B、若函数依赖XY在R（U）上成立，则对于任何Y Y均有XY 成立。多值依赖XY若在R(U)上成立，不能断言对于任何Y Y有XY 成立。,（6）第四范

26、式（4NF）A、第四范式定义：关系模式R1NF,如果对于R的每个非平凡多值依赖XY（YX），X都含有码，则称R 4NF。注：当F只包含函数依赖时，4NF就是BCNF。但一个BCNF不一定是4NF，而一个4NF必定是BCNF。B、实例：Teaching(C,T,B)候选码（C,T,B）因为存在非平凡的多值依赖CT，且C不是候选码。所以Teaching(C,T,B)4NF。,C、解决方法：用投影分解法把Teaching分解为如下两个关系模式：CT(C,T)4NF CB(C,B)4NF 且 CT，CB是平凡多值依赖。,课堂练习：设关系模式（ABC）上有一个多值依赖AB。如果已知R的当前关系中存在三个

27、元组（a,b1,c1）、（a,b2,c2）、（a,b3,c3）。那么这个关系中至少还应该存在哪些元组？解：（参见多值依赖的另一等价定义）（a,b1,c2）、（a,b2,c1）、（a,b1,c3）、（a,b3,c1）、（a,b2,c3）、（a,b3,c2）,六、（了解）连接依赖与第五范式（5NF又称PJNF）（1）连接依赖A、定义：设R、R1、R2、Rn是关系模式，U、U1、Un分别是R、R1、R2Rn的属性集合，而且U=U1U2Un。如果R的任意关系实例r满足 r=R1(r)R2(r)Rn(r)则称R满足连接依赖，记作(R1,R2,Rn）。B、在上述定义中，若存在一个i使得Ri=R,则对应的连

28、接依赖称为平凡连接依赖。,如一关系模式R的连接依赖（R1，R2）若R的某一个实例r为：R=（a1,a2,ai,ai+1,ai+2,aj,aj+1,an），（b1,b2,bi,ai+1,ai+2,aj,bj+1,bn）R1=（a1,a2,ai,ai+1,ai+2,aj），（b1,b2,bi,ai+1,ai+2,aj）R2=（ai+1,ai+2,aj,aj+1,an），（ai+1,ai+2,aj,bj+1,bn）rR1(r)R2(r)该关系模式不满足连接依赖。,（2）第五范式A、定义：设R，R1，R2，,Rn是关系模式，RiR，F是R上的函数依赖、多值依赖和连接依赖的集合。R称为满足F的第五范式，

29、如果对于F+中的每个连接依赖(R1,R2,Rn)下面至少一条成立：1）(R1,R2,Rn)是平凡连接依赖；2）每个Ri都包含R的一个候选码。,七、规范化小结关系数据库的规范化理论是数据库逻辑设计的工具。一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化。规范化程度可以有多个不同的级别,规范化程度不易过低。,关系模式规范化的基本步骤 1NF 消除非主属性对码的部分函数依赖 2NF 消除非主属性对码的传递函数依赖 3NF 消除主属性对码的部分和传递函数依赖 BCNF 消除非平凡且非函数依赖的多值依赖 4NF,规范化的基本思想：（1）消除不合适的数据依赖；（2）使模式中的各关系模式达到某种程度的“分离”，采用“一事一地”的模式设计原则。（每个规范化的关系只有一个主题。）（3）让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它“分离”出去。（4）所谓规范化实质上是概念的单一化。,（5）不能说规范化程度越高的关系模式就越好。（6）在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式。（7）关系模式的规范化过程是通过对关系模式的分解来实现的。分解不是唯一的。（8）上面的规范化步骤可以在其中任何一步终止。,待续！,