Chương 9: Phụ thuộc hàm
Chương 9: Phụ thuộc hàm
(Functional Dependency)
(Functional Dependency)
1
Nội dung
Nội dung

Dư thừa dữ liệu

Phụ thuộc hàm

Hệ tiên đề Amstrong

Bao đóng của tập phụ thuộc hàm

Bao đóng của tập thuộc tính

Tìm khóa
2
Dư thừa dữ liệu
Dư thừa dữ liệ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:
◦

987654321
987654321
John Doe
John Doe
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

Phụ thuộc hà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.

Đị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
giá trị X trong r có quan hệ chính xác với 1
giá trị Y trong r. Nghĩa là bất kể khi nào 2
bộ của r có cùng giá trị X thì cũng có cùng
giá trị Y.
∀t1, t2 ∈ r(R): t1[X] = t2[X] ⇒ t1[Y]=
t2[Y]
6
Phụ thuộc hàm
Phụ thuộc hàm
(Functional Dependency)
(Functional Dependency)
X là vế trái, ký hiệu left(f) hay còn gọi là
determinant
Y là vế phải, ký hiệu right(f) hay còn gọi là
dependent
7
Phụ thuộc hàm
Phụ thuộc hàm
(Functional Dependency -FD)
(Functional Dependency -FD)

thừa dữ liệu.
9
Ví dụ FD và dư thừa dữ liệu
Ví dụ FD và dư thừa dữ liệu

Xét lược đồ PERSON(SSN, Name,
Address,Hobby) với quy tắc là 1 người có thể
có nhiều sở thích (hobby)
◦ SSN,Hobby  SSN, Name, Address,Hobby

Bất thường xảy ra khi một người có nhiều sở
thích thay đổi địa chỉ
10
Giải thuật kiểm tra phụ thuộc
Giải thuật kiểm tra phụ thuộc
hàm
hàm

Bài toán: cho quan hệ r và 1 phụ thuộc
hàm f:X Y. Kiểm tra xem r thỏa mãn f
hay không?

Function Satisfies(r,f:X Y)
◦
Sắp thứ tự các bộ trong r theo các thuộc tính
của X
◦
If mỗi tập các bộ có cùng giá trị X thì có cùng
giá trị Y then


Tập phụ thuộc hà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

Phụ thuộc hàm tầm thường ( trivial
FD) hay phụ thuộc hàm hiển nhiên X
Y nếu Y ⊆ X
◦
Ví dụ: Name, Address
→
Name
13
Tập phụ thuộc hàm
Tập phụ thuộc hàm

Số tập con có thể có của R =
{A1,A2, ,An} là 2
n
.

Ứng với 2 tập con sẽ tạo thành 1 FD 
Số FD có thể có được là 1 chỉnh hợp lặp
chập 2 của 2
n
phần tử. Số FD tối đa có
thể có (2
n)2
=2

Hệ tiên đề Amstrong
Hệ tiên đề Amstrong

Quy tắc suy diễn (inference rule): nếu 1
quan hệ thỏa mãn 1 số phụ thuộc hàm
nào đó thì quan hệ này cũng thỏa mãn 1
số phụ thuộc hàm khác
17
Hệ tiên đề Amstrong
Hệ tiên đề Amstrong

Các tiên đề suy diễn:
◦
F1. Phản xạ (reflexivity): Y⊆X ⇒
X→Y
◦
F2. Gia tăng (augmentation): X→Y
⇒ XZ →YZ
◦
F3. Bắc cầu (transitivity): X→Y và
Y→Z ⇒ X →Z
18
Hệ tiên đề Amstrong
Hệ tiên đề Amstrong

F4. Hợp (additivity): X→Y và X→Z ⇒ X
→YZ

F5. Chiếu (projectivity): X→YZ ⇒ X →Y



F+ là 1 tập hợp các FD được suy diễn từ F
21
Các tính chất của bao đóng của
Các tính chất của bao đóng của
tập phụ thuộc hàm
tập phụ thuộc hà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+.
22
Hệ tiên đề Amstrong
Hệ tiên đề Amstrong

Hệ tiên đề Amstrong là đúng đắn (sound)
 các phụ thuộc hàm suy diễn từ F (tập
phụ thuộc hàm trên r) theo hệ tiên đề
Amstrong cũng là một phụ thuộc hàm trên
r

Hệ tiên đề Amstrong là toàn vẹn
(completeness)  bảo đảm rằng f ∈ F+
nếu và chỉ nếu f là 1 FD được suy diễn
23
Phụ thuộc hàm tương đương
Phụ thuộc hàm tương đương

Nếu F và G là 2 tập FD. F suy diễn G ( F