Java教程

数据库原理:求最小依赖集和候选键

本文主要是介绍数据库原理:求最小依赖集和候选键,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 数据依赖的公理系统
    • Armstrong 公理
    • 函数依赖闭包
  • 最小函数依赖集
    • 最小函数依赖集的定义
    • 最小依赖集的计算算法
    • 样例
      • 样例一
      • 样例二
      • 样例三
  • 求候选键
    • 候选键的求法
    • 样例
      • 样例一
      • 样例二
      • 样例三
  • 参考资料

数据依赖的公理系统

Armstrong 公理

设有关系模式 R(U) 及其函数依赖集 F,如果对于 R 的任一个满足 F 的关系 r 函数依赖 X→Y 都成立,则称 F 逻辑蕴涵 X→Y,或称 X→Y 可以由 F 推出。给定关系模式 R(U) 和 FD 集 F,Armstrong 公理规定了以下的推理规则:

推理规则 说明
A1 自反律 若 Y⊆X⊆U, 则 X⊆Y 成立(平凡依赖)
A2 增广律 若 Z⊆U 且 X→Y,则 XZ→YZ 成立
A3 传递律 若 X→Y,Y→Z,则 X→Z 成立

根据以上三条公理,可得到以下推理规则:

推理规则 说明
合并规则 若 X→Y,X→Z,则 X→YZ 成立
伪传递规则 若 X→Y,WY→Z,则 WX→Z 成立
分解规则 若 X→Y,且 Z⊆Y,则 X→Z 成立
复合规则 若 X→Y,且 W→Z,则 XW→ZY 成立

函数依赖闭包

在关系模式 R<U,F> 中为 F 所逻辑蕴含的函数依赖的全体叫作 F 的闭包,记为 F+。设 F 为属性集 U 上的一组函数依赖,X⊆U,XF+={A|X→A 能由 F 根据 Armstrong 公理导出},XF+ 称为属性集 X 关于函数依赖集 F 的闭包。
翻译成人话就是你有一些字母 X,通过函数依赖集 F 的箭头可以得到的所有字母就是 X 关于 F 的闭包。例如设属性集 U={A,B,C},函数依赖集 F={A→B, B→C} 则 AF+={A,B,C},BF+={B,C},CF+={C}。

最小函数依赖集

最小函数依赖集的定义

最小函数依赖集是函数依赖集 F 如果满足下列条件,则称 F 为最小函数依赖集:

  1. F 中每一个函数依赖的右部都是单个属性;
  2. 对 F 中任一函数依赖 X→A,F-{X→A}都不与 F 等价;
  3. 对于 F 中的任一函数依赖 X→A,X 有真子集 Z 使得{X→A}∪{Z→A}都不与 F 等价。

翻译成人话就是你有一些你有一些字母 X 和函数依赖集 F,你可以找到一个更小的函数依赖集,它的所有函数依赖的箭头右边都只有一个字母,且不影响把箭头右边的字母都推出来。

最小依赖集的计算算法

  1. 应用分解规则,使 F 中每一个依赖的右部属性单一化。
  2. 去掉各依赖左部多余的属性。具体做法是:一个一个地检查 F 中左边是非单属性的依赖,例如 XY→A。判断Y是否为多余的,即以 X→A 代替 XY→A 是否等价,在 F 中求 X+,若 X+ 包含
    A,则 Y 是多余的属性;否则 Y 不是多余属性。依次判断其他属性即可消除各依赖左边的多余属性。
  3. 去掉多余的依赖。具体做法是:从第一个依赖开始,从 F 中去掉它(假设该依赖为 X→Y),然后在剩下的依赖中求 X,看 X+ 是否包含 Y,若是则去掉 X→Y,若不包含 Y 则不能去掉 X→Y。

样例

样例一

先看一个简单的例,属性集 ABC 上的 FD 集,设 F={A→BC, B→AC, C→A},求 Fm。第一步先将每一个依赖的右部属性单一化:

F={A→B, A→C, B→A, B→C, C→A}

接着去掉各依赖左部多余的属性:

判断 A→B 是否冗余:G1={A→C, B→A, B→C, C→A}
    AG1+=AC,B 不属于 AG1+,A→B 不冗余;

判断 A→C 是否冗余:G2={A→B, B→A, B→C, C→A}
    AG2+= ABC,C∈AG2+,A→C 冗余,
    修改为:F={A→B, B→A, B→C,C→A};    

判断 B→A 是否冗余:G3={A→B, B→C, C→A}
    BG3+= ABC,A∈BG3+,B→A 冗余,
    F={A→B, B→C, C→A};

判断 B→C 是否冗余:G4={A→B, C→A}
    BG4+=B,C 不属于 BG4+,B→C 不冗余;

判断 C→A 是否冗余:G5={A→B, B→C}
    CG5+=C,A 不属于 CG5+,C→A 不冗余。  

由于例中函数依赖的决定因素均为单属性,因而不需要第三步检查,上述结果就是最小函数依赖集。

Fm={A→B, B→C, C→A}

样例二

接着看一个啰嗦点的例子,设有依赖集 F,计算与其等价的最小依赖集。

F={MN→XZ, M→X, GP→N, ZP→M, XYZ→P, HN→P, Y→H, MNX→PG}

第一步,右边单一化:

F1={MN→X, MN→Z, M→X, GP→N, ZP→M, XYZ→P, HN→P, Y→H, MNX→P, MNX→G}

第二步:逐个求,在去掉它的 F 中求闭包

去掉 MN→X  后,求得的闭包包含   X,不保留
去掉 MN→Z  后,求得的闭包不包含 Z,保留
去掉 M→X   后,求得的闭包不包含 X,保留
去掉 GP→N  后,求得的闭包不包含 N,保留
去掉 ZP→M  后,求得的闭包不包含 M,保留
去掉 XYZ→P 后,求得的闭包不包含 P,保留
去掉 HN→P  后,求得的闭包不包含 P,保留
去掉 Y→H   后,求得的闭包不包含 H,保留
去掉 MNX→P 后,求得的闭包不包含 P,保留
去掉 MNX→G 后,求得的闭包不包含 G,保留

去掉各依赖左部多余的属性后得到:

F2={MN→Z, M→X, GP→N, ZP→M, XYZ→P, HN→P, Y→H, MNX→P, MNX→G}

第三步,对左边属性单一化:

MN→Z:
    M→Z,求(M)+不包含 Z,所以 N 不冗余。
    N→Z,求(N)+不包含 Z,所以 M 不冗余。

GP→N:
    G→N,求(G)+不包含 N,所以 P 不冗余。
    P→N,求(P)+不包含 N,所以 G 不冗余。

ZP→M:
    Z→M,求(Z)+不包含 M,所以 P 不冗余。
    P→M,求(P)+不包含 M,所以 Z 不冗余。

XYZ→P:
    XY→P,求(XY)+不包含 P,所以 Z 不冗余。
    YZ→P,求(YZ)+不包含 P,所以 X 不冗余。
    XZ→P,求(XZ)+不包含 P,所以 Y 不冗余。

HN→P:
    H→P,求(H)+不包含 P,所以 N 不冗余。
    N→P,求(N)+不包含 P,所以 H 不冗余。

MNX→P:
    MN→P,求(MN)+包含   P,所以 X 冗余。
    MX→P,求(MX)+不包含 P,所以 N 不冗余。
    NX→P,求(NX)+不包含 P,所以 M 不冗余。

MNX→G:
    MN→G,求(MN)+包含   G,所以 X 冗余。
    MX→G,求(MX)+不包含 G,所以 N 不冗余。
    NX→G,求(NX)+不包含 G,所以 M 不冗余。

综上所述,去掉多余的依赖后得到最小函数依赖集。

Fm={MN→Z, M→X, GP→N, ZP→M, XYZ→P, HN→P, Y→H, MN→P, MN→G}

样例三

最后给一个实际的例子,设有关系模式如下。设一个学生可以选多门课程,一门课程可以被多名学生选。一个学生有唯一的所在系,每门课程有唯一的课程名和学分。每个学生对每门课程有唯一的成绩。

学生修课(学号, 姓名, 所在系, 性别, 课程号, 课程名, 学分, 成绩)

对关系模式归纳出函数依赖如下,得到候选键是{学号,课程号}。

学号→(姓名, 所在系, 性别)
课程号→(课程名, 学分)
(学号, 课程号)→成绩

第一步,右边单一化:

F1={学号→姓名, 学号→所在系, 学号→性别, 课程号→课程名, 课程号→学分, (学号, 课程号)→成绩}

第二步逐个求,在去掉它的F中求闭包。

去掉“学号→姓名”后,求得的闭包不包含“姓名”,保留
去掉“学号→所在系”后,求得的闭包不包含“所在系”,保留
去掉“学号→性别”后,求得的闭包不包含“性别”,保留
去掉“课程号→课程名”后,求得的闭包不包含“课程名”,保留
去掉“课程号→学分”后,求得的闭包不包含“学分”,保留
去掉“(学号, 课程号)→成绩”后,求得的闭包不包含“课程号”,保留

去掉各依赖左部多余的属性后得到:

F2={学号→姓名, 学号→所在系, 学号→性别, 课程号→课程名, 课程号→学分, (学号, 课程号)→成绩}

第三步,对左边属性单一化:

(学号,课程号)→成绩:
    学号→成绩,求(学号)+不包含“成绩”,所以“学号”不冗余。
    课程号→成绩,求(课程号)+不包含“成绩”,所以“课程号”不冗余。

综上所述,去掉多余的依赖后得到最小函数依赖集。

Fm={学号→姓名, 学号→所在系, 学号→性别, 课程号→课程名, 课程号→学分, (学号,课程号)→成绩}

求候选键

候选键的求法

博客数据库原理:数据模型和关系数据库有提到过,候选码是它的值能唯一地标识一个元组,而其子集不能标识的属性组。
由于其他求法我都没看懂,所以只介绍快速判断方法。先计算函数依赖集 F 的最小函数依赖集,然后采用快速判定法,以及候选键的定义来确定候选键。对于给定的关系 R(U, F),可将其属性分为四类:

属性类别 说明
L 类 仅出现在函数依赖集 F 的左部的属性
R 类 仅出现在函数依赖集 F 的右部的属性
LR 类 在函数依赖集 F 的左右两边均出现的属性
N 类 在函数依赖集 F 的左右两边均未出现的属性

快速求解候选码的一个充分条件是,对于给定的关系模式 R(U, F),X∈U:

  1. 若 X 是 R 的 L 类属性,则 X 必为 R 的任一候选码中的属性;
  2. 若 X 是 R 的 R 类属性,则 X 必不在 R 的任一候选码中;
  3. 若 X 是 R 的 N 类属性,则 X 必为 R 的任一候选码中的属性。

快速求解候选码过程:

  1. 将 R 的所有属性分为 L、R、N 和 LR 四类,并令 X 代表 L、N 两类,Y 代表 LR 类;
  2. 求属性集闭包 X+,若 X+ 包含了 R 的全部属性则 X 即为 R 的唯一候选码,转(5);
  3. 在 Y 中取一属性 A,求属性集闭包(XA)+,若(XA)+包含了 R 的全部属性,则转(4);否则调换一属性反复进行这一过程,直到试完所有 Y 中的属性;
  4. 如果已找出了所有的候选码,则转(5);否则在 Y 中依次取 2个、3个、…… 属性,求 X 与它们的属性集闭包,直到其闭包包含 R 的全部属性;
  5. 停止,输出结果。

样例

样例一

设有关系模式 R(M, N, X, Y),其函数依赖集 F={Y→N, N→Y, MY→N, MX→Y},求 R 的所有候选键。

Left:{M, X}
LR:{N, Y}
Not:{}
因为对 {Left,Not}F+=R,所以{M,X}是 R 的所有候选键。

样例二

设有关系模式 R(U, F),其中 U={M, N, X, Y, Z, P},F={M→N, X→Y, Z→ M ,XZ→Y},试求此关系的候选键。

Left:{X,Z}
LR:{M}
Not:{P}
因为对{Left,Not}F+=R,所以{X, Z, P}是 R 的所有候选键

样例三

设关系模式 R(S, D, I, B, O, Q),其函数依赖集 F={S→D, I→B, B→O, O→Q, Q→I},求 R 的所有候选码。

Left:{S}
LR:{I, B, O, Q}
Not:{}

因为S+=SD,所以 S 不是 R 的候选码;
因为(SI)+=SIDBOQ,所以 SI 是一个候选码;
因为(SB)+=SBDOQI,所以 SB 是一个候选码;
因为(SO)+=SODQIB,所以 SO 是一个候选码; 
因为(SQ)+=SQDIBO,所以 SQ 是一个候选码。

参考资料

《数据库系统概论(第5版)》,王珊 萨师煊 编著,高等教育出版社

这篇关于数据库原理:求最小依赖集和候选键的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!