《函数依赖公理体系》PPT课件.ppt

《《函数依赖公理体系》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《函数依赖公理体系》PPT课件.ppt（32页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第2讲讲 函数依赖的公理体系函数依赖的公理体系第第第第5 5章章章章 关系数据库模式设计关系数据库模式设计关系数据库模式设计关系数据库模式设计主要内容主要内容主要内容主要内容n nn阿姆斯特朗公理及推论阿姆斯特朗公理及推论阿姆斯特朗公理及推论阿姆斯特朗公理及推论n nnX X关于关于关于关于F F的闭包及其计算的闭包及其计算的闭包及其计算的闭包及其计算n nn最小函数依赖集最小函数依赖集最小函数依赖集最小函数依赖集n nn候选键的求解方法候选键的求解方法候选键的求解方法候选键的求解方法一、阿姆斯特朗公理及推论一、阿姆斯特朗公理及推论一、阿姆斯特朗公理及推论一、阿姆斯特朗公理及推论一、阿姆斯特

2、朗公理及推论一、阿姆斯特朗公理及推论是一系列推理规则是一系列推理规则是一系列推理规则是一系列推理规则是一系列推理规则是一系列推理规则最早出现在最早出现在最早出现在最早出现在最早出现在最早出现在197419741974197419741974年年年年年年的论文里的论文里的论文里的论文里的论文里的论文里他人与他人与他人与他人与他人与他人与197719771977197719771977年提出改进形式年提出改进形式年提出改进形式年提出改进形式年提出改进形式年提出改进形式F F F F =XY=XY=XY=XYF F F F+侯选键侯选键XYXY在在R中是否成立中是否成立能从能从能从能从F F F F

3、导出的所有导出的所有导出的所有导出的所有XYXYXYXY推导工具？推导工具？推导工具？推导工具？问题引入：问题引入：问题引入：问题引入：1 1 1 1 1 1、阿姆斯特朗阿姆斯特朗阿姆斯特朗阿姆斯特朗阿姆斯特朗阿姆斯特朗公理公理公理公理公理公理 设设设设设设有有有有有有关关关关关关系系系系系系模模模模模模式式式式式式R(U,F)R(U,F)R(U,F)R(U,F)R(U,F)R(U,F)，U=AU=AU=AU=AU=AU=A1 1 1 11 1,A,A,A,A,A,A2 2 2 22 2,A,A,A,A,A,An n n nn n 是是是是是是R R R R R R的的的的的的属属属属属属性性

4、性性性性集集集集集集，F F F F F F是是是是是是R R R R R R的的的的的的属属属属属属性性性性性性集集集集集集U U U U U U上上上上上上的的的的的的FDFDFDFDFDFD集集集集集集，X X X X X X、Y Y Y Y Y Y、Z Z Z Z Z Z、W W W W W W是是是是是是U U U U U U的子集。的子集。的子集。的子集。的子集。的子集。阿姆斯特朗阿姆斯特朗阿姆斯特朗阿姆斯特朗阿姆斯特朗阿姆斯特朗公理为：公理为：公理为：公理为：公理为：公理为：A1 A1 A1 A1 A1 A1 自反律自反律自反律自反律自反律自反律：若：若：若：若：若：若Y Y Y

5、 Y Y Y X X X X X X，则则则则则则X X X X X XY Y Y Y Y Y A2 A2 A2 A2 A2 A2 增广律增广律增广律增广律增广律增广律：若：若：若：若：若：若X X X X X XY Y Y Y Y Y，则则则则则则XZXZXZXZXZXZYZYZYZYZYZYZ A3 A3 A3 A3 A3 A3 传递传递传递传递传递传递律律律律律律：若：若：若：若：若：若X X X X X XY,YY,YY,YY,YY,YY,YZ Z Z Z Z Z，则则则则则则X X X X X XZ Z Z Z Z Z ArmstrongArmstrongArmstrongArmst

6、rongArmstrongArmstrong公理是正确的。公理是正确的。公理是正确的。公理是正确的。公理是正确的。公理是正确的。方法方法方法方法方法方法：从函数依从函数依从函数依从函数依从函数依从函数依赖赖赖赖赖赖的定的定的定的定的定的定义义义义义义出出出出出出发发发发发发 A1 A1 A1 A1 A1 A1 自反律自反律自反律自反律自反律自反律：若若若若若若Y Y Y Y Y Y X X X X X X，则则则则则则X X X X X XY Y Y Y Y Y证：证：证：证：证：证：设设设设设设u u u u u u、v v v v v v为为为为为为r r r r r r的任意两个元组。的

7、任意两个元组。的任意两个元组。的任意两个元组。的任意两个元组。的任意两个元组。若若若若若若uX=vXuX=vXuX=vXuX=vXuX=vXuX=vX，则，则，则，则，则，则u u u u u u和和和和和和v v v v v v在在在在在在X X X X X X的任何子集上必然的任何子集上必然的任何子集上必然的任何子集上必然的任何子集上必然的任何子集上必然相等。相等。相等。相等。相等。相等。由条件由条件由条件由条件由条件由条件Y Y Y Y Y Y X X X X X X ，所以有：，所以有：，所以有：，所以有：，所以有：，所以有：uY=vYuY=vYuY=vYuY=vYuY=vYuY=vY

8、，由由由由由由u u u u u u、v v v v v v的任意性，并根据函数依赖的定义，的任意性，并根据函数依赖的定义，的任意性，并根据函数依赖的定义，的任意性，并根据函数依赖的定义，的任意性，并根据函数依赖的定义，的任意性，并根据函数依赖的定义，可得可得可得可得可得可得 X X X X X XY Y Y Y Y Y。2 2 2 2 2 2、3 3 3 3 3 3、阿姆斯特朗阿姆斯特朗阿姆斯特朗阿姆斯特朗阿姆斯特朗阿姆斯特朗公理的推论公理的推论公理的推论公理的推论公理的推论公理的推论 合并合并合并合并合并合并规则规则规则规则规则规则：若：若：若：若：若：若X X X X X XY Y Y

9、Y Y Y且且且且且且X X X X X XZ Z Z Z Z Z，则则则则则则X X X X X XYZYZYZYZYZYZ 分解分解分解分解分解分解规则规则规则规则规则规则：若：若：若：若：若：若X X X X X XY Y Y Y Y Y，且，且，且，且，且，且Z Z Z Z Z Z Y Y Y Y Y Y，则则则则则则X X X X X XZ Z Z Z Z Z 伪传递规则伪传递规则伪传递规则伪传递规则伪传递规则伪传递规则：若：若：若：若：若：若X X X X X XY Y Y Y Y Y且且且且且且WYWYWYWYWYWYZ Z Z Z Z Z，则则则则则则WXWXWXWXWXWXZ

10、 Z Z Z Z Z增广律增广律增广律增广律传递律传递律传递律传递律证：证：证：证：X X X XY Y Y YWXZWXZWXZWXZWXWYWXWYWXWYWXWYWYZWYZWYZWYZ作作作作用用用用：将将将将一一一一个个个个FDFDFDFD分分分分解解解解成成成成若若若若干干干干个个个个右右右右边边边边是是是是单单单单属属属属性性性性的的的的FDFDFDFD。用于确定关系的主键。用于确定关系的主键。用于确定关系的主键。用于确定关系的主键。4 4 4 4 4 4、定理定理定理定理定理定理 如果如果如果如果如果如果A A A A A Ai i i ii i(i=1,n)(i=1,n)(i

11、=1,n)(i=1,n)(i=1,n)(i=1,n)是关系模式是关系模式是关系模式是关系模式是关系模式是关系模式R R R R R R的属性的属性的属性的属性的属性的属性,则则则则则则X X X X X XA A A A A A1 1 1 11 1A A A A A A2 2 2 22 2AAAAAAn n n nn n成立的充分必要条件是成立的充分必要条件是成立的充分必要条件是成立的充分必要条件是成立的充分必要条件是成立的充分必要条件是X X X X X XA A A A A Ai i i ii i(i=(i=(i=(i=(i=(i=1,n)1,n)1,n)1,n)1,n)1,n)均成立。均

12、成立。均成立。均成立。均成立。均成立。二、二、二、二、二、二、X X X关于关于关于关于关于关于F F F的闭包及其计算的闭包及其计算的闭包及其计算的闭包及其计算的闭包及其计算的闭包及其计算 例例例例例例：已已已已已已知知知知知知关关关关关关系系系系系系模模模模模模式式式式式式R(A,B,C)R(A,B,C)R(A,B,C)R(A,B,C)R(A,B,C)R(A,B,C)，其其其其其其函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖集集集集集集为为为为为为F=ABF=ABF=ABF=ABF=ABF=AB，BCBCBCBCBCBC，求函数依，求函数依，求函数依，求函数依，求函数依，求函数依赖赖赖

13、赖赖赖集集集集集集F F F F F F的的的的的的闭闭闭闭闭闭包包包包包包F F F F F F+。F+=A ，AB ，AC ，ABC ，B ，C A A，AB A，AC A，ABC A，B B，C CA B，AB B，AC B，ABC B，B C，A C，AB C，AC C，ABC C，B BC，A AB，AB AB，AC AB，ABC AB，BC ，A AC，AB AC，AC AC，ABC AC，BC B，A BC，AB BC，AC BC，ABC BC，BC C，A ABC，AB ABC，AC ABC，ABC ABC，BC BC，1 1 1、X X X关于关于关于关于关于关于F F F的

14、闭包的闭包的闭包的闭包的闭包的闭包 设设设设设设 有有有有有有 关关关关关关 系系系系系系 模模模模模模 式式式式式式 R(U,F)R(U,F)R(U,F)R(U,F)R(U,F)R(U,F)和和和和和和 属属属属属属 性性性性性性 集集集集集集U=AU=AU=AU=AU=AU=A1 1 1 11 1,A,A,A,A,A,A2 2 2 22 2,A,A,A,A,A,An n n nn n 的的的的的的子子子子子子集集集集集集X X X X X X。则则则则则则称称称称称称所所所所所所有有有有有有用用用用用用阿阿阿阿阿阿姆姆姆姆姆姆斯斯斯斯斯斯特特特特特特朗朗朗朗朗朗公公公公公公理理理理理理从从

15、从从从从F F F F F F推推推推推推导导导导导导出出出出出出的的的的的的函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖X X X X X XAAAAAAi i i ii i的的的的的的属属属属属属性性性性性性A A A A A Ai i i ii i组组组组组组成成成成成成的的的的的的集集集集集集合合合合合合称称称称称称为为为为为为X X X X X X关关关关关关于于于于于于F F F F F F的的的的的的闭闭闭闭闭闭包包包包包包，记记记记记记为为为为为为X X X X X XF F F FF F+，通通通通通通常常常常常常简简简简简简记记记记记记为为为为为为X X X X X X

16、+。即即即即即即 X X X X X XF F F FF F+=A=A=A=A=A=Ai i i ii i|用公理从用公理从用公理从用公理从用公理从用公理从F F F F F F推出的推出的推出的推出的推出的推出的X X X X X XAAAAAAi i i ii i 集合元素集合元素集合元素集合元素对比对比F F F F+和和和和X X X X+设设设设设设有有有有有有关关关关关关系系系系系系模模模模模模式式式式式式R(UR(UR(UR(UR(UR(U，F)F)F)F)F)F)，U=AU=AU=AU=AU=AU=A1 1 1 11 1,A,A,A,A,A,A2 2 2 22 2,A,A,A,

17、A,A,An n n nn n 是是是是是是R R R R R R的的的的的的属属属属属属性性性性性性集集集集集集，F F F F F F是是是是是是R R R R R R的的的的的的属属属属属属性性性性性性集集集集集集U U U U U U上上上上上上的的的的的的函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖集集集集集集，X X X X X X、Y Y Y Y Y Y是是是是是是U U U U U U的子集，的子集，的子集，的子集，的子集，的子集，则则则则则则 X X X X X XY Y Y Y Y Y能用能用能用能用能用能用ArmstrongArmstrongArmstrongArms

18、trongArmstrongArmstrong公理从公理从公理从公理从公理从公理从F F F F F F导导导导导导出出出出出出Y Y Y Y Y Y X X X X X X。该该该该定定定定理理理理把把把把判判判判定定定定X X X XY Y Y Y是是是是否否否否能能能能由由由由F F F F根根根根据据据据ArmstrongArmstrongArmstrongArmstrong公理导出的问题公理导出的问题公理导出的问题公理导出的问题求出求出求出求出X X X X，判定，判定，判定，判定Y Y Y Y是否为是否为是否为是否为X X X X的子集的问题。的子集的问题。的子集的问题。的子集的问

19、题。2 2 2 2 2 2、定理定理定理定理定理定理算法算法算法算法算法算法 求属性集求属性集求属性集求属性集求属性集求属性集X X X X X X关于函数依关于函数依关于函数依关于函数依关于函数依关于函数依赖赖赖赖赖赖集集集集集集F F F F F F的的的的的的闭闭闭闭闭闭包包包包包包X X X X X X输输输输输输入：入：入：入：入：入：关关关关关关系系系系系系模模模模模模式式式式式式R R R R R R的的的的的的全全全全全全部部部部部部属属属属属属性性性性性性集集集集集集U,UU,UU,UU,UU,UU,U上上上上上上的的的的的的函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖集

20、集集集集集F F F F F F，U U U U U U的子集的子集的子集的子集的子集的子集X X X X X X。输输输输输输出：出：出：出：出：出：X X X X X X关于关于关于关于关于关于F F F F F F的的的的的的闭闭闭闭闭闭包包包包包包X X X X X X。计计计计计计算方法：算方法：算方法：算方法：算方法：算方法：3 3 3、X X X关于关于关于关于关于关于F F F的闭包的闭包的闭包的闭包的闭包的闭包X X X的的的的的的计算计算计算计算计算计算（1 1 1 1 1 1）X X X X X X(0)(0)(0)(0)(0)(0)=X=X=X=X=X=X。（2 2 2

21、 2 2 2）从从从从从从F F F F F F中中中中中中找找找找找找出出出出出出满满满满满满足足足足足足条条条条条条件件件件件件V V V V V V X X X X X X(i)(i)(i)(i)(i)(i)的的的的的的所所所所所所有有有有有有函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖VWVWVWVWVWVW，并并并并并并把把把把把把所所所所所所有有有有有有的的的的的的VWVWVWVWVWVW中中中中中中的的的的的的属属属属属属性性性性性性W W W W W W组组组组组组成成成成成成的的的的的的集集集集集集合合合合合合记记记记记记为为为为为为Z Z Z Z Z Z；也也也也也也即

22、即即即即即从从从从从从F F F F F F中中中中中中找找找找找找出出出出出出那那那那那那些些些些些些其其其其其其决决决决决决定定定定定定因因因因因因素素素素素素是是是是是是X X X X X X(i)(i)(i)(i)(i)(i)的的的的的的子子子子子子集集集集集集的的的的的的函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖，并并并并并并把把把把把把由由由由由由所所所所所所有有有有有有这这这这这这样样样样样样的的的的的的依依依依依依赖赖赖赖赖赖的的的的的的被被被被被被决决决决决决定定定定定定因素组成的集合记为因素组成的集合记为因素组成的集合记为因素组成的集合记为因素组成的集合记为因素组成的

23、集合记为Z Z Z Z Z Z。（3 3 3 3 3 3）若）若）若）若）若）若Z Z Z Z Z Z X X X X X X(i)(i)(i)(i)(i)(i)，则转（，则转（，则转（，则转（，则转（，则转（5 5 5 5 5 5）。）。）。）。）。）。（4 4 4 4 4 4）否则，）否则，）否则，）否则，）否则，）否则，X X X X X X(i+1)(i+1)(i+1)(i+1)(i+1)(i+1)=X=X=X=X=X=X(i)(i)(i)(i)(i)(i)Z Z Z Z Z Z，并转（，并转（，并转（，并转（，并转（，并转（2 2 2 2 2 2）。）。）。）。）。）。（5 5 5

24、5 5 5）停止计算，输出）停止计算，输出）停止计算，输出）停止计算，输出）停止计算，输出）停止计算，输出X X X X X X(i)(i)(i)(i)(i)(i)，即为，即为，即为，即为，即为，即为X X X X X X+。3 3、X X关于关于关于关于F F的闭包的闭包的闭包的闭包X X的计算（续）的计算（续）的计算（续）的计算（续）例例例例例例5.4 5.4 5.4 5.4 5.4 5.4 已知已知已知已知已知已知R(U),U=A,B,C,D,E,GR(U),U=A,B,C,D,E,GR(U),U=A,B,C,D,E,GR(U),U=A,B,C,D,E,GR(U),U=A,B,C,D,E

25、,GR(U),U=A,B,C,D,E,G，R R R R R R上的上的上的上的上的上的FDFDFDFDFDFD集集集集集集 F=ABC,CA,BCD,ACDB F=ABC,CA,BCD,ACDB F=ABC,CA,BCD,ACDB F=ABC,CA,BCD,ACDB F=ABC,CA,BCD,ACDB F=ABC,CA,BCD,ACDB，DEG,BEC,DEG,BEC,DEG,BEC,DEG,BEC,DEG,BEC,DEG,BEC,CGBD,CEAG CGBD,CEAG CGBD,CEAG CGBD,CEAG CGBD,CEAG CGBD,CEAG，X=BD X=BD X=BD X=BD X

26、=BD X=BD，求，求，求，求，求，求X X X X X X，BDABDABDABDABDABDA是否成立？是否成立？是否成立？是否成立？是否成立？是否成立？(1)X(1)X(1)X(1)X(1)X(1)X（0 0 0 00 0）=BD=BD=BD=BD=BD=BD。(2)X(2)X(2)X(2)X(2)X(2)X（1 1 1 11 1）=BDEG=BDEG=BDEG=BDEG=BDEG=BDEG(3)X(3)X(3)X(3)X(3)X(3)X（2 2 2 22 2）=BCDEG=BCDEG=BCDEG=BCDEG=BCDEG=BCDEG(4)X(4)X(4)X(4)X(4)X(4)X（3

27、3 3 33 3）=ABCDEG=ABCDEG=ABCDEG=ABCDEG=ABCDEG=ABCDEGX X=ABCDEG=ABCDEGABDABD，故，故BDABDA成立成立4 4 4、举例、举例、举例、举例、举例、举例Z=EG BD=X(0)一一一一一一个个个个个个函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖集集集集集集F F F F F F的的的的的的闭闭闭闭闭闭包包包包包包F F F F F F通通通通通通常常常常常常包包包包包包含含含含含含很很很很很很多多多多多多函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖，有有有有有有些些些些些些函函函函函函数数数数数数依依依依依依赖赖赖赖

28、赖赖是是是是是是无无无无无无意意意意意意义义义义义义的的的的的的，如如如如如如平平平平平平凡凡凡凡凡凡的的的的的的函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖，还还还还还还有有有有有有一一一一一一些些些些些些是是是是是是可可可可可可以以以以以以推推推推推推导导导导导导出出出出出出的的的的的的，即即即即即即无无无无无无关关关关关关的的的的的的函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖。如如如如如如果果果果果果将将将将将将每每每每每每一一一一一一个个个个个个函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖看看看看看看作作作作作作是是是是是是对对对对对对关关关关关关系系系系系系的的的的的的

29、一一一一一一个个个个个个约约约约约约束束束束束束，要要要要要要检检检检检检查查查查查查F F F F F F中中中中中中的的的的的的每每每每每每一一一一一一个个个个个个函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖对对对对对对应应应应应应的的的的的的约约约约约约束束束束束束，显显显显显显然然然然然然是是是是是是一一一一一一件件件件件件很很很很很很繁繁繁繁繁繁重重重重重重的的的的的的任任任任任任务务务务务务。如如如如如如果果果果果果能能能能能能找找找找找找出出出出出出一一一一一一个个个个个个与与与与与与F F F F F F等等等等等等价价价价价价的的的的的的、包包包包包包含含含含含含较较较较

30、较较少少少少少少数数数数数数目目目目目目函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖的的的的的的函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖集集集集集集G G G G G G，则则则则则则可可可可可可以以以以以以简简简简简简化化化化化化此此此此此此工工工工工工作作作作作作。最最最最最最小小小小小小函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖集集集集集集的概念由此而提出。的概念由此而提出。的概念由此而提出。的概念由此而提出。的概念由此而提出。的概念由此而提出。三、最小函数依赖集三、最小函数依赖集三、最小函数依赖集三、最小函数依赖集三、最小函数依赖集三、最小函数依赖集 定义定义定义定义

31、定义定义 设设设设设设F F F F F F和和和和和和G G G G G G是是是是是是两两两两两两个个个个个个函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖集集集集集集，如如如如如如果果果果果果F F F F F FG G G G G G，则则则则则则称称称称称称F F F F F F和和和和和和G G G G G G等等等等等等价价价价价价。如如如如如如果果果果果果F F F F F F和和和和和和G G G G G G等等等等等等价价价价价价，则则则则则则称称称称称称F F F F F F覆覆覆覆覆覆盖盖盖盖盖盖G G G G G G，同同同同同同时时时时时时也称也称也称也称也称也称

32、G G G G G G覆盖覆盖覆盖覆盖覆盖覆盖F F F F F F。1 1 1 1 1 1、函数依赖集的等价与覆盖函数依赖集的等价与覆盖函数依赖集的等价与覆盖函数依赖集的等价与覆盖函数依赖集的等价与覆盖函数依赖集的等价与覆盖定理定理定理定理定理定理 F F F F F FG G G G G G的充要条件是的充要条件是的充要条件是的充要条件是的充要条件是的充要条件是F F F F F F G G G G G G和和和和和和G G G G G G F F F F F F。F F F F=G G G GF F F FG G G GX X X XY Y Y Y所所所所有有有有 F F G Guu定理

33、定理定理定理定理定理G G F FX X X XY Y Y Y能否由能否由能否由能否由G G G G根据公理导出？根据公理导出？根据公理导出？根据公理导出？Y Y X XGG+？作作作作用用用用：任任任任一一一一函函函函数数数数依依依依赖赖赖赖集集集集都都都都可可可可转转转转化化化化成成成成由由由由右右右右端端端端只只只只有单一属性的依赖组成的集合。有单一属性的依赖组成的集合。有单一属性的依赖组成的集合。有单一属性的依赖组成的集合。该结论是最小函数依赖集的基础。该结论是最小函数依赖集的基础。该结论是最小函数依赖集的基础。该结论是最小函数依赖集的基础。uu推论推论推论推论推论推论 每每每每每每一

34、一一一一一个个个个个个函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖集集集集集集F F F F F F都都都都都都被被被被被被其其其其其其右右右右右右端端端端端端只只只只只只有有有有有有一一一一一一个个个个个个属属属属属属性性性性性性的函数依的函数依的函数依的函数依的函数依的函数依赖组赖组赖组赖组赖组赖组成的依成的依成的依成的依成的依成的依赖赖赖赖赖赖集集集集集集G G G G G G所覆盖。所覆盖。所覆盖。所覆盖。所覆盖。所覆盖。满满满满满满足足足足足足下下下下下下列列列列列列条条条条条条件件件件件件的的的的的的函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖集集集集集集F F F F F

35、 F称称称称称称为为为为为为最最最最最最小小小小小小函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖集。集。集。集。集。集。F F F F F F中每一个中每一个中每一个中每一个中每一个中每一个FDFDFDFDFDFD的右端都是的右端都是的右端都是的右端都是的右端都是的右端都是单单单单单单个属性；个属性；个属性；个属性；个属性；个属性；对对对对对对F F F F F F中任何中任何中任何中任何中任何中任何FD:XFD:XFD:XFD:XFD:XFD:XA A A A A A，F-XF-XF-XF-XF-XF-XAAAAAA不等价于不等价于不等价于不等价于不等价于不等价于F F F F F F；

36、对对对对对对F F F F F F中的任何中的任何中的任何中的任何中的任何中的任何FD:XFD:XFD:XFD:XFD:XFD:XA A A A A A和和和和和和X X X X X X的任何真子集的任何真子集的任何真子集的任何真子集的任何真子集的任何真子集Z Z Z Z Z Z，(F-X (F-X (F-X (F-X (F-X (F-XA)ZA)ZA)ZA)ZA)ZA)ZAAAAAA不等价于不等价于不等价于不等价于不等价于不等价于F F F F F F。2 2 2 2 2 2、最小函数依赖集、最小函数依赖集、最小函数依赖集、最小函数依赖集、最小函数依赖集、最小函数依赖集F F F F没有多余

37、的没有多余的没有多余的没有多余的FDFDFDFD每个每个每个每个FDFDFDFD左端无多余的属性左端无多余的属性左端无多余的属性左端无多余的属性uu求解方法求解方法求解方法求解方法求解方法求解方法（1 1 1 1 1 1）用用用用用用分分分分分分解解解解解解规规规规规规则则则则则则将将将将将将F F F F F F中中中中中中的的的的的的所所所所所所有有有有有有函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖分分分分分分解解解解解解成成成成成成右右右右右右端端端端端端为单为单为单为单为单为单个属性的函数依个属性的函数依个属性的函数依个属性的函数依个属性的函数依个属性的函数依赖赖赖赖赖赖；Arm

38、strongArmstrongArmstrongArmstrong公理的推论公理的推论公理的推论公理的推论分解规则：分解规则：分解规则：分解规则：若若若若X X X XY Y Y Y，且，且，且，且Z Z Z Z Y Y Y Y，则，则，则，则X X X XZ Z Z Zuu求解方法（求解方法（求解方法（求解方法（求解方法（求解方法（续续续续续续一）一）一）一）一）一）（2 2 2 2）去掉）去掉）去掉）去掉F F F F中冗余的函数依中冗余的函数依中冗余的函数依中冗余的函数依赖赖赖赖 对于对于对于对于对于对于F F F F F F中任一中任一中任一中任一中任一中任一FDFDFDFDFDFD：

39、X X X X X XY Y Y Y Y Y G=F-X G=F-X G=F-X G=F-X G=F-X G=F-XYYYYYY；求求求求求求X X X X X X关于关于关于关于关于关于G G G G G G的闭包的闭包的闭包的闭包的闭包的闭包X X XG GG+；看看看看看看X X X X X XG G G GG G+是是是是是是否否否否否否包包包包包包含含含含含含Y Y Y Y Y Y。如如如如如如果果果果果果X X X X X XG G G GG G+包包包包包包含含含含含含Y Y Y Y Y Y，则则则则则则在在在在在在G G G G G G中中中中中中逻逻逻逻逻逻辑辑辑辑辑辑蕴蕴蕴

40、蕴蕴蕴涵涵涵涵涵涵X X X X X XY Y Y Y Y Y，说说说说说说明明明明明明X X X X X XY Y Y Y Y Y是是是是是是多多多多多多余余余余余余的的的的的的函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖，所所所所所所以以以以以以F=GF=GF=GF=GF=GF=G；如果；如果；如果；如果；如果；如果X X X X X X+不包含不包含不包含不包含不包含不包含Y Y Y Y Y Y，则保留，则保留，则保留，则保留，则保留，则保留X X X X X XY Y Y Y Y Y。uu求解方法求解方法求解方法求解方法求解方法求解方法（续二）（续二）（续二）（续二）（续二）（续二

41、）（3 3 3 3）去掉左端多余的属性）去掉左端多余的属性）去掉左端多余的属性）去掉左端多余的属性 对对对对对对于于于于于于F F F F F F中中中中中中左左左左左左端端端端端端是是是是是是非非非非非非单单单单单单属属属属属属性性性性性性的的的的的的函函函函函函数数数数数数依依依依依依赖赖赖赖赖赖（XYXYXYXYXYXYA A A A A A），假设要判断假设要判断假设要判断假设要判断假设要判断假设要判断Y Y Y Y Y Y是否是多余的属性是否是多余的属性是否是多余的属性是否是多余的属性是否是多余的属性是否是多余的属性 G=(F-XY G=(F-XY G=(F-XY G=(F-XY G

42、=(F-XY G=(F-XYA)XA)XA)XA)XA)XA)XAAAAAA；求求求求求求X X X X X X关于关于关于关于关于关于F F F F F F的闭包的闭包的闭包的闭包的闭包的闭包X X XF FF+；如如如如如如果果果果果果A A A A A A不不不不不不属属属属属属于于于于于于X X X X X XF F F FF F+，则则则则则则X X X X X XA A A A A A不不不不不不在在在在在在F F F F F F+中中中中中中，说说说说说说明明明明明明Y Y Y Y Y Y不不不不不不是是是是是是多多多多多多余余余余余余的的的的的的属属属属属属性性性性性性，接接接

43、接接接着着着着着着判判判判判判别别别别别别X X X X X X是是是是是是否否否否否否是是是是是是多多多多多多余余余余余余的的的的的的属属属属属属性性性性性性；如果如果如果如果如果如果A A A A A A属于属于属于属于属于属于X X X X X XF F F FF F+，则说明，则说明，则说明，则说明，则说明，则说明Y Y Y Y Y Y是多余的属性，是多余的属性，是多余的属性，是多余的属性，是多余的属性，是多余的属性，F=GF=GF=GF=GF=GF=G。ABABABABC C C C，C C C CA A A A，BCBCBCBCD D D D，ACDACDACDACDB B B B

44、，D D D DEGEGEGEG，BEBEBEBEC C C C，CGCGCGCGBDBDBDBD，CECECECEAGAGAGAGF=F=F=F=ABABABABC C C C，C C C CA A A A，BCBCBCBCD D D D，ACDACDACDACDB,B,B,B,D D D DE,DE,DE,DE,DG G G G，BEBEBEBEC C C C，CGCGCGCGB B B B，CGCGCGCGD D D D，CECECECEA,CEA,CEA,CEA,CEG G G G F F F F1 1 1 1=例例例例例例：求函数依：求函数依：求函数依：求函数依：求函数依：求函数依赖

45、赖赖赖赖赖集集集集集集F F F F F F的最小函数依的最小函数依的最小函数依的最小函数依的最小函数依的最小函数依赖赖赖赖赖赖集集集集集集法法法法法法1 1 1 1 1 1：3 3 3、举例、举例、举例、举例、举例、举例 F F F F21212121=ABABABABC C C C，C C C CA A A A，BCBCBCBCD D D D，ACDACDACDACDB,B,B,B,D D D DE,DE,DE,DE,DG G G G，BEBEBEBEC C C C，CGCGCGCGB B B B，CGCGCGCGD D D D，CECECECEA,CEA,CEA,CEA,CEG G G

46、G F F F F1 1 1 1=ABABABABC C C C，C C C CA A A A，BCBCBCBCD D D D，ACDACDACDACDB B B B，D D D DE E E E，D D D DG G G G，BEBEBEBEC C C C，CGCGCGCGD D D D，CECECECEA,CEA,CEA,CEA,CEG G G G3 3 3、举例（续一）、举例（续一）、举例（续一）、举例（续一）、举例（续一）、举例（续一）例例例例例例：求函数依：求函数依：求函数依：求函数依：求函数依：求函数依赖赖赖赖赖赖集集集集集集F F F F F F的最小函数依的最小函数依的最小函数

47、依的最小函数依的最小函数依的最小函数依赖赖赖赖赖赖集集集集集集 F F F F22222222=ABABABABC C C C，C C C CA A A A，BCBCBCBCD D D D，ACDACDACDACDB,B,B,B,D D D DE,DE,DE,DE,DG G G G，BEBEBEBEC C C C，CGCGCGCGD D D D，CECECECEA,CEA,CEA,CEA,CEG G G G F F F F21212121=ABABABABC C C C，C C C CA A A A，BCBCBCBCD D D D，ACDACDACDACDB B B B，D D D DE E

48、E E，D D D DG G G G，BEBEBEBEC C C C，CGCGCGCGD D D D，CECECECEG G G G3 3 3、举例（续二）、举例（续二）、举例（续二）、举例（续二）、举例（续二）、举例（续二）例例例例例例：求函数依：求函数依：求函数依：求函数依：求函数依：求函数依赖赖赖赖赖赖集集集集集集F F F F F F的最小函数依的最小函数依的最小函数依的最小函数依的最小函数依的最小函数依赖赖赖赖赖赖集集集集集集ABABABABC C C C，C C C CA A A A，BCBCBCBCD D D D，ACDACDACDACDB B B B，D D D DE E E

49、E，D D D DG G G G，BEBEBEBEC C C C，CGCGCGCGD D D D，CECECECEG G G G F F F F22222222=F F F F3 3 3 3=ABABABABC C C C，C C C CA A A A，BCBCBCBCD D D D，CDCDCDCDB B B B，D D D DE E E E，D D D DG G G G，BEBEBEBEC C C C，CGCGCGCGD D D D，CECECECEG G G G3 3 3、举例（续三）、举例（续三）、举例（续三）、举例（续三）、举例（续三）、举例（续三）例例例例例例：求函数依：求函数依：

50、求函数依：求函数依：求函数依：求函数依赖赖赖赖赖赖集集集集集集F F F F F F的最小函数依的最小函数依的最小函数依的最小函数依的最小函数依的最小函数依赖赖赖赖赖赖集集集集集集 F F F F21212121=ABABABABC C C C，C C C CA A A A，BCBCBCBCD D D D，D D D DE E E E，D D D DG G G G，BEBEBEBEC C C C，CGCGCGCGB B B B，CECECECEG G G GABABABABC C C C，C C C CA A A A，BCBCBCBCD D D D，ACDACDACDACDB,B,B,B,D