HeCSDL
1
NN
NN
CHƯƠNG
CHƯƠNG
Ph
Ph
ụ
ụ
thu
thu
ộ
ộ
c h
c h
à
à
m
m
(Functional Dependency)
(Functional Dependency)
HeCSDL 2
NN
NN
N
N
ộ
ộ
i dung
i dung

c d
c d
ữ
ữ
li
li
ệ
ệ
u
u
 Dư thừa (redundancy): Họ tên của các sinh viên
được lặp lại mỗi lần cho mỗi môn thi.
 Mâu thuẫn tiềm ẩn (potentia inconsistancy)
hay bất thường khi cập nhật. Do hậu quả của dư
thừa, chúng ta có thể cập nhật họ tên của một sinh
viên trong một bộ nào đó nhưng vẫn để lại họ tên
cũ trong những bộ khác
HeCSDL 4
NN
NN
C
C
á
á
c v
c v
ấ
ấ
n đ
n đ

NN
NN
Dư th
Dư th
ừ
ừ
a d
a d
ữ
ữ
li
li
ệ
ệ
u
u
(Data redundancy)
(Data redundancy)
 Mục đích của thiết kế CSDL là gom các
thuộc tính thành các quan hệ sao cho
giảm thiểu dư thừa dữ liệu
 Hậu quả của dư thừa dữ liệu:
 Lãng phí không gian đĩa
 Các bất thường khi cập nhật
 Ba loại bất thường:
 Bất thường khi thêm vào
 Bất thường khi xóa bỏ
 Bất thường khi sửa đổi
5
HeCSDL 6

John Doe
John Doe
Mary Doe
Mary Doe
Mary Doe
Mary Doe
Bart Simpson
Bart Simpson
123 Main St.
123 Main St.
123 Main St.
123 Main St.
7 Lake Dr.
7 Lake Dr.
7 Lake Dr.
7 Lake Dr.
Fox 5 TV
Fox 5 TV
Stamps
Stamps
Coins
Coins
Hiking
Hiking
Skating
Skating
Acting
Acting
 Khóa chính của bảng PERSON?
Î SSN + Hobby

 Phụ thuộc hàm (functional dependancy) là
một công cụ dùng để biểu diễn một cách
hình thức các ràng buộc toàn vẹn.
 Dựa vào phụ thuộc hàm để thiết kế lại
CSDL, loại bỏ các dư thừa dữ liệu
7
HeCSDL 8
NN
NN
Ph
Ph
ụ
ụ
thu
thu
ộ
ộ
c h
c h
à
à
m
m
(Functional Dependency)
(Functional Dependency)
 Cho lược đồ quan hệ R(U), r là 1 quan hệ
bất kỳ trên R, X và Y là 2 tập thuộc tính con
của U.
 Định nghĩa: Phụ thuộc hàm (FD) f: X Æ Y
trên lược đồ quan hệ R nếu và chỉ nếu mỗi

tồn tại hai bộ trong r có các thuộc tính trong tập X
giống nhau mà lại có một hay nhiều thuộc tính
trong tập Y khác nhau).
 Khi đó ta ký hiệu là X → Y.
9
HeCSDL 10
NN
NN
Gi
Gi
ả
ả
i thu
i thu
ậ
ậ
t ki
t ki
ể
ể
m tra ph
m tra ph
ụ
ụ
thu
thu
ộ
ộ
c h
c h

a1 b1 c2 d1 e2 f3
a2 b1 c2 d3 e2 f3
a3 b2 c3 d4 e3 f2
a2 b1 c3 d3 e4 f4
a4 b1 c1 d5 e1 f1 HeCSDL 12
NN
NN
T
T
ậ
ậ
p ph
p ph
ụ
ụ
thu
thu
ộ
ộ
c h
c h
à
à
m
m
 Gọi F là 1 tập phụ thuộc hàm trên R nếu mọi phụ
thuộc hàm trong F đều là phụ thuộc hàm trên R

tiên đ
tiên đ
ề
ề
Amstrong
Amstrong
 Phụ thuộc hàm X Æ Y được suy diễn luận
lý từ F nếu mọi quan hệ thỏa mãn mọi
phụ thuộc hàm trong F thì cũng thỏa mãn
X Æ Y
 Ký hiệu F ⊨ XÆY
 F bao hàm (implies) XÆY
 XÆY được suy diễn theo quan hệ từ F
14
HeCSDL 15
NN
NN
H
H
ệ
ệ
tiên đ
tiên đ
ề
ề
Amstrong
Amstrong
 Để có thể xác định được các phụ thuộc
hàm khác từ tập phụ thuộc hàm đã có, ta
dùng hệ tiên đề Armstrong (1974), gồm

tiên đ
ề
ề
Amstrong
Amstrong
Từ 3 tiên đề trên có thể suy ra:
 F4. Hợp (additivity): X→Y và X→Z ⇒ X
→YZ
 F5. Chiếu (projectivity): X→YZ ⇒ X →Y
 F6. Bắc cầu giả (pseudotransitivity): X→Y
và YZ→W ⇒ XZ →W
17
HeCSDL 18
NN
NN
V
V
í
í
d
d
ụ
ụ
 Dùng hệ tiên đề Amstrong để chứng minh
Nếu X → YZ và Z → W, thì X → YZW
 Chứng minh:
 Từ Z → W Î YZZ → YZW (luật gia tăng)
hay YZ → YZW
 Từ XÆ YZ và YZ Æ YZW Î X → YZW
(luật bắc cầu)

ể
m tra c
m tra c
á
á
c t
c t
ậ
ậ
p FD tương đương
p FD tương đương
 Input: F, G – các tập FD
 Output: true nếu F tương đương G,
false nếu ngược lại
For each f ∈F do
if G does not entail f then return false
For each g ∈ G do
if G does not entail f then return false
Return true
20
HeCSDL 21
NN
NN
V
V
í
í
d
d
ụ

thu
thu
ộ
ộ
c h
c h
à
à
m
m
 Bao đóng (closure) của tập phụ thuộc hàm
F (ký hiệu là F+) là tập hợp tất cả các phụ
thuộc hàm có thể suy ra từ F dựa vào các tiên
đề Armstrong. Rõ ràng F ⊆ F+
 Ký hiệu F+
 F+ là 1 tập hợp các FD được suy diễn từ F
22
HeCSDL 23
NN
NN
C
C
á
á
c t
c t
í
í
nh ch
nh ch

m
m
1. Tính phản xạ: với mọi tập phụ thuộc
hàm F+ ta luôn có F ⊆ F+
2. Tính đơn điệu: nếu F ⊆ G thì F+ ⊆
G+
3. Tính lũy đẳng: với mọi tập phụ thuộc
hàm F ta luôn có (F+)+ = F+.
23
HeCSDL 24
NN
NN
Bao đ
Bao đ
ó
ó
ng c
ng c
ủ
ủ
a t
a t
ậ
ậ
p ph
p ph
ụ
ụ
thu
thu

i thi
i thi
ể
ể
u
u
 F được gọi là một tập phụ thuộc hàm tối
thiểu nếu F thoả đồng thời ba điều kiện sau: