第05章关系数据理论

第五章关系数据理论5.1问题的提出回顾讨论了关系数据库的基本概念、关系模型的三个部分以及关系数据库的标准语言。问题针对一个具体问题，应该如何构造一个适合于它的数据库模式，即应该构造几个关系模式，每个关系模式由哪些属性组成等。这是数据库设计的问题，确切地讲是关系数据库逻辑设计问题。一、关系模型的形式化定义一个关系模式应当是一个五元组，即：R(U,D,DOM,F)。其中：R——关系名；U——属性组；D——属性组U中的属性所来自的域；DOM——属性到域的映射；F——属性组U上的一组数据依赖。由于D和DOM对模式设计关系不大，因此在本章中把关系模式看作是一个三元组，即：RU,F。当且仅当U上的一个关系r满足F时，r称为关系模式RU,F的一个关系。二、数据依赖接下来的任务就是研究：如何设计一个“好”的（没有“毛病”的）关系模式的办法。要找到这样一个方法，需要了解数据依赖的概念。数据依赖是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系。它是现实世界属性间相互联系的抽象，是数据内在的性质，是语义的体现。现在人们已经提出了许多种类型的数据依赖，其中最重要的是函数依赖(FunctionalDependency简记为FD)和多值依赖(MultivaluedDependency简记为MVD)。函数依赖极为普遍地存在于现实生活中。比如：描述一个学生的关系，可以有学号(Sno)，姓名(Sname)，系名(Sdept)等几个属性。由于一个学号只对应一个学生，一个学生只在一个系学习。因而当“学号”值确定之后，姓名和该生所在系的值也就被唯一地确定了。就象自变量x确定之后，相应的函数值f(x)也就唯一地确定了一样，我们说Sno函数决定Sname和Sdept，或者说Sname，Sdept函数依赖于Sno，记作：Sno→Sname，Sno→Sdept。三、函数依赖与插入删除异常建立一个数据库来描述学生的一些情况，面临的对象有：学生（用学号Sno描述），系（用系名Sdept描述），系负责人（用其姓名Manager描述），课程（用课程名Cname描述）和成绩（Grade）。由现实世界的已知事实得知：①一个系有若干学生，但一个学生只属于一个系；②一个系只有一名（正职）负责人；③一个学生可以选修多门课程，每门课程有若干学生选修；④每个学生学习每一门课程有一个成绩。根据上面的定义，我们建立一个学生关系模式SU,F，其中：U={Sno,Sdept,Manager,Cname,Grade}F={Sno→Sdept,Sdept→Manager,(Sno,Cname)→Grade}其函数依赖F还可以表示成如图5.1。图5.1学生关系模式的函数依赖图5.2学生关系模式的一个关系这个模式有下面三个“毛病”：①插入异常：如果一个系刚成立尚无学生，或者虽然有了学生但尚未安排课程。那么我们就无法把这个系及其负责人的信息存入数据库。②删除异常：反过来，如果某个系的学生全部毕业了，我们在删除该系学生选修课程的同时，把这个系及其负责人的信息也丢掉了。③冗余太大：比如，每一个系负责人的姓名要与该系每一个学生的每一门功课的成绩出现的次数一样多。这样，一方面浪费存储，另一方面系统要付出很大的代价来维护数据库的完整性。比如某系负责人更换后，就必须逐一修改有关的每一个元组。四、有函数依赖的关系改造把关系S分成三个关系模式，如下：S(Sno,Sdept,Sno→Sdept)SG(Sno,Cname,Grade,(Sno,Cname)→Grade)Dept(Sdept,Manager,Sdept→Manager)这三个模式就不会发生插入异常、删除异常的毛病，数据的冗余也得到了控制。5.2规范化为了使数据库设计的方法走向完备，人们研究了规范化理论，指导我们设计规范的数据库模式。按属性间依赖情况来区分，关系规范化的程度为第一范式，第二范式，第三范式和第四范式等。5.2.1函数依赖一、函数依赖的定义定义5.1设R(U)是属性集U上的关系模式。X，Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作X→Y。举例：如图5.2中，只要Sdept是“CS”，Manager就是“张军”，记作Sdept→Manager。注意：函数依赖不是指关系模式R的某个或某些关系满足的约束条件，而是指R的一切关系均要满足的约束条件。也就是说这个约束是针对这个关系模式的所有关系。二、函数依赖的几个术语和记号·X→Y，但YX则称X→Y是非平凡的函数依赖。若不特别声明，我们总是讨论非平凡的函数依赖。·X→Y，但YX则称X→Y是平凡的函数依赖。·若X→Y，则X叫做决定因素(Determinant)。·若X→Y，Y→X，则记作X←→Y。·若Y不函数依赖于X，则记作XY。三、完全函数依赖和部分函数依赖定义5.2在R(U)中，如果X→Y，并且对于X的任何一个真子集X'，都有X'Y，则称Y对X完全函数依赖，记作：XY。若X→Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作XY。四、传递函数依赖和直接函数依赖定义5.3在R(U)中，如果X→Y，(YX)，YX，Y→Z，则称Z对X传递函数依赖。加上条件Y→X，是因为如果Y→X，则X←→Y，实际上是XZ，即直接函数依赖而不是传递函数依赖。5.2.2码在第二章中已经讲了有关码的若干定义。这里用函数依赖的概念来定义码。一、码和主码定义5.4设K为RU,F中的属性或属性组合，若KU则K为R的候选码(Candidatekey)或码(key)。若候选码多于一个，则选定其中的一个为主码(Primarykey)。主属性：包含在任何一个候选码中的属性。非主属性或非码属性：不包含在任何码中的属性。最简单的情况，单个属性是码。最极端的情况，整个属性组是码，称为全码(All-key)。二、外码定义5.5关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码(Foreignkey)也称外码。主码与外部码提供了一个表示关系间联系的手段。5.2.3范式(NormalForm)范式，即正规公式。关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同范式。满足最低要求的叫第一范式，简称lNF。在第一范式中满足进一步要求的为第二范式，简称2NF。其余以此类推。关系模式R为第i范式就可以写成RiNF，如关系模式R为第3范式，则写成R3NF。对于各种范式，有：5NF4NFBCNF3NF2NFlNF成立。一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫规范化。5.2.41NF一、定义若关系模式R的每一个分量是不可再分的数据项，则R1NF。理解：关系R消除了行合并和列合并的情况后，则成为1NF。二、举例图5.3R1NF图5.4R1NF5.2.52NF一、定义定义5.6若R1NF，且每一个非主属性完全函数依赖于码，则R2NF。理解：当1NF消除了非主属性对码的部分函数依赖，则成为2NF。二、举例举例：一个不是2NF的例子。关系模式S-L-C(Sno,Sdept,Sloc,Cno,Grade)，其中Sloc为学生的住处，并且每个系的学生住在同一个地方。这里码为(Sno,Cno)。函数依赖有。(Sno,Cno)GradeSno→Sdept，(Sno,Cno)SdeptSno→Sloc，(Sno,Cno)SlocSdept→Sloc其依赖关系可见图5.5，图中实线表示完全函数依赖，虚线表示部分函数依赖。图5.5关系模式S-L-C的函数依赖从上面列出的依赖关系可以看出：非主属性Grade完全依赖于码(Sno,Cno)，而非主属性Sdept、Sloc只是部分依赖于码(Sno,Cno)。因此，S-L-C(Sno,Sdept,Sloc,Cno,Grade)不符合2NF的定义，即：S-L-C2NF。三、非2NF关系模式的问题如果一个关系模式R不属于2NF，就会产生以下问题：①插入异常假如要插入一个学生Sno='95010'、Sdept='MA'、Sloc='12-1'，该元组不能插入。因为该学生无Cno，而插入元组时必须给定码值。②删除异常假如某个学生只选一门课，如：95003学生只选了一门5号课，现在他不选了，希望该选课。而Cno是主属性，删除了5号课，整个元组都必须删除，从而造成删除异常，即不应该删除的信息也删除了。③修改复杂如某个学生从数学系(MA)转到计算机科学系(CS)，这本来只需修改此学生元组中的Sdept分量。但由于关系模式S-L-C中还含有系的住处Sloc属性，学生转系将同时改变住处，因而还必须修改元组中的Sloc分量。另外，如果这个学生选修了k门课，Sdept、Sloc重复存储了k次，不仅存储冗余度大，而且必须无遗漏地修改k个元组中全部Sdept、Sloc信息，造成修改的复杂化。四、非2NF关系模式的转换分析上面的例子，可以发现问题在于有两种非主属性。一种如Grade，它对码是完全函数依赖。另一种如Sdept、Sloc对码不是完全函数依赖。解决的办法是用投影分解把关系模式S-L-C分解为两个关系模式。SC(Sno,Cno,Grade)S-L(Sno,Sdept,Sloc)关系模式SC与S-L中属性间的函数依赖可以用图5.6和图5.7来表示。图5.6SC中的函数依赖图5.7S-L中的函数依赖关系模式SC的码为(Sno,Cno)，关系模式S-L的码为Sno，这样就使得非主属性对码都是完全函数依赖了。即：(Sno,Cno)Grade(Sno)Sdept(Sno)Sloc5.2.63NF一、定义定义5.7关系模式RU,F中若不存在这样的码X，属性组Y及非主属性Z(ZY)使得X→Y，(YX)Y→Z成立,则称RU,F3NF。理解：当2NF消除了非主属性对码的传递函数依赖，则成为3NF。二、举例在图5.？中关系模式SC没有传递依赖，因此SC3NF。在图5.？中关系模式S-L存在非主属性对码传递依赖，即：由Sno→Sdept，(SdeptSno)，Sdept→Sloc，可得SnoSloc。，因此S-L3NF。三、非3NF关系模式的问题一个关系模式R若不是3NF，同样会产生插入异常、删除异常、冗余度大等问题。四、非3NF关系模式的转换解决的办法同样是将S-L分解为：S-D(Sno,Sdept)和D-L(Sdept,Sloc)。分解后的关系模式S-D与D-L中不再存在传递依赖。5.2.7BCNF(BoyceCoddNormalForm)由于BCNF是由Boyce和Codd提出的，故叫BCNF，比3NF又进了一步，通常认为BCNF是修正的3NF，有时也称扩充的3NF。一、定义定义5.8关系模式RU,F1NF。若X→Y且YX时X必含有码，则RU,FBCNF。理解：当3NF消除了主属性对码的部分和传递函数依赖，则成为BCNF。由BCNF的定义可以得知，一个满足BCNF的关系模式有：·所有非主属性对每一个码都是完全函数依赖。·所有的主属性对每一个不包含它的码，也是完全函数依赖。·没有任何属性完全函数依赖于非码的任何一组属性。由于RBCNF，按定义排除了任何属性对码的传递依赖与部分依赖，所以R3NF。但是若R3NF，则R未必属于BCNF。二、举例下面用几个例子说明属于3NF的关系模式有的属于BCNF，但有的不属于BCNF。例1对关系模式C、SC、S进行分析。关系模式C(Cno,Cname,Pcno)，它只有一个码Cno，这里没有任何属性对Cno部分依赖或传递依赖，所以C3NF。同时C中Cno是唯一的决定因素，所以CBCNF。关系模式SC(Sno,Cno,Grade)可作同样分析。关系模式S(Sno,Sname,Sdept,Sage)，假定Sname也具有唯一性，那么S就有两个码，这两个码都由单个属性组成，彼此不相交。其他属性不存在对码的传递依赖与部分依赖，所以S3NF。同时S中除Sno，