关系模式中候选关键字的图论求解法
李
莉
【摘
要】
文章首先介绍了函数依赖图的概念及理论，并应用该理论对数据库理
论和实际问题中关系模式候选关键字的求解问题进行了深入系统的讨论，并用
该方法解决了关系模式中函数依赖的左边为单属性的候选关键字的求解问题，
该算法与传统算法相比，可显著降低
I/0
时间和
CPU
时间，急剧降低算法的时
间复杂度
.
【期刊名称】
河西学院学报
【年
(
卷
),
期】
2009(025)002
【总页数】
2
【关键词】
关系模式；候选关键字；函数依赖图
1
引言
在关系数据库理论和实际问题中，经常要求解一个关系模式的候选关键字，传
统的方法是通过求属性闭包来确定，但理论上对于
n
个属性的关系模式，要计
算
2n-1
次属性闭包才能找到所有的候选关键字，显然这是一个
N-p
完全问题
[1].
本文将介绍一种针对左边为单属性的极小函数依赖集的候选关键字成员的图
论求解法
.
2
问题与讨论
2.1
定义和记号
1.
对于关系的描述称为关系模式，它形式化地表示为
R(U,F)
，其中
R
为关系名，
U
为组成该关系的属性名集合，
F
为属性间函数依赖集合
.
2.
对于给定的
R
(
U
)和函数依赖集
F
，可以将它的属性划分为
4
类：

主关键字只能有一个，候选关键字若干不限

关系模式判断候候选关键字 与 函数依赖无损连接

例题:设关系模式R(U， F），其中R上的属性集U={A， B， C， D， E}，R上的函数依赖集F=｛A→B，DE→B，CB→E，E→A，B→D｝。（  ）为关系R的候选关键字。分解（  ）是无损连接，并保持函数依赖的。

问题一:

A: AB    B:DE    C:CE    D:DB

问题二:

A.p=｛R1(AC)，R2(ED)，R3(B)｝

B.p=｛R1(AC)，R2(E)，R3(DB)｝

C.p=｛R1(AC)，R2(ED)，R3(AB)｝

D.p=｛R1(ABC)，R2(ED)，R3(ACE)｝

 

解:

问题一:

依据每个选项以及函数依赖集F判断是否能够遍历全图;



嗯...图太丑,见谅!  答案:CE;

问题二: 答案:D



原则:关系模式包含此列头,那么记为a,下标为列号(1开始);如果不包含此列头,那么记为b,下标为坐标.

依据函数依赖集,反复计算,直到无法计算为止.

计算方法:例: DE->B 找到,DE 2列相同值的行,目标列B中如果有a,则记为a;没有a,记为此列最小b;

反复计算后可得出:



 行一全部为a,则无损分解.(某一行全部为a即可)

1、已知关系R(A,B,C,D,E)及其上的函数相关性集合,F={A→B,E→A,CE→D},该关系的候选关键字是？

涉及知识点



一、关系R：

1、在用户看来的定义

关系R，即关系模式，就是对关系（表）的描述。    
关系名（属性1，属性2，属性3， …） 
关系名：表名
属性：  表中的一列即为一个属性
2、形式化定义

关系定义2.3： 

n目关系必有n目关系
二、候选关键字

候选关键字：候选码，关系中的某一属性组的值能唯一地标识一个元组织。
元组：表中的一行即为一组，属性所对应的行值。
三、函数相关性集合F

函数相关性集合F，有时称为函数依赖集F
对于给定的R,可以将它的属性划分为4类: 
L类,仅出现在F的函数依赖左部的属性.
R类,仅出现在F的函数依赖右部的属性.
N类,在F的函数依赖左部和右部均未出现的属性.
LR类,在F的函数依赖左部和右部两部均出现的属性
求解候选码.

定理1:对于给定的关系模式R,若X(X∈U)是 L类 或 N类 属性组,则X必为R的任一候选码的成员.

推论1:对于给定的关系模式R,若X(X∈U)是 L类 属性组,且X+包含了R的全部属性,则X必为R的唯一候选码.

推论2:对于给定的关系模式R,若X是R的 N类 和 L类 组成的属性组,且X+包含了R的所有属性,则X是R的唯一候选码.

分析题目：

F={A→B,E→A,CE→D} 

有依赖关系可知 

E-> A -> B 

CE->D 


所以候选码为C、E、。

举一反三：


  
1、(2016Tecent.4)关系R(F,G,H,I,J)极其上的函数相关性集合F = {F->G, J->F, 

  HJ->I}，该关系的候选关键字为？


分析：J->F->G,  HJ->I. 所以 

答案：H,J


  
2、设有关系模式R（A,B,C,D,E）,模式中有函数依赖集合={A-BC,CD-E,B-D,E-A}，试求关系模式R的所有候选码


分析：所以 


怎样： 


候选码：（1）A；（2）CD；（3）E； 

？？？？？？


  
3、设有关系模式R(A,B,C,D,E), F是R上成立的函数依赖集, F={A->BC,B->D,E->A},试写出关系模式R的候选码,并说明理由.


分析： 


或者这样看： 


根据上面的推论1可知E为唯一的候选码；

类似：计算范式的