函数依赖推理资料

《函数依赖推理资料》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.2.3函数依赖公理系统1974年W.W.Armstrong首先提出了函数依赖的公理系统，称为Armstrong公理。对于一组已知的函数依赖，利用该公理可导出所蕴函的函数依赖。对于关系模式R(U,F)，为了确定一个关系模式的码，为了从一组函数依赖求得蕴含的函数依赖，我们需要从现有的函数依赖集合F下推导或者至少需要判断函数依赖X→Y是否为F所蕴含。为此，我们需要一套推理规则。这样的推理规则，在1974年由Armstrong首先提出来，称为Armstrong公理(Armstrong'saxioms)系统。在介绍Armstrong公理系

2、统之前，我们先给出逻辑蕴含和F的闭包的概念。1.逻辑蕴含给定一个关系模式，只考虑给定的函数依赖是不够的，必须找出在该关系模式上成立的其他函数依赖。逻辑蕴含：设F是关系模式R（U）的函数依赖集合，由F出发，可以证明其他某些函数依赖也成立，我们称这些函数依赖被F逻辑蕴含。例如，设F={A→B，B→C}，则函数依赖A→C被F逻辑蕴含，记作：F

3、=A→C。即函数依赖集F逻辑蕴含函数依赖A→C。2.F的闭包F+　　对于一个关系模式，如何由已知的函数依赖集合F，找出F逻辑蕴涵的所有函数依赖集合呢？这就是我们下面要讨论的问题。F的闭包F+：设F为

4、一个函数依赖集，F的闭包是指F逻辑蕴涵的所有函数依赖集合。F的闭包记作F+。例如，给定关系模式R(A,B,C,G,H,I)，函数依赖集合F={A→B，A→C，CG→H，CG→I，B→H}。可以证明函数依赖A→H被F逻辑蕴涵。设有元组s和t，满足s[A]=t[A]，根据函数依赖的定义，由已知的A→B，可以推出s[B]=t[B]。又根据函数依赖B→H，可以有s[H]=t[H]。因此，已经证明对任意的两个元组s和t，只要有s[A]=t[A]，就有s[H]=t[H]。所以，函数依赖A→H被F逻辑蕴涵。计算F的闭包F+，可以由函数依赖的定义直

5、接计算，如上面的示例。但是，当F很大时，计算的过程会很长。为了从已知的函数依赖推导出其它函数依赖，Armstrong提出了一套推理规则，称为Armstrong公理，通过反复使用这些规则，可以找出给定F的闭包F+。其推理规则可归结为如下3条：自反律(reflexivity)、增广律(augmentation)和传递律(transitivity)。3．Armstrong公理设U为属性总体集合，F为U上的一组函数依赖，对于关系模式R（U，F），X、Y、Z为属性U的子集，有下列推理规则：A1：自反律(reflexivity)若YXU，则X→

6、Y为F所蕴函。A2：增广律(augmentation)　　若X→Y为F所蕴函，且Z是U的子集，则XZ→YZ为F所蕴函。式中XZ和YZ是X∪Z和Y∪Z的简写。A3：传递律(transitivity)若X→Y、Y→Z为F所蕴函，则X→Z为F所蕴函。由自反律所得到的函数依赖都是平凡的函数依赖，自反律的使用并不依赖于F，而只依赖于属性集U。Armstrong公理是有效的和完备的。可以利用该公理系统推导F的闭包F+。由于利用Armstrong公理直接计算F+很麻烦。根据A1,A2,A3这三条推理规则还可以得到其他规则，用于简化计算F+的工作。

7、如下面扩展的三条推理规则:　　＊合并规则:由X→Y,X→Z,有X→YZ　　＊伪传递规则:由X→Y,WY→Z,有XW→Z　　＊分解规则:由X→YZ,则有X→Z，X→Y　　Armstrong公理可以有多种表示形式，例如，增广律A2可以用合并规则代替。例如，用自反律A1，传递律A3和合并规则可推导出增广律A2。　　证明：XZ→X(A1：自反律)　　X→Y(给定条件)　　XZ→Y(A3：传递律)　　XZ→Z(A1：自反律)　　XZ→YZ(合并规则)4．属性集的闭包　　原则上讲，对于一个关系模式R(U,F)，根据已知的函数依赖F，反复使用前面

8、的规则，可以计算函数依赖集合F的闭包F+。但是，利用推理规则求出其全部的函数依赖F+是非常困难的，而且也没有必要。因此，可以计算闭包的子集，即选择一个属性子集，判断该属性子集能函数决定哪些属性，这就是利用属性集闭包的概念。　（1）属性集闭包的定义　　设F为属性集U上的函数依赖集，XU，即X为U的一个子集。在函数依赖集F下被X函数决定的所有属性为F+下属性集X的闭包，记作X+。即X+＝{A

9、X→A}。　（2）计算属性集闭包X+的算法如下：　　输入：X，F　　输出：X+　迭代算法的步骤：　　①选取X+的初始值为X，即X+＝{X}；　　②

10、计算X+，X+＝{XZ}，其中Z要满足如下条件：YX+，且F中存在一函数依赖Y→Z。实际上就是以X+中的属性子集作为函数依赖的决定因素，在F中搜索函数依赖集，找到函数依赖的被决定属性Z放到X+中。　　③判断：如果X+没有变化？或X+等