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

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

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

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

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

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

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

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

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

10.1 关系模式设计中的数据语义问题 关系作为一张二维表,我们对它有一个最起键的要求： 每一个分量必须是不可分的数据项。满足了这个条件 的关系模式就属于第一范式(1NF)。 我们的任务是研究模式设计，研究设计一个“好”的 (没有“毛病”的)关系模式的办法。 数据依赖是通过一个关系中属性间值的相等与否体现 出来的数据间的相互关系。它是现实世界属性间相互 联系的抽象，是数据内在的性质，是语义的体现。 现在人们已经提出了许多种类型的数据依赖，其中最 重要的是函数依赖(Functional Dependency简记为FD)和 多值依赖(Multivalued Dependency简记为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) 一个系有若干学生,但一个学生只属于一个系； 一个系只有一名(正职)负责人； 一个学生可以选修多门课程,每门课程有若干学生选修； 每个学生学习每一门课程有一个成绩；

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

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

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

2)

3)

4)

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

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

10.1 关系模式设计中的数据语义问题 为什么会发生插入异常和删除异常呢 ? 这是因为这个模式中的函数依赖存在某些不好的性 质。 假如我们把这个单一的模式改造一下,分成三个关系 模式： S<SNO,SDEPT, SNO→SDEPT>; SG<SNO,CNAME,G, (SNO,CNAME)→G>; DEPT<SDEPT,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,但Y X,则称X→Y为平凡的函数依赖。否则，称 X→Y为非平凡的函数依赖。 今后，若不特别声明，我们总是讨论非平凡的函数依赖。 若X→Y,则称X为决定因素(Determinant)。 若X→Y,Y→X,则记作X←→Y。 若Y不函数依赖于X,则记作X Y。

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

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

际上是 , 是直接 函数依赖而不是传递函数依赖。 定义10.4:对于满足一组函数依赖F的关系模式R<U,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上的一组函数依赖, 于是有关系模式 R<U,F>。 对R<U,F>来说有以下的推理规则： Al.自反律(Reflexivity): 若Y X U,则X→Y为F所蕴含。 A2.增广律(Augmentation): 若X→Y为F所蕴含，且Z U,则 XZ→YZ为F所蕴含。 A3.传递律(Transitivity): 若X→Y及Y→Z为F所蕴含，则X→Z为F 所蕴含。 注意，由自反律所得到的函数依赖均是平凡的函数依赖，自反律 的使用并不依赖于F。

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

10.2 函数依赖定理10.l:Armstrong推理规则是正确(sound)的。 证：1) 设Y X U 。 对R<U,F>的任一关系r中的任意两个元组t,s: 若t[X]=s[X],由于Y X,有t[y]=s[y], 所以X→Y成立，自反律得证。 设X→Y为F所蕴含,且Z U。 设R<U,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所蕴含。 对R<U,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及Z Y,有X→Z。

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

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

10.2 函数依赖 定义10.5:在关系模式R<U,F>中为F所逻辑蕴含的函 数依赖的全体叫做F的闭包,记为F+ 。 定义10.6:给定关系模式R<U,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上的一组函数依赖，X U, XF+={ A|X→A能由F根据Armstrong公理导出},XF+ 称为属性集X关于函数依赖集F的闭包。

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

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

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

10.2 函数依赖 算法10.l: 求属性集X(X U)关于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:已知关系模式R<U,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公理系统的有效性可由定理10.l得到证明。 下面我们给出完备性的证明。 我们证明完备性的逆否命题，即若函数依赖X→Y不 能由F从Armstrong公理导出，那么它必然不为F所蕴 含，其证明分三步： 若V→W成立，且V XF+,则W XF+ 。 因V XF+ ,有X→V成立；由A3规则有X→W成立，所 以W XF+ 。

1)

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

10.2 函数依赖2) 由下列两个元组构成的二维表，必是R<U,F>的一个 关系r,即满足F中的全部函数依赖。

若r不是R<U,F>的关系，则必由于F中有函数依赖 V→W在r上不成立所致。由r的构成可知，V必定是 XF+ 的子集，而W不是XF+ 的子集，可是由 l), W XF+,矛盾。所以r必是R<U,F>的一个关系。

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

10.2 函数依赖3) 若X→Y不能由F从Armstrong公理导出，则Y不是XF+ 的子集，因此必有Y的子集Y‘满足Y’ U-XF+,即 X→Y在r上不成立，故X→Y必不为R<U,F>蕴含.

Armstrong公理的完备性及有效性说明了“逻辑导出” 与“逻辑蕴含”是两个完全等阶的概念。 于是F+ 也可以说成是由F出发借助Armstrong公理导出 的函数依赖的集合。 从蕴含(或导出)的概念出发，又引出了两个函数依赖 集等价和最小依赖集的概念。

本文来源：https://www.bwwdw.com/article/bzbe.html