Tìm phủ tối thiểu

 Tìm phủ tối thiểu của 1 tập Phụ thuộc hàm

Hướng dẫn – Tìm phủ tối thiểu của 1 Phụ thuộc hàm (minimal cover)

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

1. Tách các phụ thuộc hàm sao cho vế phải chỉ còn một thuộc tính. (ví dụ: A->BC thành A->B và A->C)

2. Bỏ các thuộc tính dư thừa ở vế trái. (ví dụ: cho F = {A → B, B → C, AB → D} các phụ thuộc hàm có vế trái 1 thuộc tính là đầy đủ nên ta không xét, xét AB → D có B dư thừa(bỏ B) vì bao đóng của A có chứa B. A+=ABC) (dễ hiểu là chúng ta bỏ thuộc tính bên vế trái, khi và chỉ khi bao đóng của các thuộc tính còn lại có chứa thuộc tính đó)

3. Loại khỏi F các phụ thuộc hàm dư thừa. (Các thuộc tính ở vế phải của PTH chỉ xuất hiện di nhất 1 lần thì không thể loại bỏ. Còn lại tính bao đóng của tập thuộc tính vế trái nếu có xuất hiện thuộc tính vế phải thì có thể loại bỏ thuộc tính đó và đó là PTH dư thừa.)

Ví dụ: Cho lược đồ quan hệ Q(A,B,C,D) và tập pth F={AB->CD, B->C, C->D} Tìm phủ tối thiểu?

1. Tách các phụ thuộc hàm sao cho vế phải chỉ còn một thuộc tính.

+ ta có F={AB->C, AB->D, B->C, C->D}

2. Bỏ các thuộc tính dư thừa ở vế trái.

+ B->C, C->D Không xét vì vế trái chỉ có một thuộc tính.

+ xét AB->C : Nếu Bỏ A thì B+=BCD không chứa A nên không thể Bỏ A. Nếu Bỏ B thì A+=A. không bỏ được thuộc tính nào.

+ xét AB->D : Nếu Bỏ A thì B+=BCD không chứa A nên không thể Bỏ A. Nếu Bỏ B thì A+=A. không bỏ được thuộc tính nào.

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

+ xét AB->C : Tính AB+=ABCD = Q nên loại bỏ AB->C

+ xét AB->D : tính AB+=ABCD = Q nên loại bỏ AB->D

+ B->C : tính B+=B không thể bỏ.

+ C->D : tính C+=C không thể bỏ.

Phủ tối thiểu là Ftt = {B->C, C->D}