. Phụ thuộc hàm có vế trái dư thừa

Gọi F là tập phụ thuộc hàm của quan hệ R(U)và X, Y  ⊆U, X → Y ∈ F.

Nói rằng phụ thuộc hàm X → Y có vế trái dư thừa (phụ thuộc không đầy đủ) nếu có thuộc tính A ∈ X sao cho:

F≡F – { X → Y }∪{ (X-A) → Y }

Nói một cách khác ta không thể thay thế bất kì một phụ thuộc hàm X → Y trong F bằng một phụ thuộc hàm A → Y mà A là tập con của X mà vẫn được tập phụ thuộc hàm tương đương với F ban đầu (Không có thuộc tính dư thừa ở vế trái của phụ thuộc hàm)

Ví dụ:

Cho tập phụ thuộc hàm F={ A → BC, B → C, AB → D} ta thấy phụ thuộc hàm AB → D có vế trái dư thừa B vì

F≡ F – { AB → D}∪{ A → D }

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

Ta nói F là tập phụ thuộc hàm có vế trái không dư thừa nếu F không chứa các phụ thuộc hàm có vế trái dư thừa.

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

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

Output: Tập phụ thuộc hàm F không chứa phụ thuộc hàm có vế trái dư thừa

Các bước thực hiện:

• Bước 1: Với mỗi pth X ® Y của F thì thực hiện bước 2
• Bước 2: Với mỗi A Î X, nếu A ® YÎ F⁺  thì thay X ® Y bằng A ® Lặp lại bước 2 đến khi vế trái X không dư thừa

Ví dụ: Cho tập F={ A → BC, B → C, AB → D}

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

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