规范化设计算法描述
1）FD推导求F+。
问题描述：已知R(U,F)，求FD集闭包F+。
输入：U, F
输出：F+
算法描述：
① A1规则生成的所有FDs；
② A2规则生成的所有FDs；
③ A3规则生成的所有FDs。
2）求属性集闭包
问题描述：已知关系R(U,F)，求属性集X的闭包X+。
输入：U, F和属性集X
输出：属性集X相对于F的闭包X+。
算法描述：
① X+ = X；
② 对于FD: Y→Z，如果Y⊆X+，那么Z也放入X+中。
③ 验证F中所有FD，直到X+不再扩充。
3）用属性集闭包求F+。
问题描述：已知关系R(U,F)，用属性集闭包方法求F+。
输入：U, F
输出：F+
算法描述：Fclosure2(U,F)
① 求U的所有子集；
② 对U的所有子集X求X+；
③ 求X+的所有子集Yi，构造X→Yi；
引用算法：
substring(U): 求属性集U的所有子集；
Xclosure(X,F)：相对于F求属性集X的闭包X+。
4）求属性集U的所有子集substring(U)
问题描述：已知属性集U，求U的所有子集，包括空集∅，用字符串并置表示，按字母次序排列。
输入：属性集U
输出：U的所有子集，用字符串的列表表示。
数据结构：
U = 'ABC'
P = [∅,A,B,C,AB,BC,AC,ABC]
5）FD求关系模式所有候选键
问题描述：已知R(U)与F，求R的所有候选键。
输入：U, F
输出：R的所有候选键
算法描述：
① 找出FD右边没有出现过的属性，设为K；
② 求K+，如果K+=U，则K为唯一候选键；
③ 如果K+⊆U，则K与其他属性结合，继续求闭包，同理判断，找出所有候选键。
④ 如果所有属性都出现在FD右边，则从单个属性开始求闭包，依次组合进行判断。
6）求最小依赖集Fmin
问题描述：已知R(U, F)，求最小依赖集Fmin。
输入：F
输出：Fmin
算法描述：
① FD集右边分解为单属性；
② 消除FD右边重复属性；
③ 消除重复FD和平凡FD；
即得Fmin。
7）无损连接测试算法
分两种情况测试无损分解：① 模式存有数据集；② 模式不含数据集。
②又分成两种情况：子模式3个及以上，用表格法CHASE过程进行更新；如果分解为2个子模式，用定理进行验证。
问题描述：已知R(U,F,P)，判断基于F，U分解为P是否为无损分解。
输入：R(U,F,P）
输出：True无损分解，False损失分解
① 有数据集情况
r = mρ(R)为无损分解，否则为损失分解。
② 无数据集情况-表格作业法
作初始化表；
在表中按照FD集来更新数据，使其符合约束条件。
更新完后，如果有一行数据全是aj，则为无损分解，否则损失分解。
③ R分解为2个子模式情况，根据定理判断，满足：
R1∩R2 → R1-R2 或者 R1∩R2 → R2-R1 成立。
8）FD集F在属性集Z上投影
问题描述：已知FD集F，求F在属性集Z上投影。
输入：F
输出：πZ(F)
算法描述：
① 首先把F中的FD投影到Z上，即对于X→Y，有：XY⊆Z；
② 把F+中跟属性集Z有关联的FD也同样投影过来，不包含平凡FD。
9）判断范式
问题描述：已知R(U,F)，判断关系模式是第几范式？
输入：U, F
输出：第几范式（?NF)
算法描述：
① BCNF：要求每个FD左边包含候选键；
② 3NF：要求每个FD要么左边包含候选键，要么右边是主属性；
③ 2NF：要求每个FD都完全依赖于候选键。
④ 1NF：默认都是。
10）模式分解
问题描述：已知R(U,F)，把R分解为3NF或BCNF。
输入：U, F
输出：3NF或BCNF模式集
算法描述：
① 无损分解且保持依赖分解为3NF模式集；
根据最小依赖集进行分解。
② 无损分解为BCNF模式集。
根据不满足条件的FD集进行无损分解。
