数据库系统原理及应用 丁忠俊 第四章 关系数据库理论

第四章关系数据库设计理论第一节概述一、关系DB设计理论的主要内容1、解决的主要问题从理论上来讲，如何设计一个比较好的关系模式的集合？2、本章的主要内容三方面的内容：数据依赖（函数依赖、关键字、函数依赖的推理规则）关系模式的分解（两种特性：无损联接性和保持依赖性）范式理论（1NF-5NF）其中：数据依赖是基础。即：范式理论和关系模式的分解都是建立在数据依赖的概念基础之上。二、关系模式使用中的异常问题例:设有关系模式R（TNAME，ADDR，C#，CNAME）（分别为：教师名，地址，课程号，课程名）其关系如下：TNAMEADDRC#CNAMEt1t1t1t2t2t3a1a1a1a2a2a3c1c2c3c4c5c6n1n2n3n4n2n4R现实世界的事实可知：一个教师只有一个地址一个教师可讲若干课程每门课程只有一个教师任教R的侯选关键字为:(TNAME,C#)在使用过程中会存在以下问题：（1）数据冗余：当一个教师若讲多门课程，则其地址值会重复存储多次。数据冗余：同一个数据重复存储。数据冗余会引起：①浪费存储空间；②造成修改数据不一致性。（2）更新操作异常①修改异常：由数据冗余引起的。如上例：t1教师讲了三门课，其地址值a1重复存储了三次；若t1搬家，则它的地址值必须修改三处值，若只修改一处，则会产生修改不一致性。②插入异常：指该插入的数据而不能插入到关系中。如：新增加一个教师，但尚未分配讲课任务，则不能将其姓名和地址值插入到R中。原因：R的候选关键字（TNAME，C#）中，C#为空值。即：候选关键字中主属性为空或部分为空的元组违反了实体完整性原则。③删除异常：指不该从关系中删除的数据被删除了。如：若要把原来上过课，但目前未上课的教师的所有元组删去，则将该教师的姓名和地址信息也从R中删除了。注：DB的更新操作异常和数据冗余在网状，层次，面向对象的模型也存在。什么原因使得关系产生操作异常和数据冗余呢？原因：关系模式中的属性之间依赖问题；这就是引入属性之间函数依赖的原因。现在采用函数依赖的概念，利用分解方法，将R分解两个等价的关系：R1（TNAME，ADDR）R2（TNAME，C#，CNAME）TNAMEADDRt1t2t3a1a2a3TNAMEC#CNAMEt1t1t1t2t2t3c1c2c3c4c5c6n1n2n3n4n2n4数据冗余大减，上述情况的异常消除。关系模式如何分解；分解到一个什么程度为好？将是本章讨论的问题。R1R2第二节函数依赖一、函数依赖（FunctionalDependency简称FD）的定义定义1：设有关系模式R（U），U={A1，A2，…，An}，，若对R的所有具体关系r都存在：对于每一个X值，都有唯一的Y值与之对应，则称X函数决定Y；或说Y函数依赖于X，记为：UY,XYX定义2：设有关系模式R(A1,A2,…,An),和均{A1,A2,…,An}的子集，r是R的任一具体的关系(R-型,r值),t1和t2是r中任意两个元组,若由导致,则称函数决定,或说函数依赖于,记为：X]X[t]X[t21]Y[t]Y[t21YXXYXYY注：(1)FD是对R一切可能的当前值r定义的，不是针对某个特定关系。(2)FD是语义范畴的概念，只有通过属性之间的语义来确定是否存在函数依赖关系，不能用数学方法推导或证明。它是现实世界中属性之间客观存在或设计者人为强制相结合的产物。例:若设计者限定：无同名同姓；则：姓名→年龄（反之：年龄姓名），若有同名同姓：则，姓名年龄。(3)中，称为决定的因素，只要取一个值，则有唯一的值与之对应。YXXYX二、函数依赖与属性间联系的关系设关系模式R，，则：(1)如果，之间是1-1联系，则存在：和，即，相互函数依赖记为。(2)如果,之间是m-1联系，则存在,。(3)如果X,Y之间是n-m联系，则X,Y之间不存在函数依赖，即，.结论：根据关系r当前值，可从属性间的联系入手来决定函数依赖是否存在。XXXYYYYXXYYXYXXYXY例：已知关系r如下ABCDEa1a1a2a2b1b2b1b1c1c2c3c4d1d2d3d3e1e1e1e1r下列函数依赖中，关系r满足哪些依赖？a、A→Bb、(A,B)→Dc、C→(B,D,E)d、E→Ae、A→EUY,XXY三、关键字（键、码）用FD概念精确定义关键字定义：设关系模式R（A1，A2，…，An），F是R上的函数依赖集，X是（A1，A2，…，An）的一个子集，如果：（1）X→A1，A2，…，An且（2）在X中不存在真子集Y，使得Y→A1，A2，…，An成立，则称X是R的候选关键字。注：条件（1）表示X能唯一决定一个元组。条件（2）表示X是满足（1）而无多余的属性集。例：关系模式R（学号，姓名，性别，年龄）中，按语义：学号→姓名学号→性别学号→年龄∵学号→（学号，姓名，性别，年龄）∴学号是R一个候选关键字。也可说明：（学号，姓名）也可决定R中的全部属性，但（学号，姓名）不是候选关键字。∵（学号，姓名）存在真子集：“学号”可以决定全部属性；“姓名”属性多余。说明：主属性：包含在候选关键字中的属性。非主属性：不包含在候选关键字中的属性。四、函数依赖的分类根据不同性质，函数依赖分类：完全函数依赖部分函数依赖传递函数依赖1、完全函数依赖与部分函数依赖定义：在关系模式R（U）中，如果，并且对的任何一个真子集，都有则称完全函数依赖于，记作。如果对某个真子集,有，则称对的函数依赖是部分的函数依赖，记作：。例：关系模式SC(学号，课程号，成绩)中，显然：学号成绩，课程号成绩，而：(学号，课程号)→成绩,可见：(学号、课程号)是候选关键字：学号，课程号是主属性；成绩为非主属性。又如：关系模式R(学号，课程名，系名)中：学号→系名,课程名系名,(学号，课程名)→系名.fpYXX/XY/XYXYXfX/XYX/YXYXp注：只有决定因素是组合属性，才存在部分函数依赖，当决定因素是单属性时，只能是完全函数依赖。2、传递函数依赖定义：在关系模式R（U）中，如果，，且，，则称Z传递函数依赖于，记作:。注：当条件不成立时，即，则，实际上是直接函数依赖而非传递函数依赖。例：在关系模式R（学号，学生姓名，系名，系主任名）中。学号→学生姓名学生姓名→系名（设无同名同姓）则：学号→系名是直接函数决定再：学号→系名，系名学号，系名→系主任名，则有：学号→系主任名。tYXZYXYYZXZXtXYYXZXXYXY五、函数依赖的逻辑蕴涵有时需要从一些已知的FD去判断另一些FD是否成立。如：已知F={A→B，B→C}在模式R中成立，那么A→C在R中是否成立。这个问题称为逻辑蕴涵问题。定义：设F在关系R上成立的函数依赖集,X→Y是一个其他的FD(X⊆R,Y⊆R)。如果从F中的函数依赖能推出X→Y，则称F逻辑蕴涵X→Y，记为：F|＝X→Y。定义：被F函数蕴涵的函数依赖的全体构成的集合称为F的闭包(closure),记为：F+={x→Y|F⊨X→Y}一般，FF+，若F=F+则称F是函数依赖的完备集。值得注意：依据F计算F+是很麻烦的，即使F不大，F+也可能很大。如：有关系R(X,Y,Z)其函数依赖集F={X→Y,Y→Z}则...Y)Y,X(YX...X)Y,X(XX...YXXF），（共有43个依赖这些函数依赖怎么出来？待学习了函数依赖的推理规则，再回答此问题第三节FD公理目的：确定函数依赖的逻辑蕴涵。即从给定的F中的函数依赖，推出F+中的函数依赖。也就是说给定了F和，，判断是否在F+中。为此，要有一套推理规则。XYYX一、Armstrong公理设有关系R(A1,A2,…,An)和属性全集U=A1A2…AnX，Y，Z，W均是U的子集；F是U上的一个函数依赖集，推导规则是：A1自反性(Reflexivity)：若，则F逻辑蕴涵（平凡的函数依赖）A2增广性(Augmentation)：若F逻辑蕴涵，则F逻辑蕴涵A3传递性(Transitivity)：若F逻辑蕴涵,,F逻辑蕴涵：XYYXYXYZXZYXZYZX例：设R(C,S,Z)，其中：C为城市名，S为街名，Z为邮编，给定F={CS→Z,Z→C}即函数依赖图如下：CSZ由Armstrong公理，有(1)Z→C(已知)说明：Z→C逻辑蕴涵F+中。(2)SZ→CS(由(1)和A2增广性)说明:SZ→CS逻辑蕴涵在F+中。(3)CS→Z(已知)(4)CS→CSZ(由(3)和A2增广性)说明：CS→CSZ在F+，也说明CS是R的一个候选关键字。(5)SZ→CSZ(由(2)和A2增广性，或由(2),(4)和A3传递性)说明：SZ→CSZ在F+中，也说明SZ是R的另一个候选关键字。注：可以证明候关键字：CS和SZ中没有多余的属性存在。说明：①通过公理可以推出F中的隐含的FD，尤其可推出关系R的候选关键字。②能否保证由公理推出的函数依赖都是正确的，即所推出的函数依赖都是否都属于F+？——公理的正确性。正确性：只要F的FD为真，由公理推出的FD也为真，则推出的FD都由F+逻辑蕴涵。若公理正确，求F+，则可根据F通过公理推出所有的函数依赖。③属于F+中函数依赖是否都能够由公理通过F中的FD推出？——公理完备性。定理：Armstrong公理是正确的，即若是由F通过公理推出的，那么在F+中。证明：用FD定义证明(1)自反性：设r是R的任意一个关系，t1和t2是r任意的两个元组。若，则在t1和t2中的的任何子集也必相等由条件：∴必有由FD定义可知：XXYYXYX]X[t]X[t21]Y[t]Y[t21YX(2)增广性：设t1,t2,r的含义同上采用反证法：假定结果不成立：，即：但由设：或若则与已知的相矛盾(,)若则与假设的相矛盾∴增广性是正确的YZXZ]XZ[t]XZ[t21]YZ[t]YZ[t21]Y[t]Y[t21]Z[t]Z[t21YX]Z[t]Z[t21]XZ[t]XZ[t21(3)传递性：设t1,t2,r的含义同上采用反证法：假设结果不成立：即XZ即但若则与条件相矛盾(∵则，但由上)，若则与条件相矛盾(∵，则)∴传递性正确]X[t]X[t21]Z[t]Z[t21]Y[t]Y[t21ZY]Z[t]Z[t21]Z[t]Z[t21]Y[t]Y[t21YX]X[t]X[t21]Y[t]Y[t21]YZ[t]YZ[t21]Y[t]Y[t21]X[t]X[t21]Y[t]Y[t21]Y[t]Y[t21推论：由阿氐公理可以得出如下推论：(1)合并规则：若，成立，则成立(2)分解规则：若成立，则，成立(3)伪传递规则：若，成立，则成立YXZXYZXZYWZXW证明：用公理证明(1)∵(已知)(2)∵(3)∵(已知)∴(公理A2)∴(公理A1)∴(公理A2)又∵(已知)同理(公理A1)∵(已知)∴(公理A2)∵(已知)∴(公理A3)∴(公理A3)∴(公理A3)同理(公理A3)XYXYZXYYZXUYZYYYZZYZYZXZXYWXWZYWZXWYXYXYXYXYXYZXZXZX例：判断下列推论是否正确，若正确给出相关证明；若错误，试举出一反例说明(1)如果AB→C，则B→C(2)如果AB→C，则A→B,或A→C(3)如果A→B并且BC→D,则ABC→D解：(1)错误(2)错误(3)正确ABC010001ABC000101RR∵A→B∴ABC→BC又∵BC→D∴ABC→D（公理A3）R满足AB→C但BC;R满足AB→C但AC，AB说明：①通过规则A1，得出平凡的FD概念：对于函数依赖,若,则称是平凡的函数依赖；若，则为非平凡的FD。如：A→A,A→Φ是平凡FD.平凡FD总是成立的，对A的语义无影响，对模式设计也没有影响。一般不考虑平凡FDYXXYYXXYYX②根据推论中合并和分解规则：得出推论