关系数据库理论

简介

依赖（dependency）理论涉及如何构建一个良好的关系数据库模式，以及当一个模式存在缺陷时应如何改进。

函数依赖

关系R上的函数依赖（functional dependency，FD）是指如果R的两个元组在属性 $A_{1},A_{2},...A_{n}$ 上一致，那么它们必定在其他属性 $B_{1},B_{2},...B_{m}$ 上也一致。该函数依赖形式地标记为 $A_{1},A_{2},...A_{n}\rightarrow B_{1},B_{2},...B_{m}$ ，并称 $A_{1},A_{2},...A_{n}$ 函数决定 $B_{1},B_{2},...B_{m}$ 。如果确定关系R的每个实例都能使一个给定的FD为真，那么称R满足函数依赖f。这是在R上声明来一个约束，而不是仅仅针对R的一个特殊实例。

函数依赖中的函数是什么意思呢？ $A_{1},A_{2},...A_{n}\rightarrow B$ 被称为“函数”依赖是因为在这条规则中，有一个函数对于一个值的列表（列表中每个值对应 $A_{1},A_{2},...A_{n}$ 中的一个属性），都产生一个唯一的B值。这个函数和数学中常见的函数不同，因为这条规则无法用来计算。也就是说，不能根据前面的属性集算出后面的属性，它只有通过关系的观察才能得出结果。

分解规则：可以用一个FD的集合 $A_{1}A_{2}...A_{n}\rightarrow B_{i}$ (i=1,2,...m)替换FD $A_{1}A_{2}...A_{n}\rightarrow B_{1}B_{2}...B_{m}$

组合规则：可以用一个FD $A_{1}A_{2}...A_{n}\rightarrow B_{i}B_{2}...B_{m}$ 替换FD集合 $A_{1}A_{2}...A_{n}\rightarrow B_{i}$ (i=1,2,...m)

平凡函数依赖：如果关系上的一个约束对所有关系实例都成立，且与其他约束无关，则称其为平凡FD。平凡FD是这样一类FD： $A_{1}A_{2}...A_{n}\rightarrow B_{1}B_{2}...B_{m}$ ，其中 $\{B_{1}B_{2}...B_{m} \} \subseteq \{A_{1}A_{2}...A_{n}\}$

平凡依赖规则：FD $A_{1}A_{2}...A_{n}\rightarrow B_{1}B_{2}...B_{m}$ 等价于 $A_{1}A_{2}...A_{n}\rightarrow C_{1}C_{2}...C_{m}$ , 其中C是集合B中而不是集合A中的属性

传递规则：若关系R中FD $A_{1}A_{2}...A_{n}\rightarrow B_{1}B_{2}...B_{m}$ 和 $B_{1}B_{2}...B_{m}\rightarrow C_{1}C_{2}...C_{k}$ 都成立，那么FD $A_{1}A_{2}...A_{n}\rightarrow C_{1}C_{2}...C_{k}$ 在R中也成立

关系的键

如果下列条件满足，就认为一个或多个属性集{ $A_{1},A_{2},...A_{n}$ }是关系R的键。

1 这些属性函数决定关系的其他所有属性。也可以说，关系R不可能存在两个不同的元组，它们具有相同的 $A_{1},A_{2},...A_{n}$ 值

2 在{ $A_{1},A_{2},...A_{n}$ }的真子集中，没有一个能函数决定R的所有其他属性。也就是说，键必须是最小的

超键

一个包含键的属性集就叫做超键，超键都满足键的第一个条件，但不符合第二个。

属性的闭包

假设 $\{A_{1}A_{2}...A_{n} \}$ 是属性集合，S是FD的集合，则S集合下的属性集合 $\{A_{1}A_{2}...A_{n} \}$ 的闭包是满足下面条件的属性集合B，即使得每一个满足S中所有FD的关系，也同样满足 $A_{1}A_{2}...A_{n}\rightarrow B$ ，属性集合 $\{A_{1}A_{2}...A_{n} \}$ 的闭包记为 $\{A_{1}A_{2}...A_{n} \} ^{+}$

计算属性集合闭包的算法

输入：属性集合 $\{A_{1}A_{2}...A_{n} \}$ ，FD的集合S

输出： $\{A_{1}A_{2}...A_{n} \} ^{+}$

1 如果有必要，分解S中FD，使每个FD的右边只有一个属性

2 设X是属性集合，也就是闭包，首先将X初始化为 $\{A_{1}A_{2}...A_{n} \}$

3 反复寻找这样的FD： $B_{1}B_{2}...B_{n}\rightarrow C$ ，使得 $B_{1},B_{2},...,B_{m}$ 在X中，而C不在X中；若找到，则把C加入X，并重复这个过程。因为集合X只能增长，而任何一个关系模式中的属性都是有限的，所有最终没有任何元素能再加入X时，本步骤结束

4 当不能再看见任何属性时，集合X就是

计算闭包能方便的对某些函数依赖是否存在做出判断，举个例子，假如相对于FD集合S， $\{A，B \} ^{+} = \{A，B,C,D \}$ ,我们可以轻易的判断FD可以推导出 $AB\rightarrow C$ ，但不能推导出 $AB\rightarrow E$

闭包和键

注意当且仅当 $A_{1}，A_{2}，...A_{n}$ 是关系的超键时， $\{A_{1}，A_{2}，...，A_{n} \} ^{+}$ 才是这个关系的所有属性的集合。只有这样， $A_{1}，A_{2}，...A_{n}$ 才能函数决定所有其他的属性。如果要验证 $\{A_{1}，A_{2}，...，A_{n} \}$ 是否是一个关系的键，可以先检查 $\{A_{1}，A_{2}，...，A_{n} \} ^{+}$ 是否包含了该关系的全部属性，然后再检查不存在从 $\{A_{1}，A_{2}，...，A_{n} \}$ 中移除一个属性后的集合X，使得 $\{ X \} ^{+}$ 包含关系的所有属性。

函数依赖的闭包集合

给定一个FD集合S，则任何与S等价的FD集合都被称为S的基本集（basis）。为避免基本集的激增，只考虑那些FD的右边是单一属性的基本集，满足下面三个条件的基本集B被称为关系的最小化基本集（minimal basis），注意，最小化基本集不一定是唯一的。

1 B中所有FD的右边均为单一属性

2 从B中删除任何一个FD后，该集合不再是基本集

3 对于B中的任何一个FD，如果从其左边删除一个或多个属性，B将不再是基本集

投影函数依赖

假设有一个含有FD集合S的关系R，通过计算 $R_{l} = \Pi _{l}(R)$ 得到L对其部分属性的投影，那么 $R_{l}$ 中有哪些FD成立？这个问题的答案原则上可以通过计算函数依赖集S的投影（projection of functional dependencies S）获得。S的投影是所有满足下面条件的FD的集合：

1 从S推断而来 2 只包含 $R_{l}$ 的属性

函数依赖集的投影算法

输入：关系R和通过 $R_{l} = \Pi _{l}(R)$ 计算得到的关系 $R_{l}$ ，以及在R中成立的FD的集合S

输出：在 $R_{l}$ 中成立的FD集合

方法：1 另T为最终输出FD的集合，初始化T为空集

2 对于 $R_{l}$ 的属性集合的每一个子集X，计算 $X^{+}$ ，该计算根据FD集合S，可能会涉及一些在R模式中却不在 $R_{l}$ 模式中的属性。对于所有在 $X^{+}$ 中且属于 $R_{l}$ 的属性A，将所有非平凡的FD $X\rightarrow A$ 添加到T中

3 现在，T是在 $R_{l}$ 中成立的FD基本集，但可能不是最小化基本集。通过如下方法对T进行修改来构造最小化基本集。

a 如果T中的某个FD F能从T中其他FD推断出来，则从T中删除F

b 设 $Y\rightarrow T$ 是T中的一个FD，Y至少有两个属性，从Y中删除一个属性并记为Z。如果 $Z\rightarrow B$ 能从T中的FD（包含 $Y\rightarrow B$ ）推断，则使用 $Z\rightarrow B$ 替换 $Y\rightarrow B$

c 重复以上两个步骤，直到T不再变化

关系数据库模式设计

如何设计一个好的关系模式呢，一般来说，我们首先设计好一个能工作的关系模式，然后分析这个模式存在哪些问题，然后对已有模式进行分解，使得分解后的关系符合BCNF范式，同时也会消除之前设计的问题。

当试图在一个关系中包含过多信息时，产生的问题（如冗余）称为异常，异常基本类型有：

冗余：信息在多个元组重复

更新异常：更新某字段时，可能更新来部分元组中的字段，但另外一些元组的字段忘记更新

删除异常：某些不太相关的属性在一个关系表中，如果某属性需要清空，结果会导致另外的属性也被一起删掉，这可能不是用户所希望看到的

分解关系

一般用分解关系的方法来消除异常，给定一个关系 $R(A_{1}，A_{2}，...，A_{n} )$ ,把它分解为关系 $S(B_{1}，B_{2}，...，B_{m} )$ 和 $T(C_{1}，C_{2}，...，C_{k} )$ ,并且满足：

1 $\{ A_{1}，A_{2}，...，A_{n} \} = \{ B_{1}，B_{2}，...，B_{m} \} \cup \{ C_{1}，C_{2}，...，C_{k} \}$

2 $S = \Pi _{B_{1},B_{2},...,B_{m}}(R)$

3 $T = \Pi _{C_{1},C_{2},...,C_{k}}(R)$

Boyce-Codd范式

分解的目的就是将一个关系用多个不存在异常的关系替换。也就是说，在一个简单的条件下保证讨论的异常不存在，这个条件成为Boyce-Codd范式，简称BCNF。关系R属于BCNF当且仅当：如果R中非平凡FD $A_{1}A_{2}...A_{n}\rightarrow B_{1}B_{2}...B_{m}$ 成立，则 $\{ A_{1}，A_{2}，...，A_{n} \}$ 是关系R的超键。

任意一个两元关系属于BCNF，我们可以设想两个属性A和B，分别看下可能出现的情形：

1 没有非平凡的FD。因为只有非平凡的FD才能违反这个条件，所以BCNF肯定成立，此时{A,B}是唯一的键

2 $A\rightarrow B$ 成立，但 $B\rightarrow A$ 不成立，这种情况下，A是唯一的键，每个非平凡的FD左边都包含A，因此没有违反BCNF

3 $B\rightarrow A$ 成立但 $A\rightarrow B$ 不成立，同上

4 $A\rightarrow B$ 和 $B\rightarrow A$ 都成立，此时A和B都是键，由于任一FD的左边至少会包含A和B中的一个，因此，没有FD违反BCNF

BCNF分解算法如下

输入：关系 $R_{0}$ 和其上的函数依赖集 $S_{0}$

输出：由 $R_{0}$ 分解出的关系集合，其中每个关系均属于BCNF

方法：下列步骤可以被递归地用于任意关系R和FD集合S。初始时，R = $R_{0}$ ，S= $S_{0}$

1 检验R是否属于BCNF。如果是，不需要做任何事，返回{R}作为结果

2 如果存在BCNF违例，假设为 $X\rightarrow Y$ 。首先计算X的闭包 $X^{+}$ 。选择 $R_{1}= X^{+}$ 作为一个关系模式，并使另一个关系模式 $R_{2}$ 包含属性X以及那些不在 $X^{+}$ 中的属性

3 计算 $R_{1}$ 和 $R_{2}$ 的FD集，分别记为 $S_{1}$ 和 $S_{2}$

4使用本算法递归的分解 $R_{1}$ 和 $R_{2}$ 。返回这些分解得到的结果集合。

分解的优劣

一个关系模式被分解为一系列属于BCNF的关系前，它可能包含异常，分解之后则不包含异常。这就是所谓的“优”。但是分解也可能造成一些坏的结果。本节介绍一个分解具有的三个性质。

1 消除异常（Elimination of Anomalie）

2 信息的可恢复（recoverability of Information）。是否能够从分解后的各个元组中恢复原始关系

3 依赖的保持（Preservation of Dependencies）。如果FD的投影在分解后的关系上成立，能否确保对分解后的关系用连接重构获取的原始关系仍然满足原来的FD

BCNF分解可以保证1 和 2，第三范式能保证2和3，但没有方法能同时保证这三个性质。

如果 $Y\rightarrow Z$ 在关系R上成立，且R的属性集为 $X\cup Y\cup Z$ ,则 $R=\Pi _{X\cup Y}⋈\Pi _{Y\cup Z}$

第三范式

关系R属于第三范式，如果它满足：只要 $A_{1}A_{2}...A_{n}\rightarrow B_{1}B_{2}...B_{m}$ 是非平凡FD，那么或者 $\{A_{1},A_{2},...,A_{n} \}$ 是超键，或者每个属于 $B_{1}，B_{2}，...，B_{m}$ 但不属于A的属性都是某个键的成员

具有无损连接和依赖保持性的3NF关系综合算法

输入：关系R和其上成立的函数依赖集F

输出：由R分解出的关系集合，其中每个关系均属于3NF。分解具有无损连接和依赖保持性质

方法：1 找出F的一个最小基本集，记为G

2 对于G中的每一个FD $X\rightarrow A$ ，将XA作为分解出的某个关系的模式

3 如果第2步中分解出的关系的模式均不包含R的超键，则增加一个关系，其模式为R的任何一个键

多值依赖（multivalued dependency,简称MVD）

多值依赖是指在关系R中，当给定某个属性集合的值时，存在另外一组属性集合，该组属性的值与关系中所有其他属性的值独立。准确的说，若给定R中属于集合A的各属性的值，存在一个属性集B，其中属性的值独立于R中既不属于A也不属于B的属性集合的值，则称MVD $A_{1}A_{2}...A_{n}\rightarrow\rightarrow B_{1}B_{2}...B_{m}$

准确的说，若要MVD成立，则对于R中每个在所有A属性上一致的元组对t和u，能在R中找到满足下列条件的元组v：

1 在A属性上的取值与t和u相同

2 在B属性上的取值与t相同

3 在R中不属于A和B的所有其他属性上的取值与u相同

MVD规则

平凡MVD规则，如果 $B_{1}B_{2}...B_{m}\subseteq A_{1}A_{2}...A_{n}$ ，则MVD $A_{1}A_{2}...A_{n}\rightarrow\rightarrow B_{1}B_{2}...B_{m}$ 在任何关系中成立

传递规则，如果关系中存在 $A_{1}A_{2}...A_{n}\rightarrow\rightarrow B_{1}B_{2}...B_{m}$ 和 $B_{1}B_{2}...B_{m}\rightarrow\rightarrow C_{1}C_{2}...C_{k}$ ，则 $A_{1}A_{2}...A_{n}\rightarrow\rightarrow C_{1}C_{2}...C_{k}$

升级规则，每个FD都是MVD。

第四范式

如果对于R中的每个非平凡MVD $A_{1}A_{2}...A_{n}\rightarrow\rightarrow B_{1}B_{2}...B_{m}$ ， $\{A_{1}A_{2}...A_{n} \}$ 都是超键，则R属于第四范式

分解为第四范式

输入：关系 $R_{0}$ ，其上的FD和MVD集合为 $S_{0}$

输出：由 $R_{0}$ 分解出的关系集合，其中每个关系均属于4NF，分解具有无损连接性质

方法：一次执行下列步骤，另 $R=R_{0}$ , $S=S_{0}$

1在R中找到一个4NF违例，记为 $A_{1}A_{2}...A_{n}\rightarrow\rightarrow B_{1}B_{2}...B_{m}$ ，其中 $\{A_{1}A_{2}...A_{n} \}$ 不是超键。注意这个MVD可以是S中的一个真的MVD，也可以源自S中对应的FD，这是因为每个FD都是MVD。如果不存在，返回，R自身就是一个合适的分解

2如果存在这样的4NF违例，则将含有该4NF违例的关系R分解为两个模式

a $R_{1}$ ，其模式为A和B

b $R_{2}$ ,其模式是A以及R中所有不属于A和B的其他属性

3 找出在 $R_{1}$ 和 $R_{2}$ 上成立的FD和MVD。根据投影后的依赖关系递归地分解 $R_{1}$ 和 $R_{2}$

注意，4NF蕴含BCNF，BCNF蕴含3NF，如下图所示

最后编辑于：2020.03.26 18:01:22

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,968评论 6赞 482
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,601评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 153,220评论 0赞 344
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,416评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,425评论 5赞 374
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,144评论 1赞 285
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,432评论 3赞 401
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,088评论 0赞 261
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,586评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,028评论 2赞 325
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,137评论 1赞 334
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,783评论 4赞 324
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,343评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,333评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,559评论 1赞 262
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,595评论 2赞 355
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,901评论 2赞 345

关系数据库理论

推荐阅读更多精彩内容