第六章 关系数据库理论 算法合集

• XF+X_{F}^{+}XF+​求解算法
• 极小函数依赖集求解算法
• 候选码求解算法
• 模式分解
• • 无损连接性的判定算法(通用)
  • 一分为二的模式分解的无损连接性判定算法
  • • 不考虑多值依赖
    • 考虑多值依赖(Multivalued Dependency,MVD)
  • 函数依赖集的投影求解算法

XF+X_{F}^{+}XF+​求解算法

即求XXX在函数依赖集FFF条件下所能决定的属性的集合。

1. XF+=XX_F^+=XXF+​=X
2. 逐一考察FFF中的每一个函数依赖v→wv \rightarrow wv→w, 如果v∈XF+v \in X_F^+v∈XF+​，则www并入XF+X_F^+XF+​
3. XF+=UX_F^+ = UXF+​=U or XF+X_F^+XF+​不再增加，算法结束

极小函数依赖集求解算法

拆右，去左（属性冗余），去重（函数依赖冗余）

1. 分解右部属性，得F1F_1F1​
2. 去除左侧属性冗余，即变动XF+X_F^+XF+​中的XXX，函数依赖集为FFF，此步骤将F1F_1F1​修改得到F2F_2F2​
3. 去除函数依赖冗余，函数依赖集为上一步得到的F2F_2F2​

候选码求解算法

1. 划分L,R,N,LR类属性，L,N类属性必包含在候选码中，R类属性必不在候选码中，LR类属性不确定，需要筛选。XXX为L,N类属性的集合，YYY为LR属性的集合
2. 若XF+=UX_F^+ = UXF+​=U，算法结束。XXX是唯一的候选码
3. 逐一查看YYY中的单个属性AAA，若(XA)F+=U(XA)_F^+ = U(XA)F+​=U，则XAXAXA为候选码，Y=Y−AY=Y-AY=Y−A
4. YYY不为空，依次查看YYY中任意2个、3个、…属性ZZZ，若(XZ)F+=U(XZ)_F^+=U(XZ)F+​=U，且XZXZXZ不包含已求得的候选码，XZXZXZ为候选码，直至取完所有属性的集合

模式分解

无损连接性的判定算法(通用)

1. 建立一张nnn列kkk行的表，每一列对应一个属性AjA_jAj​，每一行对应一个关系模式RiR_iRi​。若属性AjA_jAj​属于UiU_iUi​，则在表中 i行j列处填上aja_jaj​，否则填上bijb_{ij}bij​
2. 把表看作RRR的一个关系，依次检查FFF中每一函数依赖在表中是否成立.若不成立，则做出修改使其成立。修改原则：能改成aaa则改成aaa，否则改成行下标最小的bbb；(称为一趟扫描过程)【看某一函数依赖X→YX\rightarrow YX→Y左侧的属性XXX所在的列，是否有两行出现相同的aaa。若出现,，且有一行YYY所在的列取值也为aaa，则将另一行的YYY所在列的值也改为aaa】
3. 如果在一趟扫描中的某次更改之后出现形如a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​的行，算法结束，分解ρ具有无损连接性；否则，继续下一趟扫描过程，直到一趟扫描之后表无任何变化时算法结束 (此时未出现形如a1,a2,…,ana_1,a_2,…,a_na1​,a2​,…,an​的行)，分解ρ不具有无损连接性

一分为二的模式分解的无损连接性判定算法

不考虑多值依赖

关系模式RRR的一个分解ρ=R1，R2ρ={ R1，R2 }ρ=R1，R2具有无损连接性的充分必要条件是：U1∩U2→U1－U2U1∩U2 → U1－U2U1∩U2→U1－U2 或 U1∩U2→U2－U1U1∩U2 → U2－U1U1∩U2→U2－U1成立。

考虑多值依赖(Multivalued Dependency,MVD)

MVD 定义：设R(U)R(U)R(U)是一个属性集UUU上的关系模式，XXX和YYY是UUU的子集。如果对R(U)R(U)R(U)的任一关系 rrr，rrr中任意在XXX上值相同的元组 s,ts, ts,t，交换 s,ts, ts,t 在YYY上的分量而得到的元组仍在关系$ r$ 中，则称YYY多值依赖于XXX，或XXX多值决定YYY，记为X→→YX→→YX→→Y

关系模式RRR中，FFF为RRR中的函数依赖和多值依赖的集合。分解ρ=R1，R2ρ={ R1，R2 }ρ=R1，R2具有无损连接性的充分必要条件是U1∩U2→→U1－U2U1∩U2 →→ U1－U2U1∩U2→→U1－U2 成立

函数依赖集的投影求解算法

设ρ=R1，R2，…，Rkρ={ R1，R2，…，Rk}ρ=R1，R2，…，Rk是关系模式RRR的一个分解，求解FFF在每个UiU_iUi​上投影Fi(i=1,2,...,k)F_i (i=1, 2, ..., k)Fi​(i=1,2,...,k)。

1. 初始令每个FiF_iFi​为空集；
2. 依次取UiU_iUi​中的单一属性XXX，求XF＋X_F^＋XF＋​，若A∈UiA\in U_iA∈Ui​且A∈XF＋A\in X_F^＋A∈XF＋​且X→AX→AX→A不能由当前求得的FiF_iFi​推导出，则将X→AX→AX→A加入FiF_iFi​，如加入使得FiF_iFi​中一部分已有依赖变得多余，则从FiF_iFi​中删除多余的依赖；
3. 依次任取UiU_iUi​中的两个、三个、…个属性构成属性组XXX，求XF＋X_F^＋XF＋​，若A∈UiA \in U_iA∈Ui​且A∈XF＋A\in X_F^＋A∈XF＋​且X→AX→AX→A不能由当前求得的FiF_iFi​推导出，则将X→AX→AX→A加入FiF_iFi​ ，如加入使得FiF_iFi​中一部分已有依赖变得多余，则从FiF_iFi​中删除多余的依赖；
4. 重复3，直到取尽Ui中的所有属性组XXX，算法结束