從已知的一些函式依賴，可以推導出另外一些函式依賴，這就需要一系列推理規則，這些規則常被稱作“Armstrong 公理”。
基本介紹
- 中文名：Armstrong公理
- 提出者：W.W.Armstrong
- 提出時間：1974年
- 套用學科：數學
- 包含規則：合併規則、分解規則等
- 推理規則：自反律、增廣律、傳遞律
公理,有效性完備性,公理的推論,
公理
從已知的一些函式依賴，可以推導出另外一些函式依賴，這就需要一系列推理規則。函式依賴的推理規則最早出現在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公理系統的有效性指的是：由R出髮根據Armstrong公理系統推導出來的每一個函式依賴一定是R所邏輯蘊含的函式依賴。
②Armstrong公理系統的完備性指的是：對於R所邏輯蘊含的每一函式依賴，必定可以由R出髮根據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∈Y，則X→Z為F所蘊含
證明6
因Z∈Y 所以Y→Z （自反律）
因X→Y 所以X→Z （傳遞律）
閉包及其計算
定義1：設F是關係模型R的一個函式依賴集，X,Y是R的屬性子集，如果從F中的函式依賴能夠推出X→Y，則稱FX→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的真子集。
