THIẾT KẾ CƠ SỞ DỮ LIỆU
QUAN HỆ (Relational Database Designing)
Phần IV – PHỤ THUỘC HÀM
(Functional Dependency)

Phụ thuộc hàm – Khái niệm
•
Phụ thuộc hàm là công cụ để biểu diễn hình thức
các RBTV phụ thuộc.
•
Các lý thuyết về Phụ thuộc hàm ứng dụng nhiều
trong bài toán Chuẩn Hóa CSDL.
•
Ký hiệu :
X  Y : Y phụ thuộc hàm vào X hay X xác
định Y.
với X, Y là các tập thuộc tính (trong 1 lược đồ
quan hệ).
Khái niệm về Phụ thuộc hàm

Phụ thuộc hàm – Định nghĩa
Cho Q(A
1
,A
2
,…,A
n
); X, Y là 2 tập con của Q
+
; q là 1 quan

tâm đến các PTH hiển nhiên.
Phụ thuộc hàm hiển nhiên

Thuật toán kiểm tra PTH : Satifies
Input : _ Quan hệ q,
_ Tập thuộc tính X, Y
Output :
_ True nếu XY, ngược lại, False
Thuật toán kiểm tra Phụ thuộc hàm (p.1)

Thuật toán kiểm tra PTH (t.t)
Bước 1 :
Sắp lại các bộ trong q sao cho các bộ giống
nhau trên X nằm kề nhau.
Bước 2 :
Kiểm tra nếu tất cả các bộ giống nhau trên
X cũng giống nhau trên Y thì trả về True,
ngược lại, trả về False.
Thuật toán kiểm tra Phụ thuộc hàm (p.2)

Hệ luật dẫn Amstrong(Amstrong inference rule) -
Một số định nghĩa
Ký hiệu F là tập các phụ thuộc hàm của lược đồ quan hệ
Q, F = {f
1
,f
2
,…,f
n
}, quy ước ta không quan tâm đến các

+
= F
+
Định nghĩa : Phủ của F, ký hiệu F
-
= G - F
+
,

với G
là tập tất cả các phụ thuộc hàm có thể có của Q
Hệ luật dẫn Amstrong (p.2)

Hệ luật dẫn Amstrong
Cho X,Y,Z,W là các tập con của Q
+
; q là 1 quan hệ bất kỳ
trên Q.
1. Luật phản xạ (Reflexive rule) : X  X
2. Luật thêm vào (Augmentation rule) : X  Y => XZ  Y
3. Luật hợp (Union rule) : X  Y, X  Z => X  YZ
4. Luật phân rã (Decomposition rule) : X  YZ => X  Y, X  Z
5. Luật bắt cầu (Transitive rule) : X  Y, Y  Z => X  Z
6. Luật giả bắt cầu (Pseudo transitive rule) :
X  Y, YZ  W => XZ  W
Hệ luật dẫn Amstrong (p.3)

Bao đóng của tập thuộc tính
Cho lược đồ quan hệ Q(A
1

Hệ luật dẫn Amstrong (p.4)

Các tính chất của Bao đóng
Hệ quả : Bao đóng của Q chính là Q
+
: Q
F
+
= Q
+
•
Tính phản xạ : X ⊆ X
+
•
Tính đơn điệu : X ⊆ Y => X
+
⊆ Y
+
•
Tính lũy đẳng : (X
+
)
+
= X
+
•
(XY)
+
⊇ X
+

+
= Y
+
 X  Y và Y  X
Hệ luật dẫn Amstrong (p.5)

Thuật toán tìm Bao đóng
Input : lược đồ quan hệ Q, tập phụ thuộc hàm F, tập
thuộc tính X.
Output : X
+
Bước 1 : i = 0, X
i
= X
Bước 2 : Duyệt tập F,
Nếu F
k
= YZ có Y ⊆ X
i
thì
X
i+1
= X
i
∪ Z và F = F \ F
k
Bước 3 : Nếu X
i+1
≠ X
i

Hệ luật dẫn Amstrong (p.7)

Tìm Bao đóng - Ví dụ (t.t)
Hệ luật dẫn Amstrong (p.8)
Bước Các giá trị của i,X
i
, F
1 i = 0; X
0
= X = {AC}
2 X
i+1
=X
1
={ACD}; F = F \ f
5
= {f
1
,f
2
,f
3
,f
4
}
3
X
1
≠ X
0

}
7
X
3
≠ X
2
=> i = i+1 = 3, quay lại bước 2
8 Không có f
k
nào.
9 X
4
= X
3
=> Kết thúc giải thuật. X
+
={ACDHE}

Thuật toán Kiểm tra F|=d
Cho d = XY, kiểm tra F|=d ?
Bước 1 : Tính X
+
=X
F
+
Bước 2 : Y ⊆ X
+
<=> F|=d
Hệ luật dẫn Amstrong (p.9)


F
+
2.2 Tìm tất cả các tập con Y của X
F
+
và Y ⊄ X
2.3 F
+
= F
+
+ XY
Hệ luật dẫn Amstrong (p.11)