数据库原理

第10章数据依赖和关系模式的规范化10.1关系模式设计中的一些数据语义问题数据的语义不但表现为完整性约束，对数据库的状态或状态的转换施加一定的限制，而且对关系模式的设计也提出一定的要求。属性间往往存在一定的依赖关系，而最基本的依赖关系是函数依赖。所谓函数依赖是指一个或一组属性的值可以决定其他属性的值。一般地讲，设Ｘ，Ｙ是关系的两个不同的属性组，如果Ｙ函数依赖于Ｘ，或Ｘ函数决定Ｙ，则其依赖关系可表示为Ｘ→Ｙ。设有一关系Ｒ，具有下列属性：学号（S＃）、课程号（C＃）、成绩（G）、任课教师姓名（TN）、教师所在系名（D）。这些数据具有下列语义：（１）学号是一个学生的标识，课程号是一门课程的标识，这些标识与其代表的学生和课程分别一一对应；（２）一位学生所修的每门课程都有一个成绩；（３）每门课程（注意：不是每种课程！同一种课，如数学课，可以开好多门，每门课有一个课程号）只有一位任课教师，但一位教师可以教多门课；（４）教师中没有重名，每位教师只属于一个系。根据上述语义，可以确认下面函数依赖的集合：Ｆ＝｛｛Ｓ＃，Ｃ＃｝→Ｇ，Ｃ＃→ＴＮ，ＴＮ→Ｄ｝从图１０－１可以看出，属性集｛Ｓ＃，Ｃ＃｝可以决定其他所有属性的值，而｛Ｓ＃，Ｃ＃｝的任何子集则不能，故｛Ｓ＃，Ｃ＃｝是这个关系的主键。这样的关系用来查询是很方便的。计算机系通知教师准备给学生补考，可以“查询图10-1函数依赖计算机系所开课程的不及格学生的学号、不及格课程号以及任课教师的姓名”.查询仅涉及Ｒ一个关系，是一元查询，不须做连接运算，可以用下面的SQL语句来表达：SELECTS＃，C＃，TNFROMRWHEREＤ＝CS′ANDＧ＝F′;但是这样的关系也有问题，首先数据冗余太多，如一门课程的教师名须对选这门课的所有学生重复一次；一个系名须对选该系所开课程的所有学生重复一次。除冗余外，在进行增、删、改操作时，还会发生所谓更新异常现象:（１）由于冗余，在修改时往往会导致数据的不一致。例如，改变一门课程的任课教师，或一门课改由另一个系开出，则需要修改多个元组。如果部分修改，部分不修改，则会导致数据的不一致。这叫修改异常。（２）由于主属性不能为空值，如某系有位教师不教课，则这位教师的姓名及所属的系名就不能插入；同样，如果一位教师所开的课暂时无人选，或是列入计划而目前不开，则也无法插入。这叫插入异常。（３）如果所有学生都退选一门课，则有关这门课的其他数据（任课教师名及所属系名）也将被删除。如果一位教师因病暂时停开他所开的课，则有关这位教师的其他信息（所属系、可开课程）都将被删去。这叫删除异常。在上例的关系中，包含了三方面的信息：学生各门课程的成绩，各门课程开课的教师以及各个教师所属的系。上例中,所有这三方面的数据都集中在一个关系中，此关系的主键为属性集｛S＃，C＃｝。（C＃，TN）和（TN，D）本来可以作为独立的关系而存在，而今却不得不依附于其他关系。这就是说，必须对应一个主键｛S＃，C＃｝的值，才能插入或存在一个（C＃，TN）或（TN，D）的值。这是关系结构带来的限制，不是现实世界的真实反映。解决这个问题的途径是把关系分解，也就是进行所谓关系规范化。例如，把上例的关系分解为下列三个关系：SCG（S＃，C＃，G）CTN（C＃，TN）TND（TN，D）这样的分解使关系的语义单纯化，使之符合“一地一事”的原则。但是分解以后，对某些查询必须进行开销很大的连接操作，影响数据库的性能。关系的规范化主要是对关系进行必要的分解，但如何分解，分解后是否有损于原来的信息，回答这些问题需要理论的指导，下面将讨论这些问题。Ｒ表示一个关系的模式，U={A1,A2,…,An}是R的所有属性的集合，F是R中函数依赖的集合，r是R所取的值，即R实有元组的集合。定义10-1设有一关系模式R(A1,A2,…,An),X和Y为其属性的子集。设t1,t2是关系R中的任意两个元组，如果t1[X]=t2[X],则t1[Y]=t2[Y]。这时我们称Y函数依赖于X，或X函数决定Y，X称为决定子（determinant）。一个函数依赖要能成立，不但要求关系的当前值都能满足函数依赖条件，而且还要求关系的任一可能值都能满足函数依赖条件。确认一个函数依赖，需要弄清数据的语义，而语义是现实世界的反映，不是主观的臆断。如果Ｙ为Ｘ的子集，显然Ｘ→Ｙ成立，这称为平凡函数依赖（trivialfunctionaldependency）。平凡函数依赖必然成立，它不反映新的语义。我们平常所指的函数依赖一般都指非平凡函数依赖（nontrivialfunctionaldependency）。如果Ｙ不函数依赖于Ｘ，则记做ＸＹ。如果Ｘ→Ｙ且Ｙ→Ｘ，则Ｘ与Ｙ一一对应，可记做定义10-2设X,Y是某关系的不同属性集,如X→Y，且不存在X′为X的子集，使X′→Y，则称Y完全函数依赖(fullfunctionaldependency）于X，记做XY；否则称Y部分函数依赖p（partialfunctionaldependency)于X，记做XY。fp在10.1节的例子中,｛S＃,C＃｝是主键，故｛S＃,C＃}→TN，但C＃→TN，故｛S＃，pfC＃}→TN，而｛S＃，C＃｝→G。定义10-3设X,Y,Z是某关系的不同的属性集，如果X→Y,YX,Y→Z,则称Ｚ传递函数依赖（transitivefunctionaldependency）于X。定义10-4设F是R的函数依赖集合，X→Y是R的一个函数依赖。如果一个关系模式满足F，则必然满足X→Y，就称F逻辑蕴涵X→Y，或表示为F|=X→Y。定义10-5函数依赖集合Ｆ所逻辑蕴涵的函数依赖的全体称为F的闭包（closure），记为F＋，即F＋＝{X→Y｜F|=X→Y}。为了从已知的函数依赖推导出其他函数依赖，Armstrong提出了一套推理规则，我们常称为Armstrong公理（Armstrongsaxions）。其推理规则可归结为如下三条:A1：自反律（reflexivity），则Ｘ→Ｙ成立。这是一个平凡函数依赖。A2：扩展律（augumentation）如果Ｘ→Ｙ成立，，则ＸＺ→ＹＺ成立。式中，ＸＺ和ＹＺ是Ｘ∪Ｚ和Ｙ∪Ｚ的简写，以后将沿用此表示法。A3：传递律（transitivity）如果Ｘ→Ｙ，Ｙ→Ｚ成立，则Ｘ→Ｚ成立。引理10-1Armstrong公理是正确的（sound），即如果F成立，则由F根据Armstrong公理所推导的函数依赖总是成立的。引理10-2下列三条推理规则是正确的。(1)合并规则（theunionrule）｛Ｘ→Ｙ，Ｘ→Ｚ｝|=Ｘ→ＹＺ。(2)伪传递规则（thepseudotransitivityrule）：｛Ｘ→Ｙ，ＷＹ→Ｚ｝|=ＸＷ→Ｚ。(3)分解规则（thedecompositionrule）：如果Ｘ→Ｙ且Ｚ为Ｙ的子集，则Ｘ→Ｚ成立。定义10-6设Ｘ为Ｕ的子集，则属性集Ｘ关于函数依赖集Ｆ的闭包Ｘ＋定义为Ｘ＋＝｛Ａ｜Ａ∈Ｕ且Ｘ→Ａ可由Armstrong公理导出｝。引理10-3Ｘ→Ｙ能由Armstrong公理导出的充分必＋。定理10-1Armstrong公理是正确的、完备的(complete)算法10-1计算属性集Ｘ关于Ｆ的闭包Ｘ＋。输入：属性集Ｘ为Ｕ的子集，函数依赖集Ｆ。输出：Ｘ＋。方法：按下列方法计算属性集序列X(0),X(1),…,Ｘ(i)…(1)初始化X(０)＝X，i＝０。(2)求属性集B=｛A|(V)(W)(V→W∈F∧VX(i)∧A∈W）}。(3)X(i+1)＝B∪X(i)。(4)判别X(i+1)＝X(i)。(5)若不等，i＝i＋1，返回(2)；若相等，X+=X(i)，结束。【例10-1】设Ｆ＝｛AB→C，D→EG，C→A，BE→C，BC→D，CG→BD，ACD→B，CE→AG｝，试用算法10-1计算(BD)+。解：令Ｘ(0)＝BD。找左部为BD的子集的函数依赖，只有Ｄ→ＥＧ。Ｘ(1)＝BD∪EG＝BDEG,找左部为BDEG的子集的函数依赖，有D→EG，BE→C。X(2)＝BDEG∪EGC＝BCDEG找左部为BCDEG的子集的函数依赖，有D→EG，C→A，BE→C，BC→D，CG→BD，CE→AG。X(3)＝BCDEG∪ABCDEG=ABCDEG因X(3)＝U，一望可知不必再进行计算了，(BD)+=ABCDEG。可是在算法10-1中，还要迭代一次才能结束。定义10-7设F，G为两个函数依赖集，如果F+＝G+，则称F和G是等价的，也可称F覆盖（cover）G，或G覆盖F；也可说F和G互相覆盖。引理10-4F＝G的充分必要条件是FG+且GF+。引理10-5任一函数依赖集F总可以为一右部恒为单属性的函数依赖集所覆盖.定义10-8函数依赖集Ｆ如果满足下列条件，则称为极小函数依赖集或最小覆盖。(1)F中每个函数依赖的右部为单属性。(2)F中不存在这样的函数依赖X→A，使得F－｛X→A｝与F等价。(3)在F中也不存在这样的X→A，使得F－｛X→A｝∪｛Z→A｝与F等价，式中，Z为X的子集。定理10-2任一函数依赖集F都与一最小函数依赖集F′等价。F′称为F的最小覆盖。10.3多值依赖除了函数依赖外，关系的属性间还有其他一些依赖关系，多值依赖（MultiValuedDependency,MVD）是其中之一。在多值依赖（表示为Ｘ→→Ｙ，读做Ｘ多值决定Ｙ，或Ｙ多值依赖于Ｘ）中，对于给定的Ｘ值，其对应的是Ｙ的一组数值（其个数可以从零到多个），而且这种对应关系，对于给定的Ｘ值所对应的（Ｕ－Ｘ－Ｙ）每个值都能成立。定义10-9设Ｘ，Ｙ是关系模式Ｒ的属性集，如果对于Ｒ的任何值ｒ，都有如下的性质：则称Ｒ满足X→→Y。与函数依赖一样，多值依赖也有一组公理：Ａ４：互补律如果Ｘ→→Ｙ，则Ｘ→→（Ｕ－Ｘ－Ｙ）。如果需要，可用Ｘ→→Ｙ｜（Ｕ－Ｘ－Ｙ）表示多值依赖，以强调其互补关系。Ａ５：扩展律（多值依赖）如果Ｘ→→Ｙ，，则ＷＸ→→ＶＹ。A6：传递律（多值依赖）如果Ｘ→→Ｙ，且Ｙ→→Ｚ，则Ｘ→→（Ｚ－Ｙ）。下面两个公理与函数依赖和多值依赖都有关。A7：如果Ｘ→Ｙ，则Ｘ→→Ｙ，即函数依赖是多值依赖的特例。A8：如果Ｘ→→相交的Ｗ，有Ｗ→Ｚ，则Ｘ→Ｚ。由前述公理，还可以推导出下列４个多值依赖推理规则。（１）多值依赖合并规则如果Ｘ→→Ｙ，Ｘ→→Ｚ，则Ｘ→→ＹＺ。（２）多值依赖伪传递规则如果Ｘ→→Ｙ，ＷＹ→→Ｚ，则ＷＸ→→（Ｚ－ＷＹ）。（３）混合伪传递规则如果Ｘ→→Ｙ，ＸＹ→→Ｚ，则Ｘ→（Ｚ－Ｙ）。（４）多值依赖分解规则如果Ｘ→→Ｙ，Ｘ→→Ｚ，则Ｘ→→（Ｙ∩Ｚ），Ｘ→→（Ｙ－Ｚ）及Ｘ→→（Ｚ－Ｙ）均成立。10.4连接依赖前面所讲的函数依赖和多值依赖都是数据语义对数据所施加的某种限制。这些依赖关系可以统称为数据依赖（DataDependency,DD）。数据依赖不仅包含函数依赖和多值依赖，还有其他一些依赖。函数依赖实际表现为对属性值的约束，例如，王平是计算机系的教师，若有函数依赖TN→D（参看图10-1），则在TN为王平的元组中，其对应的D必为计算机系，不能为其他值。多值依赖实际上表示为对元组值的约束，如在图10-3中，由于T→→S｜C，如果出现元组Li，No1physics及Li，No2chemistry，则必有元组Li，No2physics及Li，No1chemistry。推广这个概念，还可以发现其他依赖关系，连接依赖（JoinDependency,JD）就是其中之一。定义10-10设X1，X2，…，Xn是关系R的属性集U的子集，且∪Xi＝U。若对R的任一值，Ｒ＝∞R[Xi]均成立，则称R具有连接依赖，记为∞（X1，X2，…，Xn)。注：∞表示连接操作10.5关系模式的分解及其问题在10.1节中讨论过由函数依赖所引起的更新异常问题。同样，多值依赖和连接依赖也会引起类似的问题。解决这些问题的途径，就是按照前面曾提到过的“一地一事”原则，对关系模式进行分解，使其语义单纯化。定义10-11设有一关系模式R(U)，若用一关系模式的集合｛R1(U1)，R2(U2),…,Rk(Uk)｝来取代，其中，U＝∪