Học viện công nghệ BƯu chính viễn thông khoa viễn thông 1 Bài giảng Học phần: CƠ SỞ DỮ liệU

129 
- (Đk2) Với ∀ f = X→Y ∈ F
c
, !
∃ A ∈ X (A là 1 thuộc tính) mà (F
c
\ f) U {(X \ 
A)→Y} 
≅ F
c
- (Đk3) !∃ X→A ∈ F
c
và F
c
\ {X→A} 
≅ F
c
Thuật toán: Tìm phủ tối thiểu của một tập phụ thuộc hàm 
Đầu vào: Tập hữu hạn các thuộc tính U = {A
1
, A
2
, …, A
n
}, tập các phụ 
thuộc hàm F trên U, F = {L
i
→ 
R
i
| i = 1..n} 
Đầu ra: phủ tối thiểu F
c
của tập phụ thuộc hàm F 
Thuật toán 
B1: Biến đổi F về dạng F
1
={L
i
→ A
j
} trong đó A
j
là 1 thuộc tính bất kỳ 
thuộc U (thỏa mãn Đk1) 
B2: Loại bỏ thuộc tính thừa trong vế trái của các phụ thuộc hàm. Lần lượt 
giản ước từng thuộc tính trong vế trái của từng phụ thuộc hàm trong F
1
thu 
được F
1
’. Nếu F
1
’ ≅ F
1
thì loại bỏ thuộc tính đang xét
Khi không có sự giản ước nào xảy ra nữa, thu được F
2
thỏa mãn Đk2 
B3: Loại bỏ phụ thuộc hàm dư thừa. Lần lượt kiểm tra từng phụ thuộc hàm 
f. Nếu F
2
\ f 
≅ F
2
thì loại bỏ f. Khi không còn phụ thuộc hàm nào có thể 
loại bỏ thì thu được F
3
thoả mãn Đk3 
B4: F
c
= F
3
Bảng 4.6: Phủ tối thiểu của một tập phụ thuộc hàm. 
Ví dụ: U = {A,B,C} 
F = {A→BC, B→C, A→B, AB→C}.
Tìm phủ tối thiểu của F? 
Thực hiện: 
- Bước 1: F
1
= {A→B, A→C, B→C, AB→C} 

130 
- Bước 2: Xét các phụ thuộc hàm trong F
1
mà vế trái có nhiều hơn 1 thuộc tính, 
chỉ có AB→C. Giản ước A thì ta còn B→C có trong F
1
, vậy A là thuộc tính thừa. 
Tương tự ta cũng tìm được B là thừa, vậy loại bỏ luôn AB→C khỏi F
1
. F
2
= 
{A→B, A→C, B→C} 
- Bước 3: Bỏ phụ thuộc hàm thừa: A→C là thừa. Vậy F
c
= {A→B, B→C} 

tải về 4.98 Mb.

Chia sẻ với bạn bè của bạn: