跳至內容

阿姆斯特朗公理

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

阿姆斯特朗公理系統(英語: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.

外部連結

[編輯]