H-íng dÉn «n tËp CSDL quan hÖ
Tµi liÖu tham kh¶o Trang 27
DẠNG 7: TÌM KHOÁ TỐI THIỂU CỦA QUAN HỆ
Bài toán: Cho quan h R(U, F). Hãy tìm một khoá tối thiểu của R.
Kiến thức liên quan: Cho quan hệ R(U, F), X ⊆ U.
X được gọi là khoá của R nếu X
+
≡ U.
X được gọi là một khoá tối thiểu của R nếu: X là khoá của R và X tối thiểu (tức
không tồn tại một tập con thực sự nào của X mà tập con đó cũng là khoá của R).
Giải thuật tìm khoá tối thiểu của R:
B1: Đặt K
0
= {U}
B2: Tính K
1
= K
0
∪ Z nếu ∃ Y → Z mà Y ∈ K
0

...
Tính K
i
= K
i-1
∪ Z nếu ∃ Y → Z mà Y ∈ K
i-1

Lặp cho tới khi K
i

= {AB} vì AB → C và AB ∈ K
3

K
5
≡ K
4

Vậy {AB} là một khóa tối thiểu của R.
Chú ý: Với một quan hệ R(U, F) cho trước có thể tồn tại nhiều khóa tối thiểu
khác nhau, tùy thuộc vào thứ tự loại bỏ các thuộc tính trong giải thuật. Chẳng hạn, với ví
dụ trên, ta có thể thu được một khóa khác bằng cách loại B đi ngay từ đầu:
Đặt K
0
= {A,B,C,D,E,G,H}
K
1
= {ABCDEG} vì E → H và E ∈ K
0

K
2
= {ACDEG} vì G → B và G ∈ K
1

K
3
= {ACD} vì C → EG và C ∈ K
2