1
CHƯƠNG 5
PHỤ THUỘC HÀM
Functional dependency
2
NỘI DUNG
•
PHỤ THUỘC HÀM
•
BÀI TOÁN TÌM PHỦ TỐI THIỂU
•
BÀI TOÁN TÌM KHÓA

Pth là một công cụ biểu diễn một cách hình thức
một dạng ràng buộc tòan vẹn

Pth được ứng dụng trong việc giải quyết bài tóan
tìm khóa, tìm phủ tối thiểu và chuẩn hóa cơ sở dữ liệu
3
PHỤ THUỘC HÀM
•
Khái niệm phụ thuộc hàm
•
Bao đóng của một tập phụ thuộc hàm F
•
Bộ luật dẫn AMSTRONG
•
Bao đóng của tập thuộc tính X
•
Thuật toán tìm F+
4

 Định nghĩa phụ thuộc hàm
Cho lược đồ quan hệ Q(A1,A2,…,An)
X, Y là hai tập con của Q
+
= {A1,A2,…,An}
r là quan hệ trên Q
t1, t2 là hai bộ bất kỳ trên r
X
→
Y
⇔
( t1.X = t2.X
⇒
t1.Y= t2.Y )
- Nếu
∃
t1,t2
∈
r , sao cho t1.X = t2.X và t1.Y ≠ t2.Y
ta nói : pth X
→
Y không thỏa trên r
- Nếu với mọi quan hệ r đều thỏa mãn pth X
→
Y ,
ta nói pth X
→
Y được định nghĩa trên lược đồ
quan hệ Q
7

phụ thuộc hàm hệ quả)
NX : Nếu (1) thỏa mãn thì (4) cũng được thỏa mãn
NX : Nếu (1) thỏa mãn thì (4) cũng được thỏa mãn
⇒
⇒
chỉ
chỉ
cần kiểm tra (1)
cần kiểm tra (1)
1. MB
1. MB
→
→
G
G
2. MB,N
2. MB,N
→
→
PC
PC
3. PC,N,G
3. PC,N,G
→
→
MB
MB
4. MB,N
4. MB,N
→

Bao đóng F
Bao đóng F
+
+
của F
của F
:
:
là tập tất cả các phụ thuộc hàm được suy
là tập tất cả các phụ thuộc hàm được suy
diễn logic từ F
diễn logic từ F

Luật dẫn để suy ra phụ thuộc hàm hệ quả từ F :
Luật dẫn để suy ra phụ thuộc hàm hệ quả từ F :
f’ là phụ thuộc hàm suy từ F qua luật dẫn (ký hiệu F
f’ là phụ thuộc hàm suy từ F qua luật dẫn (ký hiệu F



f’ ) nếu
f’ ) nếu
∃
∃
f
f
1

i
được suy diễn từ f
được suy diễn từ f
j
j
với j=1,…,i-1)
với j=1,…,i-1)Ký hiệu F ’={f’ | F
Ký hiệu F ’={f’ | F




f’}
f’}
⇒
⇒
cần tìm luật dẫn sao cho F ’= F
cần tìm luật dẫn sao cho F ’= F
+
+
; nghóa là
; nghóa là
∀
∀
f, F
f, F
=

Cho quan hệ Q(Q
+
) . X,Y,Z,W là các tập thuộc tính của Q
+
Hệ tiên đề Amstrong gồm các luật sau
(F1) Luật phản xạ (reflexive rule):
Nếu Y
⊆
X thì X
→
Y
(F2) Luật thêm vào (augmentation rule):
Nếu X
→
Y thì XZ
→
Y trong đó ký hiệu XZ thay cho X
∪
Z
(F3) Luật bắc cầu (transitive rule):
Nếu X
→
Y và Y
→
Z thì X
→
Z
Các luật dẫn khác suy từ (F1), (F2), (F3)
Các luật dẫn khác suy từ (F1), (F2), (F3)
(F4) Bắc cầu giả : nếu X

f
f
⇒
⇒
F
F
=
=
f
f Tính đầy đủ :
Tính đầy đủ :
∀
∀
F
F
=
=
f
f
⇒
⇒
F
F


f
f

Y) (2)
⇒
XZ
→
Y (do (1)
⇒
(2))
Luật hợp: giả sử có t1.X = t2.X (1)
⇒
t1.Y = t2.Y và t1.Z = t2.Z
⇒
t1.YZ = t2.YZ (2)
⇒
X
→
YZ (do (1)
⇒
(2))
Luật phân rã: gỉa sử có t1.X = t2.X (1)
⇒
t1.YZ = t2.YZ (do X
→
YZ)
⇒
t1.Y = t2.Y (2)
⇒
X
→
Y (do (1)
⇒

Bài tập 1 : Chứng tỏ các pth sau được suy diễn từ F
nhờ bộ luật dẫn Amstrong ?
F = { B
→
→
A ,
A ,
DA
DA
→
→
CE ,
CE ,
D
→
→
H ,
H ,
AC
→
→
D
D }
AC
→
→
DA
DA
AC
→

GE
GE
→
→
H
H }
?

BD
→
→
EH
EH B
B
→
→
CG
CG
14
Ta có f4 :
Ta có f4 : AC
→
→
D
D
và
và

→
D
D }
Ví dụ
Chứng minh
AC
→
→
DA ?
DA ?
15
Cho Q là lược đồ quan hệ Q( Q
+
), F là tập các phụ
thuộc hàm định nghĩa trên Q , gọi X, A
i

⊆
⊆ Q
+
.
Bao đóng của tập thuộc tính X dựa trên F ký hiệu
là X
+
(hoặc X
+
F
)
X
+

Q
Q
+
+
⇒
⇒Bổ đề :
Bổ đề :
X
X
→
→
Y
Y
∈
∈
F
F
+
+⇔
⇔
Y
Y
⊆
⊆

X
X
+
+
(2) Y
(2) Y
⊆
⊆
X
X
+
+⇒
⇒
X
X
+
+
= Y
= Y
∪
∪
(X
(X
+
+
- Y)
- Y)

0
,X
1
,X
2
, theo phương pháp sau:
Bước 1: X
0
= X
Bước 2: lần lượt xét các phụ thuộc hàm của F
Nếu Y
→
Z có Y
⊆
X
i
thì X
i+1
= X
i

∪
Z
Loại phụ thuộc hàm Y
→
Z khỏi F
Bước 3: Nếu ở bước 2 không tính được X
i+1

thì X

xét f2 vì B
⊆
X1

X2 = AB
∪
C = ABC , lọai f2
xét f3 vì C
⊆
X2

X3 = ABC
∪
D = ABCD , loại f3
xét f4 vì D
⊆
X3

X4 = ABCD
∪
E = ABCDE , loại f4
Bước 3 : X+ = X4 = {ABCDE} là bao đóng của X
18
Ví dụ 2: (sgk )
Cho lược đồ quan hệ Q(ABCDEGH) và tập phụ thuộc
hàm F
F = { f1: B
→
A
f2: DA

xét f3 vì D
⊆
X2

X3 = ACDE
∪
H = ACDEH
Xét f1, f4 :không thỏa vì có vế trái không nằm trong X3
Vậy X3 không thay đổi

X+=X3={ACDEH} là bao đóng của X

AC
→
EH ∈ F+
19
Bài tập 2: Cho Q(ABCDEGH) và tập pth F thỏa trên Q.
Tìm bao đóng của AC ?
F = { B
→
→
A ,
A ,
DA
DA
→
→
CE ,
CE ,
D

GE
GE
→
→
H
H }
AC
+
= ?
B
+
= ?
20
5. Thuật toán tìm F+
Thuật toán cơ bản
Để tính bao đóng F+ của tập các phụ thuộc hàm F ta thực
hiện các bước sau:
•
Bước 1: Tìm tất cả tập con của Q+
•
Bước 2: Tìm tất cả các phụ thuộc hàm có thể có của Q.
•
Bước 3: Tìm bao đóng của tất cả tập con của Q.
•
Bước 4: Dựa vào bao đóng của tất cả các tập con đã tìm
để xác định phụ thuộc hàm nào thuộc F+
Thuật toán cải tiến
Dựa vào thuật toán cơ bản trên, ta nhận thấy có thể tính
F+ theo các bước sau:
Bước 1: Tìm tất cả tập con của Q+


Nếu F
Nếu F
≡
≡
G
G ⇒
F
F
=
=
G
G và
G
G
=
=
F
F ∀
∀
g
g
∈
∈
G +, g: X
G +, g: X
→

=
G
G
Tương tự
Tương tự
∀
∀
f
f
∈
∈
F thì G
F thì G
=
=
f hay G
f hay G
=
=
F
F
Nếu F
Nếu F
=
=
G
G và

G
G
=
=
F
F ⇒
F
F ⊆
G
G + ⇒
F
F +⊆ (
G
G +)+=
G
G +
Tập phụ thuộc hàm F và G tương đương nếu F+ = G+
ký hiệu F
≡
≡
G
G
23
Thuật tóan xác định F và G có tương đương không ?
B1 :với mỗi X
→
→
Y của F xác định xem
Y của F xác định xem X
→

→
D, CD
D, CD
→
→
E
E } và G ={A
→
→
BCE,
BCE, A
→
→
ABD, CD
ABD, CD
→
→
E
E }
1. F có tương đương với G không ?
2. F có tương đương với G’ = { A
→
→
BCDE
BCDE }
1. Nhận xét : F được suy diễn từ G (1)
Ta Kiểm tra G có được suy diễn từ F không ?
Tính A
F
+

→
→
BC,
BC, A
→
→
D, CD
D, CD
→
→
E
E } và
G ={A
→
→
BCE,
BCE, A
→
→
ABD, CD
ABD, CD
→
→
E
E }
1. F có tương đương với G không ?
2. F có tương đương với
G’ = { A
→
→