阿姆斯特朗公理
阿姆斯特朗公理系統(英語: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的傳遞性) |
參考文獻
- ^ William Ward Armstrong: Dependency Structures of Data Base Relationships, page 580-583. IFIP Congress, 1974.