Môn CƠ SỞ DỮ LIỆU
Chương 5:
Phụ thuộc
hàm và một số ứng dụng
2
Nội dung
1. PHỤ THUỘC HÀM

Định Nghĩa Phụ Thuộc Hàm

Một số tính chất của phụ thuộc hàm - hệ luật dẫn
armstrong
2. BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM F & CỦA
TẬP THUỘC TÍNH X

Bao đóng của tập phụ thuộc hàm F

Bao đóng của tập thuộc tính X
3. THUẬT TOÁN TÌM BAO ĐÓNG F+ VÀ X+, BÀI
TOÁN THÀNH VIÊN

Bài toán thành viên

Thuật toán tìm bao đóng của một tập thuộc tính (X)
3
Nội dung (tt)
4. PHỦ TỐI THIỂU CỦA MỘT TẬP PHỤ THUỘC HÀM

Tập Phụ Thuộc Hàm Tối Thiểu


là hai tập con khác rỗng của Q.
Ta nói X xác định Y (hay Y phụ thuộc hàm vào X) nếu với r là một
quan hệ trên Q và nếu hai bộ t
1
,t
2
bất kỳ thuộc r mà t
1
.X = t
2
.X ==>
t
1
.Y = t
2
.Y. Khi đó ta ký hiệu là X → Y

Phụ thuộc hàm X → X được gọi là phụ thuộc hàm hiển nhiên. người
ta thường dùng F để chỉ tập các phụ thuộc hàm định nghĩa trên Q. Vì
Q hữu hạn nên F cũng hữu hạn, ta có thể đánh số các phụ thuộc hàm
của F là f
1
, f
2
, , f
m
.

Quy ước rằng chỉ cần mô tả các phụ thuộc hàm không hiển nhiên
trong tập F (các phụ thuộc hàm hiển nhiên được ngầm hiểu là đã có

◆
Tính phản xạ: Với mọi tập phụ thuộc hàm F+ ta luôn luôn có F ⊆ F+
◆
Tính đơn điệu: Nếu F ⊆ G thì F+ ⊆ G+
◆
Tính lũy đẳng: Với mọi tập phụ thuộc hàm F ta luôn luôn có F++ = F+.
7
2. BAO ĐÓNG (tt)
Bao đóng của tập thuộc tính X

Cho r là quan hệ trên lược đồ quan hệ Q. giả sử F là
tập các phụ thuộc hàm trong Q, X ⊆ Q
+
.
Bao đóng của tập thuộc tính X đối với F ký hiệu là X
+

(hoặc X
+
F
) là tập tất cả các thuộc tính A của Q được
suy ra từ X dựa vào hệ tiên đề Armstrong và các phụ
thuộc hàm trong F.
X+ = {A : A ∈ Q và X → A ∈ F+}
8
2. BAO ĐÓNG (tt)
Bao đóng của tập thuộc tính X – Ví dụ
Q(A,B,C,D,E,G);
F={A → C; A → EG; B → D; G → E};
X={A,B};

+
◆
Tính lũy đẳng: X
++
= X
+
◆
(XY)+ ⊇ X
+
Y
+
◆
(X
+
Y)
+
= (XY
+
)
+
= (X
+
Y
+
)
+
◆
X → Y∈ F+ ⇔ Y ⊆ X+
◆
X → Y ⇔ Y


Để trả lời câu hỏi này (bài toán thành viên) không đơn giản,
vì mặc dù F là rất nhỏ nhưng F
+
thì có thể rất lớn.

Tuy nhiên để giải bài toán thành viên, chúng ta có thể dùng
tính chất 6 của tập bao đóng X
+
. đó là tính chất X → Y ∈ F
+

⇔ Y ⊆ X . Do vậy chỉ cần tính X
+
và so sánh với tập Y, ta
có ngay câu trả lời X → Y ∈ F
+
hay không ? Do đó, việc
tính X
+
được giải quyết đơn giản hơn rất nhiều.
11
3. TT TÌM BAO ĐÓNG F+ VÀ X+ (tt)
Thuật toán tìm bao đóng của một tập thuộc tính (X)
(độ phức tạp O(N2), với N là số thuộc tính của Q)
Dữ Liệu Vào Q, F, X ⊆ Q
+
Dữ Liệu Ra X
+



Bước 3: X
+
= X

Bước 4: Mọi thuộc tính A X
+
Giảm COUNT|X → Y| đi một nếu A ∈ X
Nếu COUNT|X → Y| = 0 thì X+ = X
+
∪ Y
Quay lại duyệt thuộc tính kế tiếp trong X+ cho đến khi nào
duyệt hết mọi phần tử của X
+
thì dừng lại. Kết quả X
+
là bao
đóng cần tìm.
13
4. PHỦ TỐI THIỂU CỦA MỘT TẬP PTH
Tập Phụ Thuộc Hàm Tối Thiểu
Để có thể phục vụ quá trình thiết kế cơ sở dữ liệu, cần đưa ra
thêm khái niệm tập PTH tối thiểu.
Bổ đề: Mỗi tập các phụ thuộc hàm F đều được phủ bởi tập các
phụ thuộc hàm G mà vế phải của các phụ thuộc hàm G chỉ
gồm một thuộc tính.
F được gọi là một tập phụ thuộc hàm tối thiểu nếu F thỏa đồng
thời ba điều kiện sau:
(a) Vế phải của F chỉ có một thuộc tính.
(b) Không ∃ X → A ∈ F và Z ⊂ X mà: F

nếu và chỉ nếu mỗi phụ thuộc hàm
thuộc F đều thuộc G
+
và mỗi phụ thuộc hàm thuộc
G đều thuộc F
+
.
16
4. PHỦ TỐI THIỂU CỦA MỘT TẬP PTH
Thuật Toán Tìm Phủ Tối Thiểu Của Một Tập PTH

Dữ liệu vào : Lược đồ quan hệ ban đầu (lược đồ quan hệ
phổ quát) Q và tập phụ thuộc hàm F, số lượng phụ thuộc
hàm trong F là cardF.

Dữ liệu ra :Lược đồ quan hệ Q và tập phụ thuộc hàm tối
thiểu của F và số lượng phụ thuộc dữ liệu trong phủ tối
thiểu.
Bước 1: Tách vế phải mỗi phụ thuộc hàm trong F sao cho vế
phải của mỗi phụ thuộc hàm chỉ chứa một thuộc tính (đều
này luôn thực hiện được do bổ đề trên)
∀ f: X → Y ∈ F
∀ A ∈ Y
g = X → A
F = F ∪ g
Cardf = Cardf + 1
Cuối ∀
Cuối ∀
17
4. PHỦ TỐI THIỂU CỦA MỘT TẬP PTH

Q +.

K là một khóa của Q nếu thỏa đồng thời cả hai điều kiện
sau:
◆
K → Q
+
∈ F
+
(hay K
+
F
= Q
+
) (K chỉ thỏa điều kiện 1 thì được
gọi là siêu khóa)
◆
Không tồn tại K' ⊂ K sao cho K'
+
= Q
+

Một lược đồ quan hệ có thể có nhiều khóa và tập thuộc tính
không khóa cũng có thể bằng rỗng.
19
5. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ …
Thuật toán tìm một khóa của một lược đồ quan hệ Q
K=Q
+
;

, …,X
2n-1
}

Bước 2: Chọn trong S ra tập siêu khóa của Q
Nếu một tập con Xi (i=1 ,2
n
-1) của Q+ có bao đóng đúng bằng Q+ thì
tập con dó (theo định nghĩa trên) là một siêu khóa của Q.
Giả sử ta đã có các siêu khóa là S = {S
1
,S
2
,…,S
m
}

Bước 3:Xây dựng tập chứa tất cả các khóa của Q từ tập S
Xét mọi Si,Sj con của S (i ≠ j), nếu Si ⊂ Sj thì ta loại Sj (i,j=1 n), kết
quả còn lại của S chính là tập tất cả các khóa cần tìm.
21
5. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ …
Thuật Toán Tìm Tất Cả Các Khóa Của Một Lược Đồ Quan
Hệ (Thuật toán cải tiến)

Một số khái niệm:
◆
Tập thuộc tính nguồn(TN) chứa tất cả các thuộc tính có xuất hiện
ở vế trái và không xuất hiện ở vế phải của tập phụ thuộc hàm.
◆


Bước 4: S= ∅
Xi tập trung gian
if (Tập nguồn Xi)+ = Q+ then
S = S ∪ { Tập nguồn ∪ Xi}
{S là tập các siêu khóa cần tìm}

Bước 5: Loại bỏ các siêu khóa không tối tiểu
∀ SI, Sj ∈ S if Si ⊂ Sj then Loại Sj ra khỏi Tập siêu
khóa S
S còn lại chính là tập khóa cần tìm.
24
6. DẠNG CHUẨN CỦA LƯỢC ĐỒ Q.HỆ

Chất lượng thiết kế của một lược đồ CSDL có thể được
đánh giá dựa trên nhiều tiêu chuẩn trong đó sự trùng lắp
thông tin và chi phí kiểm tra các ràng buộc toàn vẹn là hai
tiêu chuẩn quan trọng.

Thuộc tính khóa/không khóa: A là một thuộc tính khóa nếu
A có tham gia vào bất kỳ một khóa nào của quan hệ, ngược
lại A gọi là thuộc tính không khóa.

Thuộc tính phụ thuộc đầy đủ: A là một thuộc tính phụ thuộc
đầy đủ vào tập thuộc tính X nếu X → A là một phụ thuộc
hàm đầy đủ (tức la không tồn tai X' ⊂ X sao cho X' → A ∈
F)
25
6. DẠNG CHUẨN CỦA LĐ QH (tt)
Định Nghĩa Dạng Chuẩn Một (First Normal Form)