CHƯƠNG 5 PHỦ CỦA TẬP PHỤ THUỘC HÀM
I ĐỊNH NGHĨA
Nói rằng hai tập phụ thuộc hàm F và G là tương đương (Equivalent) nếu F
+
=
G
+

ký hiệu F ≡ G.
Ta nói F phủ G nếu F
+
⊇ G
+
Thuật toán xác đònh F và G có tương đương không
Bước 1: Với mỗi phụ thuộc hàm X
→
Y của F ta xác đònh xem X
→
Y có là thành
viên của G không
Bước 2: Với mỗi phụ thuộc hàm X
→
Y của G ta xác đònh xem X
→
Y có là thành
viên của F không
Nếu cả hai bước trên đều đúng thì F
≡
G
Ví dụ 1: Cho lược đồ quan hệ Q(ABCDE) hai tập phụ thuộc hàm:
F={A→BC,A→D,CD→E} và G = {A→BCE,A→ABD,CD→E}

= G
+
⇒ F ≡ G.
b) Do
+
'
)(
G
CD
= CD ⇒ G’
+
không chứa phụ thuộc hàm CD→E ⇒ F
không tương đương với G’
II PHỦ TỐI THIỂU CỦA MỘT TẬP PHỤ THUỘC HÀM (minimal cover)
1 Phụ thuộc hàm có vế trái dư thừa
F là tập các phụ thuộc hàm trên lược đồ quan hệ Q, Z là tập thuộc tính, Z→Y∈F.
Nói rằng phụ thuộc hàm Z
→
Y có vế trái dư thừa (phụ thuộc không đầy đủ)
nếu có một A
∈
Z sao cho:
F
≡
F-{Z
→
Y}
∪
{(Z-A)
→

+
thì thay X
→
Y trong F bằng X'
→
Y thực hiện lại
bước 2
Ví dụ: Ở ví dụ 3 phụ thuộc hàm AB→D có A
+
=ABCD ⇒ A→D∈F
+
. Trong F ta
thay AB→D bằng A→D ⇒ F ≡ {A → BC,B → C,A → D}
2 Tập phụ thuộc hàm có vế phải một thuộc tính (the right sides of
dependencies has a single attribute)
Mỗi tập phụ thuộc hàm F đều tương đương với một tập phụ thuộc hàm G mà vế
phải của các phụ thuộc hàm trong G chỉ gồm một thuộc tính.
Ví dụ 4: cho F = {A → BC,B → C,AB → D} ta suy ra
F ≡ {A → B, A → C ,B → C,AB → D} = G
G được gọi là tập phụ thuộc hàm có vế phải một thuộc tính.
3 Tập phụ thuộc hàm không dư thừa
Nói rằng F là tập phụ thuộc hàm không dư thừa nếu không tồn tại F’⊂ F sao
cho F’≡ F. Ngược lại F là tập phụ thuộc hàm dư thừa.
Ví dụ: cho F = {A→BC, B→D, AB→D} thì F dư thừa vì
F ≡ F’= {A→BC, B→D}
Thuật toán loại khỏi F các phụ thuộc hàm dư thừa:
Bước 1: Lần lượt xét các phụ thuộc hàm X
→
Y của F
Bước 2: nếu X

Bước 1: AB→CD là phụ thuộc hàm có vế trái dư thừa?
B → CD ∈ F
+
? trả lời: B
+
=BCD ⇒ B → CD ∈ F
+
Vậy AB → CD là phụ thuộc hàm có vế trái dư thừa A ⇒ kết quả của
bước 1 là:
F≡{B → CD;B → C;C → D}
Bước 2: kết quả của bước 2 là:
F≡{B → D; B → C;C → D}=F
1tt
Bước 3: trong F
1tt
, B → C là phụ thuộc hàm dư thừa?
B → C ∈ G
+
? với G = F
1tt
- {B → C}={B → D;C → D}
B
G
+
=BD ⇒ B → C ∉ G
+
⇒ trong F
1tt
B → C không dư thừa.
trong F

= {MSCD → CD;
CD → MSCD;
CD,HG → MSSV;
MSCD,MSSV → HG}
III KHÓA CỦA LƯC ĐỒ QUAN HỆ (Key)
1 Đònh Nghóa
Q(A
1
,A
2
,…,A
n
)là lược đồ quan hệ.
Q
+
là tập thuộc tính của Q.
F là tập phụ thuộc hàm trên Q.
K là tập con của Q
+
.
Nói rằng K là một khóa của Q nếu:
1. K
+
= Q
+
và
2. Không tồn tại K'
⊂
K sao cho K’
+

Ta được một khóa là của lược đồ quan hệ là {C,G,H}
(Lưu ý là thuật toán này chỉ nên sử dụng trong trường hợp chỉ cần tìm một
khóa).
2 Thuật toán tìm tất cả khóa
i Thuật toán cơ bản
Bước 1: Xác đònh tất cả các tập con khác rỗng của Q
+
. Kết quả tìm được
giả sử là các tập thuộc tính X
1
, X
2
, …,X
2
n
-1
Bước 2: Tìm bao đóng của các X
i
Bước 3: Siêu khóa là các X
i
có bao đóng đúng bằng Q
+
. Giả sử ta đã có
các siêu khóa là S = {S
1
,S
2
,…,S
m
}

CZ CZ
SZ SZC SZ SZ
CS
Z
CSZ CSZ
Vậy lược đồ quan hệ Q có hai khóa là: {C,S} và {S,Z}