Phủ tối thiểu (Minimal cover)

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 X A in Fc  For each attribute B that is an element of X  If { {Fc- {XA}} U { (X- {B}) A }}  Fc then replace X A with (X-{B})  A in Fc 4. For each X A in Fc if {Fc- {XA}}  Fc then remove X A from Fc Return Fc 4 Ví dụ  Cho F={ BA, DA, AB D}. 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 ABD có thuộc tính dư thừa vế trái không? Có thể thay thế bởi AD hay BD  F’= (F – {ABD})  {AD} = ={ BA, DA, B D}.  Cần chứng minh F  F’  Từ F ta có B A AB  D ⟹ B AB ⟹ 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 AB D  F’ ={ BA, DA, B  D} 5 Ví dụ  Bước 4:  F’= { BA, DA, B  D}  Vì B  D và DA  BA. FD BA là dư thừa  𝐾ế𝑡 𝑙𝑢ậ𝑛 𝐹𝑐 " = {𝐷 → 𝐴, 𝐵 → 𝐷} là phủ tối thiểu 6 Lược đồ tổng hợp thành 3NF  Input R(U,F) 1. Tìm phủ tối thiểu G 2. Đối với FD có vế trái X trong G, tạo 1 lược đồ quan hệ với thuộc tính {X {A1} {A2}{Ak}, với XA1, X A2,, XAk 3. Nếu không có lược đồ nào trong D chứa khóa của R, tạo thêm 1 lược đồ trong D chứa các thuộc tính của khóa 4. Loại bỏ quan hệ dư thừa khỏi D. Một quan hệ được gọi là dư thừa nếu nó là phép chiếu của 1 quan hệ khác trong D 7 Ví dụ  Cho phủ tối thiểu G sau, hãy tổng hợp thành các lược đồ quan hệ :  {Emp  Esal, Ephone, Dno; Pno  Pname, Plocation}. Khóa chính của lược đồ là Emp, Pno.  Áp dụng giải thuật, sau bước 2 có 2 lược đồ:  R1(Emp_ssn, Esal, Ephone, Dno)  R2(Pno, Pname, Plocation)  Bước 3: tạo thêm 1 quan hệ mới tương đương với khóa của R {Emp_ssn, Pno}  Kết quả là có 3 lược đồ  R1(Emp_ssn, Esal, Ephone, Dno)  R2(Pno, Pname, Plocation)  R3(Emp_ssn, Pno} 8