关系数据理论 Flashcards
关系
把关系模式看作是一个三元组：R。
当且仅当U上的一个关系r满足F时，r称为关系模式R的一个关系。
关系数据库逻辑设计问题
针对一个具体问题，应该如何构造一个适合于它的数据模式，即应该构造几个关系模式，每个关系由哪些属性组成等。
第一范式（1NF）
一个关系模式R的所有属性都是不可分割的基本数据项。
第一范式是对关系模式最起码的要求。不满足第一范式的数据库模式不能称为关系数据库。
数据依赖（非形式的概念）
一个关系内部属性与属性之间的一种约束关系。通过属性间值的相等与否体现出来的数据间相关联系。是现实世界属性间相互联系的抽象，是数据内在的性质，是语义的体现。
最重要的数据依赖
函数依赖（FD），多值依赖（MVD）。
关系模式存在的问题
1。数据冗余太大。（系主任姓名重复出现）
2。更新异常。由于数据冗余，当更新数据库中的数据时，系统要付出很大的代价来维护数据库的完整性，否则会面临数据不一致的危险。（某系更换系主任后，必须修改与该系学生有关的每一个元组）
3。插入异常。（如果一个系刚成立，尚无学生，就无法把这个系及其系主任的信息存入数据库）
4。删除异常。（如果某个系的学生全部毕业了，在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了）
一个＂好＂的模式应当不会发生插入异常、删除异常、更新异常，数据冗余应尽可能少。
函数依赖
设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在任何时刻的一切关系均要满足的约束条件。
非平凡的函数依赖
（在笔记本上）
平凡的函数依赖
（在笔记本上）
决定属性组（决定因素）
若X->Y，则X称为这个函数依赖的决定属性组，也称为决定因素。
不函数依赖
（在笔记本上）
完全函数依赖
（在笔记本上）
部分函数依赖
（在笔记本上）
传递函数依赖
（在笔记本上）
直接函数依赖
（在笔记本上）
候选码
（在笔记本上）
若关系中的某一属性值能唯一地标识一个元组，则称该属性组为候选码。
主码
若候选码多于一个，则选定其中的一个为主码。
主属性
包含在任何一个候选码中的属性。
非主属性（非码属性）
不包含在任何码中的属性。
全码
最简单的情况，单个属性是码。
最极端的情况，整个属性组是码，称为全码。
外码
关系模式R中属性或属性组X并非R的码，但X是另一个关系模式的码，则称X是R的外部码，也称外码。
主码与外部码提供了一个表示关系间联系的手段。
范式
符合某一种级别的关系模式的集合。
关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同范式。满足最低要求的叫第一范式，简称1NF。在第一范式中满足进一步要求的为第二范式，其余以此类推。
1971-1972 : E.F.Codd系统地提出了1NF、2NF、3NF的概念，讨论了规范化问题。
1974 : E.F.Codd和Boyce共同提出BCNF。
1976 : Fagin提出4NF。
后来又有人提出5NF。
各种范式之间的联系
（在笔记本上）
规范化
一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫规范化。
2NF
（在笔记本上）
一个关系模式R不属于2NF，就会产生以下几个问题
1。插入异常。（要插入一个学生，但该生还未选课。因为插入元组时必须给定码值，而这时码值的一部分为空，因而学生的固有信息无法插入）
2。删除异常。（删除主属性则整个元组都必须跟着删除。不应删除的信息也删除了）
3。修改复杂。
3NF
（在笔记本上）
BCNF
（在笔记本上）
一个满足BCNF的关系模式有
所有非主属性对每一个码都是完全函数依赖；
所有的主属性对每一个不包含它的码，也是完全函数依赖；
没有任何属性完全函数依赖于非码的任何一组属性。
3NF和BCNF是在函数依赖的条件下对模式分解所能达到的分离程度的测度
一个模式中的关系模式如果都属于BCNF，那么在函数依赖范畴内，它已实现了彻底的分离，已消除了插入和删除的异常。3NF的＂不彻底＂性表现在可能存在主属性对码的部分依赖和传递依赖。
多值依赖
设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。
平凡的多值依赖
若X->->Y，而Z为空，则称X->->Y为平凡的多值依赖。
多值依赖的性质
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。
多值依赖的另一种定义，证明其与原定义等价
（笔记本）
XY
若X->Y，Y->X。
多值依赖与函数依赖的区别
（在笔记本上）
嵌入型多值依赖
（在笔记本上）
4NF
（在笔记本上）
4NF就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。因为对于每一个非平凡的多值依赖X->->Y，X都含有候选码，于是就有若X->Y，所以4NF所允许的非平凡的多值依赖实际上是函数依赖。
如果一个关系模式是4NF，则必为BCNF。
函数依赖和多值依赖是两种最重要的数据依赖。如果只考虑函数依赖，则属于BCNF的关系模式规范化程度已经是最高的了。如果考虑多值依赖，则属于4NF的关系模式规范化程度是最高的
。
一个关系模式中若存在多值依赖（指非平凡的非函数依赖的多值依赖），则数据的冗余度大而且存在插入、删除、修改异常等问题。为此要消除这种多值依赖，使模式分离达到一个新的高度4NF。
数据依赖中除函数依赖和多值依赖之外，还有其他数据依赖（例如连接依赖）
函数依赖是多值依赖的一种特殊情况，而多值依赖实际上又是连接依赖的一种特殊情况。但连接依赖不像函数依赖和多值依赖可由语义直接导出，而是在关系的连接运算时才反映出来。存在连接依赖的关系模式仍可能遇到数据冗余及插入、修改、删除异常等问题。如果消除了属于4NF的关系模式中存在的连接依赖，则可以进一步达到5NF的关系模式。
规范化的目的
在关系数据库中，对关系模式的基本要求是满足第一范式。这样的关系模式就是合法的、允许的。但是，人们发现有些关系模式存在插入、删除异常，修改复杂，数据冗余等毛病。人们寻求解决这些问题的方法，这就是规范化的目的。
规范化的基本思想
逐步消除数据依赖中不合适的部分，使模式中的各关系模式达到某种程度的＂分离＂，即＂一事一地＂的模式设计原则。让一个关系描述一个概念、一个实体或者实体间的一种联系。若多于一个概念就把它＂分离＂出去。因此所谓规范化实质上是概念的单一化。
规范化过程
1NF-消除非主属性对码的部分函数依赖-2NF-消除非主属性对码的传递函数依赖-3NF-消除主属性对码的部分和传递函数依赖-BCNF-消除非平凡且非函数依赖的多值依赖-4NF
关系模式的规范化过程是通过对关系模式的分解来实现的。把低一级的关系模式分解为若干个高一级的关系模式。这种分解不是唯一的。
模式分解算法的理论基础
数据依赖的公理系统
F逻辑蕴含X->Y
对于满足一组函数依赖F的关系模式R，其任何一个关系r，若函数依赖X->Y都成立（即r中任意两元组t, s，若t[X]=s[X]，则t[Y]=s[Y]），则称F逻辑蕴含X->Y。
Armstrong公理系统
为了求得给定关系模式的码，为了从一组函数依赖求得蕴含的函数依赖，就需要一套推理规则。
（在笔记本上）
定理6.1
Armstrong推理规则是正确的。
（证明）
根据A1、A2、A3得到三条有用的推理规则（合并规则，伪传递规则，分解规则）
（在笔记本上，证明）
引理6.1
根据合并规则和分解规则，很容易得到这样一个重要事实：
X->A1A2…Ak成立的充分必要条件是X->Ai成立（i=1,2,…,k）。
定义6.12（闭包）
（在笔记本上）
Armstrong公理的有效性
由F出发根据Armstrong公理推导出来的每一个函数依赖一定在F的闭包中。
Armstrong公理的完备性
F的闭包中的每一个函数依赖，必定可以由F出发根据Armstrong公理推导出来。
要证明完备性，就首先要解决如何判定一个函数是否属于由F根据Armstrong公理推导出来的函数依赖的集合。（这是一个NP完全问题。求出这个集合很麻烦。）
定义6.13（属性集X关于函数依赖集F的闭包）
（在笔记本上）
引理6.2
（在笔记本上）
算法6.1（求属性集X关于U上的函数依赖集F的闭包）
（在笔记本上）
定理6.2
Armstrong公理是有效的、完备的。
Armstrong公理的完备性及有效性说明了＂导出＂与＂蕴含＂是两个完全等价的概念。于是F的闭包也可以说成是由F出发借助Armstrong公理导出的函数依赖的集合。
（证明）
定义6.14（F覆盖G或F与G等价）
（在笔记本上）
引理6.3（F的闭包G的闭包的充要条件）
（在笔记本上）
（证明）
定义6.15（极小函数依赖集或最小依赖集或最小覆盖）
如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。
1。F中任一函数依赖的右部仅含有一个属性。
2。F中不存在这样的函数依赖X->A，使得F与F-{X->A}等价。
3。F中不存在这样的函数依赖X->A，X有真子集Z使得F-{X->A}并{Z->A}与F等价。
定理6.3
每一个函数依赖集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是允许的。
定义6.16（关系模式的分解）
（笔记本）
定义6.17（F在属性Ui上的投影）
（笔记本）
模式分解的3个定义
对于一个模式的分解是多种多样的，但是分解后产生的模式应与原模式等价。
人们从不同的角度去观察问题，对＂等价＂的概念形成了三种不同的定义：
1。分解具有＂无损连接性＂。
2。分解要＂保持函数依赖＂。
3。分解既要＂保持函数依赖＂，又要具有＂无损连接性＂。
按照不同的分解准则，模式所能达到的分离程度各不相同，各种范式就是对分离程度的测度。
一个关系分解为多个关系，相应地原来存储在一张二维表内的数据就要分散存储到多张二维表中，要使这个分解有意义，起码的要求是后者不能丢失前者的信息。
定义一个记号（r在各关系模式上投影的连接）
（笔记本）
引理6.4
（笔记本）
（证明）
定义6.18（无损连接性或无损分解）
（笔记本）
算法6.2（判别一个分解的无损连接性）
（笔记本）
定理6.4（无损连接分解）
（笔记本）
定理6.5（关系模式分解时的判定准则）
（笔记本）
定义6.19（分解保持函数依赖）
（笔记本）
关于模式分解的几个重要事实
1。若要求分解保持函数依赖，那么模式分离总可以达到3NF，但不一定能达到BCNF；
2。若要求分解既保持函数依赖，又具有无损连接性，可以达到3NF，但不一定能达到BCNF；
3。若要求分解具有无损连接性，那一定可达到4NF。
算法6.3（合成法）转换为3NF的保持函数依赖的分解
（笔记本）
（证明）
算法6.4 转换为3NF既有无损连接性又保持函数依赖的分解。
（笔记本）
（证明）
算法6.5（分解法）转换为BCNF的无损连接分解。
P192
引理6.5
P192
引理6.6
（笔记本）
（证明P192）
定理6.6（达到4NF的具有无损连接性的分解）
（笔记本）
（证明P192）
算法6.6 达到4NF的具有无损连接的分解。
首先使用算法6.5，得到R的一个达到了BCNF的无损连接分解。然后对某一Ri，若不属于4NF，则可按定理6.6的做法进行分解。直到每一个关系模式均属于4NF为止。
定理6.6和引理6.5保证了最后得到的分解的无损连接性。
关系模式R，U是属性总体集，D是U上的一组数据依赖（函数依赖和多值依赖），对于包含函数依赖和多值依赖的数据依赖有一个有效且完备的公理系统。
（笔记本）
（部分证明见小书P48）
公理系统的有效性和完备性
有效性是指从D出发根据8条公理推导出的函数依赖或多值依赖一定为D所蕴含；完备性是指凡D所蕴含的函数依赖或多值依赖均可以从D根据8条公理推导出来。
在函数依赖和多值依赖的条件下，＂蕴含＂与＂导出＂仍是等价的。
确定关系模式候选码的准则
关系R中，F是最小函数依赖集。
1。如果属性A只在F中各个函数依赖的左端出现，则A必是码中的属性。
2。如果属性A不在F的各个函数依赖中出现，则A必是码中的属性。
3。如果属性A只在F中各个函数依赖的右端出现，则A必不是码中的属性。
已知R属于3NF，且具有唯一的候选码，则R属于BCNF。
对
任何二元关系属于4NF？
错
（笔记本）
如果R中，R属于BCNF，则F一定是最小函数依赖集？
错
关系模式R中，U=ABC, F={A->BC}，显然R属于BCNF，但F不是最小函数依赖集。
如果R中，F是最小函数依赖集，则R一定属于2NF？
错
关系模式R中，U=ABCD, F={AB->C, B->D}，显然F是最小函数依赖集，但R不属于2NF。
由8条公理得到4条有用的推理规则
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。
