《关系数据理论》PPT课件.ppt

数据库系统概论,第六章 关系数据理论,主要内容,6.1问题的提出6.2 规范化6.3 数据依赖的公理系统6.4 模式的分解,6.1 问题的提出,一、关系数据库逻辑设计定义：针对具体问题，如何构造一个适合于它的数据模式数据库逻辑设计的工具关系数据库的规范化理论,二、引例：数据模式“好”与“不好”,例：建立描述学校教务的数据库，涉及的对象如下：学生的学号（Sno）、学生的姓名（Sname）、所在系（Sdept）、系主任姓名（Mname）、课程号（Cno）、成绩（Grade）对象间联系：1.一个系有若干学生，一个学生只属于一个系；2.一个系只有一名主任；3.一个学生可以选修多门课程，每门课程有若干学生选修；4.每个学生所学的每门课程都有一个成绩。,引例：数据模式“好”与“不好”(续),第一种设计方案：使用单一的关系模式：Student（Sno,Sname,Sdept,Mname,Cno,Grade）思考：确定表的主键。,主键：Sno，Cno,下面给出该方案的一个实例：,存在以下问题：数据冗余太大更新异常插入异常删除异常,结论：该方案“不好”,引例：数据模式“好”与“不好”(续),第二种设计方案：使用三个关系模式：S（Sno,Sname,Sdept,）SC（Sno,Cno,Grade）DEPT（Sdept,Mname）,该方案解决了方案一中的问题，因此，该方案“好”,三、关系数据库规范化理论的内容,数据依赖范式模式设计（模式分解）,四、关系模式的简化表示,关系模式由五部分组成，即它是一个五元组：R(U,D,DOM,F)R：关系名U：组成该关系的属性名集合D：属性组U中属性所来自的域DOM：属性向域的映象集合F：属性间数据的依赖关系集合在规范化理论中，简化为一个三元组：R（U,F）,6.2 规范化6.2.1 函数依赖,函数依赖例如：“学号”确定之后，学生姓名就被唯一地确定；Sno，Cno确定之后，成绩就被唯一地确定；这种依赖关系类似于数学中的函数y=f(x)，因此，称为函数依赖。,Student,一、函数依赖定义,定义6.1 设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称“X函数确定Y”或“Y函数依赖于X”，记作XY。X称为这个函数依赖的决定属性集(Determinant)。,思考：写出Student中的函数依赖。Student（Sno,Sname,Sdept,Mname,Cno,Grade）,F=Sno Sname,Sno Sdept,Sdept Mname,（Sno,Cno）Grade，,说明：,函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。例如：姓名年龄这个函数依赖只有在不重名的条件下才成立,函数依赖例题,例:S(Sno,Sname,Ssex,Sage,Sdept)假设不允许重名，则有:F=Sno Ssex，Sno Sage，Sno Sdept，Sname Ssex，Sname Sage，Sname Sdept，Sno Sname 若XY，并且YX,则记为XY。若Y不函数依赖于X,则记为X Y，例如：Ssex Sage,二、函数依赖的分类,可以从不同角度分类：平凡函数依赖与非平凡函数依赖完全函数依赖与部分函数依赖直接函数依赖与传递函数依赖,1、平凡函数依赖与非平凡函数依赖,如果XY，但Y X，则称XY是平凡的函数依赖若果XY，但Y X,则称XY是非平凡的函数依赖例如：Student（Sno,Sname,Sdept,Mname,Cno,Grade）非平凡的函数依赖：Sno Sname Sdept Mname（Sno,Cno）Grade平凡的函数依赖：Sno Sno,（Sno,Sname）Sname,平凡函数依赖与非平凡函数依赖（续）,对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别声明，我们总是讨论非平凡函数依赖。,2、完全函数依赖与部分函数依赖,如果XY，并且对于X的任何一个真子集X，都有X Y,则称Y完全函数依赖于X，记作X Y。若XY，但Y不完全函数依赖于X，则称Y部分函数依赖于X，记作X P Y。,例如：Student（Sno,Sname,Sdept,Mname,Cno,Grade）指出下面的函数依赖哪些是完全的，哪些是部分的：Sno Sname（Sno,Cno）Grade（Sno,Sname）Sdept,直接函数依赖与传递函数依赖,如果XY，YZ，且Y X，YX，则称Z传递函数依赖于X。例如：Student（Sno,Sname,Sdept,Mname,Cno,Grade）因为Sno Sdept，Sdept Mname 所以存在传递依赖Sno Mname注:如果XY，则Z直接依赖于X。,6.2.2 码,若K U，则K称为R的一个侯选码（Candidate Key）。若关系模式R有多个候选码，则选定其中的一个做为主码（Primary key）。,一些概念：候选码主码主属性非主(码)属性超键,包含候选码的属性组称为超键，即:候选码超键例如，Student（Sno,Sname,Sdept,Mname,Cno,Grade）候选键：Sno，Cno超键：Sno，Cno，Sname、Sno，Cno，Sdept等等,6.2.3 范式,范式是符合某一种级别的关系模式的集合。关系必须满足一定的要求。满足不同程度要求的为不同范式。范式的种类：第一范式(1NF)第二范式(2NF)第三范式(3NF)BC范式(BCNF)第四范式(4NF)第五范式(5NF),问题越少,6.2.3 范式,各种范式之间存在联系，如右图所示。某一关系模式R为第n范式，可简记为RnNF。一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程叫做规范化。,1NF,2NF,3NF,4NF,5NF,1NF,1NF的定义如果一个关系模式R的所有属性都是不可分的基本数据项，则R1NF。第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。但是满足第一范式的关系模式并不一定是一个好的关系模式。,6.2.4 2NF,2NF的定义如果R1NF，且每一个非主属性完全函数依赖于码，则，R2NF。,2NF（续）,例:关系模式S-L-C(Sno,Sdept,Sloc,Cno,Grade)其中，Sloc为学生住处，假设每个系的学生住在同一个地方。主键：Sno,Cno 函数依赖包括：F=(Sno,Cno)f Grade，Sno Sdept，Sno Sloc，Sdept Sloc,指出主属性和非主属性是2NF吗？为什么？,2NF（续）,S-L-C满足第一范式。非主属性Sdept和Sloc部分函数依赖于码(Sno,Cno)S-L-C不是2NF，存在诸多问题。,2NF（续）,解决方法：投影分解,2NF（续）,SLC分解为两个关系模式，以消除这些部分函数依赖 SC（Sno，Cno，Grade）SL（Sno，Sdept，Sloc）思考：分别指出两个表的主键。,第二范式（续）,采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。,课堂练习1：,例如：Student（Sno,Sname,Sdept,Mname,Cno,Grade）主键：Sno,Cno其上的函数依赖集合如下：F=Sno Sname,Sno Sdept,Sdept Mname,（Sno,Cno）Grade1、指出主属性和非主属性2、该关系是否属于2NF？为什么？如果不是，请将其分解为一组2NF关系模式。,课堂练习1答案：,将Student（Sno,Sname,Sdept,Mname,Cno,Grade）分解为一组2NF模式：SC(Sno,Cno,Grade)主键：Sno，CnoSD(Sno,Sname,Sdept,Mname)主键：Sno,6.2.5 3NF,3NF的定义如果R 是2NF，且每个非主属性都不传递依赖于R的候选码，则R属于3NF。,3NF（续）,分析下面的两个2NF，它们是不是属于3NF。SC（Sno，Cno，Grade）SL（Sno，Sdept，Sloc）,3NF（续）,解决方法 采用投影分解法，把SL分解为两个关系模式，以消除传递函数依赖：SD（Sno，Sdept）DL（Sdept，Sloc）SD的码为Sno，DL的码为Sdept。,3NF（续）,这样S-L-C(Sno,Sdept,Sloc,Cno,Grade)就分解成为一组3NF模式SC（Sno，Cno，Grade）SD（Sno，Sdept）DL（Sdept，Sloc）,3NF（续）,若R3NF，则R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。如果R3NF，则R也是2NF。采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。将一个2NF关系分解为多个3NF的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。,课堂练习2：,将Student（Sno,Sname,Sdept,Mname,Cno,Grade）分解为一组2NF模式：SC(Sno,Cno,Grade)SD(Sno,Sname,Sdept,Mname)判断上述两个2NF是否是3NF，如果不是请分解。,课堂练习2答案：,SC是3NF SD不是3NF 将SD分解为S（Sno,Sname,Sdept）和D（Sdept，Mname）这样，Student（Sno,Sname,Sdept,Mname,Cno,Grade）分解为一组3NF模式：SC(Sno,Cno,Grade)S（Sno,Sname,Sdept）D（Sdept，Mname）,小结：2NF和3NF都是对非主属性的要求，2NF要求每一个非主属性完全函数依赖于码；3NF要求每一个非主属性既不部分依赖于码也不传递依赖于码。,6.2.6 BCNF,BCNF的定义R 1NF，若XY且Y X 时X必含有码，则，RBCNF。说明：BCNF不仅对非主属性有要求，而且也对主属性有要求；每一个函数依赖的“决定属性集”必须是超键。,BCNF（续）,S-L-C(Sno,Sdept,Sloc,Cno,Grade)已经分解成为一组3NF模式SC（Sno，Cno，Grade）key:Sno,Cno F=(Sno,Cno)GradeSD（Sno，Sdept）key:Sno F=Sno SdeptDL（Sdept，Sloc）key:Sdept F=Sdept Sloc判断该模式集中的每个模式是不是同时满足BCNF？,答：三个模式都满足BCNF.,BCNF（续）,如果一个关系模式只有两个属性构成，则该关系模式一定属于BCNF。证明：R(A,B)BCNF,R上的函数依赖集可能有四种情况：1、F=A B，此时，A是候选码，函数依赖的“决定属性集”是超键，因此R BCNF,2、F=B A，此时，B是候选码，函数依赖的“决定属性集”是超键，因此R BCNF,3、F=A B，B A，此时，A、B都是候选码，每个函数依赖的“决定属性集”是超键，因此R BCNF,4、A，B是候选码，则不存在非平凡的函数依赖，因此R BCNF,结论：R(A,B)BCNF,课堂练习3：,Student（Sno,Sname,Sdept,Mname,Cno,Grade）已经分解为一组3NF模式：SC(Sno,Cno,Grade)S（Sno,Sname,Sdept）D（Sdept，Mname）对于该组模式：1、指出每个模式的主键，写出其函数依赖集。2、确定每个模式是否同时满足BCNF。,BCNF（续）,例7、关系模式SJP(S,J,P)中，S是学生学号，J是课程号，P表示名次（没有并列名次），每一个学生选修每门课程的成绩有一定的名次，由语义可得到函数依赖集F如下：F=（S,J）P，（J,P）S 思考：指出该关系模式的候选码指出主属性、非主属性该关系模式是否是3NF？该关系模式是否是BCNF？,有两个：（S,J），（J,P）,主属性：S、J、P；没有非主属性,SJP 3NF,SJP BCNF,BCNF（续）,例8、关系模式STJ(S,T,J)中，S是学生学号，T表示教师编号，J是课程号，每个教师只教一门课，每门课有若干教师讲授，某一学生选定某门课，就对应一个固定的教师。由语义可得到函数依赖集F如下：F=（S,J）T，（S,T）J,T J 思考：指出该关系模式的候选码指出主属性、非主属性该关系模式是否是3NF？该关系模式是否是BCNF？,有两个：（S,J），（S,T）,主属性：S、J、P；没有非主属性,SJP 3NF,规范化小节,关系模式规范化的基本步骤 1NF 消除非主属性对码的部分函数依赖 2NF 消除非主属性对码的传递函数依赖 3NF 消除主属性对码的部分和传递函数依赖 BCNF,规范化小节（续）,说明：不能说规范化程度越高的关系模式就越好在设计数据库模式结构时，必须对现实世界的实际情况和用户应用需求作进一步分析，确定一个合适的、能够反映现实世界的模式上面的规范化步骤可以在其中任何一步终止,第六章 关系数据理论,6.1 数据依赖6.2 规范化6.3 数据依赖的公理系统6.4 模式的分解,6.3 数据依赖的公理系统,逻辑蕴含定义6.11 对于满足一组函数依赖 F 的关系模式R，其任何一个关系r，若函数依赖XY都成立,则称F逻辑蕴含X Y 例如：已知R(X,Y,Z)，F=XY，YZ,则 XZ成立，XZ被F逻辑蕴含。,Armstrong公理系统,一套推理规则，是模式分解算法的理论基础用途从一组函数依赖求得蕴含的函数依赖求给定关系模式的码,1.Armstrong公理系统,关系模式R 有以下的推理规则：Al.自反律（Reflexivity）：若Y X U，则X Y为F所蕴含。A2.增广律（Augmentation）：若XY为F所蕴含，且Z U，则XZYZ为F所蕴含。A3.传递律（Transitivity）：若XY及YZ为F所蕴含，则XZ为F所蕴含。注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F,证明,(2)增广律:若XY为F所蕴含，且Z U，则XZYZ 为F所蕴含。证：设XY为F所蕴含，且Z U。设R 的任一关系r中任意的两个元组t，s；若tXZ=sXZ，则有tX=sX和tZ=sZ；由XY，于是有tY=sY，所以tYZ=sYZ，所以XZYZ为F所蕴含.增广律得证。,2.导出规则,1.根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：合并规则：由XY，XZ，有XYZ。伪传递规则：由XY，WYZ，有XWZ。分解规则：由XYZ，有XY、XZ。,3.函数依赖集闭包,定义6.l2 在关系模式R中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包，记为F+。说明：F+是R上的全部函数依赖。,F的闭包,F+计算是NP完全问题，F+是R上的全部函数依赖。F+=X,Y,Z,XY,XZ,YZ,XYZ,X X,Y Y,Z Z,XY X,XZ X,YZ Y,XYZ X,X Y,Y Z,XY Y,XZ Y,YZ Z,XYZ Y,X Z,Y YZ,XY Z,XZ Z,YZ YZ,XYZ Z,X XY,XY XY,XZ XY,XYZ XY,X XZ,XY YZ,XZ XZ,XYZ YZX YZ,XY XZ,XZ YZ,XYZ XZ,X XYZ,XY XYZ,XZ XYZ,XYZ XYZ,R（X,Y,Z）,F=X Y,Y Z,属性组的闭包,定义6.13 设F为属性集U上的一组函数依赖，X U，XF+=A|XA能由F 根据Armstrong公理导出，XF+称为属性集X关于函数依赖集F 的闭包。,求闭包的算法,算法6.l 求属性集X（X U）关于U上的函数依 赖集F 的闭包XF+输入：X，F输出：XF+步骤：（1）令X（0）=X，i=0（2）求B，YB，其中Y X且 B X；（3）X（i+1）=BX（i）,算法6.l,（4）判断X（i+1）=X（i）吗?（5）若相等或X（i）=U,则X（i）就是XF+,算法终止。（6）若否，则 i=i+l，返回第（2）步。对于算法6.l，令ai=|X（i）|，ai 形成一个步长大于1的严格递增的序列，序列的上界是|U|，因此该算法最多|U|-|X|次循环就会终止。,U=A,B,C,D;F=A B,BC D;计算AF+=AB,例子,B,AF+=A，B,U=A,B,C,D;F=A B,BC D;计算CF+,例子,CF+=C,U=A,B,C,D;F=A B,BC D;计算(AC)F+,课堂练习1,(AC)F+=A,B,C,D,B,D,R(A,B,C,D)，F=A B,BC D;问：AC D是否在R上成立？,判断一个函数依赖在R上是否成立,由于(AC)F+=A,B,C,D，所以AC D在R上成立。,第一种解决方法：计算F+，看看AC D是否在其中。该方法计算量大，不可行。,第二种解决方法：如果AC D成立，则D一定属于(AC)F+,因此，首先计算(AC)F+，如果D(AC)F+，则成立，否则，不成立。,关于闭包的引理,引理6.2 设F为属性集U上的一组函数依赖，X，Y U，XY能由F 根据Armstrong公理导出的充分必要条件是Y XF+用途 将判定XY是否能由F根据Armstrong公理导出的问题，就转化为求出XF+，判定Y是否为XF+的子集的问题,课堂练习2,已知关系模式R，其中U=A，B，C，D，E；F=ABC，BD，CE，ECB，ACB。ABE是否成立？,由于(A,B)F+=A,B,C,D,E，所以ABE成立。,内容回顾,以上详细讲解了：函数依赖 规范化,作业：,本章习题：1、2,Thank You!,