关系数据库的规范化理论

第3章关系数据库的规范化理论本章导读：关系规范化理论研究的是关系模式中各属性之间的依赖关系及其对关系模式性能的影响，探讨“好”的关系模式应该具备的性质，以及达到“好”的关系模式提供的方法。关系规范化理论提供了判断关系逻辑模式优劣的理论标准，是数据库设计的理论基础和关系模式算法工具，用于帮助数据库设计工程师预测和优化模式可能出现的问题。知识要点：存储异常函数依赖数据依赖的公理系统规范化3.1存储异常现实世界中，事物往往是相关的，一个实体型的诸属性之间具有内在联系，例如一个学生的学号总是包含入学年份，院系编号等相关信息；又如通过查找一个课程编号，可以确定该课程的名称及其学时信息；再如通过学号和课程编号可以确定一个学生一门课的成绩。设计、验证和修改关系模式，首要的问题就是将关系模式中各属性之间的关系分析清楚。在关系模式设计过程中，同样一个问题的求解，不同人抽象出来的数据库模式可能有所不同。如何设计和评价一个合理的关系模式，使之既能准确反映现实世界，又能适合实际应用，是关系数据库设计的主要内容。例如，设计一个教学管理系统，该系统涉及的有学生、教师、课程三个对象。对象具有的属性如下：（1）学生：学号，姓名，年龄，籍贯等；（2）教师：职工编号，姓名，职称，课酬标准等；（3）课程：课程编号，课程名称，学时等。由现实世界的已知事实知道，可以得到以下语义。（1）一个学生的学号是唯一的；（2）一个教师的职工编号是唯一的；（3）一门课程的课程编号是唯一的；（4）一个学生可以选修多门课，每门课程可由多个学生学习；（5）每个学生的每门课程均有一个成绩；（6）每个教师可以讲授多门课。3.1存储异常根据以上分析，可以采用单一的数据库模式，即Jxgl(学号，学生姓名，年龄，籍贯，职工编号，教师姓名，职称，课酬标准，课程编号，课程名称，学时，成绩)对应这种单一的模式，在实际数据库，可能会存在如下几个问题：（1）数据冗余如果某个学生选修多门课，则学生的信息会重复出现多次，造成数据冗余。同理多个学生选修一门课，则该门课程及授课的教师信息也会重复出现多次。（2）更新异常由于数据的冗余，当更新数据库中的数据时，系统需要付出很大的代价来维护数据库的完整性，否则会造成数据不一致。如更新某门课程的主讲教师，则要更新选修该门课程的所有元组，修改其中的主讲教师信息，如有疏忽，就会造成数据的不一致。（3）插入异常如果某个学生还没有选课，课程号为空，但是根据实体完整性规则——主属性不能为空，无法插入主属性取空值的学生信息，同理也不能插入主属性取空值的课程信息和教师信息。（4）删除异常如果删除某个教师信息，由于主属性不能为空，必然在删除教师信息的同时，连带删除学生和课程信息，从而删除掉了不应该删除的信息，但事实上学生和课程信息应该予以保留。同理删除学生信息，或者课程信息，也会存在这个问题。3.1存储异常发生这些异常问题的根本原因：数据冗余，即没有考虑模式内部属性之间的内在相关性，简单地把无直接联系的属性放在一起构成关系模式，造成不必要的数据冗余。解办法就是将现有单一关系模式进行分解，改造成如下5个模式。（1）学生(学号，姓名，年龄，籍贯)。（2）教师(职工编号，姓名，职称，课酬标准)。（3）课程(课程编号，课程名称，学时)。（4）选课(学号，课程编号，成绩）。（5）授课(职工编号，课程编号，课酬)。3.2函数依赖设计好的数据库是否实用、高效，或者是否合理、正确，可依据关系数据库设计理论进行核查。关系数据库设计理论要包括3个方面：数据依赖、范式、模式设计方法，其中数据依赖起着核心作用，因为它是解决数据库的数据冗余和操作（插入、删除和更新）异常问题的关键所在。3.2函数依赖1．数据依赖和函数依赖关系模式中各属性之间相互依赖，相互制约的关系称为数据依赖。数据依赖是通过关系中属性间的值是否相等体现出来的数据间的相互关系，它是信息世界属性间相互联系的抽象，是数据内在的性质，是语义的体现。数据冗余的产生和数据依赖有密切的关系。数据依赖一般分为函数依赖、多值依赖和连接依赖，其中最重要的是函数依赖。【定义3.1】设有关系模式R(A1,A2,A3,…An)，简记R(U)，X和Y是属性集U的子集，如果对于R(U)的任意一个可能的关系r，对于X的每一个具体值，Y都有唯一的具体值与之对应，则称X函数决定Y，或Y函数依赖于X，记为X→Y。其中X称为这个函数依赖的决定属性集或决定因素，与之相对应，Y称为被决定因素。函数依赖如同数学中函数一样，自变量x确定以后，相应的的函数值f(x)也就唯一确定了。对于函数依赖有以下几点具体说明：（1）函数依赖不是指关系模式R的某个或某些关系满足的约束条件，而是指R的所有关系均要满足的约束条件；（2）函数依赖是语义范畴的概念，只能根据语义来确定函数依赖。例如：函数依赖“姓名→所在系”只有在学生不重名的情况下成立，如果允许重名，则“所在系”不能函数依赖于“姓名”了；（3）函数依赖是属性关联的客观存在和数据库设计者的人为强制相结合的产物；（4）若Y不函数依赖于X，记作X↛Y；（5）若X→Y，且Y→X，则记作X↔Y。函数依赖根据其性质可分为完全函数依赖，部分函数依赖，传递函数依赖、平凡函数依赖和非平凡函数依赖等。3.2函数依赖2．平凡函数依赖和非平凡函数依赖（1）非平凡函数依赖设有关系模式R(U)，X和Y是属性集U的子集，如果对于R(U)的任意一个可能的关系r，若XY，且Y不属于X的子集，则称XY是非平凡函数依赖。（2）平凡函数依赖若XY，且Y属于X的子集，则称XY是平凡函数依赖。平凡函数依赖总是成立的，它不反映新的语义，没有特别说明，总是讨论非平凡函数依赖。例如在关系模式R(学号,姓名,课程号,成绩)中，(学号,课程号)成绩是非平凡函数依赖，(学号,课程号)学号，(学号,课程号)课程号是平凡函数依赖。3.2函数依赖3．完全函数依赖和部分函数依赖（1）完全函数依赖设有关系模式R(U)，X和Y是属性集U的子集，如果对于R(U)的任意一个可能的关系r，若XY，且对X中的任何真子集Z，都有Z↛Y，则称Y完全函数依赖于X，记作：XfY。例如，在关系模式R(教师编号，姓名，职称，课酬标准，课程号，课程名称，学时，课酬)中，因为教师编号↛课酬，且课程号↛课酬，所以(教师编号，课程号)f课酬。（2）部分函数依赖设有关系模式R(U)，X和Y是属性集U的子集，如果对于R(U)的任意一个可能的关系r，若XY，且X中存在一个真子集Z，满足ZY，则称Y部分函数依赖于X，记作：XP→Y。例如，在关系模式R(教师编号，姓名，职称，课酬标准，课程号，课程名称，学时，课酬)中，因为教师编号→姓名，且课程号课程名称，所以(教师编号，课程号)P姓名，(教师编号，课程号)P课程名称。换言之，在一个函数依赖关系中，只要决定属性集中不包含多余的属性，即从决定属性集中去掉任何一个属性，函数依赖关系都不成立，就是完全函数依赖，否则就是部分函数依赖。由此可知，决定属性集中只包含一个属性的函数依赖一定是完全函数依赖。3.2函数依赖4．传递函数依赖设有关系模式R(U)，X、Y和Z是属性集U的子集，如果对于R(U)的任意一个可能的关系r，如果XY，YZ，且Y↛X，Z-X、Z-Y和Y-X均不为空，则称Z传递函数依赖于X，记作：Xt→Z。例如，在关系模式R(教师编号，姓名，职称，课酬标准，课程号，课程名称，学时，课酬)中，因为教师编号→职称，职称课酬标准，职称↛教师编号，所以教师编号t课酬标准是课酬标准传递函数依赖教师编号。3.3规范化数据依赖的公理系统是模式分解算法的理论基础，函数依赖的一个有效而完备的公理系统是Armstrong系统，它是Armstrong于1974年提出来的一套从函数依赖推导逻辑蕴含的推理规则。1.Armstrong公理系统【定义3.2】设R是一个具有属性集合U的关系模式，F是R上函数依赖集合，对于任何一组满足函数依赖F的关系r，若函数依赖X→Y都成立（即r中任意两元组t，s，若t[X]=s[X]，则t[Y]=s[Y]），则称F逻辑蕴含X→Y。为了求得给定关系模式的码，从一组函数依赖中求得其蕴含的函数依赖，就需要使用Armstrong公理系统。Armstrong公理系统对关系模式RU,F来说有以下的推理规则：A1.自反律（平凡函数依赖）：若Y⊆X⊆U，则X→Y为F所蕴含。A2.增广律：若X→Y为F所蕴含，且Z⊆U，则XZ→YZ为F所蕴含。A3.传递律：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F。根据A1、A2、A3这3条推理规则可以得到下面3条很有用的导出规则：合并规则：由X→Y，X→Z，有X→YZ（由A2、A3导出）。伪传递规则：由X→Y，WY→Z，有XW→Z（由A2、A3导出）。分解规则：由X→Y及ZY，有X→Z（由A1、A3导出）。3.3规范化【引理3.1】X→A1A2…Ak成立的充分必要条件是X→Ai成立（i=l,2,…,k）。【定义3.3】设F为属性集U上的一组函数依赖，X⊆U，XF+={A|X→A能由F根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F的闭包。【引理3.2】设F为属性集U上的一组函数依赖，X、Y⊆U，X→Y能由F根据Armstrong公理导出的充分必要条件是Y⊆XF+。于是，判定X→Y是否能由F根据Armstrong公理导出的问题，就转化为求出XF+，判定Y是否为XF+的子集的问题。这个问题可以使用算法3.1解决。2.求解函数依赖集的闭包【算法3.1】求属性集X（X⊆U）关于U上的函数依赖集F的闭包XF+。输入：X，F。输出：XF+。步骤：（1）令X（0）=X，i=0；（2）求B，这里B={A|(V)(W)(V→W∈F∧V⊆X（i）∧A∈W)}；注意：逐一的扫描F集合中的各函数依赖，找决定因素是X（i）的子集的函数依赖，用找到的函数依赖的依赖因素A组成集合B。（3）X（i+1）=B∪X（i）；（4）判断X（i+1）=X（i）；（5）若相等或X（i+1）=U，则X（i+1）就是XF+，算法终止；（6）若否，则i=i+l，返回第（2）步。【例3-1】已知关系模式RU,F，其中U={A,B,C,D,E}，F={AB→C,B→D,C→E,EC→B,AC→B}，求(AB)F+。解：设X（0）=AB（1）计算X（1）：逐一扫描F集合中各个函数依赖，找左部为A、B或AB的函数依赖，得到两个：AB→C，B→D。于是，X（1）=AB∪CD=ABCD。（2）因为X（0）≠X（1），所以再找出左部为ABCD的子集的那些函数依赖，又得到AB→C，B→D，C→E，AC→B。于是，X（2）=X（1）∪BCDE=ABCDE。（3）因为X（2）=U，算法终止。得到结果：(AB)F+=ABCDE。3．最小依赖集从蕴含的概念出发，又引出了最小依赖集的概念。每一个函数依赖集F均等价于一个极小函数依赖集Fm，此Fm称为F的最小依赖集。求得最小函数依赖集是模式分解的基础。下面就给出求F的最小依赖集的算法。【算法3.2】分3步对F进行“极小化处理”，找出F的一个最小依赖集。（1）逐一检查F中各函数依赖FDi：X→Y。若Y=A1A2…Ak，k2，则用{X→Aj|j=1,2,…,k}来取代X→Y。（2）逐一检查F中各函数依赖FDi：X→A，令G=F－{X→A}，若A∈XG+，则从F中去掉此函数依赖。（3）逐一取出F中各函数依赖FDi：X→A，设X=B1B2…Bm，逐一考察Bi（i=l,2,…,m），若A∈(X－Bi)F+，则以X－Bi取代X。最后剩下的F就一定是极小依赖集。【例3-2】F={AB→C,B→D,C→E,EC→B,AC→B}，求其极小函数依赖集。解：第一步：先分解右端，F不变。F={AB→C,B→D,C→E,EC→B,AC→B}第二步：（1）去掉AB→C，得到G={B→D,C→E,EC→B,AC→B}，求ABG+，ABG+中不包含C，不可以