关系数据库理论.ppt

数据库系统,西安电子科技大学,2,第五章 关系数据库理论(4版第六章),关系数据库系统由三级结构两级映象的体系结构构成。关系模式是指关系数据库三结构中的模式，即数据库的逻辑结构。 模式是数据库的整体结构，由所有的基本表的结构构成的整体就是模式。视图是子模式，它是模式的子集，是面向某一具体应用的。 内模式是对数据的存储形式，它由一组物理文件构成，每一个物理文件对应一个或多个基本表。,引言,3,第五章 关系数据库理论,从合理组织数据加以存储的角度出发，要求达到数据的冗余度小、共享性高。解决的办法是对模式进行分解，分解成一组关系模式，每一关系模式对应一个基本表。而在使用方面，通过将多各关系模式进行自然连接，构成完整的关系模式。 怎样的分解才是合理的？关系数据库理论就是用来指导关系数据库模式设计的。模式设计是数据库设计的主要内容之一。,引言,4,5.1 关系模式设计引论,关系的外延和内涵 外延：关系模型的值，即关系模型中的数据，称为关系、实例或当前值。它随着时间的推移而变化，主要由元组的插入、删除和修改而引起。外延是动态的。 内涵：是对关系、属性、域的定义和说明，即关系模型的型的定义。内涵是静态的。 一个完整的关系模型内涵的定义：,关系的内涵称为关系模式。它是静态的，与时间无关。 关系模式通常简记为：R 。,5,5.1 关系模式设计引论,关系模式的存储异常 例：描述学校的数据库有如下属性： 学生的学号(Sno)、所在系(Sdept)、系主任姓名(Mname)、课程名(Cname)、成绩(Grade) 关系模式 ：Student ( Sno, Sdept, Mname, Cname, Grade ) 语义： 1. 一个系有若干学生， 一个学生只属于一个系； 2. 一个系只有一名主任； 3. 一个学生可以选修多门课程， 每门课程有若干学生选修； 4. 每个学生所学的每门课程都有一个成绩。,6,5.1 关系模式设计引论,关系模式 Student (Sno, Sdept, Mname, Cname, Grade) 存在的问题：,1. 数据冗余度大 浪费大量的存储空间 例：每一个系主任的姓名重复出现 2. 修改异常（Update Anomalies） 数据冗余 ，更新数据时，维护数据完整性代价大。 例：某系更换系主任后，系统必须修改与该系学生有关的每一个元组 3. 插入异常（Insertion Anomalies） 该插的数据无法插入到表中。 例：如果一个系刚成立，尚无学生，我们就无法把这个系及其系主任的信息存入数据库。,7,5.1 关系模式设计引论, 删除异常（Deletion Anomalies） 不该删除的数据不得不删 例：如果某个系的学生全部毕业了， 我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。 结论： Student关系模式不是一个好的模式。 所谓“好”的模式：不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。 原因：由存在于模式中属性间的某些依赖关系引起的 如Mname的取值依赖于Sdept的值。 解决方法：通过分解关系模式来消除其中不合适的依赖。 如：分解为Student ( Sno, Sdept, Cname, Grade )和 Dept ( Sdept, Mname ) 两关系模式即可解决。,8,5.2 规范化,规范化(Normalization)是指定义一组关系模式应该符合的条件(范式)，而符合这些条件的关系模式就不存在某些操作异常，冗余也会减小。 函数依赖(Functional Dependencies，简写为FD) 定义：设R(U)是一个属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等， 而在Y上的属性值不等， 则称 “X函数确定Y” 或 “Y函数依赖于X”，记作XY（读作X决定Y）。 X称为这个函数依赖的决定因素(Determinant)。 例: 学生关系Student(Sno,Sname,Ssex,Sage,Sdept)假设不允许重名，则有： SnoSsex, SnoSage, SnoSdept, SnoSname, SnameSno, SnameSsex, SnameSage, SnameSdept。,9,5.2 规范化,说明：,1. 函数依赖不是指关系模式R的某个或某些关系实例满足的约束条件，而是指R的所有关系实例均要满足的约束条件。 2. 函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。 例如: “姓名年龄” 这个函数依赖只有在不允许有同名人的条件下成立。 3. 现实世界中实体的很多属性间都有函数依赖关系，如 “学生学号决定学生的姓名” ，即如果知道了学生的学号，就能确定该学生的姓名。 4. 数据库设计者也可以对现实世界作强制的规定。例如规定不允许同名人出现，函数依赖 “姓名年龄” 成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在， 则拒绝装入该元组。,10,5.2 规范化,几种特殊的函数依赖： 在关系模式R(U)中，对于U的子集X和Y，,例：在关系SC(Sno, Cno, Grade)中， 非平凡函数依赖：(Sno, Cno) Grade 平凡函数依赖： (Sno, Cno) Sno, (Sno, Cno) Cno 注：对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别声明， 我们总是讨论非平凡函数依赖。,若XY，但Y X，则称XY是平凡的函数依赖(Trivial FD) 若XY，并且YX，则记为XY。(X与Y相互决定),11,5.2 规范化,12,5.2 规范化,主码的两个性质： 决定性：K U 最小性：KK，使得K U 主属性(Prime Attribute)：所有候选码中出现的属性 非主属性(Nonprime Attribute)：不出现在任何候选码中的属性 全码(All Key)：由关系模式的所有属性构成码 例：设关系模式S(Sno,Sname,Sdept,Sage)，若无重名，则Sno, Sname是候选码，Sno, Sname是主属性，Sdept, Sage是非主属性。,13,5.2 规范化,定义：关系模式 R 中属性或属性组X 并非R 的码，但 X 是另一个关系模式的码，则称 X 是R 的外部码(Foreign key),也称外码。 例：在关系SC(Sno, Cno, Grade)中，码为(Sno, Cno)，Sno是另一关系 S(Sno, Sname, )的码，而非SC的码，故Sno是SC的外码，同样Cno也是SC的外码。 注： 主码又和外部码一起提供了表示关系间联系的手段。 给出多个候选码时，以 “,” 分隔不同的候选码；当候选码为多个属性时，候选码用( )括起来，属性间用 “,” 隔开。 如: 关系模式S(Sno, Sname, Sdept, Sage)的候选码为：Sno, Sname。 关系模式SC(Sno, Cno, Grade)的候选码为(Sno, Cno)。,14,5.2 规范化,范式 范式(Normal Form)是符合某一类满足一定要求的关系模式的集合。关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。 定义：如果一个关系模式R的所有属性都是不可分的基本数据项，则称关系R为第一范式的关系模式(First Normal Form)，简称关系R属于一范式，记为：R1NF。 注： 第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。(由关系属性的原子性得出)。 但是满足第一范式的关系模式并不一定是一个好的关系模式。,15,5.2 规范化,函数依赖示意图：,注： 虚线表示部分函数依赖； 通常函数依赖示意图只画出基本函数依赖，对于部分函数依赖和传送函数依赖并不画出。,16,5.2 规范化,定义：若关系模式R1NF，并且每一个非主属性都完全函数依赖于R的码，则R2NF。 例：SLC(Sno, Sdept, Sloc, Cno, Grade) 每个属性都是由不可再分的值构成，故SLC1NF 候选码：(Sno, Cno) 非主属性： Sdept, Sloc, Grade,不属于2NF的关系模式存在的问题： (1) 插入异常 (2) 删除异常 (3) 数据冗余度大 (4) 修改异常,原因：Sdept、 Sloc部分函数依赖于码。 解决方法：SLC分解为两个关系模式，以消除这些部分函数依赖 SC(Sno, Cno, Grade)2NF SL(Sno, Sdept, Sloc)2NF,17,5.2 规范化,采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。如SL(Sno, Sdept, Sloc)2NF中就可以插入未选课的学生信息。 将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余。如SL(Sno, Sdept, Sloc) 2NF，如果有一个新开设的系，已经划分了宿舍区，但还没有招生，则无法记录该系的学生宿舍区这一信息(插入异常)。,数据库系统,19,5.2 规范化,说明： 若 Z Y，则 XY 时必然有 XZ； 若Y X，则X Y，YZ为自身固有的依赖; 3NF是指不含纯粹的非主属性对码的传递依赖的关 系模式 例：SC(Sno, Cno, Grade)2NF 码：(Sno, Cno)，非主属性： Grade 非主属性Grade直接依赖于码(Sno, Cno) Grade而非传递依赖于码，故SC3NF SL(Sno, Sdept, Sloc)2NF 码：Sno，非主属性： Sdept, Sloc FD：Sno Sdept，Sdept Sloc。则有Sno Sloc，即存在非主属性对码的传递依赖，故SL不属于3NF。,20,5.2 规范化,不属于3NF的关系模式存在的问题： SL(Sno, Sdept, Sloc) 3NF,(1) 插入异常 如果有一个新开设的系，已经划分了宿舍区，但还没有招生，则无法记录该系的学生宿舍区这一信息。 (2) 删除异常 如果删除全部学生所在系及宿舍区信息，则该系的学生宿舍区信息也被迫删除。 (3) 数据冗余度大 如果某系有多名学生，则该系学生宿舍区的信息被记录多次。 (4) 修改复杂 如果某系学生住宿区改变，则需要改变所有学生的记录。 原因：Sloc传递依赖于码Sno 解决方法：分解为3NF：SD(Sno, Sdept)和DL(Sdept, Sloc)。,21,5.2 规范化,定理：如果R3NF，则R2NF。 证： R3NF R2NF R2NF R 3NF,推论： R3NF，则R中的每一个非主属性既不部分依赖于码，也不传递依赖于码。 结论： 将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。 将一个2NF关系分解为多个3NF的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。,22,5.2 规范化,例：关系模式C(Cno, Cname, Credit)，课程允许重名。 码：Cno FD：CnoCname， CnoCredit 非主属性：Cname， Credit 不存在非主属性对码的部分依赖 C2NF 不存在非主属性对码的传递依赖 C3NF 每一个函数依赖的决定因素都包含码 CBCNF 定理： BCNF 3NF。（作业） 提示：仿照上一定理的证明方法证RBCNF R3NF； 举反例R3NF但RBCNF证明真包含。,23,5.2 规范化,定理： 若RBCNF，则R中所有非主属性对每一个码都完全函数依赖。(由2NF定义得到) 若RBCNF，则R中所有主属性对每个不包含它的码都完全函数依赖。 证明：设K1、K2是关系R的码，AK2 且AK1，则根据码的定义得到K1A；由BCNF定义，K1要么是码，要么包含码；假设K1包含码，即存在KK1，使得KA，则K是码而K1不是码，故K1是码。 若RBCNF，则R中没有任何属性完全函数依赖于非码的任何一组属性。 证明：设有XA，由BCNF定义，X是码或X含有码，若为后者，存在码KX且KA是部分函数依赖，故X只能是码。,24,5.2 规范化,例：关系模式S(Sno, Sname, Sdept, Sage)，不允许重名。 码：Sno, Sname FD：SnoSname, SnameSno, SnoSdept, SnoSage 非主属性：Sdept, Sage 不存在非主属性对码的部分依赖 S2NF 不存在非主属性对码的传递依赖 S3NF 每一个函数依赖的决定因素都包含码 SBCNF,25,5.2 规范化,例：关系模式SJP(S, J, P) 中，S是学生，J表示课程，P表示名次。每一学生选修每门课程的成绩都有一定名次，且名次不重复。 FD: (S, J)P，(J, P)S 码： (S, J) ，(J, P) 非主属性：无 不存在非主属性对码的部分依赖 SJP2NF 不存在非主属性对码的传递依赖 SJP3NF 每一个函数依赖的决定因素都包含码 SJPBCNF,26,5.2 规范化,例：在关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示课程。每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。某个学生选修某个教师的课就确定了所选课的名称。 由语义得如下FD： (S，J)T，(S，T)J，TJ 函数依赖图：,码： (S, J)， (S, T) 非主属性：无 不存在非主属性对码的部分依赖 STJ2NF 不存在非主属性对码的传递依赖 STJ3NF 存在函数依赖TJ，其中的决定因素T不包含码 STJBCNF,27,5.2 规范化,不属于BCNF的关系模式存在的问题： STJ(S, T, J) (1) 插入异常 学生未开始选修某门课程前，无法输入教师任课信息 (2) 删除异常 删除学生选课信息，教师任课信息一并删除 (3) 数据冗余度大 同一教师的任课信息在多个学生选课的记录中重复存储 (4) 修改复杂 由冗余性决定 结论：BCNF消除了主属性对码的部分依赖和传递依赖，在函数依赖的范畴内解决了数据插入异常和删除异常，但可能存在着数据冗余和修改复杂。,28,5.2 规范化,三、多值依赖(Multivalued Dependencies，简写为MVD) 定义：在关系模式R(X,Y,Z)的任一关系r中，如果存在元组t, s，使得tX = sX，就必然存在元组 w, v r，使得 wX = vX = tX (= sX)，而 wY = tY, wZ = sZ ；vY = sY，vZ = tZ （即交换 t, s 在Z上的分量构成的新元组必然在r中），则称Y多值依赖于X，记为XY。 这里，X、Y、Z是U的子集，且Z=U-X-Y。 即：,29,5.2 规范化,例：关系模式WSC(W,S,C)中，W表示仓库，S表示保管员，C表示商品。每个仓库有若干保管员，有若干商品，每个保管员保管所在仓库的所有商品，每种商品被所有它所在的仓库的保管员所保管。(假设仓库w1有两个保管员s1,s2，存放三个商品c1, c2, c3；仓库w2有两个保管员s3,s4，存放两个商品c4, c5),对于同一个X值，对应的Y与Z值集合间构成完全二分图。,30,5.2 规范化,特殊的多值依赖： 若XY，而Z，则称XY为平凡的多值依赖，否则称XY为非平凡的多值依赖。,定义：关系模式R 1NF，如果对于R的每个非平凡多值依赖XY (YX)，X都含有候选码，则R4NF。 说明: (1) 对于平凡的多值依赖，X不可能成为码，应是全码； (2) 每个非平凡的多值依赖XY, X含有码, 则XY ； (3) 4NF只允许平凡的多值依赖； (4) 所有含有非平凡MVD和EMVD都不是4NF。 例：WSC(W, S, C)是非平凡的MVD，故不是4NF。 分解为：WS(W, S)4NF，WC(W, C) 4NF,31,5.2 规范化,定理：4NFBCNF。 证： (反证法) 假设关系模式R4NF，但R不属于BCNF，则必存在某个非平凡的函数依赖XY，且X不是码；若XYR，则X是码，与假设矛盾，若XYR，由XY知XY成立，且是非平凡的MVD，则X不是码，违反4NF条件，与假设矛盾。 举特例RBCNF但R 4NF (略),32,5.2 规范化,规范化总结： 关系数据库的规范化理论是数据库逻辑设计的工具； 一个关系只要其分量都是不可分的数据项，它就是规范化的关系，但这只是最基本的规范化(1NF)； 规范化程度可以有多个不同的级别； 规范化程度过低的关系不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题； 一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化。 范式间的包含关系：1NF 2NF 3NF BCNF 4NF,33,作业(13),1. 证明：BCNF3NF 2. P195 题2，并指出你所列出的每个关系模式所属范式。 要求: (1)所有的关系名和属性名使用题目所给的中文名称; (2)极小函数依赖集是指不含部分依赖和传递依赖等多余的依赖。,数据库系统,35,5.3 数据依赖的公理系统,公理系统 给定一组公式(公理)和推理规则，由这些公式依据推理规则得到更多的公式，公理、规则和推导出的公式构成公理系统。如欧氏几何即为公理系统。 公理系统的有效性： 通过推理规则得到的公式(形式推演)与通过逻辑推理得到的结论(逻辑推论)一致，即形式推演的结论是有效的。 公理系统的完备性： 通过逻辑推理得到的结论(逻辑推论)，都可以用形式推演得到，逻辑推理是完备的。,36,5.3 数据依赖的公理系统,函数依赖的公理系统 定义：设关系模式R ，其中F是属性集U上的函数依赖集，X,YU，对其任何一个关系实例r，若函数依赖XY都成立, 则称F逻辑蕴含X Y，记为：F X Y 。 函数依赖的推理规则由Armstrong于1974年首先提出，故函数依赖的公理系统又称作Armstrong公理系统。 Armstrong公理系统： 设关系模式R ，其中F是属性集U上的函数依赖集。对关系模式R 有以下推理规则： (A1)自反律(Reflexivity)：若Y X U，则F XY。 证明：对于关系模式R的任一关系r中的任意两个元组t和s，若tX=sX，由于Y X，则tY=sY，故XY。 注：A1属于逻辑推理规则，其证明方法属于语义证明，下同。,37,5.3 数据依赖的公理系统,(A2)增广律(Augmentation)： 若F XY，Z U，则F XZYZ。 证明：对于关系模式R的任一关系r中的任意两个元组t和s，若tXZ=sXZ；则有tX=sX和tZ=sZ；由XY，则有tY=sY；所以tYZ=sYZ，故FXZYZ。 (A3)传递律(Transitivity)： 若F XY， F YZ ，则F XZ。 证明：对于关系模式R 的任一关系 r中的任意两个元组 t和s，若tX=sX，由于XY，有 tY=sY；再由YZ，有tZ=sZ，所以F XZ。 注：自反律(A1)是平凡的函数依赖，与函数依赖集F无关，是关系自身就有的性质。 定理：以上三条推理规则是正确的。(已证明),38,5.3 数据依赖的公理系统,定义：由自反律(A1)、增广律(A2)和传递律(A3)三条推理规则构成Armstrong公理系统。 Armstrong公理系统还可以得到以下三条推理规则： 合并规则：XY，XZ XYZ。 证明： (1) XY 已知(P规则) (2) XXY A2，(1) (3) XZ 已知 (4) XYYZ A2，(3) (5) XYZ A3，(2)，(4) XY，XZ XYZ 注： 合并规则属于逻辑推理规则，其证明方法属于逻辑推证，下同。,39,5.3 数据依赖的公理系统,分解规则： XY，Z Y XZ。 证明： (1) XY 已知 (2) Z Y 已知 (3) YZ A1, (2) (4) XZ A3，(1)，(3) XY，Z Y XZ 伪传递规则：XY， WYZ WXZ。 证明： (1) XY 已知 (2) WX WY A2，(1) (3) WYZ 已知 (4) WXZ A3，(2)，(3) XY， WYZ WXZ,40,5.3 数据依赖的公理系统,定理：XA1A2Ak成立的充分必要条件是 XAi 成立（i =1, 2, ，k）。 证明方法：由分解规则证必要性，合并规则证充分性。 （作业：证明此定理）,41,5.3 数据依赖的公理系统,函数依赖集的闭包 定义：在关系模式R中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包(Closure)，记为F+。 例: 已知R，其中UA, B, C，F=AB, BC，求关系模式R上的函数依赖集F的闭包F。 解： F= , A, AA, , ABA, /A1 AB,AAB,ABB,ABCBC, /A2 BC, ABAC, /A2 A C /A3 注：本题F共计43个不重复的FD。 |F|属于NP完全问题 F+的意义：包含了给定函数依赖集F(部分)所蕴涵的属性集U上的全部函数依赖。 缺点：这些依赖信息太多太庞杂，很难管理和利用。,42,5.3 数据依赖的公理系统,属性集的闭包 定义：设F为属性集U上的一组函数依赖，XU， X关于函数依赖集F 的闭包(Closure of X under F ) XF+ = A | XA能由F 根据Armstrong公理导出。 求XF+的算法： (1) 令X (0)=X，i=0； (2) 令X(i+1)=X(i) A |(V)( W)(VWFV X(i)AW)； (3) 若已没有VW F，使得X(i+1) X(i)，算法结束，XF+=X(i)；否则，令i=i+1，转(2)。,43,5.3 数据依赖的公理系统,例：已知关系模式R，其中U=A, B, C, D, E， F= ABC, BD, CE, ECB, ACB ，求 (AB)F+。,解：(AB)F+ ,(1) X XF+ ；,AB,C,D,E,(2) 逐一考察F中的FD，如果存在VWF，且V中的全部属性都出现在当前的XF+中，将属性组W并入XF+；,(3) 当当前的XF+包含全部属性U，或者按(2)重新遍历F而没有对当前XF+ 增加任何属性时算法结束。,44,5.3 数据依赖的公理系统,定理：设F为属性集U上的一组函数依赖，X，Y U，XY能由F 根据Armstrong公理导出的充分必要条件是Y XF+。 证明：(充分性)设YA1A2Am, 且Y XF+。由XF+的定义知XAi(i=1,m)逻辑地推出，由并规则得X A1A2Am, 即XY。 (必要性) 设F XY，由分解规则，XAi(i=1,m)，由XF+的定义得A1A2Am XF+，即YXF+。 意义：可以将庞杂的函数依赖集的闭包F+等价地转换为多个属性集X关于F的闭包XF+，可以方便地处理。 定理：Armstrong公理系统是有效的、完备的。 有效性是指由F出发根据Armstrong公理推导的每一FD都在F+中；完备性是指F+中的每一FD都可以F出发根据Armstrong公理推导推导出来。(证明不作要求),45,5.3 数据依赖的公理系统,最小函数依赖集 函数依赖集的闭包是给定FD所蕴涵的全部的属性间的函数依赖关系。换一个角度，怎样用最少的函数依赖来表达全部的属性间的依赖关系？这就是最小函数依赖集讨论的内容。 定义：假设在关系模式R上有两个函数依赖集F和G。如果F=G+，则称F和G是等价的，或称F与G相互覆盖。 定理：F=G+，当且仅当FG+且GF+。 证明：(略) 意义：给出了两个函数依赖集等价的判定方法。,46,5.3 数据依赖的公理系统,定义：如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。 (1) F中任一函数依赖的右部仅含有一个属性； (2) F中不存在这样的函数依赖XA，使得F与FXA等价； (3) F中不存在这样的函数依赖XA，X有真子集Z使得 (FXA )ZA与F等价。 最小函数依赖集求解算法： (1) 对F中每一函数依赖XY ，若Y= A1A2Am(m2)，则用 XAi | i=1,m 替换XY ；(等价变换) (2) 对F中每一函数依赖XA，若X= B1B2Bn，逐一考察Bi，若A(X-Bi)F+，则用(X-Bi)A替换XA，Bi 称为无关属性；(等价变换) (3) 对于F中的每一函数依赖XA，若A XF-XA+，则从F中去掉XA。 (等价变换),47,5.3 数据依赖的公理系统,定理：每一函数依赖集F均与其对应的最小函数依赖集Fmin等价。(证明：在构造Fmin的过程中每一步变换都是等价的) 例：设关系模式R(ABCDE) 上的函数依赖集F=ABC, BCDE, BD, AD, EA，求F的最小函数依赖集。 解： 对每个函数依赖右部属性分离，得： F1=AB, AC, BCDE, BD, AD, EA 去掉左部冗余属性 (BC)F+=BCDEA，包含E，BCDE中的D为冗余属 性，以BCE取代BCDE，得： F2AB, AC, BCE, BD, AD, EA 去掉多余函数依赖 AB, BD可以得到AD，故AD多余，去 掉，得FminAB, AC, BCE, BD, EA,48,5.3 数据依赖的公理系统,结论：一个给定的函数依赖集F的最小函数依赖集不是唯一的。 原因：在求解过程中由于考察FD的次序的不同会产生不同的结果，但一个函数依赖集F的所有最小函数依赖集是等价的（都等价于F）。 例：F = AB, BA, BC, AC, CA Fm1、Fm2都是F的最小依赖集： Fm1= AB, BC, CA Fm2= AB, BA, AC, CA ,49,5.3 数据依赖的公理系统,候选码求解算法 分析： 对于给定的关系模式R，依照函数依赖集F将U中的属性分为以下四类： L类属性: 在F中只出现在函数依赖的左部的属性； R类属性: 在F中只出现在函数依赖的右部的属性； LR类属性: 分别出现在F中的函数依赖左部和右部的属性； N类属性: 不在F中的函数依赖中出现的属性。 结论： L类属性和N类属性必包含于任何候选码中； R类属性必不包含于任何候选码中； LR类属性不能确定是否在候选码中。,50,5.3 数据依赖的公理系统,算法： 对于给定的关系模式R，其中U为属性集合，F为函数依赖集。 (1) 依照函数依赖集F将R中的所有属性分为L类、R类、LR类和N类属性，令X为L、N类属性的集合，Y为LR类属性集合；,例：设R，其中： U=A,B,C,D,E，F=ABC, CDE, BD, EA，求R的所有候选码。,解: (1) R中无L、N类属性，A, B,C,D,E均为LR类属性，故X= ，YA,B,C,D,E;,(2) 若XF=U，则X为R的唯一候选码 (?)，结束；否则，转(3)；,(2) XF= U；(但不能说明R的候选码不唯一?),51,5.3 数据依赖的公理系统,算法： 对于给定的关系模式R，其中U为属性集合，F为函数依赖集。 (1) (2) ,例：设R，其中： U=A,B,C,D,E，F=ABC, CDE, BD, EA，求R的所有候选码。 解: (1) X= ，YA,B,C,D,E; (2) ,(3)取A，则AF+=ABCDE=U，A为候选码； 取B、C、D，其闭包均不等于全属性集U； 取E，则EF+=ABCDE=U，E为候选码； Y= B,C,D,(3)逐一取Y中的单一属性A，若(XA)F+=U，则XA为候选码 (?) ，令YYA (?)，转(4)；,52,5.3 数据依赖的公理系统,算法： 对于给定的关系模式R，其中U为属性集合，F为函数依赖集。 (1) (2) (3) ,例：设R，其中： U=A,B,C,D,E，F=ABC, CDE, BD, EA，求R的所有候选码。 解:(3) ，A为候选码； ，E为候选码； Y= B,C,D,(4)在Y中任取两个属性判定 (BC)F+=BCDEA=U，BC为候选码； (BD)F+不等于全属性集U，BC不是候选码； (CD)F+=CDEAB=U，CD为候选码；,(4) 依次取Y中的任意两个、三个属性与XZ组成属性组，若XZ不包含已求得的候选码 (?)，求其关于F的闭包(XZ)F+，若(XZ)F+ =U，则XZ为候选码。直到取完Y中的所有属性为止，算法结束。,53,5.3 数据依赖的公理系统,例：设R，其中： U=A,B,C,D,E，F=ABC, CDE, BD, EA，求R的所有候选码。 解:(3) ，A为候选码； ，E为候选码； Y= B,C,D (4)在Y中任取两个属性判定 ， BC为候选码； ， CD为候选码；,(5) BCD包含已求得的候选码BC，BCD不是码，结束。 故关系R的候选码为：A，E，BC，CD。,54,5.3 数据依赖的公理系统,算法： (完整版 ) (1) 依照函数依赖集F将R中的所有属性分为L类、R类、LR类和N类属性，令X为L、N类属性的集合，Y为LR类属性集合； (2) 若XF=U，则X为R的唯一候选码 (?)，结束；否则，转(3)； (3) 逐一取Y中的单一属性A，若(XA)F+=U，则XA为候选码 (?) ，令YYA (?)，转(4)； (4) 依次取Y中的任意两个、三个属性与XZ组成属性组，若XZ不包含已求得的候选码 (?)，求其关于F的闭包(XZ)F+，若(XZ)F+ =U，则XZ为候选码。直到取完Y中的所有属性为止，算法结束。,55,5.3 数据依赖的公理系统,例：设R(A,B,C,D,E)，F=ABC, CDE, BD, EA，求R的所有候选码。(完整版 ) 解: (1) R中无L、N类属性，ABCDE均为LR类属性； (2) 取A，则AF+=ABCDE=U，A为候选码； 取B、C、D，其闭包均不等于全属性集U； 取E，则EF+=ABCDE=U，E为候选码； (3) 在BCD中任取两个属性判定 (BC)F+=BCDEA=U，BC为候选码； (BD)F+不等于全属性集U，BD不是候选码； (CD)F+=CDEAB=U，CD为候选码； (4) BCD包含已求得的候选码BC，BCD不是码，结束。 故关系R的候选码为：A，E，BC，CD。,56,第五章 关系数据库理论,作业： 证明定理：XA1A2Ak成立的充分必要条件是XAi成立（i=l, 2, ，k）。,数据库系统,58,5.4 模式分解,模式分解的定义 定义：关系模式R的一个分解 = R1，R2，Rn,其中： U ，并且不存在 Ui Uj，1 i, j n, i j；, Fi 为与函数依赖集 XY | XYF+XY Ui 等价的一个函数依赖集，称为 F在 Ui 上的投影。,范式是通过数据依赖(函数依赖和多值依赖)对关系模式进行规范，范式间关系：1NF 2NF 3NF BCNF 4NF。 规范化的过程就是对关系模式进行分解，使其达到更高一级的范式，来减少和避免更新异常和数据冗余。 满足BCNF的关系模式可以在函数依赖的范畴内解决更新异常和数据冗余；如果关系模式中存在多值依赖，则分解应达到4NF。,59,5.4 模式分解,模式分解应考虑的问题： 分解不能丢失信息 如学生关系S(Sno, Sname, Ssex, Sage, Sdept)，它的一个实例 r 如下：,其中的每条记录都是一个学生实体的描述，如(95001,李勇，男，20, CS)，表示：学号为95001的同学名叫李勇，男性，今年20岁，在CS系学习。 如果将该关系模式分解为=S1(Sno), S2(Sname), S3(Ssex), S4(Sdept)，则任一关系实例都被分解为一些离散的值，不再表示原关系中的意义，即分解丢失了信息。,60,5.4 模式分解,分解应该能够被还原 模式的分解是为了更好地存储，在使用中通过自然连接还原为分解前的关系模式，如下表为一银行的存款记录：,将其分解为右上图的两个关系R1和 R2：,还原后的关系模式如右图：,多出了两条记录! 这是绝对不允许的!,分解应保持函数依赖 函数依赖是属性间自身具有的性质，通常的查询与此有关，故应保持。,61,5.4 模式分解,模式分解的无损连接性(Lossless join) 定理：设关系模式R的一个分解= R1，R2，Rk ，r是R的一个关系实例，ri=Ri(r) 为关系r在模式Ri上的投影，则：,(2) 若 s = m(r)，则Ri(s) = ri (3) m(m(r) = m(r) 此定理描述了分解之后的关系与原关系的联系。,定义：= R1，R2，Rk是关系模式R的一个分解，若对于R的任一关系r均有r = m(r) 成立，则称分解具有无损连接性。简称为无损分解。,62,5.4 模式分解,例：学生成绩登记表SCG：,分解为如下三个表(分别为S、C、SC)：,63,5.4 模式分解,无损连接性的判定算法： 设= R1，R2，Rk是关系模式R的一个分解，U= A1, , An，F= FD1,FD2, , FDm ，(假设F为最小函数依赖集，若不是，求之，可提高求解效率)，并设FDi为Xi Ai。,例：已知R，U= A, B, C, D, E ，F= ABC , DE, CD，R的一个分解= R1(A,B,C), R2(C,D), R3(D,E)。判定分解是否为无损连接的分解。,解： (1) 构造初始表：,(1) 建立一张n列k行的表，每一列对应一个属性，每一行对应一个关系模式，若属性Aj属于Ui，则在j列i行交叉处填上aj，否则填上bij；,64,5.4 模式分解,(2) 把表看作R的一个关系，依次检查每一FDi在表中是否成立，若不成立，做如下修改使其成立：找到Xi所对应的列中具有相同符号的那些行，如果Ai列出现ali，则将这些行的Ai列换成ali，否则全部改为bmli，m是行号的最小值；(称为一趟Chase过程),(例)：，(F= ABC, DE , CD ，。 解：(1) 构造初始表；,(2) 第一趟Chase： ABC：无AB列上取值相同的行，不做修改；,a5, DE：第二、三行在D上的取值均为a4，第三行E列出现a5，将这两行在E上的取值修改为a5；,65,5.4 模式分解,(例)：，(F= ABC, DE , CD ，。 (2) 第一趟Chase： , CD：第一、二行在C上的取值为a3，将这两行在D上的值改为a4；,66,5.4 模式分解,(3) 如果在一趟Chase中的某次更改之后出现形如a1,a2,an的行，算法结束，分解具有无损连接性；否则，继续下一趟Chase过程，直到一趟Chase之后表无任何变化时算法结束 (此时未出现形如a1,a2,an的行)，分解不具有无损连接性。,(例)：，(F= ABC, DE , CD ，。 (2) 第一趟Chase后的结果：,(3) 第二趟Chase： ABC：无改变； DE ：第一、二、三行在D上的取值为a4，将它们在E上的取值改为a5；,(4)表第一行出现a1,a2,a3,a4,a5，故分解为无损分解。,67,5.4 模式分解,定理：关系模式R的一个分解 = R1, R2 具有无损连接性的充分必要条件是：U1U2 U1U2 F+ 或 U1U2 U2U1 F+。 注： 单独的一个条件是充分条件而非必要条件； 此定理可用于一分为二的模式分解无损连接性的判定。 例：学生关系S ( Sno, Sname, Ssex, Dept, DeptManager )分解为 S(Sno, Sname, Ssex, Sdept) 和 D(Dept, DeptManager), DS = Dept , DS = DeptManager, Dept DeptManager为原关系中的函数依赖，此分解为无损连接的分解。,68,5.4 模式分解,定理：关系模式R中，D为R中的函数依赖FD和多值依赖MVD的集合。则XY成立的充要条件是R的分解= R1，R2 具有无损连接性，其中 Z = UXY。 说明： 将关系模式分解为两个关系模式R1、R2，要使其具有无损连接性，要么U1U2 U1U2 (此时必有U1U2 U2U1 )成立，要么U1U2 U1U2 或U1U2 U2U1 成立。 对含有非平凡的多值依赖XY (Z)的关系模式R，将其分解为R1 和R2 两个关系模式，该分解具有无损连接性。,69,5.4 模式分解,模式分解的保持函数依赖性(Preserve dependency),定义：若F+=( )+，则R的分解= R1，R2，Rk 保持函数依赖。,70,5.4 模式分解,例：(教材P177例2)在关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示课程。每一教师只教一门课。每门课由若干教师教，某一学生选定某门课，就确定了一个固定的教师。 解： 写出函数依赖集 F (S, J)T，(S, T)J，TJ 求码：S为L类属性，必包含于码中