Ví dụ 1: Cho lược đồ R (A, B, C) và tập PTH
F = {A -> BC, C -> AB}. Tìm phủ tối thiểu của F
(1)Phân rã: G = {A -> B, A -> C, C -> A, C -> B}
(2)Loại bỏ PTH dư thừa
Xét A -> B, kiểm tra A -> B Î (G\{A -> B})+
Tính bao đóng A+ theo G\{A -> B}
A+ = ABC ' B => A -> B dư thừa, loại bỏ A -> B
G = {A -> C, C -> A, C -> B}
Tương tự xét A -> C, C -> A, C -> B không dư thừa
(3) Loại bỏ thuộc tính dư thừa
Vì vế trái của tất cả các PTH đều có một thuộc tính nên không xét bước 3
Vậy G là phủ tối thiểu
TIM BAO ĐÓNG
-Phương pháp:
(1) Đặt X0 = X
(2) Giả sử đã có Xk-1. Tính Xk
Đặt Xk = Xk-1
Duyệt lần lược các PTH U -> V Î F
Nếu U Í Xk, VË Xk thì thay Xk = Xk È V
Nếu Xk = R thì thuật toán kết thúc, ta có X+ = R
(3) Điều kiện kết thúc: Xk = R hoặc Xk = Xk-1 (*)
Nếu (*) đúng thì kết thúc X+ = Xk
Ngược lại tăng k lên 1 và quay về bước 2