Armsmtrng

ARMSTRONG
I. HỆ LUẬT DẪN ARMSTRONG (Armstrong inference rule):
Người ta thường dùng F để chỉ tập các phụ thuộc hàm của lược đồ quan hệ Q. Ta có thể đánh số các phụ thuộc hàm của F là f1, f2, .., fm. Quy ước rằng chỉ cần mô tả các phụ thuộc hàm không hiển nhiên trong tập F (các phụ thuộc hàm hiển nhiên được ngầm hiểu là đã có trong F).
1. Phụ thuộc hàm được suy diễn logic từ F
Nói rằng phụ thuộc hàm X → Y được suy diễn logic từ F nếu một quan hệ r thỏa mãn tất cả các phụ thuộc hàm của F thì cũng thỏa phụ thuộc hàm X → Y. Ký hiệu F|= X → Y. Bao đóng của F ký hiệu F+ là tập tất cả các phụ thuộc hàm được suy diễn logic từ F.
* Các tính chất của tập F+
1. Tính phản xạ: Với mọi tập phụ thuộc hàm F+ ta luôn luôn có F ⊆ F+
2. Tính đơn điệu: Nếu F ⊆ G thì F+ ⊆ G+
3. Tính lũy đẳng: Với mọi tập phụ thuộc hàm F ta luôn luôn có (F+)+ = F+. Gọi G là tập tất cả các phụ thuộc hàm có thể có của r, phần phụ của F ký hiệu F-
= G - F+
Chứng minh
1. X → Y ∈ F ⇒ r thỏa X → Y ⇒ X → Y ∈ F+
2. Nếu X → Y là phụ thuộc hàm thuộc F+ ta phải chứng minh X → Y thuộc G+
Giả sử r thỏa tất cả các phụ thuộc hàm của G (1)
⇒ r thỏa tất cả phụ thuộc hàm của F vì F ⊆ G
⇒ r thỏa phụ thuộc hàm X → Y (2) (vì X → Y∈F+)
(1) và (2) ⇒ X → Y ∈ G+
⇒ F+ ⊆ G+
3. F ⊆ F+ (tính phản xạ) ⇒ F+ ⊆ (F+)+ (1)
Nếu X → Y ∈ (F+)+ (2)
⇒ X → Y ∈ F+ thật vậy: (3)
Giả sử r thỏa tất cả các phụ thuộc hàm của F (4)
⇒ r thỏa tất cả các phụ thuộc hàm của F+ (theo định nghĩa)
⇒ r thỏa tất cả các phụ thuộc hàm của (F+)+ (theo định nghĩa)
⇒ r thỏa X → Y (vì (2)) ⇒ X → Y ∈ F+
(1) và (3) ⇒ (F+)+ = F+
2. Hệ luật dẫn Armstrong :
Hệ luật dẫn là một phát biểu cho biết nếu một quan hệ r thỏa mãn một vài phụ thuộc hàm thì nó phải thỏa mãn phụ thuộc hàm khác.
Với X,Y,Z,W là tập con của Q+. r là quan hệ bất kỳ của Q. Ta có 6 luật dẫn sau:
1. Luật phản xạ (reflexive rule):
thì X (Y
2. Luật trưởng (augmentation rule): X → Y ⇒ XZ → YZ
3. Luật hợp (union rule): X → Y, X → Z ⇒ X → YZ
4. Luật phân rã (decomposition rule): Cho X → YZ ⇒ X → Y và X ( Z
5. Luật bắc cầu (transitive rule): Nếu X → Y, Y → Z ⇒ X → Z
6. Luật Tựa bắc cầu (pseudo transitive rule): Nếu X → Y, YZ → W ⇒ XZ → W
Hệ tiên đề Armstrong (Armstrong’s Axioms) gồm 3 luật: (1), (2) và (5)
Chứng minh
Với t1,t2 là hai bộ bất kỳ của quan hệ r.
- Luật phản xạ: Ta có (t1.X = t2.X ⇒ t1.X = t2.X) theo định nghĩa suy ra X → X
- Luật thêm vào: giả sử có t1.XZ = t2.XZ (1)
⇒ t1.X = t2.X
⇒ t1.Y = t2.Y (do X → Y) (2)
⇒ XZ → Y (do (1) ⇒ (2))
- Luật hợp: giả sử có t1.X = t2.X (1)
⇒ t1.X = t2.X và t1.Z = t2.Z
⇒ t1.XZ = t2.XZ (2)
⇒ X → YZ (do (1) ⇒ (2))
- Luật phân rã: gỉa sử có: t1.X = t2.X (1)
⇒ t1.YZ = t2.YZ (do X → YZ)
⇒ t1.Y = t2.Y (2)
⇒ X → Y