MÔ HÌnh quan hệ nguyên nhân ra đỜi của mô HÌnh quan hệ

2. 
   HỆ LUẬT DẪN ARMSTRONG (Armstrong inference rule)
   

1. 
   Phụ thuộc hàm được suy diễn logic từ F
   

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⁺

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⁺
   

 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)
   

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
   

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): X  X
   
2. 
   Luật thêm vào (augmentation rule): Cho X  Y  XZ  Y
   
3. 
   Luật hợp (union rule): Cho X  Y, X  Z  X  YZ
   
4. 
   Luật phân rã (decomposition rule): Cho X  YZ  X  Y
   
5. 
   Luật bắc cầu (transitive rule): Cho X  Y, Y  Z  X  Z
   
6. 
   Luật bắc cầu giả (pseudo transitive rule): Cho X  Y, YZ  W  XZ  W
   

Với t₁,t₂ là hai bộ bất kỳ của quan hệ r.

Luật phản xạ: Ta có (t₁.X = t₂.X  t₁.X = t₂.X) theo định nghĩa suy ra X  X

Luật thêm vào: giả sử có t₁.XZ = t₂.XZ (1)

 t₁.X = t₂.X

 t₁.Y = t₂.Y (do X  Y) (2)

 XZ  Y (do (1)  (2))

Luật hợp: giả sử có t₁.X = t₂.X (1)

 t₁.X = t₂.X và t₁.Z = t₂.Z

 t₁.XZ = t₂.XZ (2)

 X  YZ (do (1)  (2))

Luật phân rã: gỉa sử có: t₁.X = t₂.X (1)

 t₁.YZ = t₂.YZ (do X  YZ)

 t₁.Y = t₂.Y (2)

 X  Y (do (1)  (2))

Luật bắc cầu: giả sử có t₁.X = t₂.X (1)

 t₁.Y = t₂.Y

 t₁.Z = t₂.Z (2)

 X  Z (do (1)  (2))

Luật bắc cầu giả: giả sử có: t₁.XZ = t₂.XZ (1)

 t₁.X = t₂.X và t₁.Z = t₂.Z (2)

 t₁.Y = t₂.Y (do X  Y) (3)

 t₁.YZ = t₂.YZ (Kết hợp (2) và (3))

 t₁.W = t₂.W (do YZ  W) (4)

 XZ  W

Trong 6 luật trên, chỉ cần 3 luật 1, 2 và 6 là đủ, nghĩa là các luật còn lại có thể suy dẫn từ ba luật này.

1. 
   Hệ luật dẫn Armstrong là đúng
   

F₀ = {AB  C,C  B, BC  A} áp dụng luật hợp cho C  B và C  C

F₁ = {AB  C,C  B, BC  A, C  BC} áp dụng luật bắc cầu.

F₂ = {AB  C,C  B, BC  A, C BC, C  A}

2. 
   Bao đóng của tập thuộc tính X (closures of attribute sets)
   
   1. 
      Định nghĩa
      

Bao đóng của tập thuộc tính X đối với F ký hiệu là X⁺ (hoặc ) được định nghĩa như sau:

• 
  bao đóng của Q là Q⁺
  

2. 
   Các tính chất của bao đóng
   

1. X  X  X⁺  X

2. A  X⁺  X  A  Y  A  A  Y⁺

3. A  X⁺⁺  X⁺  A và X  X⁺ (áp dụng 8)  X  A  AX⁺

 X⁺⁺  X⁺. Áp dụng 1  X⁺⁺  X⁺

...............................................

7. X  A₁ và X A₂  X  A₁A₂ .... XA_i = X⁺

X⁺  X  X⁺  X (Phụ thuộc hàm hiển nhiên)

...............................................

3. 
   Thuật toán tìm bao đóng
   

Cho lược đồ quan hệ Q(ABCDEGH) và tập phụ thuộc hàm F

F = { f₁: B  A

f₂: DA  CE

f₃: D  H

f₄: GH  C

f₅: AC  D }

Tìm bao đóng của các tập X = {AC} dựa trên F.

Bước 1: X₀ = AC

Bước 2: Do f₁, f₂, f₃, f₄ không thỏa. f₅ thỏa vì X⁺  AC

X₁ = AC  D = ACD

Lập lại bước 2: f₁ không thỏa, f₂ thỏa vì X₁  AD:

X₂ = ACD  CE = ACDE

f₃ thỏa vì X₂  D

X₃ = ACDE  H = ACDEH

f₄ không thỏa, f₅ không xét vì đã thỏa

Lập lại bước 2: f₂,f₃ không xét vì đã thỏa, f₁,f₄ không thỏa,f₅ không xét vì đã thỏa.Trong bước này X₃ không thay đổi => X⁺=X₃={ACDEH} là bao đóng của X

Q(A,B,C,D,E,G)

F = {f₁: A  C;

f₂: A  EG;

f₃: B  D;

f₄: G  E}

X = {A,B}; Y = {C,G,D}

Kết qua:

X⁺ = {ABCDEG}

Y⁺ = {CGDE}

4. 
   Định lý
   

Theo tính phản xạ của hệ luật dẫn thì X  X theo thuật toán thì X₀ = X  X  X₀

Vậy X₀  X⁺

Bước qui nạp giả sử có X  X_i-1 ^­ (1) ta phải chứng minh X  X_i

Theo thuật toán tìm bao đóng thì có f_j = X_j  Y_j để X_i-1  X_j và X_i = X_i-1  Y_j

 X_i-1  Y_j (2).(1)và (2)  X  Y_j (3)

(1) và (3)  X X_i-1Y_j = X_i  X  X_i

Vậy X_i  X^+­­

2. Ta chứng minh A  X⁺  A  X_i để kết luận X_i  X⁺

A  X⁺ nên có một phụ thuộc hàm X  A. Theo thuật toán tìm bao đóng thì X  X_i  A X_i

1. 
   Hệ quả
   

1. 
   Q là lược đồ quan hệ. F là tập phụ thuộc hàm, A là thuộc tính chỉ xuất hiện ở vế phải của các phụ thuộc hàm trong F thì X⁺ = (X – A)⁺  A
   
2. 
   Q là lược đồ quan hệ. F là tập phụ thuộc hàm, X là tập con của Q⁺ và Y = {các thuộc tính xuất hiện ở vế phải của các phụ thuộc hàm trong F} thì X⁺  X  Y.
   

1. 
   Theo thuật toán tìm bao đóng thì bao đóng X⁺ hay (X-A)⁺ được hình thành qua một số bước. Ta chứng minh biểu thức X⁺ = (X – A)⁺  A theo qui nạp.
   

X_i-1  X_j và X_i = X_i-1  Y_j = (X - A)_i-1  A  Y_j (1).

Sự hình thành X_i luôn kéo theo sự hình thành (X-A)_i vì:

X_i-1 = (X - A)_i-1 ^­­­ A  X_j do X_j không chứa A nên:

(X - A)_i-1  X_j vậy (X - A)_i = (X - A)_i-1  Y_j (2)

(1) và (2) cho:

X_i = (X - A)_i  A là điều phải chứng minh

2. 
   Bước cơ sở: X₀ = X  X₀  X  Y
   

Bao đóng X_i được hình thành do có f_j = X_j  Y_j để:

X_i-1  X_j và X_i = X_i-1  Y_j  X  Y  Y_j­­ do Y_j là vế phải của phụ thuộc hàm nên Y  Y_j = Y vậy X_i  X  Y

3. 
   Hệ luật dẫn Armstrong là đầy đủ
   
   1. 
      Định lý
      

Để chứng minh X  Y được suy diễn từ F nhờ hệ luật dẫn Armstrong ta chứng minh bằng phương pháp phản chứng nghĩa là nếu X  Y không suy diễn được từ hệ luật dẫn Armstrong thì có quan hệ r thỏa các phụ thuộc hàm F nhưng không thỏa phụ thuộc hàm X  Y (điều này nghịch lý với giả thuyết là mọi quan hệ r thỏa các phụ thuộc hàm trong F thì r cũng thỏa phụ thuộc hàm X  Y).

Thật vậy giả sử Q(A₁,A₂,...,A_n) là lược đồ quan hệ, a_i,b_i là các giá trị khác nhau trên miền giá trị A_i. r là quan hệ trên Q có hai bộ t và t’được xác định như sau:

t=(a₁,a₂,...,a_n)

Vậy quan hệ r có t.X = t’.X nhưng t.Y  t’.Y (t.Y gồm các giá trị a_i còn t’.Y phải có ít nhất một b_i nếu không Y  X⁺  X  Y được suy dẫn từ hệ luật dẫn Armstrong ). Như vậy r không thỏa phụ thuộc hàm X  Y.

Bây giờ ta chứng minh quan hệ r thỏa mọi phụ thuộc hàm trong F. Gọi W  Z là phụ thuộc hàm trong F.

Nếu W  X⁺  t.W  t’.W  mệnh đề (t.W = t’.W  t.Z = t’.Z)đúng

Nếu W  X⁺  t.Z = t’.Z = bộ các a_i

 mệnh đề (t.W = t’.W  t.Z = t’.Z)đúng

2. 
   Hệ quả:
   

X  Y  có k sao cho Y = A_k   A_i = X⁺

Y  X⁺  X⁺ = Y  (X⁺ - Y)  X  Y  (X⁺ - Y)  X  Y

Bài toán thành viên

Nói rằng X  Y là thành viên của F nếu X  Y  F⁺

Một vấn đề quan trọng khi nghiên cứu lý thuyết CSDL là khi cho trước tập các phụ thuộc hàm F và một phụ thuộc hàm X  Y, làm thế nào để biết X  Y có thuộc F⁺ hay không bài toán này được gọi là bài toán thành viên. Để trả lời câu hỏi này ta có thể tính F⁺ rồi xác định xem X  Y có thuộc F⁺ hay không. Việc tính F⁺ là một công việc đòi hỏi thời gian và công sức. Tuy nhiên, thay vì tính F⁺ chúng ta có thể dùng thuật toán sau để xác định X  Y có là thành viên của F hay không. Thuật toán này sử dụng tính chất vừa chứng minh trên.

Thuật toán xác định f = XY có là thành viên của F hay không

Bước 1: tính X⁺

Bước 2: so sánh X⁺ với Y nếu X⁺­­­  Y thì ta khẳng định X  Y là thành viên của F

Bạn đọc hãy nắm thật kỹ thuật toán này – nó mở đầu cho một loạt ứng dụng về sau.

3. 
   THUẬT TOÁN TÌM F⁺
   
   1. 
      Thuật toán cơ bản
      

Cho lược đồ quan hệ Q(A,B,C) F = {AB  C,C  B} là tập phụ thuộc hàm trên Q. F⁺ được tính lần lượt theo các bước trên là như sau:

⁺ = A⁺ = A C⁺ = BC

ABC⁺ =ABC B⁺ = B AC⁺ = ABC

AB⁺ = ABC BC⁺ = BC

F⁺ = {ABC,ABAC,ABBC,ABABC,CB,CBC,ACB,ACAB,ACBC,ACABC}

2. 
   Thuật toán cải tiến
   

Ví dụ bao đóng A⁺ = A chỉ gồm các phụ thuộc hàm hiển nhiên

bao đóng {AB}⁺ = ABC cho các phụ thuộc hàm không hiển nhiên sau

ABC,ABAC,ABBC,ABABC

(Tìm tất cả các tập con của {ABC} rồi bỏ các tập con của {AB})

Các tập con của {ABC} là: , {A},{B},{AB},{C},{AC},{BC},{ABC}

Bỏ các tập con của {AB} là: , {A},{B},{AB},{C},{AC},{BC},{ABC}

Các tập còn lại chính là vế phải của phụ thuộc hàm có vế trái là AB

1. 
   BÀI TẬP
   

1. 
   Cho quan hệ sau:
   

AD,ABD,CBDE,EA,AE

2. 
   Cho Q⁺={ABCD}
   

1. 
   Tìm tất các các tập con của Q
   
2. 
   Tìm tất cả các phụ thuộc hàm có thể có của Q (không liệt kê phụ thuộc hàm hiển nhiên)
   

3. 
   Tìm bao đóng F⁺ của quan hệ phanCong(PHICONG,MAYBAY,NGAYKH,GIOKH)
   
4. 
   Cho F = {ABC,BD,CDE,CEGH,GA}
   

1. 
   Hãy chứng tỏ phụ thuộc hàm ABE,ABG được suy diễn từ F nhờ luật dẫn Armstrong
   
2. 
   Tìm bao đóng của AB(với bài toán không nói gì về lược đồ quan hệ Q ta ngầm hiểu Q⁺ là tập thuộc tính có trong F nghĩa là Q⁺={ABCDEGH})
   

5. 
   Cho F = {AD,ABDE,CEG,EH}. Hãy tìm bao đóng của AB.
   
6. 
   Cho F={ABE,AGI,BEI,EG,GIH}.
   

1. 
   Hãy chứng tỏ phụ thuộc hàm ABGH được suy diễn từ F nhờ luật dẫn Armstrong
   
2. 
   Tìm bao đóng của {AB}
   

7. 
   Cho F={AD,ABE,BIE,CDI,EC} tìm bao đóng của {AE}⁺={ACDEI}