关系数据理论

Question 0

关系

Answer 0

把关系模式看作是一个三元组：R。

当且仅当U上的一个关系r满足F时，r称为关系模式R的一个关系。

Question 1

关系数据库逻辑设计问题

Answer 1

针对一个具体问题，应该如何构造一个适合于它的数据模式，即应该构造几个关系模式，每个关系由哪些属性组成等。

Question 2

第一范式（1NF）

Answer 2

一个关系模式R的所有属性都是不可分割的基本数据项。

第一范式是对关系模式最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。

Question 3

数据依赖（非形式的概念）

Answer 3

一个关系内部属性与属性之间的一种约束关系。通过属性间值的相等与否体现出来的数据间相关联系。是现实世界属性间相互联系的抽象，是数据内在的性质，是语义的体现。

Question 4

最重要的数据依赖

Answer 4

函数依赖（FD），多值依赖（MVD）。

Question 5

关系模式存在的问题

Answer 5

1。数据冗余太大。（系主任姓名重复出现）
2。更新异常。由于数据冗余，当更新数据库中的数据时，系统要付出很大的代价来维护数据库的完整性，否则会面临数据不一致的危险。（某系更换系主任后，必须修改与该系学生有关的每一个元组）
3。插入异常。（如果一个系刚成立，尚无学生，就无法把这个系及其系主任的信息存入数据库）
4。删除异常。（如果某个系的学生全部毕业了，在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了）
一个＂好＂的模式应当不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。

Question 6

函数依赖

Answer 6

设R(U)是属性集U上的关系模式。X，Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作X->Y。
函数依赖是最基本的一种数据依赖，也是最为重要的一种数据依赖。
函数依赖是属性之间的一种联系，体现在属性值是否相等上。由定义可知，如果X->Y，则r中的任意两个元组若其在X上的属性值相同，那么在Y上的属性值也一定相同。
函数依赖和别的依赖一样是语义范畴的概念，反映（描述）了现实世界的一种语义。要从属性之间实际存在的语义来确定它们之间的函数依赖。
函数依赖不是指关系模式R的某个或某些关系满足的约束条件，而是指R的一切关系均要满足的约束条件。函数依赖不是指关系模式R在某个时刻的关系（值）所满足的约束条件，而是指R在任何时刻的一切关系均要满足的约束条件。

Question 7

非平凡的函数依赖

Answer 7

（在笔记本上）

Question 8

平凡的函数依赖

Answer 8

（在笔记本上）

Question 10

决定属性组（决定因素）

Answer 10

若X->Y，则X称为这个函数依赖的决定属性组，也称为决定因素。

Question 11

不函数依赖

Answer 11

（在笔记本上）

Question 12

完全函数依赖

Answer 12

（在笔记本上）

Question 13

部分函数依赖

Answer 13

（在笔记本上）

Question 14

传递函数依赖

Answer 14

（在笔记本上）

Question 15

直接函数依赖

Answer 15

（在笔记本上）

Question 16

候选码

Answer 16

（在笔记本上）

若关系中的某一属性值能唯一地标识一个元组，则称该属性组为候选码。

Question 17

主码

Answer 17

若候选码多于一个，则选定其中的一个为主码。

Question 18

主属性

Answer 18

包含在任何一个候选码中的属性。

Question 19

非主属性（非码属性）

Answer 19

不包含在任何码中的属性。

Question 20

全码

Answer 20

最简单的情况，单个属性是码。

最极端的情况，整个属性组是码，称为全码。

Question 21

外码

Answer 21

关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码，也称外码。

主码与外部码提供了一个表示关系间联系的手段。

Question 22

范式

Answer 22

符合某一种级别的关系模式的集合。
关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同范式。满足最低要求的叫第一范式，简称1NF。在第一范式中满足进一步要求的为第二范式，其余以此类推。
1971-1972 : E.F.Codd系统地提出了1NF、2NF、3NF的概念，讨论了规范化问题。
1974 : E.F.Codd和Boyce共同提出BCNF。
1976 : Fagin提出4NF。
后来又有人提出5NF。

Question 23

各种范式之间的联系

Answer 23

（在笔记本上）

Question 24

规范化

Answer 24

一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫规范化。

Question 25

2NF

Answer 25

（在笔记本上）

Question 26

一个关系模式R不属于2NF，就会产生以下几个问题

Answer 26

1。插入异常。（要插入一个学生，但该生还未选课。因为插入元组时必须给定码值，而这时码值的一部分为空，因而学生的固有信息无法插入）
2。删除异常。（删除主属性则整个元组都必须跟着删除。不应删除的信息也删除了）
3。修改复杂。

Question 27

3NF

Answer 27

（在笔记本上）

Question 28

BCNF

Answer 28

（在笔记本上）

Question 29

一个满足BCNF的关系模式有

Answer 29

所有非主属性对每一个码都是完全函数依赖；
所有的主属性对每一个不包含它的码，也是完全函数依赖；
没有任何属性完全函数依赖于非码的任何一组属性。

Question 30

3NF和BCNF是在函数依赖的条件下对模式分解所能达到的分离程度的测度

Answer 30

一个模式中的关系模式如果都属于BCNF，那么在函数依赖范畴内，它已实现了彻底的分离，已消除了插入和删除的异常。3NF的＂不彻底＂性表现在可能存在主属性对码的部分依赖和传递依赖。

Question 31

多值依赖

Answer 31

设R(U)是属性集U上的一个关系模式。X，Y，Z是U的子集，并且Z=U-X-Y。关系模式R(U)中多值依赖X->->Y成立，当且仅当对R(U)的任一关系r，给定的一对(x,z)值，有一组Y的值，这组值仅仅决定于x值而与z值无关。
在R(U)的任一关系r中，如果存在元组t, s使得t[X]=s[X]，那么就必然存在元组w, v属于r，（w, v可以与s, t相同），使得w[X]=v[X]=t[X]，而w[Y]=t[Y], w[Z]=s[Z], v[Y]=s[Y], v[Z]=t[Z]（即交换s, t元组的Y值所得的两个新元组必在r中），则Y多值依赖于X，记为X->->Y。

Question 32

平凡的多值依赖

Answer 32

若X->->Y，而Z为空，则称X->->Y为平凡的多值依赖。

Question 33

多值依赖的性质

Answer 33

1。对称性。若X->->Y，则X->->Z，其中Z=U-X-Y。
2。传递性。若X->->Y，Y->->Z，则X->->Z-Y。
3。函数依赖可以看作是多值依赖的特殊情况。即若X->Y，则X->->Y。因为当X->Y时，对X的每一个值x，Y有一个确定的值y与之对应，所以X->->Y。
4。若X->->Y，X->->Z，则X->->YZ。
5。若X->->Y，X->->Z，则X->->Y交Z。
6。若X->->Y，X->->Z，则X->->Y-Z，则X->->Z-Y。

Question 34

多值依赖的另一种定义，证明其与原定义等价

Answer 34

（笔记本）

Question 35

XY

Answer 35

若X->Y，Y->X。

Question 36

多值依赖与函数依赖的区别

Answer 36

（在笔记本上）

Question 37

嵌入型多值依赖

Answer 37

（在笔记本上）

Question 38

4NF

Answer 38

（在笔记本上）
4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。因为对于每一个非平凡的多值依赖X->->Y，X都含有候选码，于是就有若X->Y，所以4NF所允许的非平凡的多值依赖实际上是函数依赖。
如果一个关系模式是4NF，则必为BCNF。
函数依赖和多值依赖是两种最重要的数据依赖。如果只考虑函数依赖，则属于BCNF的关系模式规范化程度已经是最高的了。如果考虑多值依赖，则属于4NF的关系模式规范化程度是最高的
。
一个关系模式中若存在多值依赖（指非平凡的非函数依赖的多值依赖），则数据的冗余度大而且存在插入、删除、修改异常等问题。为此要消除这种多值依赖，使模式分离达到一个新的高度4NF。

Question 39

数据依赖中除函数依赖和多值依赖之外，还有其他数据依赖（例如连接依赖）

Answer 39

函数依赖是多值依赖的一种特殊情况，而多值依赖实际上又是连接依赖的一种特殊情况。但连接依赖不像函数依赖和多值依赖可由语义直接导出，而是在关系的连接运算时才反映出来。存在连接依赖的关系模式仍可能遇到数据冗余及插入、修改、删除异常等问题。如果消除了属于4NF的关系模式中存在的连接依赖，则可以进一步达到5NF的关系模式。

Question 40

规范化的目的

Answer 40

在关系数据库中，对关系模式的基本要求是满足第一范式。这样的关系模式就是合法的、允许的。但是，人们发现有些关系模式存在插入、删除异常，修改复杂，数据冗余等毛病。人们寻求解决这些问题的方法，这就是规范化的目的。

Question 41

规范化的基本思想

Answer 41

逐步消除数据依赖中不合适的部分，使模式中的各关系模式达到某种程度的＂分离＂，即＂一事一地＂的模式设计原则。让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它＂分离＂出去。因此所谓规范化实质上是概念的单一化。

Question 42

规范化过程

Answer 42

1NF-消除非主属性对码的部分函数依赖-2NF-消除非主属性对码的传递函数依赖-3NF-消除主属性对码的部分和传递函数依赖-BCNF-消除非平凡且非函数依赖的多值依赖-4NF
关系模式的规范化过程是通过对关系模式的分解来实现的。把低一级的关系模式分解为若干个高一级的关系模式。这种分解不是唯一的。

Question 43

模式分解算法的理论基础

Answer 43

数据依赖的公理系统

Question 44

F逻辑蕴含X->Y

Answer 44

对于满足一组函数依赖F的关系模式R，其任何一个关系r，若函数依赖X->Y都成立（即r中任意两元组t, s，若t[X]=s[X]，则t[Y]=s[Y]），则称F逻辑蕴含X->Y。

Question 45

Armstrong公理系统

Answer 45

为了求得给定关系模式的码，为了从一组函数依赖求得蕴含的函数依赖，就需要一套推理规则。

（在笔记本上）

Question 46

定理6.1

Answer 46

Armstrong推理规则是正确的。

（证明）

Question 47

根据A1、A2、A3得到三条有用的推理规则（合并规则，伪传递规则，分解规则）

Answer 47

（在笔记本上，证明）

Question 48

引理6.1

Answer 48

根据合并规则和分解规则，很容易得到这样一个重要事实：

X->A1A2…Ak成立的充分必要条件是X->Ai成立（i=1,2,…,k）。

Question 49

定义6.12（闭包）

Answer 49

（在笔记本上）

Question 50

Armstrong公理的有效性

Answer 50

由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F的闭包中。

Question 51

Armstrong公理的完备性

Answer 51

F的闭包中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。

要证明完备性，就首先要解决如何判定一个函数是否属于由F根据Armstrong公理推导出来的函数依赖的集合。（这是一个NP完全问题。求出这个集合很麻烦。）

Question 52

定义6.13（属性集X关于函数依赖集F的闭包）

Answer 52

（在笔记本上）

Question 53

引理6.2

Answer 53

（在笔记本上）

Question 54

算法6.1（求属性集X关于U上的函数依赖集F的闭包）

Answer 54

（在笔记本上）

Question 55

定理6.2

Answer 55

Armstrong公理是有效的、完备的。
Armstrong公理的完备性及有效性说明了＂导出＂与＂蕴含＂是两个完全等价的概念。于是F的闭包也可以说成是由F出发借助Armstrong公理导出的函数依赖的集合。
（证明）

Question 56

定义6.14（F覆盖G或F与G等价）

Answer 56

（在笔记本上）

Question 57

引理6.3（F的闭包G的闭包的充要条件）

Answer 57

（在笔记本上）

（证明）

Question 58

定义6.15（极小函数依赖集或最小依赖集或最小覆盖）

Answer 58

如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。
1。F中任一函数依赖的右部仅含有一个属性。
2。F中不存在这样的函数依赖X->A，使得F与F-{X->A}等价。
3。F中不存在这样的函数依赖X->A，X有真子集Z使得F-{X->A}并{Z->A}与F等价。

Question 59

定理6.3

Answer 59

每一个函数依赖集F均等价于一个极小函数依赖集Fm。此Fm称为F的最小依赖集。
（证明）
F的最小依赖集Fm不一定是唯一的，它与对各函数依赖FDi及X->A中X各属性的处置顺序有关。
若改造后的F与原来的F相同，说明F本身就是一个最小依赖集，因此证明过程中给出的极小化过程也可以看成是检验F是否为极小依赖集的一个算法。
两个关系模式R1, R2，如果F与G等价，那么R1的关系一定是R2的关系。反过来，R2的关系也一定是R1的关系。所以在R中用与F等价的依赖集G来取代F是允许的。

Question 60

定义6.16（关系模式的分解）

Answer 60

（笔记本）

Question 61

定义6.17（F在属性Ui上的投影）

Answer 61

（笔记本）

Question 62

模式分解的3个定义

Answer 62

对于一个模式的分解是多种多样的，但是分解后产生的模式应与原模式等价。
人们从不同的角度去观察问题，对＂等价＂的概念形成了三种不同的定义：
1。分解具有＂无损连接性＂。
2。分解要＂保持函数依赖＂。
3。分解既要＂保持函数依赖＂，又要具有＂无损连接性＂。
按照不同的分解准则，模式所能达到的分离程度各不相同，各种范式就是对分离程度的测度。
一个关系分解为多个关系，相应地原来存储在一张二维表内的数据就要分散存储到多张二维表中，要使这个分解有意义，起码的要求是后者不能丢失前者的信息。

Question 63

定义一个记号（r在各关系模式上投影的连接）

Answer 63

（笔记本）

Question 64

引理6.4

Answer 64

（笔记本）

（证明）

Question 65

定义6.18（无损连接性或无损分解）

Answer 65

（笔记本）

Question 66

算法6.2（判别一个分解的无损连接性）

Answer 66

（笔记本）

Question 67

定理6.4（无损连接分解）

Answer 67

（笔记本）

Question 68

定理6.5（关系模式分解时的判定准则）

Answer 68

（笔记本）

Question 69

定义6.19（分解保持函数依赖）

Answer 69

（笔记本）

Question 70

关于模式分解的几个重要事实

Answer 70

1。若要求分解保持函数依赖，那么模式分离总可以达到3NF，但不一定能达到BCNF；
2。若要求分解既保持函数依赖，又具有无损连接性，可以达到3NF，但不一定能达到BCNF；
3。若要求分解具有无损连接性，那一定可达到4NF。

Question 71

算法6.3（合成法）转换为3NF的保持函数依赖的分解

Answer 71

（笔记本）

（证明）

Question 72

算法6.4 转换为3NF既有无损连接性又保持函数依赖的分解。

Answer 72

（笔记本）

（证明）

Question 73

算法6.5（分解法）转换为BCNF的无损连接分解。

Answer 73

P192

Question 74

引理6.5

Answer 74

P192

Question 75

引理6.6

Answer 75

（笔记本）

（证明P192）

Question 76

定理6.6（达到4NF的具有无损连接性的分解）

Answer 76

（笔记本）

（证明P192）

Question 77

算法6.6 达到4NF的具有无损连接的分解。

Answer 77

首先使用算法6.5，得到R的一个达到了BCNF的无损连接分解。然后对某一Ri，若不属于4NF，则可按定理6.6的做法进行分解。直到每一个关系模式均属于4NF为止。
定理6.6和引理6.5保证了最后得到的分解的无损连接性。

Question 78

关系模式R，U是属性总体集，D是U上的一组数据依赖（函数依赖和多值依赖），对于包含函数依赖和多值依赖的数据依赖有一个有效且完备的公理系统。

Answer 78

（笔记本）

（部分证明见小书P48）

Question 79

公理系统的有效性和完备性

Answer 79

有效性是指从D出发根据8条公理推导出的函数依赖或多值依赖一定为D所蕴含；完备性是指凡D所蕴含的函数依赖或多值依赖均可以从D根据8条公理推导出来。
在函数依赖和多值依赖的条件下，＂蕴含＂与＂导出＂仍是等价的。

Question 80

确定关系模式候选码的准则

Answer 80

关系R中，F是最小函数依赖集。
1。如果属性A只在F中各个函数依赖的左端出现，则A必是码中的属性。
2。如果属性A不在F的各个函数依赖中出现，则A必是码中的属性。
3。如果属性A只在F中各个函数依赖的右端出现，则A必不是码中的属性。

Question 81

已知R属于3NF，且具有唯一的候选码，则R属于BCNF。

Answer 81

对

Question 82

任何二元关系属于4NF？

Answer 82

错

（笔记本）

Question 83

如果R中，R属于BCNF，则F一定是最小函数依赖集？

Answer 83

错

关系模式R中，U=ABC, F={A->BC}，显然R属于BCNF，但F不是最小函数依赖集。

Question 84

如果R中，F是最小函数依赖集，则R一定属于2NF？

Answer 84

错

关系模式R中，U=ABCD, F={AB->C, B->D}，显然F是最小函数依赖集，但R不属于2NF。

Question 85

由8条公理得到4条有用的推理规则

Answer 85

1。合并规则：X->->Y, X->->Z, 则；
2。伪传递规则：X->->Y, WY->Z, 则WX->->Z-WY；
3。混合伪传递规则：X->->Y, XY->Z, 则X->Z-Y；
4。分解规则：X->->Y, X->Z, 则X->->Y交Z, X->->Y-Z, X->->Z-Y。