1
Phủtối thiểu –Minimal cover
Phủ tối thiểu Fc của F là tập FD nh nht sao cho 𝐅+= 𝑭𝒄
+
Minimal Cover for a given set of FDs is not unique.
2
Phủtối thiểu –Minimal cover
Tập phụ thuộc hàm Fcđưc gọi là tối thiểu (minimal) nếu
tha mãn các tính cht sau:
Vế phi của mọi FD đu là thuộc tính đơn
Nếu gim bt k thuộc tính nào bên vế trái của mi FD, tập phụ
thuộc mới sẽ không tương đương với phụ thuộc hàm ban đầu.
Không thể loi b bt k FD nào khi Fc vẫn đưc tập phụ
thuộc hàm tương đương với tập Fc ban đầu.
3
Giải thuật tìm phủtối thiểu
Input: tập phụ thuộc hàm F
Output: Fc là 1 phủ tối thiểu của F
1. Fc:=F
2. Biến đổi tt c FD thành thuộc tính đơn bên phía phi
3. for each XA in Fc
For each attribute B that is an element of X
If { {Fc- {XA}} U { (X- {B}) A }} Fc then replace XA with (X-{B}) A
in Fc
4. For each XA in Fc
if {Fc- {XA}} Fc then remove XA from Fc
Return Fc
4
Ví dụ
Cho F={ BA, DA, ABD}. Tìm phủ tối thiểu của F
Bước 2: tt c FD đu có vế phi là thuộc tính đơn
Bước 3:
Với ABD có thuộc tính dư thừa vế trái không? Có thể thay thế bởi
AD hay BD
F’= (F – {ABD}) {AD} = ={ BA, DA, BD}.
Cần chứng minh F F’
Từ F ta có BA
AB D⟹BAB ⟹ B D F F’ F F’
Từ F’ ta có B D AB D F’ F
Kết luận A là thuộc tính dư thừa của ABD
F’ ={ BA, DA, B D}
5