Armstrong公理系统

一、Armstrong公理系统设关系模式R<U,F>，其中U为属性集，F是U上的一组函数依赖，那么有如下推理规则：

根据上面三条推理规则，又可推出下面三条推理规则：

引理

：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∈Y，则X→Z为F所蕴含

证明6

因Z∈Y 　所以Y→Z （自反律）

因X→Y 所以X→Z （传递律）

定义1

：设F是关系模型R的一个函数依赖集，X,Y是R的属性子集，如果从F中的函数依赖能够推出X→Y，则称F[1]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的真子集。