H-íng dÉn «n tËp CSDL quan hÖ
Tµi liÖu tham kh¶o Trang 23
DẠNG 6: PHỦ TỐI THIỂU CỦA MỘT TẬP PHỤ THUỘC HÀM
Bài toán: Cho quan hệ R(U, F). Hỏi rằng tập F đã tối thiểu chưa? Vì sao? Nếu
chưa hãy tìm một Phủ tối thiểu của F.
Kiến thức liên quan:
Ta chú ý tới một số khái niệm sau:
[1]. Phụ thuộc hàm dư thừa: Phụ thuộc hàm X → Y thuộc F được gọi là dư thừa
trong F nếu ta loại bỏ nó ra khỏi F ta vẫn thu được nó từ các phụ thuộc hàm còn lại trong F.
VD: F = {AB → C, B → C, C → D, B → D}
Có AB → C dư thừa vì nếu có B → C thì cũng có AB → C.
Có B → D dư thừa vì nếu có B → C và C → D thì cũng có B → D.
Để phát hiện phụ thuộc hàm dư thừa ta chú ý: Nếu trong tập F có 2 phụ thuộc hàm
cùng có vế phải giống nhau thì trong 2 phụ thuộc hàm đó có thể tồn tại 1 phụ thuộc hàm
dư thừa. Ngược lại, nếu X → Y mà trong F không còn phụ thuộc hàm nào cũng có vế
phải là Y (cũng suy ra Y) thì nó không thể dư thừa.
Cách xác định phụ thuộc hàm dư thừa : Phương pháp này được minh họa bằng
ví dụ sau :
Cho F = {AB → C, AB → D, B → C, D → EG, AB → G}. Hãy xác định phụ
thuộc hàm dư thừa trong F.
B1. Ta chia các phụ thuộc hàm thành các cột theo nguyên tắc: Các phụ thuộc hàm
có vế phải giống nhau sẽ được xếp chung vào một cột:
AB → C

B → C
AB → D D → E D → G
AB → G
B2. Loại bỏ các cột có 1 phụ thuộc hàm, ta còn:
Cột 1 Cột 2
AB → C
B → C

Ví dụ: F={A→B, AB→C, B→ E, AE → G}
Xét AB → C có B dư thừa. Thật vậy, ta có thể chứng minh A → C
(A → B; A → AB; AB → C; AB → C)
Xét AE → G có E dư thừa. Thật vậy, ta có thể chứng minh A → G
(A→B; B → E; A → E; A → AE; AE → G; A → G)
Nếu phụ thuộc hàm nào có vế trái có chỉ 1 thuộc tính thì nó không có thuộc tính vế
trái dư thừa. Ngược lại nếu phụ thuộc hàm nào có vế trái từ hai thuộc tính trở lên thì có
thể có thuộc tính vế trái dư thừa.
Cách xác định thuộc tính vế trái dư thừa: Phương pháp này cũng được minh họa
bằng ví dụ sau :
Cho F = {A → C, AC → D, B → C, C → G, BG → E}. Hãy xác định thuộc tính
vế trái dư thừa trong F.
B1 : Chia các phụ thuộc hàm làm 2 cột theo nguyên tắc : các phụ thuộc hàm có vế
trái là 1 thuộc tính được xếp vào một cột, cột còn lại là các phụ thuộc hàm có vế trái
nhiều thuộc tính :
Cột 1
Cột 2
A → C
B → C,
C → G
AC → D
BG → E

B2. Chỉ xét các phụ thuộc hàm có vế trái nhiều thuộc tính (cột 2). Giả sử ta xét phụ
thuộc hàm có dạng XY → Z. Ta cần kiểm tra lần lượt xem X hay Y có dư thừa hay
không. Giả sử ta kiểm tra tính dư thừa của Y, ta tính X
+
. Nếu X
+
chứa Y thì Y thừa.

B3: Loại bỏ các thuộc tính vế trái dư thừa trong F2 ta thu được F3.
F3 là tập phụ thuộc hàm tối thiểu thu được từ F. F3 gọi là một phủ tối thiểu của F.
Ví dụ: Cho tập phụ thuộc hàm sau:
F={A→C, AB→C, B→ EG, BE → D, C → H, A → H}
Hỏi F đã tối thiểu chưa? vì sao? nếu chưa hãy tìm một phủ tối thiểu của F.
Trả lời:
F chưa tối thiểu vì còn tồn tại B → EG có vế phải 2 thuộc tính.
Tìm Phủ tối thiểu của F:
B1: Tách các phụ thuộc hàm có vế phải nhiều thuộc tính thành các phụ thuộc
hàm có vế phải 1 thuộc tính ta thu được:
F1 ={A→C, AB→C, B→ E, B → G, BE → D, C → H, A → H}
B2: Loại bỏ phụ thuộc hàm dư thừa trong F2:
AB → C là thừa vì nếu có A → C thì cũng có AB → C.
A → H là thừa vì nếu có A → C và C → H thì cũng có A → H.
Vậy ta thu được:
F2 ={A→C, B→ E, B → G, BE → D, C → H}
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
H-íng dÉn «n tËp CSDL quan hÖ
Tµi liÖu tham kh¶o Trang 26
B3: Loại bỏ thuộc tính vế trái dư thừa:
Xét BE → D có E thừa. Thật vậy, ta sẽ chứng minh B → D.
B → E (gt)
B → BE (TT)
BE → D (gt)
B → D (BC)
(hoặc có thể tính B
+
= {BEGD} do vậy B → D)
Vậy ta thu được: