Tập phụ thuộc hàm không dư thừa

F là tập PTH không dư thừa nếu không tồn tại F’ ⊂ F sao cho F’ ≡ F.

Ví dụ: Cho F = {A ®BC, B ®D, AB ®D} F là dư thừa vì F≡F’={ A ®BC, B ®D}

Thuật toán loại khỏi F các phụ thuộc hàm dư thừa

• Input: Tập PTH F
• Output: Tập F không có PTH dư thừa
• Thuật toán:
  • Bước 1: Với mỗi PTH X ® Y trong F
  • Bước 2: Nếu X ® Y là thành viên của F – {X ® Y} thì loại X ® Y khỏi F
  • Bước 3: Lặp lại bước 2 cho đến khi hết các PTH cần xét

Ví dụ:

Cho F = {A ®BC, B ®D, AB ®D}. Tìm tập phụ thuộc hàm không dư thừa.

Giải:

1. Giả sử A ® BC là dư thừa F={B ® D, AB ® D}
   Kiểm tra A ® BC có là thành viên của F: A+={A} ta thấy BC ∉ A+
   Vậy: A ® BC không dư thừa
2. Giả sử B->D là dư thừa: F={A ® BC; AB ® D}
   Tính: B+ = {B} ta thấy D ∉ B+

=> B ® D không dư thừa

3. Xét AB ® D: F={A ® BC; B ® D}

Tính (AB)+ = {ABCD} ta thấy D ∈ (AB)+

=> Vậy: AB ® D là dư thừa

Kết luận: F ≡ { A ®BC, B ®D } là tập phụ thuộc hàm không dư thừa