第10章 数据依靠和关系模式规范化

本文格式为Word版，下载可任意编辑——第10章数据依靠和关系模式规范化

数据依靠和关系模式规范化

第10章数据依靠和关系模式规范化10.110.210.310.410.510.6关系模式设计中的数据语义问题函数依靠(FD)多值依靠(MVD)联接依靠(JD)*关系模式的分解及其问题关系模式的规范化

数据依靠和关系模式规范化

10.1关系模式设计中的数据语义问题前面我们已经探讨了关系数据库的基本概念、关系模型的三个部分以及关系数据库的标准语言SQL。但是还有一个很基本的问题尚未涉及，针对一个具体问题，应当如何构造一个适合于它的数据库模式，即应当构造几个关系模式，每个关系由哪些属性组成等。这是数据库设计的问题，确凿地讲是关系数据库规律设计问题。

数据依靠和关系模式规范化

10.1关系模式设计中的数据语义问题下面首先回想一下关系模型的形式化定义。一个关系模式应当是一个五元组。R(U,D,DOM,F)这里：–––––关系名R,它是符号化的元组语义；一组属性U;属性组U中属性所来自的域D;属性到域的映射DOM;属性组U上的一组数据依靠F

由于D和DOM对模式设计关系不大,因此我们在本章中把关系模式看作是一个三元组：RU,F当且仅当U上的一个关系r满足F时，称r为关系模式RU,F的一个关系。

数据依靠和关系模式规范化

10.1关系模式设计中的数据语义问题关系作为一张二维表,我们对它有一个最起键的要求：每一个分量必需是不可分的数据项。满足了这个条件的关系模式就属于第一范式(1NF)。我们的任务是研究模式设计，研究设计一个“好〞的(没有“毛病〞的)关系模式的方法。数据依靠是通过一个关系中属性间值的相等与否表达出来的数据间的相互关系。它是现实世界属性间相互联系的抽象，是数据内在的性质，是语义的表达。现在人们已经提出了大量种类型的数据依靠，其中最重要的是函数依靠(FunctionalDependency简记为FD)和多值依靠(MultivaluedDependency简记为MVD)。函数依靠极为普遍地存在于现实生活中。

数据依靠和关系模式规范化

10.1关系模式设计中的数据语义问题譬如描述一个学生的关系,可以有学号(SNO),姓名(SNAME),系名(SDEPT)等几个属性。由于一个学号只对应一个学生,一个学生只在一个系学习。因而当“学号〞值确定之后,姓名和该生所在系的值也就被唯一地确定了。就象自变量x确定之后,相应的函数值f(x)也就唯一地确定了一样，我们说SNO函数决定SNAME和SDEPT,或者说SNAME,SDEPT函数依靠于SNO,记为∶SNO→SNAME,SNO→SDEPT。

数据依靠和关系模式规范化

10.1关系模式设计中的数据语义问题现在我们要建立一个数据库来描述学生的一些倩况。面临的对象有：学生(用学号SNO描述),系(用系名SDEPT描述),系负责人(用其姓名MN描述),课程(用课程名CNAME描述)和成绩(G)。现实世界的已知事实

告诉我们∶1)2)3)4)一个系有若干学生,但一个学生只属于一个系；一个系只有一名(正职)负责人；一个学生可以选修多门课程,每门课程有若干学生选修；每个学生学习每一门课程有一个成绩；

假使只考虑函数依靠这一种数据依靠,我们就得到了一个描述学校的数据库模式SU,F,它由一个单一的关系模式构成：U={SNO,SDEPT,MN,CNAME,G}F={SNO→SDEPT,SDEPT→MN,(SNO,CNAME)→G}

数据依靠和关系模式规范化

10.1关系模式设计中的数据语义问题这个模式有下述三个“毛病〞:1)插入异常：假使一个系刚成立尚无学生,或者虽然有了学生但尚未安排课程。那么我们就无法把这个系及其负责人的信息存入数据库。删除异常：反过来,假使某个系的学生全部毕业了,我们在删除该系学生选修课程的同时,把这个系及其负责人的信息也丢掉了。更新异常：譬如，某系负责人更换后,就必需逐一修改有关的每一个元组。数据冗余：譬如,每一个系负责人的姓名要与该系每一个学生的每一门功课的成绩出现的次数一样多。

2)

3)

4)

这样,一方面浪费存储,另一方面系统耍付出很大的代价来维护数据库的完整性。

数据依靠和关系模式规范化

10.1关系模式设计中的数据语义问题为什么会发生插入异常和删除异常呢?这是由于这个模式中的函数依靠存在某些不好的性质。假使我们把这个单一的模式改造一下,分成三个关系模式：SSNO,SDEPT,SNO→SDEPT;SGSNO,CNAME,G,(SNO,CNAME)→G;DEPTSDEPT,MN,SDEPT→MN;这三个模式都不会发生插入异常、删除异常的毛病,数据的冗佘也得到了控制。一个模式的函数依靠会有哪些不好的性质,如何改造一个不好的模式,这就是本章要探讨的主要内容。

数据依靠和关系模式规范化

10.2函数依靠定义10.1:设R(U)是属性集U上的关系模式。X,Y是U的子集。若对于R(U)的任意一个可能的关系r,r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依靠于X,记作X→Y。下面介绍一些术语和记号：–––––X→Y,但YX,则称X→Y为平凡的函数依靠。否则，称X→Y为非平凡的函数依靠。今后，若不特别声明，我们总是探讨非平凡的函数依靠。若X→Y,则称X为决定因素(Determinant)。若X→Y,Y→X,则记作X←→Y。若Y不函数依靠于X,则记作XY。

数据依靠和关系模式规范化

10.2函数依靠定义10.2:在R(U)中,假使X→Y,并且对于X的任何一个真子集X',都有X'Y,则称Y对X完全函数依靠,记作:XY。若X→Y,但Y不完全函数依靠于X,则称Y对X部分函数依靠,记作XY。定义10.3:在R(U)中,假使X→Y,(YX),YX,Y→Z,则称Z对X传递函数依靠。加上条件YX,是由于假使Y→X,则X←→Y,实

际上是,是直接函数依靠而不是传递函数依靠。定义10.4:对于满足一组函数依靠F的关系模式RU,F,其任何一个关系r,若函数依靠X→Y都成立(即r中任意两元组t,s,若t[X]=s[X],则t[Y]=s[Y]),则称F规律蕴含X→Y,记为F|=X→Y

数据依靠和关系模式规范化

10.2函数依靠Armstrong公理系统为了求得给定关系模式的键,为了从一组函数依靠求得蕴含的函数依靠，例如，已知函数依靠集F,要问X→Y是否为F所蕴含，就需要一套推理规则，这组推理规则是l974年首先由Armstrong提出来的。设U为属性集总体，F是U上的一组函数依靠,于是有关系模式RU,F。对RU,F来说有以下的推理规则：Al.自反律(Reflexivity):若YXU,则X→Y为F所蕴含。A2.增广律(Augmentation):若X→Y为F所蕴含，且ZU,则XZ→YZ为F所蕴含。A3.传递律(Transitivity):若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。注意，由自反律所得到的函数依靠均是平凡的函数依靠，自反律的使用并不依靠于F。

数据依靠和关系模式规范化

10.2函数依靠定理10.l:Armstrong推理规则是正确(sound)的。证：1)设YXU。对RU,F的任一关系r中的任意两个元组t,s:若t[X]=s[X],由于YX,有t[y]=s[y],所以X→Y成立，自反律得证。设X→Y为F所蕴含,且ZU。设RU,F的任一关系r中任意的两个元组t,s;若t[XZ]=s[XZ],则有t[X]=s[X]和t[Z]=s[Z];由X→Y,于是有t[Y]=s[Y],所以t[YZ]=s[YZ],所以XZ→YZ为F所蕴含，增广律得证。设X→Y及Y→Z为F所蕴含。对RU,F的任一关系r中的任意两个元组t,s。若t[X]=s[X],由于X→Y,有t[Y]=s[Y];再由Y→Z,有t[Z]=s[Z],所以X→Z为F所蕴含，传递律得证。

2)

3)

数据依靠和关系模式规范化

10.2函数依靠根据这三条推理规则可以得到下面三条很有用的推理规则:1)2)3)合并规则:由X→Y,X→Z,有X→YZ。伪传递规则：由X→Y,WY→Z,有XW→Z。分解规则：由X→Y及ZY,有X→Z。

根据合并规则和分解规则,很简单得到这样一个重要事实：引理10.l:X→A1A2...Ak成立的充分必要条件是X→Ai成立(i=l,2,...,k)。

数据依靠和关系模式规范化

10.2函数依靠定义10.5:在关系模式RU,F中为F所规律蕴含的函数依靠的全体叫做F的闭包,记为F+。定义10.6:给定关系模式RU,F,假使能由F根据Armstrong公理导出X→Y,则称X→Y是F的规律导出，记为F=X→Y。人们把自反律,传递律和增广律称为Armstrong公理系统。Armstrong公理系统是有效的、完备的。Armsttrong公理的有效性指的是：由F出发根据Armstrong公理推导出来的每一个函数依靠一定在F+中；Armsttrong公理的完备性指的是F+中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。

数据依靠和关系模式规范化

10.2函数依靠要证明Armsttrong公理的完备性，就首先要解决如何判定一个函数依靠是否属于由F根

据Armstrong公理推导出来的函数依靠的集合。当然，假使能求出这个集合，问题就解决了。但不幸的是，这是一个NP完全问题。譬如从F={X→A1...,X→An}出发，我们至少可以推导出2n个不同的函数依靠。为此引入下面概念：定义10.7:设F为属性集U上的一组函数依靠，XU,XF+={A|X→A能由F根据Armstrong公理导出},XF+称为属性集X关于函数依靠集F的闭包。

数据依靠和关系模式规范化

10.2函数依靠由引理10.1简单得出：引理10.2:设F为属性集U上的一组函数依靠，X,YU,X→Y能由F根据Armstrong公理导出的充分必要条件是YXF+。于是,判定X→Y是否能由F根据Armstrong公理导出的问题，就转化为求出XF+,并判定Y是否为XF+的子集的问题。这个问题由算法10.l解决了。

数据依靠和关系模式规范化

10.2函数依靠算法10.l:求属性集X(XU)关于U上的函数依靠集F的闭包XF+。输入：X,F输出：XF+步骤：1)2)令X(0)=X,i=0求B,这里B={A|(存在V→W)(V→W∈F∧V∈X(i)∧A∈W)};X(i+1)=X(i)∪B判断X(i+1)=x(i)吗?若相等或X(i)=U则X(i)就是XF+,算法终止。若否，则i=i+l,返回第2)步。

3)4)5)6)

数据依靠和关系模式规范化

10.2函数依靠例1:已知关系模式RU,F,其中U={A,B,C,D,E};F={AB→C,B→D,C→E,EC→B,AC→B}。求(AB)F+。解：由算法5.1,X(0)=AB;计算X(1);逐一的扫描F集合中各个函数依靠,找左部为A,B,或AB的函数依靠。得到两个：AB→C,B→D。于是X(1)=AB∪CD=ABCD。由于X(0)≠X(1),所以再找出左部为ABCD子集的那些函数依赖，又得到C→E,AC→B,于是X(2)=X(1)∪BE=ABCDE。由于X(2)已等于全部属性集合,所以(AB)F+=ABCDE。对于算法10.l,令ai=|X(i)|,{ai}形成一个步长大于1的严格递增的序列,序列的上界是|U|,因此该算法最多|U|-|X|次循环就会终止。

数据依靠和关系模式规范化

10.2函数依靠定理10.2:Armstrong公理系统是有效的、完备的。Armstrong公理系统的有效性可由定理1