Armstrong公理_在线百科全书查询
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的真子集。
