| 词条 | Armstrong公理 |
| 释义 | Armstrong 公理从已知的一些函数依赖，可以推导出另外一些函数依赖，这就需要一系列推理规则。函数依赖的推理规则最早出现在1974年W.W.Armstrong 的论文里，这些规则常被称作“Armstrong 公理” 设U 是关系模式R 的属性集，F 是R 上成立的只涉及U 中属性的函数依赖集。函数依赖的推理规则有以下三条： 自反律：若属性集Y 包含于属性集X，属性集X 包含于U，则X→Y 在R 上成立。(此处X→Y是平凡函数依赖) 增广律：若X→Y 在R 上成立，且属性集Z 包含于属性集U，则XZ→YZ 在R 上成立。 传递律：若X→Y 和 Y→Z在R 上成立，则X →Z 在R 上成立。 其他的所有函数依赖的推理规则可以使用这三条规则推导出。 Armstrong公理系统的有效性和完备性①Armstrong公理系统的有效性指的是：由R出发根据Armstrong公理系统推导出来的每一个函数依赖一定是R所逻辑蕴含的函数依赖。 ②Armstrong公理系统的完备性指的是：对于R所逻辑蕴含的每一函数依赖，必定可以由R出发根据Armstrong公理系统推导出来。 Armstrong公理的推论合并规则：若X→Y，X→Z同时在R上成立，则X→YZ在R上也成立。 分解规则：若X→W在R上成立，且属性集Z包含于W，则X→Z在R上也成立。 伪传递规则：若X→Y在R上成立，且WY→Z，则XW→Z。 函数依赖的公理系统一、Armstrong公理系统设关系模式R<U,F>，其中U为属性集，F是U上的一组函数依赖，那么有如下推理规则： ① A1自反律：若Y X U，则X→Y为F所蕴含； ② A2增广律：若X→Y为F所蕴含，且Z U，则XZ→YZ为F所蕴含； ③ A3传递律：若X→Y，Y→Z为F所蕴含，则X→Z为F所蕴含。 根据上面三条推理规则，又可推出下面三条推理规则： ④ 合并规则：若X→Y，X→Z，则X→YZ为F所蕴含； ⑤ 伪传递规则：若X→Y，WY→Z，则XW→Z为F所蕴含； ⑥ 分解规则：若X→Y，Z Y，则X→Z为F所蕴含。 引理：X→A1A2…Ak成立的充分必要条件是X→Ai成立(i=1,2,...,k)。 二、Armstrong公理系统的证明① A1自反律：若Y X U，则X→Y为F所蕴含 证明1 设Y X U。 对R<U,F>的任一关系r中的任意两个元组t,s： 若t[X]=s[X]，由于Y X，则有t[Y]=s[Y]，所以X→Y成立，自反律得证。 ② A2增广律：若X→Y为F所蕴含，且Z U，则XZ→YZ为F所蕴含 证明2 设X→Y为F所蕴含，且Z U。 对R<U,F>的任一关系r中的任意两个元组t,s： 若t[XZ]=s[XZ]，由于X XZ，Z XZ，根据自反律，则有t[X]=s[X]和t[Z]=s[Z]； 由于X→Y，于是t[Y]=s[Y]，所以t[YZ]=s[YZ]；所以XZ→YZ成立，增广律得证。 ③ A3传递律：若X→Y，Y→Z为F所蕴含，则X→Z为F所蕴含 证明3 设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所蕴含，传递律得证。 ④ 合并规则：若X→Y，X→Z，则X→YZ为F所蕴含 证明4 因X→Y （已知） 故X→XY （增广律），XX→XY即X→XY 因X→Z （已知） 故XY→YZ （增广律） 因X→XY，XY→YZ （从上面得知） 故X→YZ （传递律） ⑤ 伪传递规则：若X→Y，WY→Z，则XW→Z为F所蕴含 证明5 因X→Y （已知） 故WX→WY （增广律） 因WY→Z （已知） 故XW→Z （传递律） ⑥ 分解规则：若X→Y，Z∈5，则X→Z为F所蕴含 证明6 因Z∈Y （已知） 故Y→Z （自反律） 因X→Y （已知） 故X→Z （传递律） 闭包及其计算定义1：设F是关系模型R的一个函数依赖集，X,Y是R的属性子集，如果从F中的函数依赖能够推出X→Y，则称F逻辑蕴含X→Y。 定义2：被F逻辑蕴涵的函数依赖的全体构成的集合，称为F的闭包，记作F+。 定义3：设F是属性集U上的一组函数依赖，则属性集X关于F的闭包X+F定义为X+F={A|A∈U且X→A可由F经Armstrong公理导出}，即X+F={A|X→A∈F+}。 定理1：设关系模型R(U)，F为其函数依赖集，X，Y为U的真子集，则从F推出X→Y的充要条件是Y是X+F的真子集。 |
| 随便看 |
百科全书收录4421916条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。