Bài tập phụ thuộc hàm
Các dạng bài tập
1. Tìm tập bao đóng của một tập thuộc tính
2. Kiểm tra một tập thuộc tính có phải là khóa không
3. Kiểm tra 2 tập phụ thuộc hàm có tương đương
4. Kiểm tra 1 phụ thuộc hàm có được suy diễn từ tập
phụ thuộc hàm cho trước
5. Tìm tất cả các khóa
6. Tìm phụ thuộc hàm dư thừa
7. Tìm tập bao phủ tối thiểu
8. Xác định chuẩn hóa và chuẩn hóa dữ liệu
Cách làm
•
Dạng 1:
–
Giải thuật tìm tập bao đóng
Cách làm
•
Dạng 1
–
Ví dụ
–
Cho tập phụ thuộc hàm:
–
Tìm tập bao đóng của tập thuộc tính:
•
A+, B+, AB+, AE+
Cách làm
•
Dạng 2
–

–
F và G tương đương khi và chỉ khi:
•
Mọi phụ thuộc hàm của F được suy ra từ G
•
Mọi phụ thuộc hàm của G được suy ra từ F
–
Kiểm tra từng phụ thuộc hàm của F và G như trên
–
2 tập phụ thuộc hàm này có tương đương:
Cách làm
•
Dạng 5: Tìm tất cả các khóa
–
We have: (U = R)
–
UL and UR are the set of LHS and RHS attributes
–
N = U – UR is the set of independent attributes and those which only
appear on LHS  N must be a part of keys
–
If N+ = R, then N is a minimal key  Stop here!
–
Otherwise:
–
D = UR – UL is the set of attributes which only appears in RHS  D
cannot be a part of key
–
L = U – (N ∪ D) is the set of attributes which may or may not be a part
of keys

Lưu ý: ta có thể tìm phụ thuộc hàm dư thừa
trước để giảm số lượng phụ thuộc hàm trong
bước tìm thuộc tính dư thừa, như cách sau:
Cách làm
•
Dạng 7:
–
Bước 1: Phân rã để vế phải còn 1 thuộc tính (dạng canonical form)
–
Bước 2: Loại bỏ thuộc tính dư thừa
Với mỗi phụ thuộc hàm X  A
Xét mỗi thuộc tính B trong X
Tính (X-B)+ đối với (X->A) thay bằng (X-B)  A
Nếu (X-B)+ chứa B thì thay X A thành X-B A
–
Bước 3: Loại bỏ phụ thuộc hàm dư thừa
•
Như dạng 6
–
Ghi chú: ta nên thực hiện bước 3 trước bước 2 để giảm công sức tính
toán
Ví dụ: tìm phủ tối thiểu:F = {AB→D, B→C,
AE→B, A→D, D→EF}
•
Bước 1: đưa về chuẩn canonical form
•
F = {AB  D, B  C, AE  B, A  D, D  E, DF}
•
Bước 2: tìm phụ thuộc hàm dư thừa
–

Bài tập kết hợp
•
Đáp án:
•
a. FDs = {AE, ED, BDE, FA, E B,
DH, BGF, CDA}