Tập phụ thuộc hàm tối thiểu

F được gọi là tập phụ thuộc hàm tối thiểu F_tt (phủ tối thiểu) nếu F thỏa mãn đồng thời các điều kiện sau:

1. F là tập phụ thuộc hàm có vế trái không dư thừa
2. F là tập phụ thuộc hàm có vế phải một thuộc tính
3. F là tập phụ thuộc hàm không dư thừa

Thuật toán tìm phủ tối thiểu của một tập phụ thuộc hàm

Input: Tập phụ thuộc hàm F

Output: Phủ tối thiểu của F

Các bước:

Bước 1: Loại khỏi F các phụ thuộc hàm có vế trái dư thừa

Bước 2: Tách các phụ thuộc hàm có vế phải nhiều hơn một thuộc tính thành các phụ thuộc hàm có vế phải một thuộc tính

Bước 3: Loại khỏi F các phụ thuộc hàm dư thừa

Lưu ý:

• Với thuật toán trên ta luôn tìm được ít nhất một phủ tối thiểu F_tt ≡ F
• Nếu ta thay đổi trật tự loại bỏ các phụ thuộc hàm trong F thì ta có thể tìm được các phủ tối thiểu khác nhau.

Ví dụ 1:

Cho tập F={ A → BC, B → C, AB → D}. Tìm phủ tối thiểu của F

Giải:

Bước 1: Xét phụ thuộc hàm AB → D có A+={ABCD} nên A → D Î F⁺  thay AB → D bằng A → D và

F≡{ A → BC, B → C, A → D }

Bước 2: Tách phụ thuộc hàm A → BC ta được

F≡{ A → B, A → C, B → C, A → D }

Bước 3: Kiểm tra xem các phụ thuộc hàm có dư thừa hay không

• Giả sử A → B dư thừa khi đó F = { A → C, B → C, A → D }

Tính A+ = {ACD} ta thấy B ∉ A+ nên A → B không dư thừa.

• Giả sử A → C dư thừa khi đó F= { A → B, B → C, A → D }

Tính A+={ABCD} ta thấy C ∈ A+ nên A → C dư thừa

F≡{ A → B, B → C, A → D }

• Giả sử B → C dư thừa khi đó F={ A → B, A → D }

Tính B+ ={B} ta thấy C ∉ B+ nên B → C không dư thừa

• Giả sử A → D dư thừa khi đó F= { A → B, B → C }

Tính A+={ABC} ta thấy D ∉ A+ nên A → D không dư thừa

Kết luận: Phủ tối thiểu của tập F đã cho là

Ftt={ A → B, B → C, A → D }

Ví dụ 2: Cho F={AB ®CD, B ®C, C ®D}. Tìm tập phụ thuộc hàm tối thiểu

Giải:

Bước 1: Loại PTH có vế trái dư thừa:

Xét AB ® CD, giả sử dư A cần CM B ® CD là thành viên của F: B+={BCD} => đúng nên dư A.

Khi đó F = {B ® CD; B ® C; C ® D}

Bước 2: Đưa về dạng PTH có vế phải 1 thuộc tính

F = {B ® C; B ® D; C ® D}

Bước 3: Loại khỏi F các PTH dư thừa

Dễ thấy B ® D là dư thừa vì B ® C và C ® D

Vậy phủ tối thiểu của Ftt = {B ® C; C ® D}