大学计算机系数据库课件--第6讲关系数据理论

1、第六讲 关系数据理论关系数据理论关系数据理论关系数据理论关系数据理论 关系数据理论关系数据理论问题的提出问题的提出 数据依赖是一种特殊的约束，定义数据依赖是一种特殊的约束，定义属性值间的相的相互关连（互关连（主要体现于值的相等与否）。）。 一个关系内部一个关系内部属性与属性之间的约束关系；的约束关系； 现实世界属性间相互联系的抽象；现实世界属性间相互联系的抽象； 数据内在的性质；数据内在的性质； 语义的体现。的体现。问题的提出（续）问题的提出（续）v 数据依赖的类型 函数依赖函数依赖 多值依赖多值依赖 连接依赖连接依赖 包含依赖包含依赖 其他其他问题的提出（续）问题的提出（续）例例1 创建关系

2、模式创建关系模式sdc(Sno, Sname, dno, dmanager,cname,grade)。单一单一的关系模式的关系模式 ： sdc(U, F), U: 属性集属性集 F：函数依：函数依赖集赖集U Sno, Sname, dno, dmanager, cname, grade F Sno dno, Sno Sname, dno dmanager, (Sno, Cname) grade 存在的问题：数据冗余、操作（增、删、改）异常。数据冗余、操作（增、删、改）异常。问题的提出（续）问题的提出（续）由存在于模式中的由存在于模式中的某些数据依赖某些数据依赖引起的。引起的。通过通过分解分解关

3、系模式来消除其中不合适的数据依关系模式来消除其中不合适的数据依赖。赖。 如：将单一的关系模式分成如：将单一的关系模式分成3个关系模式：个关系模式： S（Sno，Sname, dno，Sno dno）; S_C（Sno，Cname，Grade，（，（Sno，Cname） Grade）; D（dno，dmanager，dnodmanager）;问题的提出（续）问题的提出（续）关系数据理论关系数据理论规范化规范化 是是用来改造关系模式，通过分解关系模用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除式来消除其中不合适的数据依赖，以解决插入异常、删除异常、更新异常和数据

4、冗余问题。异常、更新异常和数据冗余问题。规范化（续）规范化（续）定义 设设R(U)是一个属性集是一个属性集U上的关系模式，上的关系模式，X和和Y是是U的子集。的子集。 若对于若对于R(U)的的任意任意一个可能的关系一个可能的关系r，r中不可能存在两个元组在中不可能存在两个元组在X上的属性值相等，而在上的属性值相等，而在Y上的属性值不等，上的属性值不等， 则称则称 “X函数确定Y” 或或 “Y函数依赖于X”，记作，记作X Y。 （X为决定因素）为决定因素） 所有关系实例均要满足；所有关系实例均要满足； 语义范畴的概念；语义范畴的概念； 数据库设计者可以对现实世界作强制的规定。数据库设计者可以对现

5、实世界作强制的规定。规范化（续）规范化（续） 非平凡的函数依赖非平凡的函数依赖 平凡的函数依赖平凡的函数依赖 完全函数依赖完全函数依赖 部分函数依赖部分函数依赖 传递函数依赖传递函数依赖规范化（续）规范化（续） 范式是符合某一种级别的关系模式的集合。范式是符合某一种级别的关系模式的集合。 关系数据库中的关系必须满足一定的要求。满足不同关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。程度要求的为不同范式。 范式的种类：范式的种类： 第一范式第一范式(1NF)、第二范式、第二范式(2NF)、第三范式、第三范式(3NF)、BC范式范式(BCNF)、第四范式、第四范式(4NF)等。

6、等。规范化（续）规范化（续）- 关系模式的基本要求关系模式的基本要求 如果如果一个关系模式一个关系模式R的所有属性都是的所有属性都是不可分的基本数不可分的基本数据项据项，则，则R1NF。分析：分析：关系模式关系模式 sdc(Sno, Sname, dno, dmanager, cname, grade) 1NF 主码主码: (Sno, Cname) (Sno, Cname) dno 存在：存在：非主属性非主属性(dno)对码对码(sno,cname)的的部分部分函数依函数依赖！赖！规范化（续）规范化（续）定义 若若R1NF，且每一个，且每一个非主属性非主属性完全完全函数依赖于码函数依赖于码，则

7、，则R2NF。例例：sdc(Sno,Sname,dno,dmanager,cname,grade) 2NF 分解后：分解后：sc（Sno， Cname， Grade） 2NF sd（Sno，sname, dno， dmanager） 2NF问题：问题：将一个将一个1NF关系分解为多个关系分解为多个2NF的关系，并不能完的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。全消除关系模式中的各种异常情况和数据冗余。 （对（对 sd 关系模式进行分析！）关系模式进行分析！）规范化（续）规范化（续）2NF关系模式关系模式sd(sno,sname, dno, dmanager)中中函数依赖：函数依

8、赖： ( snodno , dno dmanager ) sno dmanager SD中存在中存在非主属性非主属性(dmanager)对码的对码的传递传递函数依赖函数依赖！ 这种函数依赖是导致冗余和异常的直接原因；这种函数依赖是导致冗余和异常的直接原因； 应设法消除关系模式中非主属性对码的传递函数依赖。应设法消除关系模式中非主属性对码的传递函数依赖。规范化（续）规范化（续）定义 关系模式关系模式R 中若不存在这样的码中若不存在这样的码X、属性、属性组组Y及非主属性及非主属性Z（Z Y）, 使得使得XY，YZ成立，成立，Y X，则称，则称R 3NF。n 若若R3NF，则每一个，则每一个既不部分

9、依赖既不部分依赖于码于码也也不传递依赖不传递依赖于码。于码。 上例中，上例中，SD 3NF 采用投影分解法，把采用投影分解法，把SD分解为两个关系模式，消除传递依赖：分解为两个关系模式，消除传递依赖： s（sno，sname, dno） d（dno, dmanager） s的码为的码为sno， d的码为的码为dno。n分解后的关系模式分解后的关系模式s与与d中不再存在传递依赖，均属于中不再存在传递依赖，均属于 3NF。规范化（续）规范化（续） 例题分析例题分析 关系模式关系模式STJ( S, T, J )，S表示学生，表示学生，T表示教师，表示教师，J表示课程。表示课程。应用语义：应用语义：每

10、个教师只教一门课；每个教师只教一门课；每门课可以有多个教师；每门课可以有多个教师；每个学生选定某门课，就对应一个固定的教师。每个学生选定某门课，就对应一个固定的教师。函数依赖：函数依赖： (S，J) T，(S，T) J，T J， 找出候选码！找出候选码！ 规范化（续）规范化（续）学生学生教师教师课程课程S1T1J1S1T2J2S2T3J1S3T1j1S4T4j1S2T5J2S3T2j2S4T5j2存在异常！存在异常！主属性存在对主属性存在对码的部分或传码的部分或传递依赖！递依赖！规范化（续）规范化（续）关系模式关系模式R1NF，若，若XY且且Y X时时X必含有码，则必含有码，则R BCNF。n

11、等价于：每一个决定属性因素都包含码。等价于：每一个决定属性因素都包含码。n若若RBCNF ：所有非主属性对每一个码都是完全函数依赖；所有非主属性对每一个码都是完全函数依赖；所有的主属性对每一个不包含它的码，也是完全函数依赖；所有的主属性对每一个不包含它的码，也是完全函数依赖；没有任何属性完全函数依赖于非码的任何一组属性。没有任何属性完全函数依赖于非码的任何一组属性。nR BCNF R 3NF规范化（续）规范化（续）n STJ3NF 没有任何非主属性对码传递依赖或部分依赖！没有任何非主属性对码传递依赖或部分依赖！ n STJBCNF T是决定因素（是决定因素（ T J ），），T不包含码。不包含

12、码。n 解决方法：解决方法：将将STJ分解为二个关系模式：分解为二个关系模式： ST(S，T) BCNF， TJ(T，J) BCNF 例题分析 学校中某一门课程由多个教师讲授，他们使用相同的学校中某一门课程由多个教师讲授，他们使用相同的一套参考书。每个教员可以讲授多门课程，每种参考书可以一套参考书。每个教员可以讲授多门课程，每种参考书可以供多门课程使用。供多门课程使用。课课 程程 C教教 员员 T参参 考考 书书 B 物理物理数学数学 计算数学计算数学李李 勇勇王王 军军 李李 勇勇张张 平平 张张 平平 周周 峰峰 普通物理学普通物理学光学原理光学原理 物理习题集物理习题集数学分析数学分析微

13、分方程微分方程高等代数高等代数数学分析数学分析. 非规范化关系非规范化关系普通物理学普通物理学光学原理光学原理物理习题集物理习题集普通物理学普通物理学光学原理光学原理物理习题集物理习题集数学分析数学分析微分方程微分方程高等代数高等代数数学分析数学分析微分方程微分方程高等代数高等代数李李 勇勇李李 勇勇李李 勇勇王王 军军王王 军军王王 军军李李 勇勇李李 勇勇李李 勇勇张张 平平张张 平平张张 平平 物物 理理物物 理理物物 理理物物 理理物物 理理物物 理理数数 学学数数 学学数数 学学数数 学学数数 学学数数 学学 参考书B教员T课程C规范化（续）规范化（续） 用二维表表示Teaching

14、规范化（续）规范化（续） TeachingBCNF Teaching具有唯一候选码具有唯一候选码(C，T，B)， 即全码即全码 Teaching模式中存在的问题：模式中存在的问题：(1) 数据冗余度大数据冗余度大 (2) 插入操作复杂插入操作复杂(3) 删除操作复杂删除操作复杂(4) 修改操作复杂修改操作复杂 存在存在多值依赖！多值依赖！规范化（续）规范化（续）定义：设设R(U)是一个属性集是一个属性集U上的一个关系模式，上的一个关系模式， X、 Y和和Z是是U的子集，并且的子集，并且ZUXY。关系模式。关系模式R(U)中中多值依赖多值依赖 X Y 成立，当且仅当对成立，当且仅当对R(U)的的

15、任一关系任一关系r，给定的一对（，给定的一对（x，z）值，有一组）值，有一组Y的值，这组值仅由的值，这组值仅由x值决定，而与值决定，而与z值无关。值无关。规范化（续）规范化（续）F 平凡多值依赖和非平凡的多值依赖u若若XY，而，而Z，则称，则称 XY 为为平凡的多值依赖；平凡的多值依赖；u 否则称否则称 XY为为 非平凡的多值依赖。非平凡的多值依赖。F多值依赖的性质（1）多值依赖具有对称性）多值依赖具有对称性 若若XY，则，则XZ，其中，其中ZUXY（2）多值依赖具有传递性）多值依赖具有传递性 若若XY，YZ， 则则XZ Y（3）函数依赖是多值依赖的特殊情况）函数依赖是多值依赖的特殊情况 若若

16、XY，则，则XY。（4）若）若XY，XZ，则，则XY Z。（5）若）若XY，XZ，则，则XYZ。（6）若）若XY，XZ，则，则XY-Z，XZ -Y。规范化（续）规范化（续）定义：关系模式关系模式R1NF，如果对于，如果对于R的每个非的每个非平凡多值依赖平凡多值依赖XY（Y X），），X都含有码，则都含有码，则R4NF。如果如果R 4NF， 则则R BCNFn不允许不允许有非平凡且非函数依赖的有非平凡且非函数依赖的多值依赖多值依赖n允许允许的非平凡多值依赖必须存在对应的的非平凡多值依赖必须存在对应的函数依赖函数依赖规范化（续）规范化（续）上例：上例： Teaching(C,T,B) 4NF 因为

17、：存在非平凡的多值依赖因为：存在非平凡的多值依赖CT，且，且C不是码。不是码。n 用投影分解法把用投影分解法把Teaching分解为如下两个关系模式分解为如下两个关系模式： CT(C, T) 4NF CB(C, B) 4NF CT， CB是平凡多值依赖。是平凡多值依赖。 规范化（续）规范化（续） 1NF 消除非主属性对码的部分函数依赖消除非主属性对码的部分函数依赖消除决定属性消除决定属性 2NF集非码的非平集非码的非平 消除非主属性对码的传递函数依赖消除非主属性对码的传递函数依赖凡函数依赖凡函数依赖 3NF 消除主属性对码的部分和传递函数依赖消除主属性对码的部分和传递函数依赖 BCNF 消除非

18、平凡且非函数依赖的多值依赖消除非平凡且非函数依赖的多值依赖 4NF关系数据理论关系数据理论数据依赖的公理系统数据依赖的公理系统定义1：对于满足一组函数依赖对于满足一组函数依赖 F 的关系模式的关系模式R ，其任何一个关系，其任何一个关系r，若函数依赖，若函数依赖XY都成立都成立, （即（即r中任中任意两元组意两元组t，s，若，若 tX = sX，则，则 tY = sY ），则称，则称 F 逻辑蕴含逻辑蕴含X Y。数据依赖的公理系统（续）数据依赖的公理系统（续）v Armstrong公理系统 对于关系模式对于关系模式R ，有以下的推理规则：有以下的推理规则： A1.自反律自反律：若：若Y X U

19、，则，则X Y为为F所蕴含。所蕴含。 A2.增广律增广律：若：若XY为为F所蕴含，且所蕴含，且Z U，则，则XZYZ为为F所蕴含。所蕴含。 A3.传递律传递律：若：若XY及及YZ为为F所蕴含，则所蕴含，则XZ为为F所蕴含。所蕴含。1. 根据根据A1，A2，A3这三条推理规则可以得到下面三条推理规这三条推理规则可以得到下面三条推理规则：则： 合并规则合并规则：由：由XY，XZ，有，有XYZ。 （A2， A3） 伪传递规则伪传递规则：由：由XY，WYZ，有，有XWZ。 （A2， A3） 分解规则分解规则：由：由XY及及 Z Y，有，有XZ。 （A1， A3）2. 根据合并规则和分解规则，可得：根据

20、合并规则和分解规则，可得： 引理引理1：XA1 A2Ak成立的充分必要条件是成立的充分必要条件是XAi成立（成立（i=l,2,k）。）。数据依赖的公理系统（续）数据依赖的公理系统（续）定义2：在关系模式在关系模式R中为中为F所逻辑蕴含的函数依所逻辑蕴含的函数依赖的全体叫作赖的全体叫作 F的闭包的闭包，记为，记为F +。 （函数依赖的闭（函数依赖的闭包）包）定义3：设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X U， XF+ = A | XA 能由能由F 根据根据Armstrong公理导公理导出出，XF+称为属性集称为属性集X关于函数依赖集关于函数依赖集F 的闭包。的闭包。（属性

21、集的闭包）属性集的闭包）数据依赖的公理系统（续）数据依赖的公理系统（续）n有效性有效性：由：由F出发根据出发根据Armstrong公理推导出来公理推导出来的每一个函数依赖一定在的每一个函数依赖一定在 F + 中；中；n完备性完备性：F + 中的每一个函数依赖，必定可以由中的每一个函数依赖，必定可以由F出发根据出发根据Armstrong公理推导出来。公理推导出来。数据依赖的公理系统（续）数据依赖的公理系统（续） 设设F为属性集为属性集U上的一组函数依赖，上的一组函数依赖，X，Y U，XY能由能由F 根据根据Armstrong公理导出的充分必要条件是公理导出的充分必要条件是 Y XF+。 用途 将

22、判定将判定XY是否能由是否能由 F 根据根据Armstrong公理导出的公理导出的问题，转化为求出问题，转化为求出XF+ 、判定、判定Y是否为是否为XF+的子集的问题。的子集的问题。数据依赖的公理系统（续）数据依赖的公理系统（续）例例1 已知关系模式已知关系模式R，其中，其中 U = A，B，C，D，E ； F = ABC，BD，CE，ECB，ACB 。 求（求（AB）F+ 。解解 ： 设设X（0）=AB；（1） X（1）= ABCD=ABCD。（2） X（2）= X（1）E=ABCDE。（3） X（2）= U，算法终止，算法终止 （AB）F+ =ABCDE。 （AB为候选码）为候选码）数据依

23、赖的公理系统（续）数据依赖的公理系统（续）定义4：如果如果 G + = F +，就说函数依赖集，就说函数依赖集 F 覆盖覆盖 G（F是是G的的覆盖，或覆盖，或G是是F的覆盖），或的覆盖），或 F 与与 G 等价等价。定义5：如果函数依赖集如果函数依赖集F满足下列条件，则称满足下列条件，则称F为一个为一个极小函数依赖极小函数依赖集集。亦称为。亦称为最小依赖集最小依赖集或或最小覆盖最小覆盖。 (1) F中任一函数依赖的右部仅含有一个属性。中任一函数依赖的右部仅含有一个属性。 (2) F中不存在这样的函数依赖中不存在这样的函数依赖XA，使得，使得F与与F-XA等价等价。 (3) F中不存在这样的函数

24、依赖中不存在这样的函数依赖XA， X有真子集有真子集Z使得使得 F - XA ZA 与与 F 等价。等价。 数据依赖的公理系统（续）数据依赖的公理系统（续）(1)(1)逐一检查逐一检查 F F 中各函数依赖中各函数依赖 FDFDi i：X XY Y，若若Y Y = = A A1 1A A2 2 A Ak k，k k 2 2， 则用则用 X X A Aj j | |j j =1=1，2 2， k k 来取代来取代 X X Y Y。(2)(2)逐一检查逐一检查 F F 中各函数依赖中各函数依赖 FDFDi i：X X A A，令，令G G = = F F -X X A A ， 若若A A X XG

25、 G+ +， 则从则从 F F 中去掉此函数依赖。中去掉此函数依赖。(3)(3)逐一取出逐一取出 F F 中各函数依赖中各函数依赖 FDFDi i：X X A A，设，设X X = = B B1 1B B2 2B Bm m， 逐一考查逐一考查 B Bi i （i i=l=l，2 2，m m），若），若A A （X X- -B Bi i ）F F+ + ， 则以则以X X- -B Bi i 取代取代X X。数据依赖的公理系统（续）数据依赖的公理系统（续）例 F = AB，BA，BC，AC，CA Fm1、Fm2都是都是 F 的最小依赖集：的最小依赖集： Fm1= AB，BC，CA Fm2= AB，

26、BA，AC，CA 关系数据理论关系数据理论1111关系模式的分解关系模式的分解 使模式更加规范化，减少乃至消除数据冗余和使模式更加规范化，减少乃至消除数据冗余和更新异常。更新异常。 分析：分析：sdc(Sno,Sname, dno, dmanager,cname,grade) 无损连接无损连接 保持依赖保持依赖关系模式的分解（续）关系模式的分解（续） 关系模式关系模式R的一个分解的一个分解 = R1,R2, ,Rn 若若R与与R1、R2、Rn自然连接的结果相等，则称关系模自然连接的结果相等，则称关系模式式R的这个分解的这个分解。 反映了模式分解的反映了模式分解的，保证不丢失信息。，保证不丢失信

27、息。 不一定能解决操作异常和数据冗余等问题。不一定能解决操作异常和数据冗余等问题。关系模式的分解（续）关系模式的分解（续） 若关系模式分解为两个子模式若关系模式分解为两个子模式R1和和R2，该分解具有，该分解具有无损连接性的充分必要条件是：无损连接性的充分必要条件是： （1）（）（R1 R2 R2）（R1 R1 R2R2） F F+ + 或或 （2）（）（R1 R2 R2）（R2 R2 R1R1） F F+ +关系模式的分解（续）关系模式的分解（续） 设关系模式设关系模式R被分解为若干个关系模式：被分解为若干个关系模式： = R1，R2，Rn （其中（其中U = U1U2Un，且不存在，且不存在 Ui Uj，Fi 为为 F 在在 Ui 上的投影），若上的投影），若 F 所逻辑蕴含的函数依赖一定也由分解所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖得到的某个关系模式中的函数依赖 Fi