下载文档原格式
最小函数依赖集Fmin求解算法研究及实现
邸振山
【期刊名称】《电脑编程技巧与维护》
【年(卷),期】2012(000)018
【摘要】函数依赖反映了现实世界中数据的完整性约束,对关系数据库的分析和设计起着重要的作用.最小函数依赖集和模式规范化是规范化理论和模式分解中的两个最重要概念.研究并实现了最小函数依赖集的求解算法.
【总页数】3页(P14-15,21)
【作者】邸振山
【作者单位】秦皇岛市人力资源和社会保障局信息中心,河北秦皇岛066004【正文语种】中文
【相关文献】
1.关系模式最小函数依赖集的求解与应用 [J], 裴祥喜;李珉;赵福伟
2.一个用于求解关系模式上最小函数依赖集合（F）min的算法 [J], 庆振
树;chen,PP
3.函数依赖最小覆盖集求解算法——在数据库设计中的应用 [J], 邹炜;周定康
4.LR最小替换集求解算法研究 [J], 郝忠孝;刘国华;姚春龙
5.用最小不动点理论求解最小函数依赖集 [J], 谢宝永;李磊
因版权原因，仅展示原文概要，查看原文内容请购买。
最小函数依赖最小函数依赖（MinimumFunctionalDependencies，MFDs）是数据库理论中最重要的概念之一，它主要用于描述一个表里不同属性间的依赖关系。
换句话说，最小函数依赖能够描述一个表里的属性是如何联系起来的。
最小函数依赖的定义引入了一个表里的任何属性X，其他属性Y的值依赖于X的值，即X->Y。
而且这里的依赖是根据最小原则来定义的，即Y只能有一个属性X。
最小函数依赖的概念在关系数据库设计中起着非常重要的作用，它不仅能帮助我们正确地设计关系型数据库，还能帮助我们确定哪些属性是主键，也能帮助我们更好地理解属性之间的一对多（one-to-many）和多对多（many-to-many）的关系。
首先，最小函数依赖能够帮助我们设计合理的关系型数据库。
通过描述属性之间的依赖关系，我们不但可以把握准确的数据结构，还可以避免出现重复数据，从而大大提高数据库的可维护性。
其次，最小函数依赖也能帮助我们确定主键。
通过MFD的定义，我们可以明确一个表中的属性X能唯一确定其他属性Y，这样X就能作为主键，而Y可以看作其联系属性。
最后，最小函数依赖也能够帮助我们更好地理解属性之间的一对多（one-to-many）和多对多（many-to-many）的关系。
通过MFD的定义，我们可以将复杂的关系简单化，有效地解决类似“一对多”和“多对一”等关系中属性之间的对应问题。
总之，最小函数依赖是数据库理论中最重要的概念之一，它在关系数据库设计中的作用十分重要，能够帮助我们正确地设计关系型数据库，还可以帮助我们确定哪些属性是主键，更好地理解属性之间的一对多（one-to-many）和多对多（many-to-many）的关系。
最小函数依赖的概念和作用不仅仅是非常重要的，它也为数据库设计提供了理论基础，在实际应用中也非常有用。
第一部分:一、求最小依赖集例：设有依赖集：F={AB-C, C-A, BC—D, ACD-B, D—EG, BE—C, CG—BD, CE f AG},计算与其等价的最小依赖集。
解：1、将依赖右边属性单一化，结果为：F1={AB—C, C—A, BC—D, ACD—B, D—E, D—G, BE—C, CG—B, CG—D CE―A, CE—G}2、在F1中去掉依赖左部多余的属性。
对于CE—A,由于C—A成立，故E是多余的；对于ACD—B,由于(CD) +=48。
£»6,故A是多余的。
删除依赖左部多余的依赖后：F2={AB—C, C—A, BC—D, CD—B, D—E, D—G, BE—C, CG—B, CG—D, CE—G }3、在F2中去掉多余的依赖。
对于CG—B,由于(CG) +=ABCEDG,故CG—B是多余的。
删除依赖左部多余的依赖后：F3={AB—C, C—A, BC—D, CD—B, D—E, D—G, BE—C, CG—D, CE—G }CG—B与CD—B不能同时存在，但去掉任何一个都可以，说明最小依赖集不唯一。
二、求闭包例：关系模式R (U, F),其中U={A, B, C, D, E, I}, F={A—D, AB—E, BI—E, CD—I, E—C},计算(AE) +。
解：令X={AE}, X (0) =AE；计算X(1)；逐一扫描F集合中各个函数依赖，在F中找出左边是AE子集的函数依赖，其结果是：A—D, E—C。
于是X (1) =AE U DC=ACDE；因为X (0)W X (1),且X (1)WU,所以在F中找出左边是ACDE子集的函数依赖，其结果是：CD—I。
于是X (2) =ACDE UI=ACDEI。
虽然X (2)W X (1),但在F中未用过的函数依赖的左边属性已没有X (2) 的子集，所以不必再计算下去，即(AE) +=ACDEI。
一个用于求解关系模式上最小函数依赖集合（F）min的算法庆振树;chen,PP
【期刊名称】《计算机工程》
【年(卷),期】1989(000)006
【摘要】本文介绍一个采用DDHD技术求解关系模式上最小函数依赖集合(F)min 的算法,采用这种方法可以方便地从任意给定的函数依赖集合F直接求得相应的最小函数依赖集合,这种方法是关系数据库设计和规范化的有用工具。
【总页数】11页(P32-42)
【作者】庆振树;chen,PP
【作者单位】不详;不详
【正文语种】中文
【中图分类】TP311.13
【相关文献】
1.关系模式最小函数依赖集的求解与应用 [J], 裴祥喜;李珉;赵福伟
2.最小函数依赖集Fmin求解算法研究及实现 [J], 邸振山
3.函数依赖最小覆盖集求解算法——在数据库设计中的应用 [J], 邹炜;周定康
4.用最小不动点理论求解最小函数依赖集 [J], 谢宝永;李磊
5.大型Petri网模型最小trap (siphon)集合的快速求解算法 [J], 廖晶静;王明哲;倪枫;郭法滨
因版权原因，仅展示原文概要，查看原文内容请购买。
函数依赖及范式函数依赖基本概念：•函数依赖：FD(function dependency)，设有关系模式R(U)，X，Y是U的子集，r 是R的任一具体关系，如果对r的任意两个元组t1,t2,由t1[X]=t2[X]导致t1[Y]=t2[Y], 则称X 函数决定Y,或Y函数依赖于X，记为X→Y。
X→Y为模式R的一个函数依赖。
•部分函数依赖：即局部依赖，对于一个函数依赖W→A，如果存在X W(X包含于W)有X→A成立，那么称W→A是局部依赖，否则称W→A为完全函数依赖。
•传递依赖：在关系模式中，如果Y→X，X→A，且X Y（X不决定Y），A X（A不属于X）,那么称Y→A是传递依赖。
•函数依赖集F的闭包F+: 被逻辑蕴涵的函数依赖的全体构成的集合，称为F的闭包(clo sure),记为F+。
•最小依赖集：如果函数集合F满足以下三个条件(1)F中每个函数依赖的右部都是单属性；(2) F中的任一函数依赖X→A，其F-{X→A}与F是不等价的；(3)F中的任一函数依赖X→A，Z为X的子集，（F-{X→A}）∪{Z→A}与F不等价。
则称F为最小函数依赖集合，记为Fmin。
函数依赖的公理系统：设有关系模式R(U)，X，Y，Z，W均是U的子集，F是R上只涉及到U中属性的函数依赖集，推理规则如下：•自反律：如果Y X U,则X→Y在R上成立。
•增广律：如果X→Y为F所蕴涵，Z U，则XZ→YZ在R上成立。
(XZ表示X∪Z，下同) •传递律：如果X→Y和Y→Z在R上成立，则X→Z在R上成立。
以上三条为Armstrong公理系统•合并律：如果X→Y和X→Z成立，那么X→YZ成立。
•伪传递律：如果X→Y和WY→Z成立，那么WX→Z成立。
•分解律：如果X→Y和Z Y成立，那么X→Z成立。
这三条为引理注意：•函数依赖推理规则系统(自反律、增广律和传递律)是完备的。
•由自反律所得到的函数依赖均是平凡的函数依赖。
四种范式的含义：•如果某个数据库模式都是第一范式的，则称该数据库模式是属于第一范式的数据库模式。
最小函数依赖集Fm的求法：1.根据分解规则，将函数依赖的右端分解成单个属性2.对于F中的每个函数X→A，设G=F-{X→A}，如果A∈X G+，则将X→A从中删除，否则保留。
3.对于F中每一个左端包含多个属性的X→A，选择X的每个子集Z，如果A∈Z F+，则用Z→A代替X→A。
例如：F={BE→G,BD→G,CDE→AB,CD→A,CE→G,BC→A,B→D,C→D}求Fm。
解：1）右端分解成单个属性F={BE→G,BD→G,CDE→A, CDE→B,CD→A,CE→G,BC→A,B→D,C →D}2）设G=F-{X→A}，如果A∈X G+，则将X→A删除，否则保留（1）G=F-{ BE→G }={BD→G,CDE→A, CDE→B,CD→A,CE→G,BC →A,B→D,C→D}，则（BE）G+=BEDG，包含G，则删除。
（2）G=F-{BD→G, }={ CDE→A, CDE→B,CD→A,CE→G,BC→A,B →D,C→D}，则（BD）G+=BD，不包含G，则保留。
（3）G=F-{CDE→A}={ BD→G, CDE→B,CD→A,CE→G,BC→A,B →D,C→D}，则（CDE）G+= CDEBGA，包含A，则删除。
（4）G=F-{CDE→B}={ BD→G, CD→A,CE→G,BC→A,B→D,C→D}，则（CDE）G+= CDEAG，不包含B，则保留。
（4）G=F-{CD→A,}={ BD→G, CDE→B，CE→G,BC→A,B→D,C→D}，则（CD）G+= CD，不包含A，则保留。
（5）G=F-{ CE→G,}={ BD→G, CDE→B，CD→A, BC→A,B→D,C →D}，则（CE）G+= CEDBAG，包含G，则删除。
（5）G=F-{ BC→A,}={ BD→G, CDE→B，CD→A, B→D,C→D}，则（BC）G+= BCDGA，包含A，则删除。
（6）G=F-{ B→D,}={ BD→G, CDE→B，CD→A, C→D}，则（B）G+= B，不包含D，则保留。
