跳至內容

阿姆斯特朗公理

維基百科,自由的百科全書

阿姆斯特朗公理系統(英語:Armstrong's axioms)是一組用於推導關係資料庫中所有函數依賴規則。這一系統由威廉·W·阿姆斯特朗在1974年的論文中首次提出。[1] 當應用於函數依賴集(用 表示)時,這些規則在生成該集閉包(用 表示)中的函數依賴方面既可靠又完備。換言之,反覆應用這些規則,我們能夠推導出閉包 中的所有函數依賴,且不會產生不屬於該閉包的依賴關係。

讓我們用更嚴謹的方式來描述這個概念。假設 代表一個關係模式,其中 是屬性集, 是函數依賴集。如果所有滿足 中函數依賴的, 的實例 ,也都同時滿足函數依賴 ,那麼我們就說 邏輯蘊含,記作 。我們用 來表示所有被 邏輯蘊含的函數依賴的集合。

再來看推理規則集 的作用。如果我們能夠通過反覆運用 中的規則,從 中推導出函數依賴 ,我們就說 可由 通過 所推導,記作 。我們用 表示所有可以通過 推導出的函數依賴的集合。

那麼,若且唯若以下條件成立時,推理規則集 是可靠的:

也就是說,使用 推導出的函數依賴不能超出由 邏輯蘊含的函數依賴範圍。 推理規則集 的完備性若且唯若以下條件成立:

更簡單地說,推理規則集 能夠推導出所有由 邏輯蘊含的函數依賴。

公理(基本規則)

是定義在屬性集上的關係模式。在接下來的討論中,我們將用表示的任意子集。為了簡潔,我們用代替常規的來表示兩個屬性集的併集。這種記法在處理資料庫理論中的屬性集合時是相當常見的。

自反律

如果是一個屬性集,的一個子集,那麼函數決定(也就是函數依賴),記作

.

增廣律

如果決定,那麼在中同時添加任意屬性集後,這種決定關係仍然成立。這表明,增加新的屬性不會改變已有的函數依賴關係。

,則對任意屬性集,都有.

傳遞律

函數依賴關係具有傳遞性。也就是說,如果決定,且決定,那麼必然也決定

,則.

公理的推論

這些推論可以從上述公理中推導出來。

分解規則

,則

證明

1. (已知)
2. (自反性)
3. (1和2的傳遞性)

合成規則

,則

證明

1. (已知)
2. (已知)
3. (1和A的增廣性)
4. (2和Y的增廣性)
5. (3和4的傳遞性)

合併規則

如果,則

證明

1. (已知)
2. (已知)
3. (2和X的增廣性)
4. (1和Z的增廣性)
5. (3和4的傳遞性)

偽傳遞規則

,則

證明

1. (已知)
2. (已知)
3. (1和Z的增廣性)
4. (3和2的傳遞性)

自確定性

對於任意。這直接由自反性公理得到。

擴展規則

時,該屬性是增廣性的一個特殊情況。

,則

在這種意義上,擴展性可以替代增廣性作為公理,因為通過擴展性和其他公理可以證明增廣性。

證明

1. (自反性)
2. (已知)
3. (1和2的傳遞性)
4. (3的擴展性)
5. (自反性)
6. (4和5的傳遞性)

參考文獻

  1. ^ William Ward Armstrong: Dependency Structures of Data Base Relationships, page 580-583. IFIP Congress, 1974.

外部連結