Armstrong公理系统

Armstrong公理系统

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所蕴涵。

根据上述三条推理规则又可推出下述三条推理规则：
（1）合并规则：若X→Y，X→Z，则X→YZ为F所蕴涵。

（2）伪传递律：若X→Y，WY→Z，则XW→Z为F所蕴涵

（3）分解规则：若X→Y，Z⊆Y，则X→Z为F所蕴涵。

函数依赖的闭包F⁺及属性的闭包X_F⁺

函数依赖的闭包F⁺

关系模式R(U,F)中为F所逻辑蕴含的函数依赖的全体（通过Armstrong公理系统推理）称为F的闭包，记为：F⁺

属性的闭包X_F⁺

设F为属性集U上的一组函数依赖，X⊆U，X_F⁺={A|X→A能由F根据Armstrong公理导出}，则称X_F⁺为属性集X关于函数依赖集F的闭包。

候选码的求解方法

根据函数依赖。将属性划分为以下

• L：仅出现在函数依赖集F左部的属性
• R：仅出现在函数依赖集F右部的属性
• LR：在函数依赖集F左右部都出现的属性
• NLR：在函数依赖集F左右部都未出现的属性

结论1：若X(X⊆U)是L类属性，则X必为R的任一候选码的成员。若X_F⁺=U，则X必为R的唯一候选码。

结论2：若X(X⊆U)是R类属性，则X不是R的任一候选码的成员。

结论3：是X(X⊆U)是NLR类属性，则X必为R的任一候选码的成员。

结论4：若X(X⊆U)是L类和NLR类属性组成的属性集，若X_F⁺=U，则X必为R的唯一候选码。

• 第1步、根据题意，将所有的属性分类：
  •  L：只在左边出现，一定是
  •  R：只在右边出现，一定不是
  •  LR：左右都出现，有可能是，也有可能不是
  • NLR：左右都没出现，一定是
• 第2步、将所有的L类和NLR类属性组合起来，设为P，求其闭包P_F⁺，如果是全集U，那么它就是候选码。
• 第3步、如果P_F⁺不是全集U，则依次将LR类属性跟P组合起来求闭包，只要其闭包是全集U，就是候选码。

模式分解及分解后的特性

无损连接

无损连接是指将一个关系模式分解成若干个关系模式后，通过自然连接和投影等运算仍能还原到原来的关系模式，则称这种分解为无损连接分解。

这个定理只适用于分解为两个子模式的情况，分解为多个子模式的时候不适用

关系模式R(U,F)的一个分解ρ ={ R1(U1,F1),R2(U2,F2)}

具有无损连接的充分必要的条件是：

• U1⋂U2→U1－U2∈F⁺
• 或U1⋂U2→U2－U1∈F⁺

保持函数依赖

设关系模式R(U,F)的一个分解 ρ ={R1(U1,F1), R2(U2,F2),…,Rk(Uk,Fk)}，（F1 ⋃ F2 ⋃ F3 ⋃…⋃ Fk)+ =F⁺，则称分解ρ保持函数依赖