下载文档原格式
最小函数依赖集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，则保留。
数据库函数依赖和范式总结1 函数依赖1.1 定义：一个集合R(U,F)，U为属性全集，F为函数依赖集合。
F中存在着{Xi->Yi...};对于每个X都存在着一个Y与之唯一对应。
意思就是相当于X为主键，Y由主键决定。
比如一个学生他的学号相当于X，而他的姓名与年龄这些其他信息相当于Y。
但是X有时候并不是一个值，比如一个学生他的成绩需要有两个属性才能知道他的成绩，学号+课程号->成绩1.2 平凡函数依赖与非平凡函数依赖平时我们主要讨论的是非平凡函数依赖。
平凡函数依赖概念：Y集合属性属于X集合属性的子集非平凡函数则相反1.3 逻辑蕴涵(为后面求闭包做好基础)X,Y为属性集合U的子集，且X->Y不存在于F中。
即我们需要通过F中的函数依赖推出X->Y称为函数依赖。
而所有函数依赖的集合则称为闭包1.4 函数依赖的推理规则(就是求函数依赖的逻辑蕴涵)1.4.1 几个公理1.4.1.1 公理一(自反律):Y属于X的子集，则X->Y 数学公式描述 Y?X?U1.4.1.2 公理二(增广律):X->Y成立，Z?U也成立，则 XZ?YZ1.4.1.3 公理三(传递律):X->Y成立，Y->Z成立，则 X->Z1.4.2 公理的推广1.4.2.1 推广一(合并律):X->Y,X->Z,则X->YZ1.4.2.2 推广二(伪传递律):X->Y,YW->Z,则XW->Z(证明只需要在XY两边*W)1.4.2.3 推广三(分解律):X->Y成立，Z?Y，则 X->Z1.4.2.4 推广四(复合律):X->Y,W->Z,则XW->YZ1.5 完全函数依赖与部分函数依赖(范式中基础知识)X->Y的集合中，若X的任一真子集x都能 x->Y则为部分函数依赖，若不能则的完全函数依赖，如果X没有真子集则也称为完全函数依赖。
关系模式R(U，F)中，U=ABCDEG，F={B->D，DG->C,BD->E,AG->B,ADG->BC} 求F的最小函数依赖集方法如下：1.根据分解规则，将函数依赖的右端分解成单个属性该题目的话要将：BC分解成单个属性。
F={ADG->B,ADG->C,······}2.对于F中的每个函数X->A,设G=F-{X->A},如果A属于X的闭包，则将X->A从中删除，否则保留。
该题目：1)G=F-{B->D},则B的闭包={B},包不含D,则保留2)G=F-{DG->C},则DG的闭包={DG},不包含C,则保留3)G=F-{BD->E},则BD的闭包={BD},不包含E,则保留4)G=F-{AG->B},则AG的闭包={AG},不包含B,则保留5)G=F-{ADG->B},则ADG的闭包={ADGBCE},包含B,则删除6)G=F-{ADG->C},则ADG的闭包={ADGBCE},包含C,则删除F={B->D,DG->C,BD->E,AG->B}R(U, F)，U=ABCDEF, F={AD→E, AC→E, BC→F, BCD→AF, BD→A, AB→F, A→C}求最小函数依赖集答案是：分解右部为属性组的函数依赖，得F={AD→E,AC→E,BC→F,BCD→A,BCD→F,BD→A,AB→F,A→C}对于AD→E，∵(AD)的闭包=ADCE, 又∵E不属于ACDE∴AD→E 冗余对于AC→E，∵(AC)的闭包＝AC,又∵E不属于AC，∴AC→E不冗余对于BC→F，∵(BC)的闭包＝BC，又∵F不属于BC，∴BC→F 不冗余对于BCD→A，∵(BCD)的闭包=ABCDEF，又∵A不属于ABCDEF ∴BCD→A 冗余对于BCD→F，∵(BCD)的闭包=ABCDEF，又∵F不属于ABCDEF ∴BCD→F 冗余对于BD→A，∵(BD)的闭包=BD，又∵A不属于BD，∴BD→A 不冗余对于AB→F，∵(AB)的闭包=ABCDEF，又∵F属于ABCDEF ∵AB→F 冗余对于A→C，∵A的闭包=A，又∵C不属于A，∴A→C 不冗余∴F的最小函数依赖集为{AC→E,BC→F,BD→A,A→C}。
更多优质自考资料，请访问自考乐园俱乐部/club/5346389 2010年全国自考数据库系统原理模拟试卷(五)一、单项选择题（本大题共15小题,每小题2分,共30分）在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1.元数据是指()A.描述性的数据B.用户数据C.索引数据D.统计数据答案：A2.概念模型是()A.硬件独立，软件独立B.硬件独立，软件依赖C.硬件依赖，软件独立D.硬件依赖，软件依赖答案：A3.在标准SQL中，建立数据库结构(模式)的命令为()A.CREATE SCHEMA命令B.CREATE TABLE命令C.CREATE VIW命令D.CREATE INDEX命令答案：A4.下列哪种关系模型具有第一范式性质()A.平面关系模型B.嵌套关系模型C.复合对象模型D.以上均不具有答案：A5.在分布式系统中，场地是由()组成的A.计算机B.数据库C.若干终端D.A、B和C答案：D6.ODBC是指()A.对象数据库约束B.面向数据库约束C.开放式数据库互连D.开放式数据库约束答案：A7.SQL中，下列涉及空值的操作，不正确的是()A.AGE=NULLB.AGE IS NOT NULLC.AGE IS NULLD.NOT(AGE IS NULL)答案：A8.实现数据库并发控制的重要技术是()A.触发器B.数据库的后备副本C.封锁D.访问权限控制答案：C9.分布式数据库系统具有两个性质()A.场地独立性和网络协作性B.场地自治性和场地间的协作性C.场地自治性和网络自治性D.场地透明性和系统完整性答案：B10.聚合函数中，操作对象是元组的函数是()A.SUMB.AVGC.COUNTD.MIN答案：C11.()完整地揭示了数据之间的联系A.数据流图B.数据字典C.类型构造图D.对象联系图答案：D 更多优质自考资料，请访问自考乐园俱乐部/club/5346389更多优质自考资料，请访问自考乐园俱乐部/club/534638912.设关系R和S的结构相同，并且各有100个元组，那么这两个关系的运算结果的元组个数为()A.100B.小于等于100C.200D.小于等于200答案：D13.数据库管理系统(DBMS)是()A.数学软件B.应用软件C.计算机辅助设计D.系统软件答案：D14.数据库系统的操作开销包括()A.报告生成B.改组频率C.辅存空间D.以上答案都对答案：D15.下列“回收权限”语句有可能失败的是()A. AB. BC. CD. D答案：B二、填空题（本大题共10小题,每小题1分,共10分）请在每小题的空格上填上正确答案。
习题
（判定无损连接性和保持函数依赖）
1、设有关系模式R<U，F>，U={X，Y，Z，S，W}，F={X→S，W→S，S→Y，YZ→S，SZ→XY}，设R 分解成P={R1(WS)，R2(YZS)，R3(XZS)}，判断该分解是否保持函数依赖，并判断此分解是否具有无损连接性。
解：求出F的最小函数依赖集F’={X→S，W→S，S→Y，YZ→S，ZS→X}
若R分解为={R1(WS)，R2(YZS)，R3(XZS)}，
)+，则R<U,F>的分解р={R1，R2，R3}保持函数依赖。
因为： F’+ =( F
i
所以，该分解能保持函数依赖关系。
（5分）
所以，可以得到没有一行全为a,所以该分解为有损分解。
2．设有关系模式R(ABCDEG)，其函数依赖集为：
F={E→D，C→B，CE→G，B→A}
判断R的一个分解ρ={R1(AB),R2(BC),R3(ED),R4(EAG)}是否无损连接和保持函数依赖。
证：
（1）判断无损连接
A1A2A3A4A5A6，该分解有损
（2）判断是否保持函数依赖（5分）
从F={E→D，C→B，CE→G，B→A}得到：
R1(AB)，其F1={ B→A }
R2(BC)，其F2={C→B}
R3(ED)，其F3={E→D}
R4(EAG)，其F4={EAG→EAG }
G=F1∪F2∪F3∪F4={ B→A ，C→B ，E→D ，EAG→EAG }
由于CEG+={CEBA}，即CE→G不能由G根据Armstrong公理推导出来故F+!=(F1∪F2∪F3∪F4)+，故不保持函数依赖。
规范化理论习题1. 解释下列名词：函数依赖、部分函数依赖、完全函数依赖、传递函数依赖、候选关键字、主关键字、全关键字、1NF 、2NF 、3NF 、BCNF 、多值依赖、4NF 、连接依赖、5NF 、最小函数依赖集、无损分解函数依赖：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 是传递依赖。
候选关键字：设K 为关系模式R （U ，F ）中的属性或属性集合。
若K —→F U ，则K 称为R的一个候选码（Candidate Key ），也称作为候选关键字或码。
主关键字：若关系模式R 有多个候选码，则选定其中一个作为主关键字（Primary Key ），有时也称作为主码。
全关键字：若关系模式R 整个属性组都是码，称为全关键字（All Key ）或全码。
1NF ：第一范式。
如果关系模式R 的所有属性的值域中每一个值都是不可再分解的值, 则称R 是属于第一范式模式。
如果某个数据库模式都是第一范式的，则称该数据库存模式属于第一范式的数据库模式。
第一范式的模式要求属性值不可再分裂成更小部分，即属性项不能是属性组合和组属性组成。
2NF ：第二范式。
如果关系模式R 为第一范式，并且R 中每一个非主属性完全函数依赖于R 的某个候选键， 则称是第二范式模式；如果某个数据库模式中每个关系模式都是第二范式的，则称该数据库模式属于第二范式的数据库模式。
