最小函数依赖

求最小函数依赖集分三步:1.将F中的所有依赖右边化为单一元素此题fd={abd->e,ab->g,b->f,c->j,cj->i,g->h};已经满足2.去掉F中的所有依赖左边的冗余属性.作法是属性中去掉其中的一个,看看是否依然可以推导此题:abd->e,去掉a,则(bd)+不含e,故不能去掉,同理b,d都不是冗余属性ab->g,也没有cj->i,因为c+={c,j,i}其中包含i所以j是冗余的.cj->i将成为c->iF={abd->e,ab->g,b->f,c->j,c->i,g->h};3.去掉F中所有冗余依赖关系.做法为从F中去掉某关系,如去掉(X->Y),然后在F中求X+,如果Y在X+中,则表明x->是多余的.需要去掉.此题如果F去掉abd->e,F将等于{ab->g,b->f,c->j,c->i,g->h},而(abd)+={a,d,b,f,g,h},其中不包含e.所有不是多余的.同理(ab)+={a,b,f}也不包含g,故不是多余的.b+={b}不多余,c+={c,i}不多余c->i,g->h多不能去掉.所以所求最小函数依赖集为F={abd->e,ab->g,b->f,c->j,c->i,g->h};转换为3NF既具有无损连接性又保持函数依赖的分解算法：第一步：首先用算法1求出R的保持函数依赖的3NF分解，设为q={R1,R2,…,Rk}（这步完成后分解已经是保持函数依赖，但不一定具有保持无损连接）第二步：设X是R的码，求出p=q {R(X)}第三步：若X是q中某个Ri的子集，则在p中去掉R(X)第四步：得到的p就是最终结果例题：R(S#,SN,P,C,S,Z)F={S#→SN,S#→P,S#→C,S#→S,S#→Z,{P,C,S}→Z,Z→P,Z→C}•第一步:求出最小FD集：F={S# →SN, S# →P,S# →C, S#→S, {P,C,S→Z, Z →P,Z →C} // S# →Z冗余，FD：最小函数依赖按具有相同左部分组：q={R1(S#,SN,P,C,S), R2(P,C,S,Z), R3(Z,P,C)}R3是R2的子集，所以去掉R3q={R1(S#,SN,P,C,S), R2(P,C,S,Z)}•第二步:R的主码为S＃，于是p=q {R(X)}={R1(S#,SN,P,C,S), R2(P,C,S,Z), R(S#)}•第三步:因为{S＃}是R1的子集，所以从p中去掉R(S#)•第四步:p ={R1(S#,SN,P,C,S), R2(P,C,S,Z)}即最终结果判别一个分解的无损连接性举例2：已知R<U,F>，U={A,B,C,D,E}，F={A→C,B→C,C→D,DE→C,CE→A}，R的一个分解为R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，判断这个分解是否具有无损连接性。

建立一个关于系,学生,班级,学会等诸信息(1)关系模式如下：学生：S(Sno，Sname，Sbirth，Dept，Class，Rno)班级：C(Class，Pname，Dept，Cnum，Cyear)系：D(Dept，Dno，Office，Dnum)学会：M(Mname，Myear，Maddr，Mnum)(2)每个关系模式的最小函数依赖集如下：A、学生S (Sno，Sname，Sbirth，Dept，Class，Rno) 的最小函数依赖集如下:SnoàSname，SnoàSbirth，SnoàClass，ClassàDept，DEPTàRno传递依赖如下：由于SnoàDept，而DeptàSno ，DeptàRno（宿舍区）所以Sno与Rno之间存在着传递函数依赖。

由于ClassàDept，Dept à Class，DeptàRno所以Class与Rno之间存在着传递函数依赖。

由于SnoàClass，ClassàSno，ClassàDept所以Sno与Dept之间存在着传递函数依赖。

B、班级C(Class，Pname，Dept，Cnum，Cyear)的最小函数依赖集如下:ClassàPname，ClassàCnum，ClassàCyear，PnameàDept.由于ClassàPname，PnameàClass，PnameàDept所以C1ass与Dept之间存在着传递函数依赖。

C、系D(Dept，Dno，Office，Dnum)的最小函数依赖集如下：DeptàDno，DnoàDept，DnoàOffice，DnoàDnum根据上述函数依赖可知，Dept与Office，Dept与Dnum之间不存在传递依赖。

函数依赖及范式函数依赖基本概念：•函数依赖：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成立。

这三条为引理注意：•函数依赖推理规则系统(自反律、增广律和传递律)是完备的。

•由自反律所得到的函数依赖均是平凡的函数依赖。

四种范式的含义：•如果某个数据库模式都是第一范式的，则称该数据库模式是属于第一范式的数据库模式。

作者： 徐爱芸
作者机构： 江汉大学数学与计算机科学学院,湖北武汉430056
出版物刊名： 江汉大学学报：社会科学版
页码： 20-22页
主题词： 最优算法;属性集;函数依赖集闭包;属性集闭包;逻辑蕴含;最小函数依赖集;数据库原理
摘要：在数据库设计中，依据函数依赖集的定义及Armstrong公理，求出的是一个可能存在冗余的函数依赖集。

为了判断一个函数依赖是否为某一函数依赖集逻辑蕴含，只要用求属性闭包的方法求出函数依赖中决定子的属性闭包，判断依赖子是否包含在属性闭包中即可。

本文从求属性闭包的角度出发，给出一个求最小函数依赖集的算法。

数据库函数依赖和范式总结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没有真子集则也称为完全函数依赖。

函数依赖（理论及举例）教你如何理解函数依赖一、函数依赖的概念函数依赖：函数依赖就是讨论一个数据表（关系）中属性值之间所存在的函数关系。

函数是一种数学中的概念，被引入到数据库中对数据的联系进行分析。

在一个关系中，属性相当于数学上的变量，属性的域相当于变量的取值范围，属性在一个元组上的取值相当于属性变量的当前值。

例如：在下面的这个职工关系中，职工号、姓名、性别、年龄、职务等属性都相当于变量；职工号属性的域，即四位十进制数字，就是取值范围，性别属性的域：{男、女}，就是性别属性的取值范围。

此关系中包含有6个元组，如第2个元组为{3051、刘平、男、48、副处}，其中的每个属性值都是对应属性在该元组上的当前值。

单值函数和多值函数：元组中一个属性或一些属性值对另一个属性值的影响相当于自变量值对函数值的影响。

当给定一个自变量值能求出唯一的一个函数值时，称此为单值函数或单映射函数，否则为多值函数。

在单值函数中由自变量的一个值确定函数的一个值，但不同的自变量值允许具有相同的函数值。

如f(x)=2x, f(n)=(-1)^n, f(x)=x^3+1等都是单值函数，由自变量x或n的值能够唯一确定f(x)或f(n)的值。

属性的单值函数决定（依赖）：在一个关系中，若一个或一组属性的值对另一个或一组属性值起到决定性的作用，则称为单值函数决定（依赖）。

如上表中职工号的值就能够函数决定其余每个属性的值，也就是说，当职工号给定后，其他每个属性的值就跟着唯一地确定了。

如假定职工号为3074，则他的姓名必定是王海，性别必定为男，年龄必定为32岁，职务必定为正科。

这就叫做职工号能够分别单值函数决定姓名、性别和年龄属性，反过来，可以说姓名、性别和年龄等属性单值函数依赖于职工号属性。

二、函数依赖的定义定义：设一个关系为R(U)，X和Y为属性集U上的子集，若对于X上的每个值都有Y上的一个唯一值与之对应，则称X和Y具有函数依赖关系，并称X 函数决定Y，或称Y函数依赖于X，记作X→Y，称X为决定因素。

数据库基础与应用一、单选题1.利用 QL 语言所建立的视图在数据库中属于(B)A 实表B 虚表C索引D字段2.下面属于 Aecess 数据库中所含操作对象的是(B)A 文件B 宏C 索引D 视图3.设一个关系为 R(A,B,C D,E),它的最小函数依赖集为 F= 4 一→E,A→C,B 一D,D→B,则该关系的候选码为(A )A AB BC CD D4.在文件系统中,存取数据的基本单位是(A)。

A 记录B 数据项C 二进制位D学节5.在Access 中,如果只想显示表中符合条件的记录,可以使用的方法是(A) 。

A 筛选B 删除C冻结D隐藏6.在Access 中,若利用宏打开一个查询,则选择的宏操作命令是（B）。

A OpenTableB OpenQueryC OpenFormD OpenReport7.在利用计算机进行数据处理的四个发展阶段中,第三个发展阶段是（C）A 人工管理B 文件系统C 数据库系统D 分布式数据库系统8.设两个关系中分别包含有m 和n 个属性,它们具有同一个公共属性,当对它们进行等值连接时，运算结果的关系中包含的属性个数为(C)A m*nB m+n-1 Cm＋nD m＋n+19.在SOL 的查询语句中, group by 选项实现的功能是（D）A 选择B 求和C 排序D 分组统计10.在报表设计视图中,若需要在报表每一页的顶部都打印出相关信息,则该信息应设置在（B）A 报表页眉B 页面页眉C 主体D 页面页脚11.如果要将查询结果作为一个新表添加到数据库中,应该使用(C)A 选择查询B 追加查询C 生成表查询D 更新查询12.在Access 中,一屏不能够同时显示表中多条记录的窗体类型属于(D )。

A 数据表B 数据透视图C 数据透视表D 纵栏式13.在数据库系统中，存取数据的基本单位是（B）A 记录B 数据项C 二进制位D 字节14.如果要设计一个报表,该报表将用于标识公司的资产设备,则应将该报表设计为(D)A 标签报表B 一般报表C 交叉报表D 数据透视图报表15.如果要将查询结果添加到一个指定的数据表中,应该使用(B)A 选择查询B 追加查询C 生成表查询D 更新查询16.由概念设计进入关系数据模型的逻辑设计时,必须被转换为对应基本表的联系类型是(C) A 1 对1B 1 对多C 多对多D 多对117.设两个关系中分别包含有 m 和n 个属性,它们具有同一个公共属性,当对它们进行自然连接时,运算结果的关系中包含的属性个数为(B)。

最小函数依赖最小函数依赖（MinimumFunctionalDependency，简称MFD）是记录和管理数据库关系中的一种技术。

它是指数据库中的属性之间的一种依赖关系，限定在一个表的单独属性中。

MFD提供了一种非常有用的方法，可用于在关系模式中定义函数依赖。

它有助于开发分布式数据库系统，以确保用户只能访问允许的属性数据，而不会暴露隐私信息。

在实际的数据库中，MFD在确保正确的记录一致性更新，避免重复的记录和提供正确的索引方面也起着重要的作用。

它可以帮助开发人员检查表中的属性之间的依赖关系，以便确保信息的安全和完整性。

MFD可以帮助检查表中的多个属性值之间的依赖关系，并将其简化为最小依赖关系，以便可以快速地查询和更新数据库中的相关信息。

MFD是一种分布式数据库系统中一种重要的技术，它可以确保数据库中包含的数据被正确地存储、检索和更新。

它通过将一个表中数据分割成一组具有相同属性的子表，从而限制每个属性的值而不影响另一个属性的值，从而最大限度地降低数据库的复杂度。

MFD可以用来提供数据库的可靠性和安全性，确保数据的有效性和准确性，以及保证数据库的质量。

MFD还用于检查带有多种属性的表中的依赖关系，以便查找和修复数据的错误。

另外，MFD可以帮助开发人员重新组合多张表，以组成一个复杂的关系模式。

MFD是一种有效的数据库管理技术，以及一种简单而可靠的安全技术，可以有效帮助用户管理大量的数据，从而保护涉及到的数据和信息的隐私。

MFD也可以帮助确保数据库中的属性值的一致性，从而有助于保护整个数据库免受不当的修改和损坏。

综上所述，最小函数依赖是一种强大的数据库管理技术，它可以为开发人员提供大量的优势，有助于检查数据库中多个属性之间的依赖关系，以及提高数据库中的安全性和保密性。

此外，它还可以帮助组织更好地管理和更新数据库中的信息，以达到最佳效果。