函数依赖的公理系统

关于函数依赖的公理系统

数据依赖的公理系统逻辑蕴含 定义:对于满足一组函数依赖F的关系模式R<U，F>，其任何一个关系r，若函数依赖X→Y都成立,

则称F逻辑蕴含X→Y第2页,共30页，2024年2月25日，星期天Armstrong公理系统从已知函数依赖集F要问X→Y是否为F逻辑蕴含，就要一套推理规则，由Armstrong在1974年提出。这套推理规则，是模式分解算法的理论基础。用途从一组函数依赖求得蕴含的函数依赖。求给定关系模式的码。第3页,共30页，2024年2月25日，星期天1.Armstrong公理系统

关系模式R<U，F>来说有以下的推理规则：Al.自反律（Reflexivity）：若Y

X

U，则X→Y为F所蕴含。A2.增广律（Augmentation）：若X→Y为F所蕴含，且Z

U，则XZ→YZ为F所蕴含。A3.传递律（Transitivity）：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含。

注意：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于F第4页,共30页，2024年2月25日，星期天定理Armstrong推理规则是正确的（l）自反律:若Y

X

U，则X→Y为F所蕴含证:设Y

X

U

对R<U，F>

的任一关系r中的任意两个元组t，s：若t[X]=s[X]，由于Y

X，有t[y]=s[y]，所以X→Y成立.自反律得证第5页,共30页，2024年2月25日，星期天定理Armstrong推理规则是正确的(2)增广律:若X→Y为F所蕴含，且Z

U，则XZ→YZ为F所蕴含。证：设X→Y为F所蕴含，且Z

U。设R<U，F>

的任一关系r中任意的两个元组t，s；若t[XZ]=s[XZ]，则有t[X]=s[X]和t[Z]=s[Z]；由X→Y，于是有t[Y]=s[Y]，所以t[YZ]=s[YZ]，所以XZ→YZ为F所蕴含.增广律得证。第6页,共30页，2024年2月25日，星期天定理Armstrong推理规则是正确的(3)传递律：若X→Y及Y→Z为F所蕴含，则

X→Z为F所蕴含。证：设X→Y及Y→Z为F所蕴含。对R<U，F>

的任一关系r中的任意两个元组t，s。若t[X]=s[X]，由于X→Y，有t[Y]=s[Y]；再由Y→Z，有t[Z]=s[Z]，所以X→Z为F所蕴含.传递律得证。第7页,共30页，2024年2月25日，星期天2.导出规则1.根据A1，A2，A3这三条推理规则可以得到下面三条推理规则：

合并规则：由X→Y，X→Z，有X→YZ。（A2，A3）

伪传递规则：由X→Y，WY→Z，有XW→Z。（A2，A3）

分解规则：由X→Y及Z

Y，有X→Z。（A1，A3）第8页,共30页，2024年2月25日，星期天导出规则2.根据合并规则和分解规则，可得引理1

引理:X→A1A2…Ak成立的充分必要条件是X→Ai成立（i=l，2，…，k）。第9页,共30页，2024年2月25日，星期天总结:函数依赖(FD)的推理规则函数依赖有一个正确的和完备的推理规则集——Armstrong推理规则：设有关系模式R(U)，X，Y，Z，W均是U的子集，F是R上只涉及到U中属性的函数依赖集，推理规则如下：(1)自反律：如果Y

X

U,则X→Y在R上成立。(2)增广律：如果X→Y为F所蕴涵，Z

U，则XZ→YZ在R上成立。

(XZ表示X∪Z，下同)(3)传递律：如果X→Y和Y→Z在R上成立，则X→Z在R上成立。(4)合并律：如果X→Y和X→Z成立，那么X→YZ成立。(5)伪传递律：如果X→Y和WY→Z成立，那么WX→Z成立。(6)分解律：如果X→YZ成立，那么X→Y,X→Z成立。引理：X→A1A2……Ak成立的充分必要条件是X→Ai(i=1,2……K）第10页,共30页，2024年2月25日，星期天函数依赖[例]关系模式R(A,B,C,G,H,I)，函数依赖集F={A

B,A

C,CG

H,CG

I,B

H}。我们可列出F中蕴含的几个依赖：由传递律可得A

H，因为A

B且B

H；由合并律可得CG

HI，因为CG

H，CG

I；由伪传递律可得AG

I，因为A

C且CG

I。还可以使用上述规则推导出更多的函数依赖，读者可自行推导。第11页,共30页，2024年2月25日，星期天3.函数依赖闭包定义:在关系模式R<U，F>中为F所逻辑蕴含的函数依赖的全体叫作F的闭包，记为F+。定义:设F为属性集U上的一组函数依赖，X

U，

XF+={A|X→A能由F根据Armstrong公理导出}，XF+称为属性集X关于函数依赖集F的闭包第12页,共30页，2024年2月25日，星期天关于闭包的引理引理:

设F为属性集U上的一组函数依赖，X，Y

U，X→Y能由F根据Armstrong公理导出的充分必要条件是Y

XF+用途将判定X→Y是否能由F根据Armstrong公理导出的问题，就转化为求出XF+

，判定Y是否为XF+的子集的问题(简单说，求逻辑蕴含只要通过求闭包就可以了。）第13页,共30页，2024年2月25日，星期天函数依赖闭包函数依赖的闭包F+是指被F逻辑蕴涵的函数依赖的全体构成的集合函数依赖推理规则的完备性

函数依赖推理规则系统(自反律、增广律和传递律)是完备的。

由推理规则的完备性可得到两个重要结论：

(1)属性集X+中的每个属性A，都有X→A被F逻辑蕴涵，即X+是所有由F逻辑蕴含X→A的属性A的集合。

(2)F+是所有利用Amstrong推理规则从F导出的函数依赖的集合第14页,共30页，2024年2月25日，星期天闭包的计算算法：求属性集X关于函数依赖F的闭包X+方法：计算x（i）（I=0,1,……）(1)x(0)=x;(2)x(i+1)=x(i)A其中A是这样的属性，在F中寻找尚未用过的左边是x(i)子集的函数依赖（3）判断是否有A：x(i+1)=x(i);B:若在x(i+1)已包含了F中的全部属性；C：x(i+1)≠x(i)，但x(i+1)的左部属性依赖已使用完出现A，B，C的一种即结束，否则转（2）第15页,共30页，2024年2月25日，星期天闭包的计算例：在关系模式R（U，F）中，U=ABCDEF={A→C，AC→B，B→D，C→E，EC→B}计算(EC)+。计算过程如下：

(1)x(0)=EC

(2)检查函数依赖，因EC→B，X(1)=EC∪B=ECB(3)检查函数依赖，因B→D，X(2)=ECB∪D=ECBD

（4）X(3)=X(2)，所以(EC)+=ECBD第16页,共30页，2024年2月25日，星期天

属性集闭包计算举例练习已知R<U,F>,U=

(A,B,C,G,H,I)，F={A

B,A

C,CG

H,CG

I,B

H}，计算(AG)+。算法第一次循环的执行步骤：

步骤

FD

closure

1．初值AG2．

A

BABG3．A

CABCG4．CG

HABCGH6．CG

IABCGHI6．B

HABCGHI

结果为closure=ABCGHI。(AG)+＝ABCGHI。（也就是说，AG可以决定右面的每一个属性）第17页,共30页，2024年2月25日，星期天计算属性集闭包的作用计算属性集闭包的作用可归纳如下：验证X

Y是否在F+中：看是否有Y

X+。判断X是否为R的超码：通过计算X+，看其是否包含R的所有属性。例如，(AG)+＝ABCGHI，则AG为R的超码。判断X是否为R的候选码：若X是超码，可检验X包含的所有子集的闭包是否包含R的所有属性。若不存在任何这样的属性子集，则X是R的候选码。第18页,共30页，2024年2月25日，星期天候选码的判断设有关系R({A1,A2,…,An},F)，F为R的函数依赖集，X为R的属性组，若X满足：1X→A1,A2,…,An，即X+={A1,A2,…,An}2不存在X的真子集Y，Y→A1,A2,…,An。则称X为R的码例：关系R{A,B,C,D}，有FD如下：F={AB→C,C→B,BC→D,ACD→B}，R的码为？AB+=ABCD,AC+=ABCD,ACD+=ABCD,候选码为：AB，ACD;还是AB,AC？还是其他？思考！！第19页,共30页，2024年2月25日，星期天

属性集闭包计算举例R=(U,F),其中,U={A,B,C,D},F={AB,ACD};求A+,B+,C+,AC+;求R的侯选码第20页,共30页，2024年2月25日，星期天

属性集闭包计算举例U={A,B,C,D};F={AB,ACD};A+=AB.C+=C.(AC)+=ABCD.ACBD显然，AC是候选码思考：哪些属性是L类？（只出现在函数依赖左边）哪些是R类？哪些是LR类？哪些是N类？它们与候选码有什么关系？第21页,共30页，2024年2月25日，星期天候选码的作用例题：已知R(X,Y,Z),F={XY→Z}，请问R为第几范式？（请思考：解题的思路是什么？）XY为候选码，R属于BCNF。练习：R(W,X,Y,Z),F={X→Z,WX→Y}，请问R为第几范式？第22页,共30页，2024年2月25日，星期天Armstrong公理系统的有效性与完备性Armstrong公理的完备性及有效性说明:“蕴含”==“导出”等价的概念

F+==由F出发借助Armstrong公理导出的函数依赖的集合第23页,共30页，2024年2月25日，星期天6.函数依赖集等价

定义:如果G+=F+，就说函数依赖集F覆盖G（F是G的覆盖，或G是F的覆盖），或F与G等价。第24页,共30页，2024年2月25日，星期天6.最小依赖集

定义：如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。

(1)F中任一函数依赖的右部仅含有一个属性。

(2)F中不存在这样的函数依赖X→A，使得F与

F-{X→A}等价。

(3)F中不存在这样的函数依赖X→A，X有真子集Z使得F-{X→A}∪{Z→A}与F等价。如果函数依赖集F和G等价，并且G是最小集，那么称G是F的一个最小覆盖。

第25页,共30页，2024年2月25日，星期天函数依赖集的等价和覆盖求最小函数依赖集的方法：应用分解规则，使F中每一个依赖的右部单一化。去掉各函数依赖左部多余的属性。方法：检查F中左边是非单属性的依赖，如：XY→A，要判定Y是否多余，只要求X闭包，若X闭包A，则Y是多余的，以X→Y代替XY→A。去掉多余的依赖。方法：从第一个依赖开始，若要从F中去掉X→Y，则在剩下的依赖中求X闭包，若X闭包包含Y,则去掉X→Y第26页,共30页，2024年2月25日，星期天最小依赖集