Tìm phủ tối thiểu của tập phụ thuộc hàm
Với mỗi tập phụ thuộc hàm F đã cho, rất có thể có nhiều phụ thuộc hàm là dư thừa, tức là ta có thể suy dẫn ra các phụ thuộc hàm này thông qua tập phụ thuộc hàm còn lại trong F. Vấn đề đặt ra là phải làm sao thu gọn số phụ thuộc hàm F thành tối thiểu (gọi là ...
Với mỗi tập phụ thuộc hàm F đã cho, rất có thể có nhiều phụ thuộc hàm là dư thừa, tức là ta có thể suy dẫn ra các phụ thuộc hàm này thông qua tập phụ thuộc hàm còn lại trong F. Vấn đề đặt ra là phải làm sao thu gọn số phụ thuộc hàm F thành tối thiểu (gọi là G) để sao cho G vẫn tương đương với F.
Ví dụ về phụ thuộc hàm dư thừa:
F = {A → B, B → C, A → C. ở đây phụ thuộc hàm A → C là dư thừa bởi vì ta có thể dễ dàng có được phụ thuộc hàm này thông qua A → B, B → C
Như vậy tập phụ thuộc hàm tương đương với F là G = { A → B, B → C }
Cho lược đồ R = {U, F}, một phụ thuộc hàm trong F có dạng α→β được gọi là dư thừa nếu như bao đóng của α trong tập phụ thuộc hàm F−(α→β) size 12{F - ( α rightarrow β ) } {}có chứa β size 12{β} {}. Tức là : (α)(F−(α→β))+⊃β size 12{ ( α ) rSub { size 8{ ( F - ( α rightarrow β ) ) } } rSup { size 8{+{}} } supset β} {}
Một tập phụ thuộc hàm G được gọi là tương đương với tập phụ thuộc hàm F của lược đồ R nếu như : F+ = G+. Khi đó ta nói F phủ G hay G phủ F.
Một phủ tối thiểu của tập phụ thuộc hàm F là một tập phụ thuộc hàm G, Trong đó:
- G tương đương với F (tức là G+ = F+)
- Tất cả các phụ thuộc hàm trong G đều có dạng X → A Trong đó A là một thuộc tính.
- Không thể làm cho G nhỏ hơn được nữa. (Tức là không thể xoá thêm bất kỳ phụ thuộc hàm nào trong G hay xoá đi bất kỳ một thuộc tính nào bên phía phải, phía trái của mỗi phụ thuộc hàm mà G vẫn tương đương với F).
- Tách mỗi phụ thuộc hàm trong F có dạng X → A1A2A3…An thành các phụ thuộc hàm mà vế phải (RH – Right Hand) chỉ có một thuộc tính:
X → A1
X → A2
………
X → An
- Loại bỏ các thuộc tính dư thừa bên phía trái của mỗi phụ thuộc hàm.
- Duyệt từng phụ thuộc hàm và kiểm tra xem có dư thừa không, nếu dư thừa thì thì xoá đi.
Định nghĩa thuộc tính dư thừa
Một phụ thuộc hàm có dạng αA→ β, với A là một thuộc tính đơn lẻ.Ta nói A là thuộc tính dư thừa nếu có thể suy dẫn ra β từ α, Tức là α+⊇β size 12{α rSup { size 8{+{}} } supseteq β} {}
Cho F = {AC → B, C → B, ABDE → GH, A → E, A → D}
+ Xét phụ thuộc hàm AC → B:
Rõ ràng thuộc tính A trong AC → B là dư thừa vì C+ = (CB) size 12{ supset } {} B.
+ Xét phụ thuộc hàm ABDE → GH
- Thuộc tính A : Không dư thừa vì (BDE)+ = BDE không chứa GH
- Thuộc tính B : Không dư thừa vì (ADE)+ = ADE không chứa GH
- Thuộc tính D: Dư thừa vì (ABE)+ = ABDE có chứa ABDE
( Loại thuộc tính D khỏi phụ thuộc hàm ABDE → GH ta được ABE → GH
+ Xét phụ thuộc hàm ABE → GH
- Thuộc tính E: Dư thừa vì (AB)+ = ABDE size 12{ supset } {} ABE
+ Các thuộc tính trong các phụ thuộc hàm còn lại đều không dư thừa.
Cuối cùng ta được tập phụ thuộc hàm không có thuộc tính dư thừa gồm:
F = {C → B, AB → GH, A → E, A → D}
Định nghĩa phụ thuộc hàm dư thừa
Một phụ thuộc hàm có dạng α→β size 12{α rightarrow β} {}, được gọi là dư thừa nếu như xoá bỏ nó khỏi tập F thì ta vẫn có : α+⊇β size 12{α rSup { size 8{+{}} } supseteq β} {} (tức là vẫn suy dẫn ra β size 12{β} {} từ α size 12{α} {}, mặc dù đã xoá bỏ phụ thuộc hàm α→β size 12{α rightarrow β} {} khỏi F).
Cho F = {A → B, B → C, A → C, B → DE, A → E, A → D}
+ Kiểm tra xem A → B có dư thừa hay không bằng cách : Thử loại phụ thuộc hàm này khỏi F sau đó tính A+, Nếu A+ ⊇ B thì nó là dư thừa, trái lại là không dư thừa.
Sau khi loại A → B ta có F = {B → C, A → C, B → DE, A → E, A → D}
Rõ ràng A+ = {AED} nên B ∉ A+, chứng tỏ A → B là không dư thừa.
Vậy phụ thuộc hàm này không thể loại khỏi F.
F vẫn là: {A → B, B → C, A → C, B → DE, A → E, A → D}
+ Kiểm tra B → C có dư thừa ?
Loại B→C khỏi F, ta có F = {A→B, A→C, B→DE, A→E, A→D}
B+ = {BDE} không chứa C, chứng tỏ B→C là không dư thừa.
→ size 12{ rightarrow } {}F vẫn là: {A→B, B→C, A→C, B→DE, A→E, A→D}
+ Kiểm tra A → C có dư thừa ?
Loại A→C khỏi F ta được F = {A→B, B→C, B→DE, A→E, A→D}
A+ = {ABCDE} có chứa C, chứng tỏ A→C là dư thừa
→ size 12{ rightarrow } {} F bây giờ là: F = {A→B, B→C, B→DE, A→E, A→D}
+ Kiểm tra B → DE có dư thừa ?
Loại B→DE khỏi F, ta được F = {A→B, B→C, A→E, A→D}
B+ = {BC} không chứa DE, chứng tỏ B→DE không dư thừa
→ size 12{ rightarrow } {} F vẫn là {A→B, B→C, B→DE, A→E, A→D}
+ Kiểm tra A → E có dư thừa ?
Loại A→E khỏi F, ta được F = {A → B, B→C, B→DE, A→D}
A+ = {ABCDE} chứa E, chứng tỏ phụ thuộc hàm này dư thừa
→ size 12{ rightarrow } {} F bây giờ là: {A→B, B→C, B→DE, A→D}
+ Kiểm tra A → D có dư thừa ?
Loại A→D khỏi F, ta được F = {A→B, B→C, B→DE}
A+ = {ABCDE} chứa D, chứng tỏ phụ thuộc hàm A→D là dư thừa.
→ size 12{ rightarrow } {} F bây giờ là {A→B, B→C, B→DE}.
Duyệt lại các phụ thuộc hàm ta thấy không có phụ thuộc hàm nào bị loại thêm nữa (Tức là F = Const). Do vậy tập phụ thuộc hàm cuối cùng sau khi loại các phụ thuộc dư thừa là:
F = {A→ B, B → C, B → DE}
Với phương pháp loại bỏ thuộc tính và phụ thuộc hàm dư thừa đã đề cập ở trên, sau đây ta lấy ví dụ thực hiện việc tìm phủ tối thiểu của tập phụ thuộc hàm F.
T sau đây: T = {ABH → CK, A → D, C →E, BGH → F, F → AD, E →F, BH → E}
Bước 1: Chuyển vế phải của mỗi phụ thuộc hàm thành các thuộc tính đơn lẻ
- ABH → C
- ABH → K
- A → D
- BGH → F
- F → A
- F → D
- E → F
- BH → E
Bước 2: Loại bỏ các thuộc tính dư thừa bên phía trái của mỗi phụ thuộc hàm
+ Xét phụ thuộc hàm ABH→C
- A dư thừa vì (BH)+ = {BHEFDAKC} có chứa C.
- B Không dư thừa vì (AH)+ = {AHD} không chứa C
- H không dư thừa vì (AB)+ = {ABD} không chứa C
→ size 12{ rightarrow } {} Kết quả sau lần thứ nhất:
T = {BH → C, ABH → K, A → D, BGH → F, F → A, F → D, E → F, BH → E}
+ Tương tự: A dư thừa trong ABH→K vì (BH)+ = {BHCEFDAK} chứa K và G dư thừa trong BGH→F vì (BH)+ = {BHEFDAKC} có chứa F.
→ size 12{ rightarrow } {} Kết quả cuối cùng:
T = {BH → C, BH → K, A → D, BH → F, F → A, F → D, E → F, BH → E}
Đển đây ta không thể loại thêm được thuộc tính nào nữa.
Bước 3: Loại bỏ các phụ thuộc hàm dư thừa
Hiện tại T = {BH→C, BH→K, A→D, BH→F, F→A, F→D, E→F, BH→E}
- Thử loại BH → C, Ta có (BH)+ = {BHFADEK} không chứa C => không dư thừa.
- Thử loại BH→K, Ta có (BH)+ = {BHCFADE} không chứa K => không dư thừa.
- Thử loại A→ D, Ta có (A)+ = {A} không chứa D => không dư thừa.
- Thử loại BH→ F, Ta có (BH)+ = {BHCKEFAD} có chứa F => luật này dư thừa, loại ra khỏi T, ta được: T = {BH→C, BH→K, A→D, F→A, F→D, E→F, BH→E}
- Thử loại F→ A, Ta có F+ = {FD} không chứa A => không dư thừa
- Thử loại F→ D, ta có F+ = {FAD} có chứa D nên luật này dư thừa. Loại khỏi T ta được : T = {BH→C, BH→K, A→D, F→A, E→F, BH→E}
- Thử loại E→F, ta có E+ = {E} không chứa F => Không dư thừa.
- Thử loại BH→E, ta có (BH)+ = {BHCK} không chứa E nên không dư thừa.
Đến đây ta đã thử xong tất cả các phụ thuộc hàm trong lược đồ. Kết quả cuối cùng ta có phủ tối thiểu T = {BH→C, BH→ K, A→D, F→A, E→F, BH→E}.
Tìm phủ tối thiểu của lược đồ cho dưới đây: R = <U, F>, Với U = {ABCDEGH} và F = {A→ BC, BE → G, E → D, D → G, A → B, AG → BC}
Bước 1 Tách vế phải thành 1 thuộc tính:
- A→B
- A→C
- BE→G
- E→D
- D→G
- A→B
- AG→B
- AG→C
Bước 2 Xoá thuộc tính dư thừa
- B dư thừa trong BE→G. Vì (E)+ = {DEG} chứa G
- G dư thừa trong AG→B. Vì (A)+ = {ABC} chứa B
- G dư thừa trong AG→C. Vì (A)+ = {ABC} chứa C
Bước 3 Xoá phụ thuộc hàm dư thừa:
- A→B dư thừa. Vì nếu xoá khỏi F, ta vẫn có (A)+ = {ABC} Chứa B
- A→C dư thừa. Vì nếu xoá khỏi F, ta vẫn có (A)+ = {ABC} Chứa C
- A→B dư thừa. Vì nếu xoá khỏi F, ta vẫn có (A)+ = {ABC} Chứa B
- E→G dư thừa. Vì nếu xoá khỏi F, ta vẫn có (E)+ = {DEG} Chứa G
Phủ tối thiểu của F là :
1) A→B
2) A→C
3) D→G
4) E→D
Tìm phủ tối thiểu của lược đồ cho dưới đđây: R = <U, F> với U = (ABCDEGHIJ) và F = {A → BDE, DE → G, H → J, J → HI, E → DG, BC→ GH, HG→J, E→G}
Bước 1. Tách vế phi thành 1 thuộc tính:
- A→B
- A→D
- A→E
- DE→G
- H→J
- J→H
- J→I
- E→D
- E→G
- BC→G
- BC→H
- HG→J
- E→G
Bước 2. Xoá thuộc tính dư thừa
- D dư thừa trong DE→G. Vì (E)+ = {DEG} chứa G
- G dư thừa trong HG→J. Vì (H)+ = {HIJ} chứa J
Bước 3. Xoá phụ thuộc hàm dư thừa:
- A→D dư thừa. Vì nếu xoá khỏi F, ta vẫn có (A)+ = {ABDEG} Chứa D
- E→G dư thừa. Vì nếu xoá khỏi F, ta vẫn có (E)+ = {DEG} Chứa G
- H→J dư thừa. Vì nếu xoá khỏi F, ta vẫn có (H)+ = {HIJ} Chứa J
- E→G dư thừa. Vì nếu xoá khỏi F, ta vẫn có (E)+ = {DEG} Chứa G
Phủ tối thiểu của F là :
- A→B
- BC→H
- A→E
- BC→G
- H→J
- J→H
- J→I
- E→D
- E→G
