函数依赖与关系模式分解的一些技巧整理
- 关系数据库设计理论的核心是数据间的函数依赖，衡量的标准是关系规范化的程度及分解的无损连接性和保持函 数依赖性。
- 数据依赖是通过一个关系中属性间值的相同与否体现出来的数据间的相互关系
- 函数依赖（FD）是关系模式内最常见的数据依赖，属于语义范畴的概念
- 函数依赖定义为：设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，但Y∉X，则称X→Y是非平凡的函数依赖。通常情况下总是讨论非平凡的函数依赖
- 完全函数依赖：在R(U)中，如果X→Y，并且对于x的任何一个真子集X'，都有X´不能决定Y，则称Y对X完全函数依赖，记作：X-f->Y (f即 full)
- 部分函数依赖：在R(U)中，如果X→Y，但Y不完全函数依赖于X，则称Y对X部分函数依赖，记作：X-p->Y (p即part) 部分函数依赖也称为局部函数依赖
- 传递依赖：在R(U,F)中，如果X→Y，Y∉X，Y→Z，Y不完全函数依赖于X，则称Z对X传递依赖
- 候选码：设K为R(U,F)中属性的组合，若K-f->U，且对于K的任何一个真子集K'，都有K'不能决定U，则K为R的候选码（候选关键字）。若有多个候选码，则选其中一个座位主码（主键），包含在任何一个候选码中的属性称之为主属性，反之称之为非主属性
- 设F是关系模式R的一个函数依赖集，X,Y是R的属性子集，如果从F中的函数依赖能够推出X→Y，则称F逻辑蕴含X→Y，记为F|=X→Y。
- 设F是函数依赖集，被F逻辑蕴含的函数依赖的全体构成的集合，称为F的闭包，记作F+。F+={X→Y| F|=X→Y}
- 设有关系模式R（A1，A2，A3...An）和属性集U=A1，A2，...An,X,Y,Z,W是U的一个子集，F是R德的一个函数依赖集，推理规则如下：
- 自反律：如果Y∈X∈U，则X→Y在R上成立
- 增广律：如果X→Y为F所蕴含，Z∈U，则XZ→YZ在R上成立
- 传递律：如果X→Y和Y→Z在R上成立，则X→Z在R上成立
- 合并律：如果X→Y和X→Z成立，那么X→YZ成立
- 伪传递律：如果X→Y和WY→Z成立，那么WX→Z成立
- 分解律：如果X→Y和Z∈Y成立，那么X→Z成立
- 复合律：如果X→Y和W→Z成立，那么XW→YZ成立
- 如果X→Y和W→Z成立，那么X∪（W-Y）→YZ成立
关系模式的分解
- 关系模式的分解有几个不同的衡量标准：①分解具有无损连接；②分解要保持函数依赖；③分解既要保持函数依赖，又要具有无损连接
- 无损连接性判定定理：关系模式R分解为两个关系模式R1和R2，满足无损连接性的充分条件是R1∩R2→（R1-R2）或R1∩R2→（R2-R1）
- 保持函数依赖的定义是：若满足（F1∪F2）+=F+，则分解保持函数依赖，其中Fi函数依赖集F在Ri上的投影
- 在泛关系模式R分解成数据库模式ρ={R1，R2...Rk}时，泛关系r在ρ的每一模式Ri(1≤i≤n)上投影后再连接起来，比原来r中多出来的元组，称为“寄生元组”或外元组。实际上，寄生元组表示错误的信息
- 先存在r(泛关系)的情况下，再去谈论分解，这是关系数据库理论中著名的泛关系假设
- 在无泛关系假设时，对两个关系进行自然连接中被丢失的元组称为悬挂元组
- 悬挂元组是造成两个关系不存在泛关系的原因
- 模式分解的优点：①能消除数据冗余和操作异常的现象；②在分解了的数据库中可以存储悬挂元组，存储泛关系中无法存储的信息
- 模式分解的缺点：①分解以后，检索操作需要做笛卡尔积或链接操作，这将付出时间代价；②在有泛关系假设时，对数据库中的关系进行自然连接时，可能产生寄生元组（即损失了信息）；在无泛关系假设时，由于数据库可能存在悬挂元组，因此有可能不存在泛关系
- 无损分解的测试方法。①输入：关系模式R=（A1，A2...An），F是R上成立的函数依赖集，ρ={R1,R2...Rn}是R的一个分解；②输出：判断ρ相对于F是否具有无损分解特性。无损分解的测试算法如下：
- 构造一张k行n列的表格，每列对应一个属性Aj（1≤j≤n），每行对应一个模式Rj（1≤i≤k）。如果Aj在Ri中，那么在表格的第i行第j列处填上符号aj，否则填上bij。
- 把表格看成模式R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的值，修改方法为：对于F中一个函数依赖X→Y，如果表格中有两行在X值上相等，在Y值上不相等，那么把这两行在Y值上也改成相等的值，如果Y值中一个是aj,那么另一个也改成aj;如果没有aj那么用其中一个bij替换另一个字（尽量把下表ij改成较小的数）。一直到表格不能修改为止，这个过程成为chase（追踪）过程
- 若修改后的最后一直表格中有一方全是a,即a1，a2...an，则称ρ相对于F是无损分解，否则称为损失分解
- 如果某个分解能保持FD集，那么在数据输入或更新时，只要每个关系模式本身的FD约束被满足，就可以确保整个数据库中数据的语义完整性不受破坏
- 关系模式在分解时应保持等价，有数据等价和依赖等价两种，分别用无损分解和保持依赖两个特征来衡量。
- 数据等价是指两个数据库实例赢表示同样的信息内容。如果是无损分解，那么对泛关系反复的投影和连接都不会丢失信息
- 依赖等价是指两个数据库模式应有相同的依赖集闭包，在依赖集闭包相等的情况下，数据的语义是不会出差错的
范式
- 范式是衡量关系模式优劣的标准，它表达了模式中数据依赖之间应满足的联系
- 第一范式（1NF）：若关系模式R的每一个分量是不可分的数据项，则R∈1NF
- 2NF:若R∈1NF，且每一个非主属性完全函数依赖于码，则R属于2NF。换言之，当1NF消除了非主属性对码的部分函数依赖时，则称为2NF。典型有：捐赠信息（捐赠编号。捐赠校友，捐赠时间，受益人身份证号，受益人姓名），其中捐赠编号和受益人身份证号是主键，但是存在” 捐赠编号→捐赠校友，捐赠时间“和”受益人身份证号→受益人姓名“的部分依赖，所以这个不是2NF
- 3NF；若R∈2NF，且每一个非主属性既不部分依赖于码，也不传递依赖于码，则R∈3NF。换言之：当2NF消除了非主属性对码的部分函数传递时，称为3NF。典型有：校友信息（校友编号，姓名，工作单位，职位，院系，班级，入学年份，身份证号）班级为班级编号，包含院系编号，入学年份和专业方向编号。可以知道 校友编号应该是主键，同时身份证号也是该关系模式的决定性因素，因此他们都是候选键。由“班级→入学年份 ”和“校友编号→班级”,出现了“ 校友编号→入学年份”，虽然每一个非主属性不部分依赖与码，但是传递依赖与码了，因此这不是3NF
- BCNF:关系模式R∈1NF，若X→Y且Y∉X时，X必含码，则R属于BCNF。换言之，当3NF消除了主属性对码的部分和传递函数依赖时，则称为BCNF。注意：BCNF是3NF消除主属性的部分和传递函数依赖，2NF 1NF晋级是消除非主属性的依赖
- 他们之间的相互关系是：1NF⊃2NF⊃3NF⊃BCNF
- BCNF的关系模式都具有如下3个性质
- 多值依赖MVD：设R(U)施属性集U上的一个关系模式，X,Y是U的子集，若对R(U)的任一关系r，对于X的一个给定的值存在着Y的一组值与其对应，同时Y的这组值又不以任何方式与U-X-Y中的属性相关，那么称Y多值依赖于X，记为X→→Y
- 平凡多值依赖：对于属性集U上的一个多值依赖X→→Y，如果Y X或者 XY=U，那么称X→→Y是一个平凡多值依赖
- 4NF：关系模式R∈1NF，若对于R的每个非平凡多值依赖X→→Y且Y∉X时，X必含码，则R∈4NF
- 对于4NF关系进行投影，消除原关系中不是由候选码所蕴含的函数依赖，即可得到一组5NF关系，5NF是最终范
| 级别 | 特点 | 无损分解 | 保持FD |
| 1NF | 属性值是原子值 | —— | —— |
| 2NF | 消除了非主属性对码的部分函数依赖 | 能达到 | 能达到 |
| 3NF | 消除了非主属性对码的部分函数传递 | 能达到 | 能达到 |
| BCNF | 消除了主属性对码的部分和传递函数依赖 | 能达到 | 不一定能达到 |
| 4NF | 消除了没有非平凡且黑函数依赖的多值依赖 | 能达到 | 不一定能达到 |
| 5NF | 消除不是由候选码所蕴含的连接依赖 | 能达到 | 不一定能达到 |
