1

2

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.

3

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.

thuộc hàm tương đương với tập Fc ban đầu.

 Không thể loại bỏ bất kỳ FD nào khỏi Fc vẫn được tập phụ

4

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

5

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

⟹ B AB

 Từ F ta có

⟹ B  D  F  F’  F  F’

 F’= (F – {ABD})  {AD} = ={ BA, DA, B D}.  Cần chứng minh F  F’ B A AB  D

 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}

6

Ví dụ

 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

 Bước 4:

 𝐾ế𝑡 𝑙𝑢ậ𝑛 𝐹𝑐

7

Lược đồ tổng hợp thành 3NF

 Input R(U,F)

1. Tìm phủ tối thiểu G

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

2. Đối với FD có vế trái X trong G, tạo 1 lược đồ quan hệ với thuộc

nếu nó là phép chiếu của 1 quan hệ khác trong D

4. Loại bỏ quan hệ dư thừa khỏi D. Một quan hệ được gọi là dư thừa

8

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 đồ:

 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}

 R1(Emp_ssn, Esal, Ephone, Dno)  R2(Pno, Pname, Plocation)

 R1(Emp_ssn, Esal, Ephone, Dno)  R2(Pno, Pname, Plocation)  R3(Emp_ssn, Pno}

 Kết quả là có 3 lược đồ