Hệ tiên đề Amstrong

Năm 1974 Amstrong đã đưa ra hệ luật dẫn hay là tính chất của phụ thuộc hàm gọi là hệ tiên đề Amstrong, đó chính là các quy tắc biến đổi của phụ thuộc hàm.

Cho lược đồ quan hệ r(U), U là tập thuộc tính, F là tập các phụ thuộc hàm được định nghĩa trên quan hệ r.

Ta có phụ thuộc hàm A → B được suy diễn logic từ F nếu mọi quan hệ r trên U thỏa các phụ thuộc hàm trong F thì cũng thỏa phụ thuộc hàm A → B.

Ví dụ:

Tập phụ thuộc hàm: F = { A → B, B → C}

Ta có phụ thuộc hàm A → C là phụ thuộc hàm được suy từ F.

1. Các tính chất của Phụ thuộc hàm

Cho X, Y, Z, W ⊂U, ta có:

1. Phản xạ: Nếu Y ⊂X thì X → Y
2. Tăng trưởng: Nếu Z ⊂U và X → Y thì XZ → YZ

(Ký hiệuXZ là X∪Z)

3. Bắc cầu: Nếu X → Y và Y → Z thì X → Z
4. Giả bắc cầu: Nếu X → Y và WY → Z thì XW → Z
5. Luật hợp: Nếu X → Y và X → Z thì X →YZ
6. Luật phân rã: Nếu X → Y và Z ⊂Y thì X → Z

…………..

Nhận xét: Trong sáu luật trên thì  các luật 4, 5, 6 suy được từ 1, 2, 3. Người ta cũng đã chứng minh được là từ các luật 1, 2, 3 có thể suy ra được tất cả các luật khác. Vì vậy các luật 1, 2, 3 là một hệ tiên đề, có tên là Hệ tiên đề Amstrong

Ví dụ 1: Cho R(ABC) và tập phụ thuộc hàm F {AB ®C , C ®A }Áp dụng hệ tiên đề Amstrong chứng minh rằng BC®ABC

Ta có:

• C ®A tăng cường vào hai vế thêm B ta được BC ®AB (1)
• AB ®C tăng cường thêm AB vào hai vế ta được AB ®ABC (2)
• Từ (1,2) áp dụng luật bắc cầu suy ra điều phải chứng minh BC®ABC

Ví dụ 2: Chứng minh nếu Nếu X ® Y và U ® V thì XU ® YV

Ta có:

1. Từ X ® Y ( giả thiết) có XU ® YU, (tăng trưởng U)
2. Từ U ® V (giả thiết) có YU ® YV (tăng trưởng Y)
3. Có XU ® YV ( bắc cầu (1) và (2) )